You are looking at historical revision 27938 of this page. It may differ significantly from its current revision.

Disjoint Set

An implementation of a disjoint set data structure.

A disjoint set is a data structure to hold sets of items, providing efficient procedures for finding a representative of the set any item is contained in, and also for joining two sets together.

The user must provide a hash procedure and equality check procedure for the items to be stored in the data structure.

Procedures

[procedure] (make-disjoint-set hash-function equality-test)

Returns a reference to a disjoint-set object.

[procedure] (disjoint-set:make disjoint-set item)

Converts the given item into a disjoint set item, and adds it to the disjoint set. There is no usable output.

[procedure] (disjoint-set:find disjoint-set item)

Returns a reference to the representative item of the set that the given item appears in.

[procedure] (disjoint-set:union disjoint-set item-1 item-2)

Modifies the disjoint set, merging the sets represented by the given items. There is no usable output.

Author

Peter Lane.

License

GPL version 3.0.

Requirements

Needs srfi-69

Version History