- From: Graham Klyne <gk@ninebynine.org>
- Date: Thu, 15 May 2003 16:48:14 +0100
- To: www-archive <www-archive@w3.org>
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