Re: [Boost-users] Graph Isomorphism

Subject: Re: [Boost-users] Graph Isomorphism
From: Evan Driscoll (driscoll_at_[hidden])
Date: 2011-06-23 21:28:22

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.)

Evan Driscoll