▼Data:   Data Structures
On this page:
uf-new
uf-set?
uf-find
uf-union!
uf-same-set?
uf-set-canonical!
6.3
  top  ← prev  up  next → 

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.

procedure

(uf-new c) → uf-set?

  c : any/c
Makes a new set with the canonical element c.

This is a constant time operation.

Examples:

> (uf-new 'whale)

#<uf-set: 'whale>

> (uf-new 'dwarf-lantern)

#<uf-set: 'dwarf-lantern>

procedure

(uf-set? x) → boolean?

  x : any/c
Returns #t if x was created with uf-new, and #f otherwise.

This is a constant time operation.

Examples:

> (uf-set? (uf-new 'spiny-dogfish))

#t

> (uf-set? "I am not a uf-set")

#f

procedure

(uf-find a) → any/c

  a : uf-set?
Returns the canonical element of a.

This is an amortized (essentially) constant time operation.

Example:

> (uf-find (uf-new 'tasselled-wobbegong))

'tasselled-wobbegong

procedure

(uf-union! a b) → void?

  a : uf-set?
  b : uf-set?
Imperatively unifies a and b, making them both have the same canonical element. Either of a or b’s canonical elements may become the canonical element for the union.

This is an amortized (essentially) constant time operation.

Examples:

> (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?
Returns #t if the sets a and b have been unioned.

This is an amortized (essentially) constant time operation.

Examples:

> (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
Changes a to have a new canonical element.

This is an amortized (essentially) constant time operation.

Examples:

> (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

  top  ← prev  up  next →