source: project/wiki/eggref/4/disjoint-set @ 20624

Last change on this file since 20624 was 20624, checked in by svnwiki, 11 years ago

Anonymous wiki edit for IP [86.141.186.14]:

File size: 1.2 KB
Line 
1== Disjoint Set
2
3An implementation of a [[http://en.wikipedia.org/wiki/Disjoint-set_data_structure|disjoint set]] data structure.
4
5A 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.
6
7The user must provide a hash procedure and equality check procedure for the items to be stored in the data structure.
8
9=== Procedures
10
11<procedure>(make-disjoint-set hash-function equality-test)</procedure>
12Returns a reference to a disjoint-set object.
13
14<procedure>(disjoint-set:make disjoint-set item)</procedure>
15Converts the given item into a disjoint set item, and adds it to the disjoint set.  There is no usable output.
16
17<procedure>(disjoint-set:find disjoint-set item)</procedure>
18Returns a reference to the representative item of the set that the given item appears in.
19
20<procedure>(disjoint-set:union disjoint-set item-1 item-2)</procedure>
21Modifies the disjoint set, merging the sets represented by the given items.  There is no usable output.
22
23=== Author
24
25[[http://wiki.call-cc.org/users/peter-lane|Peter Lane]].
26
27=== License
28
29GPL version 3.0.
30
31=== Requirements
32
33Needs srfi-69
34
35=== Version History
36
37* 1.0: initial release
Note: See TracBrowser for help on using the repository browser.