09:41 am, 2 Apr 04

### graph-join doesn't work

Of course, putting that code up made me take another look at it, and: it doesn't work at all. My test cases were too simple. I suck.

The problem is if I have nodes a, b, c, and they have edges like:

a -> [b, c]

b -> [a, c]

c -> [a, b]

And then b and c merge (perhaps because of some other edges; on this graph, all three ought to either be independent or a single group). Then a should now have two links to the group b-c, but the whole design was based on the idea that I would keep the edge lists in sorted order without needing to iterate over the entire graph.

And I need that fact ("two links to b") to decide which edge to merge next, which is the central step of the algorithm. It's be too slow to clean up as I go.

After I realized this, I have no idea why this didn't occur to me before. This is a pretty simple failure.

Now that I've written all that out, maybe one fix would be when merging c into b would be to run the cleanup on all groups that c had links to. But that's still lame.

The problem is if I have nodes a, b, c, and they have edges like:

a -> [b, c]

b -> [a, c]

c -> [a, b]

And then b and c merge (perhaps because of some other edges; on this graph, all three ought to either be independent or a single group). Then a should now have two links to the group b-c, but the whole design was based on the idea that I would keep the edge lists in sorted order without needing to iterate over the entire graph.

And I need that fact ("two links to b") to decide which edge to merge next, which is the central step of the algorithm. It's be too slow to clean up as I go.

After I realized this, I have no idea why this didn't occur to me before. This is a pretty simple failure.

Now that I've written all that out, maybe one fix would be when merging c into b would be to run the cleanup on all groups that c had links to. But that's still lame.

mcfnord