| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Graph.Generic
Description
Generic graph search.
Synopsis
- genericComponentsOf :: (Vertex -> Vector Vertex) -> Int -> Vector Vertex -> Vector Vertex
- genericGrouping :: (Vertex -> Vector Vertex) -> Int -> (Vector Int, [[Vertex]])
- genericDfs :: (Unbox w, Num w, Eq w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w -> Vector w
- genericDfsLongestPath :: forall w. (Num w, Ord w, Unbox w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w
- genericBfs :: (Unbox w, Num w, Eq w) => (Int -> Vector (Vertex, w)) -> Int -> Vertex -> w -> Vector w
- genericBfs01 :: (Ix i, Unbox i) => (i, i) -> (i -> Vector (i, Int)) -> Int -> Vector i -> IxUVector i Int
- genericDj :: forall w. (Unbox w, Num w, Ord w) => (Vertex -> Vector (Vertex, w)) -> Int -> Int -> w -> Vector Vertex -> Vector w
- dj' :: forall w. (Unbox w, Monoid w, Ord w) => (Int -> Vector (Int, w)) -> Int -> Int -> w -> Vector Vertex -> Vector w
- genericSparseDj :: forall w. (Unbox w, Num w, Ord w) => (Int -> Vector (Int, w)) -> w -> Vector Vertex -> IntMap w
- genericDfsEveryPathL :: (Vertex -> Vector Vertex) -> Int -> Vertex -> Int -> Maybe (Vector Int)
- genericDfsTree :: (Unbox w, Num w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w -> (Vector w, Vector Vertex)
- genericBfsTree :: (Unbox w, Num w, Eq w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w -> (Vector w, Vector Vertex)
- genericDjTree :: forall w. (Unbox w, Num w, Ord w) => (Vertex -> Vector (Vertex, w)) -> Int -> Int -> w -> Vector Vertex -> (Vector w, Vector Vertex)
- restorePath :: HasCallStack => Vector Vertex -> Vertex -> Vector Vertex
- runPersistentDfs :: (HasCallStack, Monad m, Unbox w) => (Vertex -> Vector (Vertex, w)) -> Vertex -> a -> (HasCallStack => a -> Vertex -> Vertex -> w -> m a) -> m ()
- distsNN :: (Unbox w, Num w, Ord w) => Int -> w -> Vector (Int, Int, w) -> IxUVector (Int, Int) w
Graph search
genericComponentsOf :: (Vertex -> Vector Vertex) -> Int -> Vector Vertex -> Vector Vertex #
\(O(V+E)\) DFS that paints connnected components starting from a vertex.
genericGrouping :: (Vertex -> Vector Vertex) -> Int -> (Vector Int, [[Vertex]]) #
\(O(V+E)\) DFS that paints connnected components. Returns (vertexToComponentId, components).
Works on non-directed graphs only.
genericDfs :: (Unbox w, Num w, Eq w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w -> Vector w #
\(O(V+E)\) Depth-first search.
genericDfsLongestPath :: forall w. (Num w, Ord w, Unbox w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w #
\(O(N N!)\) Depth-first search that finds the longest path. Just a template!
genericBfs :: (Unbox w, Num w, Eq w) => (Int -> Vector (Vertex, w)) -> Int -> Vertex -> w -> Vector w #
\(O(V+E)\) Breadth-first search. Unreachable vertices are given distance of -1.
genericBfs01 :: (Ix i, Unbox i) => (i, i) -> (i -> Vector (i, Int)) -> Int -> Vector i -> IxUVector i Int #
\(O(V+E)\) 01-BFS. Unreachable vertices are given distance of -1.
Example
let !bnd3 = zero3 n n 4
let !res = genericBfs01 bnd3 grF (4 * n * n) source
where
grF (!y, !x, !iDir) = flip U.imapMaybe diag4 $ i (!dy, !dx) -> do
let (!y', !x') = (y + dy, x + dx)
guard $ inRange (zero2 n n) (y', x') && gr @! (y', x') /= #
return ((y', x', i), bool 1 0 (iDir == i))
source = U.generate 4 $ (sy, sx,)
Typical problems
genericDj :: forall w. (Unbox w, Num w, Ord w) => (Vertex -> Vector (Vertex, w)) -> Int -> Int -> w -> Vector Vertex -> Vector w #
\(O((E+V) \log {V})\) Dijkstra's algorithm.
Does pruning on heap entry pushing: https://www.slideshare.net/yosupo/ss-46612984 P15
Note that longest Dijkstra can be implemented by just using a max heap.
dj' :: forall w. (Unbox w, Monoid w, Ord w) => (Int -> Vector (Int, w)) -> Int -> Int -> w -> Vector Vertex -> Vector w #
\(O((E+V) \log {V})\) Monoid-based more generic genericDj. TODO: Allow `Min w`.
genericSparseDj :: forall w. (Unbox w, Num w, Ord w) => (Int -> Vector (Int, w)) -> w -> Vector Vertex -> IntMap w #
\(O((E+V) \log {V})\) Dijkstra's algorithm with sparse heap.
TODO: test
Path restoration
genericDfsEveryPathL :: (Vertex -> Vector Vertex) -> Int -> Vertex -> Int -> Maybe (Vector Int) #
\(O(V!)\) Depth-first search for finding a path with length L. The complexity is for dense
graph and IT CAN BE MUCH LOWER on different sparse graphs.
genericDfsTree :: (Unbox w, Num w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w -> (Vector w, Vector Vertex) #
\(O(V+E)\) depth-first search. Returns a vector of parents. The source vertex or unrechable vertices are given `-1` as their parent. Note that it doesn't return the shortest path.
genericBfsTree :: (Unbox w, Num w, Eq w) => (Vertex -> Vector (Vertex, w)) -> Int -> Vertex -> w -> (Vector w, Vector Vertex) #
\(O(V+E)\) breadth-first search. Returns a vector of parents. The source vertex or unrechable vertices are given `-1` as their parent.
genericDjTree :: forall w. (Unbox w, Num w, Ord w) => (Vertex -> Vector (Vertex, w)) -> Int -> Int -> w -> Vector Vertex -> (Vector w, Vector Vertex) #
\(O((E+V) \log V)\) Dijkstra's algorithm with path restoration information.
restorePath :: HasCallStack => Vector Vertex -> Vertex -> Vector Vertex #
\(O(V)\) Given a vector of vertex parents, restores path from the source to a sink.
TODO: restore without reverse?
Tree
runPersistentDfs :: (HasCallStack, Monad m, Unbox w) => (Vertex -> Vector (Vertex, w)) -> Vertex -> a -> (HasCallStack => a -> Vertex -> Vertex -> w -> m a) -> m () #
Vistor-based DFS for query processing with persistent data structure with minimum garbage collectin. Be sure to not make a bi-directed graph.