Re: Possible bug in graph isomorphism algorithm

Jeremy,

I'm happy for the entire message to be public... indeed, I should probably 
have copied www-archive, which I've just done [1] if you prefer just a URI.

I hope you noticed this:
[[
I haven't checked if it is replicated in your Jena implementation.
]]

But if your implementation follows the paper exactly, I guess the 
possibility of a bug still exists.  Whether or not you can reproduce my 
particular bug in Jena may possibly depend on the hashing algorithm you use 
for discriminating nodes -- I use a fairly simple one which may have a 
higher-than-expected instance of collisions.

#g
--

[1] http://lists.w3.org/Archives/Public/www-archive/2003May/0021.html

Also, for the archive, your paper:

[2] http://www.hpl.hp.com/semweb/publications.htm#Matching%20RDF%20Graphs


At 15:03 15/05/03 +0100, Jeremy Carroll wrote:

>Thanks for this
>can I add it the e-mail in its entirety to the public Jena tracker, or 
>should I prune it to protect the innocent.
>
>Jeremy
>
>Graham Klyne wrote:
>
>>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

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

Received on Thursday, 15 May 2003 12:10:25 UTC