An implementation of Tarjan's UNION-FIND algorithm. (Robert E Tarjan. "Efficiency of a Good But Not Linear Set Union Algorithm", JACM 22(2), 1975)
The algorithm implements three operations efficiently (all amortised
- Check whether two elements are in the same equivalence class.
- Create a union of two equivalence classes.
- Look up the descriptor of the equivalence class.
The implementation is based on mutable references. Each equivalence class has exactly one member that serves as its representative element. Every element either is the representative element of its equivalence class or points to another element in the same equivalence class. Equivalence testing thus consists of following the pointers to the representative elements and then comparing these for identity.
The algorithm performs lazy path compression. That is, whenever we walk along a path greater than length 1 we automatically update the pointers along the path to directly point to the representative element. Consequently future lookups will be have a path length of at most 1.
- data Point s a
- fresh :: a -> ST s (Point s a)
- repr :: Point s a -> ST s (Point s a)
- union :: Point s a -> Point s a -> ST s ()
- union' :: Point s a -> Point s a -> (a -> a -> ST s a) -> ST s ()
- equivalent :: Point s a -> Point s a -> ST s Bool
- redundant :: Point s a -> ST s Bool
- descriptor :: Point s a -> ST s a
- setDescriptor :: Point s a -> a -> ST s ()
- modifyDescriptor :: Point s a -> (a -> a) -> ST s ()
The abstract type of an element of the sets we work on. It is parameterised over the type of the descriptor.
O(1). Create a fresh point and return it. A fresh point is in the equivalence class that contains only itself.
repr point returns the representative point of
point's equivalence class.
This method performs the path compresssion.
O(1). Join the equivalence classes of the points (which must be distinct). The resulting equivalence class will get the descriptor of the second argument.
union, but sets the descriptor returned from the callback.
The intention is to keep the descriptor of the second argument to the callback, but the callback might adjust the information of the descriptor or perform side effects.
True if both points belong to the same
| equivalence class.
True for all but one element of an equivalence
class. That is, if
ps = [p1, .., pn] are all in the same
equivalence class, then the following assertion holds.
do rs <- mapM redundant ps assert (length (filter (==False) rs) == 1)
It is unspecified for which element function returns
False, so be
really careful when using this.
O(1). Return the descriptor associated with argument point's equivalence class.
O(1). Replace the descriptor of the point's equivalence class with the second argument.