DisjointSetTree

public class DisjointSetTree<T> : CustomStringConvertible where T : Hashable

A disjoint-set data structure, also known as union-find or merge-find. The data structure stores associations between unique values of type T. Two values are in the same subset if there are associations that link them. The structure allows you to quickly determine whether two values are in the same subset.

There are two methods used to set the associations and determine whether two values are in the same subset:

union(v1, v2) merges the subsets containing v1 and v2, if they’re not already in the same subset.

find(v) returns the root value of the subset. Two values v1 and v2 are in the same subset iff find(v1) = find(v2).

From Wikipedia: While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation called a disjoint-set forest. This is a specialized type of forest which performs unions and finds in near constant amortized time. To perform a sequence of m addition, union, or find operations on a disjoint-set forest with n nodes requires total time O(mα(n)), where α(n) is the extremely slow-growing inverse Ackermann function. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times α(n) time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both asymptotically optimal and practically efficient.

let ds = DisjointSetTree<Int>()
ds.union(2, 3)
ds.union(3, 4)
ds.find(1)     // 1
ds.find(2)     // 3
ds.find(3)     // 3
ds.find(4)     // 3   (2, 3, and 4 are in the same subset)
ds.find(5)     // 5
print(ds)

4: root = 3
2: root = 3
3: root = 3

  • Undocumented

    Declaration

    Swift

    public init()

  • Put two values in the same subset (make them have the same root).

    Declaration

    Swift

    public func union(_ value1: T, _ value2: T)

    Parameters

    value1

    first value
    value2

    second value

  • Return the root value of the given value. Two values v1 and v2 are in the same subset if find(v1) = find(v2).

    Declaration

    Swift

    public func find(_ value: T) -> T

    Parameters

    value

    value to find the root of

    Return Value

    the root of the value

  • Clear the set, i.e. remove all associations and make it like a newly-created DisjointSetTree.

    Declaration

    Swift

    public func clear()

  • A string that is a newline-separated list of “<value>: root = find(<value>)”, giving for each value in the set, the root of the value. Only values that have been given as one of the values in a union() call are listed.

    Declaration

    Swift

    public var description: String { get }