Re: [Boost-users] Graph Isomorphism

Subject: Re: [Boost-users] Graph Isomorphism
From: Evan Driscoll (driscoll_at_[hidden])
Date: 2011-06-23 13:12:48

On 06/23/2011 11:41 AM, Aaron Windsor wrote:
> 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.

I saw those in the interface but wasn't sure if that was what I'd need 
or not. That explanation is not very clear, and sounds incorrect (or at 
least incomplete).

"The resulting isomorphism will map vertex u to v if f(u) = g(v) and 
...." what? There've got to be some additional conditions in there 
relating to connections between the nodes. And because I don't know what 
it's doing behind the scenes, I can't tell what interface that map 
*really* provides because the docs don't actually say.

For instance, do I need to make sure that the out-degree is encoded in 
the integer too? I.e. should 'f(v)' encode both the out-degree and 
initialness/acceptingness of 'v'? And that's not even to the point of 
trying to figure out a way to encode the edge labels in that scheme; I'm 
not sure how to do that.

I guess maybe I should read that PDF of the algorithm. Maybe that'll help.

Evan