Union Find (disjoint sets) implemented in Racket. Refer to CLRS ch.21

union-find.rkt

#lang racket/base

(provide (all-defined-out))

(struct node (parent rank data) #:prefab #:mutable)

(define (make-set data)
  (define res (node #f 0 data))
  (set-node-parent! res res)
  res)

(define (find-set! x)
  (cond
    [(eq? x (node-parent x)) x]
    [else
      (set-node-parent! x (find-set! (node-parent x)))
      (node-parent x)]))

(define (link! x y)
  (cond
    [(> (node-rank x) (node-rank y))
     (set-node-parent! y x)]
    [else 
      (set-node-parent! x y)
      (if (= (node-rank x) (node-rank y))
        (set-node-rank! y (+ 1 (node-rank y)))
        (void))]))

(define (union! x y)
  (link! (find-set! x) (find-set! y)))


; -----
; tests
; -----
(module+ test
  (require rackunit)

  (define x (make-set 1))
  (define y (make-set 2))
  (define z (make-set 3))

  (union! x y)

  (check-eq? y (node-parent y))
  (check-eq? y (node-parent x))
  (check-eq? y (find-set! y))
  (check-eq? y (find-set! x))
  (check-not-eq? z (find-set! x))
)