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