Possible bug in graph isomorphism algorithm

Jeremy,

I just encountered a subtle bug in my implementation of graph isomorphism 
checking following the algorithm in your paper.  I haven't checked if it is 
replicated in your Jena implementation.

The test case I used was based loosely on the example in your paper (figure 
1).  Imagine 10 nodes arranged as a pair of "concentric" pentagons, with 
edges directed to form two 5-cycles, both clockwise.  Then corresponding 
nodes from the outer pentagon are also linked inwards to the centre 
pentagon.  All nodes are bnodes, and all properties used are the same (I'm 
actually using anonymous properties, so they're included in the bijection 
to be discovered).

Now take a second graph, being a copy of the first in which exactly one 
edge of one of the pentagons has its direction reversed.  This is not 
isomorphic with the first.

A version of my implementation was incorrectly reporting that these cases 
were isomorphic.  After much head-scratching, I realized that the guessing 
stage (5c of the full algorithm in your paper) is actually able to 
construct incorrect solutions that satisfy the termination condition 5b.

My solution to this problem is that the termination condition is enhanced 
with a check that the graphs are actually the same under the 
equivalence-class mapping (replacing nodes by their corresponding 
equivalence class "colours").

This is a problem that I think is quite unlikely to arise for practical RDF 
graphs, because the scope for making wrong guesses that still deliver 
viable equivalence classes is quite small, but my tests show it's 
possible.  As far as I can tell, your algorithm as described doesn't have 
any checks to detect this kind of mis-assignment.

I've compared the final version of my implementation against your paper 
and, apart from the final check noted, I think it's pretty close to what 
you describe there.

#g


-------------------
Graham Klyne
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E

Received on Thursday, 15 May 2003 11:52:58 UTC