Purely Functional Data Structures & Algorithms : Union-Find (Haskell)
*Updated 08-23-2012 01:04:38*
Replaced the use of Data.Vector with the persistent Data.Sequence which has O(logN) worst case time complexity on updates.
A Haskell version of the previous code using the more efficient(access and update) persistent Data.Sequence type so that the desired time complexity is maintained for the union operation.
-- Disjoint set data type (weighted and using path compression).
-- O((M+N)lg*N + 2MlogN) worst-case union time (practically O(1))
-- For M union operations on a set of N elements.
-- O((M+N)lg*N) worst-case find time (practically O(1))
-- For M connected(find) operations on a set of N elements.
data DisjointSet = DisjointSet
{ count :: Int, ids :: (Seq Int), sizes :: (Seq Int) }
deriving (Read, Show)
-- Return id of root object
findRoot :: DisjointSet -> Int -> Int
findRoot set p | p == parent = p
| otherwise = findRoot set parent
where
parent = index (ids set) (p - 1)
-- Are objects P and Q connected ?
connected :: DisjointSet -> Int -> Int -> Bool
connected set p q = (findRoot set p) == (findRoot set q)
-- Replace sets containing P and Q with their union
quickUnion :: DisjointSet -> Int -> Int -> DisjointSet
quickUnion set p q | i == j = set
| otherwise = DisjointSet cnt rids rsizes
where
(i, j) = (findRoot set p, findRoot set q)
(i1, j1) = (index (sizes set) (i - 1), index (sizes set) (j - 1))
(cnt, psmaller, size) = (count set - 1, i1 < j1, i1 + j1)
-- Always make smaller root point to the larger one
(rids, rsizes) = if psmaller
then (update (i - 1) j (ids set), update (j - 1) size (sizes set))
else (update (j - 1) i (ids set), update (i - 1) size (sizes set))
Tested …
jgrant@aristotle:~/jngmisc/haskell$ ghc quick_union.hs ; time ./quick_union 10
creating union find with 10 objects ...DONE
DisjointSet {count = 10, ids = fromList [1,2,3,4,5,6,7,8,9,10], sizes = fromList [1,1,1,1,1,1,1,1,1,1]}
All objects are disconnected.
1 and 9 connected ? False
4 and 6 connected ? False
3 and 1 connected ? False
7 and 8 connected ? False
creating unions ...DONE
DisjointSet {count = 1, ids = fromList [4,8,7,7,8,8,8,8,8,8], sizes = fromList [1,1,1,2,1,1,4,10,1,1]}
All objects are connected (only 1 group).
1 and 9 connected ? True
4 and 6 connected ? True
3 and 1 connected ? True
7 and 8 connected ? True
real 0m0.002s
user 0m0.000s
sys 0m0.000s