disjoint-set-0.1: Persistent disjoint-sets, a.k.a union-find.

Portabilitynon-portable (only tested with GHC 6.12.3)
Safe HaskellSafe-Inferred



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.



data IntDisjointSet Source

Represents a disjoint set of integers.


empty :: IntDisjointSetSource

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

singleton :: Int -> IntDisjointSetSource

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

insert :: Int -> IntDisjointSet -> IntDisjointSetSource

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 -> IntDisjointSetSource

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 -> IntDisjointSetSource

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)Source

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)Source

Return a list of all the elements.

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

Generate an association list of each element and its representative.

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

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

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

True if both elements belong to the same set.

disjointSetSize :: IntDisjointSet -> IntSource

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

size :: IntDisjointSet -> IntSource

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

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

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