# Possible bug in graph isomorphism algorithm

From: Graham Klyne <gk@ninebynine.org>
Date: Thu, 15 May 2003 16:48:14 +0100
Message-Id: <5.1.0.14.2.20030515164749.02e06d10@127.0.0.1>
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

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

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:42:24 UTC