union-find: classical union-find data structure for disjoint sets.

_union-find_: classical union-find data structure for disjoint sets.
----------------------------------------------------------------------

Author: Danny Yoo ([email protected] / [email protected])


This is a straightforward implementation of the disjoint-tree data
structure used to solve the "union-find" problem: given a forest of
disjoint sets, can we quickly find if two elements belong in the same
set?

We implement both union by rank and path compression techniques, which
means that this structure applies mutation to its data structures.


Example
=======

    > (define forest (make-forest 'equal))
    > (make-set forest 3)
    > (make-set forest 5)
    >
    > (find-set forest 3)
    3
    > (find-set forest 5))
    5
    > 
    > (union-set forest 5 3)
    > (find-set forest 5)
    3
    > (find-set forest 3)
    3



API
===

> make-forest: -> forest
> make-forest: [flag] [flag] -> forest
    (where flag is either 'equal or 'weak.)

Constructs a new forest of disjoint sets.


> make-set: forest element -> void

Inserts the element as a singleton set into the forest.


> find-set: forest element -> element

Finds the representative element for the element.  If two elements are
in the same set, their representatives will be the same.


> union-set: forest element element -> void

Joins the sets containing the first and second elements together into
the same set.



References
==========

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein.  "Introduction to Algorithms / Second Edition". The MIT Press
and McGraw-Hill, 2003.