Re: [Boost-users] Graph Isomorphism

Subject: Re: [Boost-users] Graph Isomorphism
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2011-06-23 12:41:47

On Thu, Jun 23, 2011 at 12:28 PM, Evan Driscoll <driscoll_at_[hidden]> wrote:
> 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
>

Hi Evan,

The BGL isomorphism-testing implementation lets you pass in vertex
invariants that can help you describe your extra conditions. Vertex
invariants are mappings f,g that map vertices to integers such that
the resulting isomorphism will map vertex u to v if f(u) = g(v). So if
you have a vertex u in the first graph that must map to vertex v in
the second graph, you can provide f,g such that f(u) = g(v) by mapping
your set of labels onto a range of integers. Additionally, if you have
an edge (u,v) in the first graph that you want to map to an edge (w,x)
in the second graph, just make sure f(u) = g(w) and f(v) = g(x) (I'm
assuming your graph is directed since you said it was an automaton.)

These invariant mappings default to mappings that return the degree of
each vertex in the graph, so you can just replace them with your
custom invariants.

-Aaron