Re: [Boost-users] graph library : isomorphism.hpp vertex invariant parameter

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-06-13 20:24:04

On 6/13/07, Patrick A. La Fratta <plafratt_at_[hidden]> wrote:
> Also, I believe the vertex_max_invariant named parameter needs to be set for
> the isomorphism function to work (mine doesn't seem to work without it set).
> I added the necessary change to my named_params.hpp, similar to the patches
> you gave, in order to set this. It seems to work fine now.
> thanks,
> Patrick
>
>
> On 6/13/07, Patrick A. La Fratta <plafratt_at_[hidden]> wrote:
> >
> > Thanks for your help and the fix. Also, there is a comment in the
> "isomorphism.hpp" file in the "match" function that says "this *HAS* to be a
> bug!".  Does anyone know if there is a problem here that hasn't been
> addressed?
> >
> > - Patrick
> >
> >

Hi Patrick,

Thanks - I'll add the named parameter for vertex_max_invariant to the
patch as well. As for the "this has to be a bug comment" - I've seen
that too. What I can say is that I've hit the isomorphism code pretty
hard recently with several thousands of small graphs and it looks good
to me. I use it in the planarity testing/embedding code that I have in
the vault right now (http://tinyurl.com/2dltju) to verify non-planar
graphs - any graph that isn't planar contains a subgraph that can be
contracted and tested for isomorphism against either the complete
graph on 5 vertices or the complete bipartite graph on 6 vertices
(with 3 vertices in each bipartition). So, admittedly, I'm using it to
test for isomorphism against two very special small graphs, but I've
never seen it give incorrect results.

Regards,
Aaron