Evan Martin (evan) wrote in evan_tech,
Evan Martin

  • Mood:

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.

  • closest computer

    I have a computer in the closet that serves music. I haven't thought much about the computer as I've used it -- I just know it's always available on…

  • fonts on linux

    I wrote a document on how to diagnose font problems on Linux. I would appreciate feedback, corrections, other common misconfigurations, etc.

  • münchen

    On that note: I'm living in Munich for the next week plus a few days. Do I know anyone around here? (PS: The LJ → PubSubHubbub → Reader…

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment