
Boost Users : 
Subject: Re: [Boostusers] Graph Isomorphism
From: Evan Driscoll (driscoll_at_[hidden])
Date: 20110623 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
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