10 Union-Find: Sets with only Canonical Elements
| (require data/union-find) | package: data-lib |
The union-find algorithm and data structure provides an API for representing sets that contain a single, canonical element. The sets support an (imperative) union operation (the library picks one of the canonical elements of the original sets to be the canonical element of the union), as well as getting and setting the canonical element.
These operations are not thread-safe.
This is a constant time operation.
This is a constant time operation.
This is an amortized (essentially) constant time operation.
This is an amortized (essentially) constant time operation.
> (define a (uf-new 'sand-devil)) > (define b (uf-new 'pigeye)) > (uf-union! a b) > (uf-find a) 'sand-devil
> (uf-find b) 'sand-devil
procedure
(uf-same-set? a b) → boolean?
a : uf-set? b : uf-set?
This is an amortized (essentially) constant time operation.
> (define a (uf-new 'finetooth)) > (define b (uf-new 'speartooth)) > (uf-same-set? a b) #f
> (uf-union! a b) > (uf-same-set? a b) #t
procedure
(uf-set-canonical! a c) → void?
a : uf-set? c : any/c
This is an amortized (essentially) constant time operation.
> (define a (uf-new 'sand-devil)) > (uf-set-canonical! a 'lemon) > (uf-find a) 'lemon
> (define b (uf-new 'pigeye)) > (uf-union! a b) > (uf-set-canonical! b 'sicklefin-lemon) > (uf-find a) 'sicklefin-lemon