class

Collections::DisjointSet(T)

Inherits Reference < Object

A disjoint-set (union-find) structure over arbitrary hashable values, with path compression and union by rank so find/union run in near-constant amortized time.

Values are added lazily: find, union and connected? all register any value they are handed that has not been seen before.

ds = Collections::DisjointSet(Int32).new
ds.union(1, 2)
ds.union(2, 3)
ds.connected?(1, 3) # => true
ds.connected?(1, 4) # => false
ds.count            # => 2  (the set {1, 2, 3} and the singleton {4})

Constructors

Instance methods

add(value : T) : self

Registers value as its own singleton set if it is not already present. Returns self.

Source
connected?(a : T, b : T) : Bool

Returns whether a and b belong to the same set.

Source
count

Returns the number of disjoint sets.

Source
empty?
Source
find(value : T) : T

Returns the representative of value's set, compressing the path to the root along the way. Registers value first if it is unseen.

Source
includes?(value : T) : Bool

Returns whether value has been registered.

Source
size

Returns the number of registered elements.

Source
subsets

Returns the members of each disjoint set, one array per set.

Source
union(a : T, b : T) : Bool

Merges the sets containing a and b. Returns true if they were in different sets (and are now merged), or false if they were already together.

Source