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.

  • blog moved

    As described elsewhere, I've quit LiveJournal. If you're interested in my continuing posts, you should look at one of these (each contains feed…

  • dremel

    They published a paper on Dremel, my favorite previously-unpublished tool from the Google toolchest. Greg Linden discusses it: "[...] it is capable…

  • treemaps

    I finally wrote up my recent adventures in treemapping, complete with nifty clickable visualizations.

  • 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