Data.IntDisjointSet

Persistent Disjoint-Sets (a.k.a. Union-Find). This implements disjoint-sets according to the description given in "Introduction to Algorithms" by Cormen et al (http://mitpress.mit.edu/algorithms). Most functions incur an additional O(logn) overhead due to the use of persistent maps.

Disjoint-sets are a set of elements with equivalence relations defined between elements, i.e. two elements may be members of the same equivalence set. Each element has a set representative. The implementation works by maintaining a map from an element to its parent. When an element is its own parent, it is the set representative. Two elements are part of the same equivalence set when their set representatives are the same.

In order to find the set representative efficiently, after each traversal from an element to its representative, we compress the path so that each element on the path points directly to the set representative. For this to be persistent, lookup is stateful and so returns the result of the lookup and a new disjoint set.

Additionally, to make sure that path lengths grow logarithmically, we maintain the rank of a set. This is a logarithmic upper bound on the number of elements in each set. When we compute the union of two sets, we make the set with the smaller rank a child of the set with the larger rank. When two sets have equal rank, the first set is a child of the second and the rank of the second is increased by 1.

Documentation

data IntDisjointSet

Represents a disjoint set of integers.

Instances

Show IntDisjointSet

empty :: IntDisjointSet

Create a disjoint set with no members. O(1).

singleton :: Int -> IntDisjointSet

Create a disjoint set with one member. O(1).

insert :: Int -> IntDisjointSet -> IntDisjointSet

Insert x into the disjoint set. If it is already a member, then do nothing, otherwise x has no equivalence relations. O(logn).

unsafeMerge :: IntDisjointSet -> IntDisjointSet -> IntDisjointSet

Given two instances of disjoint sets that share no members in common, computes a third disjoint set that is the combination of the two.

This method is unsafe in that is does not verify that the two input sets share no members in common and in the event that a member overlaps, the resulting set may have incorrect equivalence relations.

union :: Int -> Int -> IntDisjointSet -> IntDisjointSet

Create an equivalence relation between x and y.

Amortized O(logn * alpha(n)) where alpha(n) is the extremely slowly growing inverse Ackermann function.

This function works by looking up the set representatives for both x and y. If they are the same, it does nothing. Then it looks up the rank for both representatives and makes the tree of the smaller ranked representative a child of the tree of the larger ranked representative. If both representatives have the same rank, x is made a child of y and the rank of y is increase by 1.

lookup :: Int -> IntDisjointSet -> (Maybe Int, IntDisjointSet)

Find the set representative for this input. This performs path compression and so is stateful.

Amortized O(logn * alpha(n)) where alpha(n) is the extremely slowly growing inverse Ackermann function.

elems :: IntDisjointSet -> ([Int], IntDisjointSet)

Return a list of all the elements.

toList :: IntDisjointSet -> ([(Int, Int)], IntDisjointSet)

Generate an association list of each element and its representative.

fromList :: [(Int, Int)] -> IntDisjointSet

Given an association list representing equivalences between elements, generate the corresponding disjoint-set.

equivalent :: Int -> Int -> IntDisjointSet -> (Bool, IntDisjointSet)

True if both elements belong to the same set.

disjointSetSize :: IntDisjointSet -> Int

Return the number of disjoint sets. O(1).

size :: IntDisjointSet -> Int

Return the number of elements in all disjoint sets. O(1).

map :: (Int -> Int) -> IntDisjointSet -> IntDisjointSet

Map each member to another Int. The map function must be a bijection, i.e. 1-to-1 mapping.