evan_tech

Previous Entry Share Next Entry
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.