
Boost Users : 
Subject: Re: [Boostusers] Graph Isomorphism
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20110623 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net