Re: [Boost-users] Graph Isomorphism

Subject: Re: [Boost-users] Graph Isomorphism
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2011-06-23 13:18:25

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

You can encode the degree in the mapping, too, and if you do, that
will help speed up the isomorphism tester. But you don't have to. The
isomorphism tester exhaustively looks for isomorphisms between the two
graphs, and the invariants can be used both as hints to speed up the
exhaustive search and as ways to enforce actual invariants in the
isomorphsim, as you're doing.

-Aaron