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

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

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