| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.UnionFind.Potencial
Description
Union-find tree under a differencial constraint system on a Group
Typical problems
Synopsis
- data PUnionFind s a = PUnionFind {
- nodesPUF :: !(MVector s MUFNode)
- potencialPUF :: !(MVector s a)
- newPUF :: forall m a. (PrimMonad m, Monoid a, Unbox a) => Int -> m (PUnionFind (PrimState m) a)
- rootPUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> m Int
- unifyPUF :: (PrimMonad m, Group a, Ord a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> a -> m Bool
- unifyPUF_ :: (PrimMonad m, Group a, Ord a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> a -> m ()
- sizePUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> m Int
- samePUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> m Bool
- canUnifyPUF :: (PrimMonad m, Semigroup a, Eq a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> a -> m Bool
- potPUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> m a
- diffPUF :: (PrimMonad m, Group a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> m a
- diffMayPUF :: (PrimMonad m, Group a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> m (Maybe a)
- clearPUF :: forall m a. (PrimMonad m, Group a, Unbox a) => PUnionFind (PrimState m) a -> m ()
- groupsPUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> m (IntMap [Int])
Documentation
data PUnionFind s a #
Union-Find tree under a differencial constraint systems. Each vertex v is given potencial
value p(v) which is a relative value tested on unifyPUF.
Implementation based on: https://qiita.com/drken/items/cce6fc5c579051e64fab
Invariants
New comping potencial always comes from left: new <> old.
Constructors
| PUnionFind | |
Fields
| |
newPUF :: forall m a. (PrimMonad m, Monoid a, Unbox a) => Int -> m (PUnionFind (PrimState m) a) #
\(O(N)\) Creates a new union-find tree under a differencial-potencal system.
rootPUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> m Int #
\(O(\alpha(N))\) Returns root to the given vertex, after updating the internal differencial potencials.
unifyPUF :: (PrimMonad m, Group a, Ord a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> a -> m Bool #
\(O(\alpha(N))\) Unifies two nodes, managing their differencial potencial so that
p(v1) = dp <> p(v2) holds after unification. Or think like unifyPUF uf dst src.
Returns True when thry're newly unified. Returns False if they're already unified or when
the unification didn't match the existing potencials.
unifyPUF_ :: (PrimMonad m, Group a, Ord a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> a -> m () #
\(O(\alpha(N))\) unifyPUF with the return value discarded.
sizePUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> m Int #
\(O(1)\) Returns the number of vertices belonging to the same group.
samePUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> m Bool #
\(O(\alpha(N))\) Has the same root / belongs to the same group.
canUnifyPUF :: (PrimMonad m, Semigroup a, Eq a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> a -> m Bool #
\(O(\alpha(N))\) Can be unified (or already unified) keeping the equiation p(v1) = dp <> p(v2).
potPUF :: (PrimMonad m, Semigroup a, Unbox a) => PUnionFind (PrimState m) a -> Int -> m a #
Returns p(v): the potencial of the vertex in their group.
diffPUF :: (PrimMonad m, Group a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> m a #
\(O(\alpha(N))\) Returns \(p(v1) <> p^{-1}(v2)\). Returns non-meaning value when the two vertices are
not connected. Or think like diffPUF uf dst src.
diffMayPUF :: (PrimMonad m, Group a, Unbox a) => PUnionFind (PrimState m) a -> Int -> Int -> m (Maybe a) #
\(O(\alpha(N))\) Returns \(p(v1) <> p^{-1}(v2)\). Returns Nothing when the two vertices are not
connected. Or think like diffMayPUF uf dst src.