
Boost Users : 
Subject: Re: [Boostusers] Graph Isomorphism
From: Evan Driscoll (driscoll_at_[hidden])
Date: 20110623 13:12:48
On 06/23/2011 11:41 AM, Aaron Windsor wrote:
> The BGL isomorphismtesting 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 outdegree is encoded in
the integer too? I.e. should 'f(v)' encode both the outdegree 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
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