Re: [Boost-users] Graph Isomorphism

Subject: Re: [Boost-users] Graph Isomorphism
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-06-23 21:37:31

On Thu, 23 Jun 2011, Evan Driscoll wrote:

> OK, I have a somewhat unrelated question. (I think I can modify the Boost 
> algorithm to do what I want.)
>
> In libs/graph/example/isomorphism.hpp, if I change undirectedS to 
> bidirectionalS, then the answer changes from the two graphs being isomorphic 
> to not. (It then proceeds to segfault when looking at the isomorphism map.)
>
>  typedef adjacency_list<vecS, listS, undirectedS,
>    property<vertex_index_t, int> > graph_t;
> to
>  typedef adjacency_list<vecS, listS, bidirectionalS,
>    property<vertex_index_t, int> > graph_t;
>
> Why is this?
>
>
> Near as I can tell, the graphs should be isomorphic. Graph 1 has three 
> cycles, 0->1->2->0, 3->4->5->6->3, and 7->8->9->10->11->7. Graph 2 has three 
> cycles of the same sizes, 9->10->11->9, 0->1->3->2->0, and 4->5->7->8->6->4. 
> (These are all the transitions.)

They are not isomorphic as directed graphs: the first component in g1 is 
0->1, 1->2, 0->2 (acyclic), while the first component in g2 is 9->10, 
10->11, 11->9 (a cycle).  The other components are isomorphic in the way 
that you show.

-- Jeremiah Willcock