- From: Graham Klyne <gk@ninebynine.org>
- Date: Thu, 15 May 2003 16:58:01 +0100
- To: Jeremy Carroll <jjc@hplb.hpl.hp.com>
- Cc: www-archive <www-archive@w3.org>
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