"DisjointSet" (Data Structure)

"DisjointSet"

represents a collection of elements that are general expressions and that are partitioned into disjoint sets.

Details

  • A disjoint set has efficient merging and removal as well as membership testing:
  • CreateDataStructure[ "DisjointSet"]create a new empty "DisjointSet"
    Typed[x,"DisjointSet"]give x the type "DisjointSet"
  • For a data structure of type "DisjointSet", the following operations can be used:
  • ds["CommonSubsetQ",x,y]return True if x and y are in the same subsettime: O(α(n))
    ds["Copy"]return a copy of dstime: O(n)
    ds["Delete",x]delete x from ds, return True if x was actually an elementtime: O(n)
    ds["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if ds is emptytime: O(1)
    ds["Find",x]return the parent of xtime: O(α(n))
    ds["Insert",x]add x to the collection of elementstime: O(α(n))
    ds["InsertAll",elems]add elements elems to the collection of elementstime: O(α(n) nelems)
    ds["Length"]return the number of elements stored in dstime: O(1)
    ds["MemberQ",x]True, if x is an element of dstime: O(1)
    ds["Merge",dsi]merge the elements of dsi into dstime: O(n)
    ds["Subsets"]return the subsets in dstime: O(n)
    ds["Unify",x,y]unify the subsets of x and ytime: O(α(n))
    ds["UnifyAll",elems]unify the subsets of the elements in elemstime: O(α(n) nelems)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression
  • Many operations such as insertion, merging and testing for common subsets have near constant-time performance, bounded by α(n), the inverse Ackermann function.

Examples

open allclose all

Basic Examples  (1)

A new "DisjointSet" can be created with CreateDataStructure:

Initially there are no elements and no subsets:

Insert two elements; each goes into its own subset:

Unify the subsets:

Add two more elements and unify; now there are two subsets:

Unify the two subsets; now there is only one subset:

A visualization of the data structure can be generated:

Scope  (1)

Information  (1)

A new "DisjointSet" can be created with CreateDataStructure:

Information about the data structure ds:

Applications  (1)

Kruskal Algorithm  (1)

The minimum spanning tree of a graph is a tree that connects all the vertices with a minimum total edge weight. The Kruskal algorithm is one way to compute a minimum spanning tree, and it can be written to use a "DisjointSet".

An implementation of the Kruskal algorithm:

A graph to use to test the Kruskal implementation:

Compute the minimum spanning tree with the Kruskal algorithm:

Show how the minimum spanning tree maps onto the original graph: