Subject: [Boost-users] Graph Isomorphism
From: Evan Driscoll (driscoll_at_[hidden])
Date: 2011-06-23 12:28:09
I am writing a library for a variant of finite automata. States in the
automata are named by "keys", which boil down to unsigned ints.
For testing purposes, I'd like to be able to test whether two automata
are isomorphic -- i.e. they are the same except for perhaps different
keys for the corresponding states. (The motivation for this is that
there are a few operations like 'determinize' that I don't want to
guarantee any particular names for the output states, but I want or need
to test something stronger than language equality between the actual and
respected result.)
One way I've thought of doing this is to convert the transition graph of
each automaton to a BGL graph and use it's 'isomorphism' function to
determine whether the two are isomorphic. However, I'd need to impose
two extra conditions:
- Edges between nodes are labeled (with the symbol that makes the
automaton take that transition), and I need to make sure these match
between the two graphs
- Nodes are labeled (with whether they correspond to an initial and
accepting state of the automaton), and I need to make sure these
match up between the two graphs
Does it sound like this task is something the BGL is suited for?
Thanks,
Evan Driscoll