search

nominolo / union-find

Efficient union and equivalence testing of sets.
Other
30 stars 12 forks source link

Data.UnionFind.IntMap, Add path compressing repr and equivalence #9

Open galpsten opened 6 years ago

galpsten commented 6 years ago

Consider 

repr       :: PointSupply a -> Point a -> Point a
descriptor :: PointSupply a -> Point a -> a
equivalent :: PointSupply a -> Point a -> Point a -> Bool

They do not perform path compression, which may lead to O(n) performance for some points. It is nice to have simple interfaces where the updated PointSupply doesn't need to be handled. But, it would be nice to also have the following functions:

repr'       :: PointSupply a -> Point a -> (PointSupply a, Point a)
descriptor' :: PointSupply a -> Point a -> (PointSupply a, a)
equivalent' :: PointSupply a -> Point a -> Point a -> (PointSupply a, Bool)

That do path compression. It would be particularly nice to have in the Control.Monad.Trans.UnionFind transformer.

reverofevil commented 1 year ago

Hmm, so it wasn't only me who didn't find path compression in this extremely efficient union-find library.