Boost logo

Boost Users :

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...


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at