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