[racket-dev] union-find

From: Danny Yoo (dyoo at hashcollision.org)
Date: Tue Jan 29 17:13:18 EST 2013

On Tue, Jan 29, 2013 at 2:51 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> I've just pushed an implementation of the union-find algorithm to the data/
> collection. I didn't do it quite the way wikipedia recommends, but instead
> made the sets be little containers whose canonical element can be mutated.

Code reviewing...

I don't understand line 31 yet.


How can the rank decrease back to one?  Isn't that supposed to be this instead?

    (set-uf-set-rank! a (add1 a-rank))

I'm assuming that uf-set-x is either going to be another uf-set, or a
box.  Is that right?

I do not understand what uf-set-canonical! is for yet; the test case
doesn't tell me too much.

Posted on the dev mailing list.