WOLFRAM

Wolfram Language & System Documentation Center

"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 all close all

Basic Examples  (1)

A new "DisjointSet" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["DisjointSet"]

Initially there are no elements and no subsets:

Wolfram Language code: ds["Subsets"]

Insert two elements; each goes into its own subset:

Wolfram Language code: ds["Insert", f[1]]; ds["Insert", f[2]]; ds["Subsets"]

Unify the subsets:

Wolfram Language code: ds["Unify", f[1], f[2]]; ds["Subsets"]

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

Wolfram Language code: ds["Insert", f[3]]; ds["Insert", f[4]]; ds["Unify", f[3], f[4]]; ds["Subsets"]

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

Wolfram Language code: ds["Unify", f[1], f[4]]; ds["Subsets"]

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

Scope  (1)

Information  (1)

A new "DisjointSet" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["DisjointSet"]

Information about the data structure ds:

Wolfram Language code: Information[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:

Wolfram Language code: Kruskal[gr_ ? EdgeWeightedGraphQ] := Module[{a = {}, ds}, ds = CreateDataStructure["DisjointSet"]; Do[ds["Insert", vert], {vert, VertexList[gr]}]; Do[ If[ds["Find", First[edge]] =!= ds["Find", Last[edge]], AppendTo[a, edge];ds["Unify", First[edge], Last[edge]] ], {edge, SortBy[EdgeList[gr], AnnotationValue[{gr, #}, EdgeWeight]&]} ]; TreeGraph[a, VertexLabels -> Automatic] ]

A graph to use to test the Kruskal implementation:

Wolfram Language code: g = [image];

Compute the minimum spanning tree with the Kruskal algorithm:

Wolfram Language code: st = Kruskal[g]

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

Wolfram Language code: HighlightGraph[g, st, GraphHighlightStyle -> "Thick"]