Re: [Boost-users] Graph Isomorphism

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

On 06/23/2011 12:18 PM, Aaron Windsor wrote:
> 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.

Ah, thanks for this explanation; that makes sense. (That paragraph 
*really* ought to be in the docs!)

I'm looking at the docs for the latest version, and it looks like there 
was a change at some point from one vertex_invariant to a 
vertex_invariant1 and vertex_invariant2. Are the docs again unclear on 
what it does: i.e. vertex_invariant1 behaves as 'f' and is fed vertices 
from graph1, and vertex_invariant2 behaves as your 'g' and is fed 
vertices from graph2? Or are they two different invariants just in case 
you want to do two things?

I'm still struggling with the edge label restrictions as well. The only 
way I can think of to incorporate them is to make sure that the set of 
labels from corresponding nodes is the same: but that's insufficient:

             A                                      B
    (q0) ---------> ((q1))               (p0) ------------> ((p1))
      |                                    |
      | B                                  | A
      |                                    |
      V                                    V
    (q2)                                 (p2)

These automata are not isomorphic; they don't even have the same 
language. But if you can only look at each vertex and the edges that are 
incident on it, it looks like it is.

There may be some clever encoding, but I'm not seeing it...

Evan