|Portability||non-portable (only tested with GHC 6.12.3)|
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.
Below alpha(n) refers to the extremely slowly growing inverse Ackermann function.
- data IntDisjointSet
- empty :: IntDisjointSet
- singleton :: Int -> IntDisjointSet
- insert :: Int -> IntDisjointSet -> IntDisjointSet
- unsafeMerge :: IntDisjointSet -> IntDisjointSet -> IntDisjointSet
- union :: Int -> Int -> IntDisjointSet -> IntDisjointSet
- lookup :: Int -> IntDisjointSet -> (Maybe Int, IntDisjointSet)
- elems :: IntDisjointSet -> ([Int], IntDisjointSet)
- toList :: IntDisjointSet -> ([(Int, Int)], IntDisjointSet)
- fromList :: [(Int, Int)] -> IntDisjointSet
- equivalent :: Int -> Int -> IntDisjointSet -> (Bool, IntDisjointSet)
- disjointSetSize :: IntDisjointSet -> Int
- size :: IntDisjointSet -> Int
- map :: (Int -> 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).
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.
Create an equivalence relation between x and y. Amortized O(logn * alpha(n)).
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.
If either x or y is not present in the input set, nothing is done.
Find the set representative for this input. This performs path compression and so is stateful. Amortized O(logn * alpha(n)).
Generate an association list of each element and its representative, in arbitrary order.
Given an association list representing equivalences between elements, generate the corresponding disjoint-set.
True if both elements belong to the same set.