April 2nd, 2004

  • evan

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.
  • Current Mood
  • evan

more 0-day

Tessa got a gmail account already! It's pretty fancy.

But it failed my first test: I sent her a mail with a subject, she responded, then I responded. The mail program grouped them together.
Then I sent her an entirely unrelated mail with the same subject. The mail program grouped them together.

I just reread jwz's threading doc, and I guess that's the behavior he suggested, but really: shouldn't everybody be sending appropriate References/whatever headers by now?