For more information including compatibility, examples and test cases, see https://github.com/petercrlane/r7rslibs
1. Disjoint Set: (import (robin disjointset))
A disjointset data structure holds items in distinct sets (or groups). Efficient procedures are provided for finding a representative of the set any item is contained in, and also for joining two sets together.
1.1. makedisjointset
makedisjointset
takes two parameters: the equality function to use on
terms, and a hash function (e.g. SRFI 69’s hash
, stringhash
or hashbyidentity
).
The return value is a disjoint set.
1.2. disjointset?
disjointset?
checks if its argument is a disjointset instance or not, returning a boolean value.
1.3. disjointset:make
disjointset:make
places an item into the disjointset as its own group.
Takes two arguments: the disjoint set and the item. Return value is undefined.
1.4. disjointset:find
disjointset:find
takes two arguments, the disjoint set and an item, and an
optional default value. The function returns the representative item for the group that
the given item is in, or the default value if not present (default is 'itemnotfound
if not provided).
1.5. disjointset:union
disjointset:union
takes three arguments, the disjoint set and two items. The
disjoint set is modified to combine the groups that the two items are in.
1.6. disjointset:size
disjointset:size
takes a disjoint set and returns the number of
distinct groups it contains.
1.7. Example: Kruskal’s Algorithm
This example illustrates how disjoint sets can be used in Kruskal’s algorithm to find a minimal spanning set. (The complete code is in "robinexamples/kruskal.sps")
(define (kruskal graph) (let ((result '()) (nodes (deleteduplicates (append (map car graph) (map cadr graph)) eq?))) ; 1. make a disjoint set, with each node an item (let ((ds (makedisjointset eq? hashbyidentity))) ; <1> (foreach (lambda (node) (disjointset:make ds node)) ; <2> nodes) ; 2. set 'links' holds all the links in graph, sorted with the shortest first (let loop ((links (sort graph (lambda (a b) (< (caddr a) (caddr b)))))) ; 3. if links nonempty and size > 1 (when (and (not (null? links)) (> (disjointset:size ds) 1)) ; <3> (let ((link (car links))) (unless (eq? (disjointset:find ds (car link)) ; <4> (disjointset:find ds (cadr link))) (set! result (cons link result)) (disjointset:union ds (car link) (cadr link)))) ; <5> (loop (cdr links))))) (reverse result))) ;; using it (let* ((graph '((a b 3) (a e 1) (b c 5) (b e 4) (c d 2) (c e 6) (d e 7))) (res (kruskal graph))) (format #t "MST has ~a links~&" (length res)) (format #t "~{ : ~a~&~}" res) ; <6> (format #t "Total length: ~a~&" (fold + 0 (map caddr res))))

Creates a disjoint set using
eq?
for equality andhashbyidentity
for the hash function, because individual items are symbols. 
Each node is added to the disjoint set, initially in its own group.

The number of groups in the disjoint set tells us how many links remain to be added.

Look for a link where its end points are in different groups: tested by finding the representative item of each end point’s group in the disjoint set.

When we add a link, connect the groups in the disjoint set.

Note use of
format
to print a list of items
Output:
MST has 4 links
: (a e 1)
: (c d 2)
: (a b 3)
: (b c 5)
Total length: 11