## 1. Disjoint Set: `(import (robin disjoint-set))`

A disjoint-set 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. make-disjoint-set

`make-disjoint-set` takes two parameters: the equality function to use on terms, and a hash function (e.g. SRFI 69’s `hash`, `string-hash` or `hash-by-identity`). The return value is a disjoint set.

### 1.2. disjoint-set?

`disjoint-set?` checks if its argument is a disjoint-set instance or not, returning a boolean value.

### 1.3. disjoint-set:make

`disjoint-set:make` places an item into the disjoint-set as its own group. Takes two arguments: the disjoint set and the item. Return value is undefined.

### 1.4. disjoint-set:find

`disjoint-set: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 `'item-not-found` if not provided).

### 1.5. disjoint-set:union

`disjoint-set: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. disjoint-set:size

`disjoint-set: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 "robin-examples/kruskal.sps")

```(define (kruskal graph)
(let ((result '())
(nodes (delete-duplicates (append (map car graph) (map cadr graph)) eq?)))
; 1. make a disjoint set, with each node an item
(let ((ds (make-disjoint-set eq? hash-by-identity)))        ; <1>
(for-each (lambda (node) (disjoint-set:make ds node))     ; <2>
nodes)
; 2. set 'links' holds all the links in graph, sorted with the shortest first
; 3. if links non-empty and size > 1
(> (disjoint-set:size ds) 1))                ; <3>
(unless (eq? (disjoint-set:find ds (car link))      ; <4>
(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))))```
1. Creates a disjoint set using `eq?` for equality and `hash-by-identity` for the hash function, because individual items are symbols.

2. Each node is added to the disjoint set, initially in its own group.

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

4. 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.

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

6. 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``````