[Boost-users] Graph Isomorphism

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