| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Graph.Tree.TreeSG
Description
Tree algorithms for SparseGraph.
Synopsis
- treeDiameterSG :: (Unbox w, Num w, Ord w) => SparseGraph w -> w -> (Vertex, Vertex, w)
- treeDiameterPathSG :: (Unbox w, Num w, Ord w) => SparseGraph w -> w -> ((Vertex, Vertex, w), Vector Vertex)
- treeDepthInfoSG :: (Monoid w, Unbox w) => SparseGraph w -> Int -> (Vector Int, IndexMapWithAction w)
- lcaCacheSG :: (Monoid w, Unbox w) => SparseGraph w -> Vertex -> LcaCache w
- foldTreeImplSG :: forall m op a w. (Monad m, Unbox w) => SparseGraph w -> Vertex -> (op -> (Vertex, w) -> op) -> (op -> a -> a) -> (Vertex -> a) -> (a -> op) -> (Vertex -> a -> m ()) -> m a
- foldTreeSG :: Unbox w => SparseGraph w -> Vertex -> (op -> (Vertex, w) -> op) -> (op -> a -> a) -> (Vertex -> a) -> (a -> op) -> a
- scanTreeSG :: (Vector v a, Unbox w) => SparseGraph w -> Vertex -> (op -> (Vertex, w) -> op) -> (op -> a -> a) -> (Vertex -> a) -> (a -> op) -> v a
- foldTreeAllSG :: forall a op w. (Unbox a, Unbox op, Monoid op, SemigroupAction op a, Unbox w) => SparseGraph w -> (Vertex -> a) -> (a -> op) -> Vector a
- foldTreeAllSG' :: forall a op w. (Unbox a, Unbox op, Monoid op, SemigroupAction op a, Unbox w) => SparseGraph w -> (op -> (Vertex, w) -> op) -> (Vertex -> a) -> (a -> op) -> Vector a
Diameter
treeDiameterSG :: (Unbox w, Num w, Ord w) => SparseGraph w -> w -> (Vertex, Vertex, w) #
\(O(V+E)\) Tree diameter calculation.
treeDiameterPathSG :: (Unbox w, Num w, Ord w) => SparseGraph w -> w -> ((Vertex, Vertex, w), Vector Vertex) #
\(O(V+E)\) Tree diameter calculation.
LCA (prefer HLD though)
treeDepthInfoSG :: (Monoid w, Unbox w) => SparseGraph w -> Int -> (Vector Int, IndexMapWithAction w) #
\(O(N)\) Returns (depths, parents).
lcaCacheSG :: (Monoid w, Unbox w) => SparseGraph w -> Vertex -> LcaCache w #
Returns LcaCache, i.e., (parents, depths, parents').
Tree folding
foldTreeImplSG :: forall m op a w. (Monad m, Unbox w) => SparseGraph w -> Vertex -> (op -> (Vertex, w) -> op) -> (op -> a -> a) -> (Vertex -> a) -> (a -> op) -> (Vertex -> a -> m ()) -> m a #
\(O(N)\) Weighted ree folding.
foldTreeSG :: Unbox w => SparseGraph w -> Vertex -> (op -> (Vertex, w) -> op) -> (op -> a -> a) -> (Vertex -> a) -> (a -> op) -> a #
\(O(N)\) Folds a tree from one root vertex using postorder DFS.
scanTreeSG :: (Vector v a, Unbox w) => SparseGraph w -> Vertex -> (op -> (Vertex, w) -> op) -> (op -> a -> a) -> (Vertex -> a) -> (a -> op) -> v a #
\(O(N)\) Folds a tree from one root vertex using postorder DFS, recording all the accumulation values on every vertex.
foldTreeAllSG :: forall a op w. (Unbox a, Unbox op, Monoid op, SemigroupAction op a, Unbox w) => SparseGraph w -> (Vertex -> a) -> (a -> op) -> Vector a #
\(O(N)\) Folds a not-weighted tree for every vertex as a root using the rerooting technique.
Typical problems
foldTreeAllSG' :: forall a op w. (Unbox a, Unbox op, Monoid op, SemigroupAction op a, Unbox w) => SparseGraph w -> (op -> (Vertex, w) -> op) -> (Vertex -> a) -> (a -> op) -> Vector a #
\(O(N)\) Folds a weighted tree for every vertex as a root using the rerooting technique.