[racket-dev] union-find

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.

http://git.racket-lang.org/plt/blob/33747ec9abc5f03d1b838aae11474351d5a6b534:/collects/data/union-
find.rkt#l31


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.