Disjoint-set Forests Go Implementation

Disjoint-set

Disjoint-set data structure also called a union–find data structure or merge–find set. It maintains a collection of disjoint dynamic sets. We identify each set by a , which is some member of the set. In some applications, it doesn't matter which member is used as the representative; we care only that if we ask for the representative of a dynamic set twice without modifying the set between the requests, we get the same answer both times. Other applications may require a prespecified rule for choosing the representative, such as choosing the smallest member in the set (assuming, of course, that the elements can be ordered). It supports two useful operations:

• Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its ; by comparing the result of two Find operations, one can determine whether two elements are in the same subset.
• Union: Join two subsets into a single subset.

Disjoint-set Forests

Disjoint-set forests are data structures where each set is represented by a tree data structure, in which each node holds a reference to its parent node.

They were first described by Bernard A. Galler and Michael J. Fischer in 1964, although their precise analysis took years.

In a disjoint-set forest, the representative of each set is the root of that set's tree. Find follows parent nodes until it reaches the root. Union combines two trees into one by attaching the root of one to the root of the other. One way of implementing these might be: MakeSet, Find, and Union.

A sequence of operations on objects that takes time, or time per operation on average, using the linked-list set representation and the simple implementation of UNION.

The total number of operations is , and so each operation on average requires time. That is, the amortized time of an operation is .

Go Implementation disjoint.go:

package disjoint

type Element struct {
    Parent *Element
    Value  interface{}
}

func Makeset() *Element {
    e := new(Element)
    e.Parent = e
    return e
}

func Find(e *Element) *Element {
    if e.Parent == e {
        return e
    }
    e.Parent = Find(e.Parent)
    return e.Parent
}

func Union(e1, e2 *Element) {
    root1 := Find(e1)
    root2 := Find(e2)
    root1.Parent = root2
}

disjoint_test.go:

package disjoint

import (
    "testing"
)

func TestMakeSet(t *testing.T) {
    e1 := Makeset()
    if e1.Parent != e1 {
        t.Errorf("Incorrect parent in Maketset")
    }
}

func TestUnion(t *testing.T) {
    e1 := Makeset()
    e2 := Makeset()

    Union(e1, e2)

    if Find(e1) != e2 {
        t.Errorf("Incorrect parent after a union")
    }
}

func TestPathCompression(t *testing.T) {
    e1 := Makeset()
    e2 := Makeset()
    e3 := Makeset()

    Union(e2, e1)
    Union(e3, e2)

    if e3.Parent != e1 {
        t.Errorf("Path was incorrectly compressed after 2 unions")
    }
}

Reference

Chapter 21 Data Structures for Disjoint Sets of Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein