fgl-5.4.2.4: Martin Erwig's Functional Graph Library

Safe Haskell | None

Data.Graph.Inductive.Query.DFS

Contents

- Undirected DFS
- Reverse DFS
- Applications of DFS/DFF
- Applications of UDFS/UDFF

Description

Depth-First Search

Synopsis

- type CFun a b c = Context a b -> c
- dfs :: Graph gr => [Node] -> gr a b -> [Node]
- dfs' :: Graph gr => gr a b -> [Node]
- dff :: Graph gr => [Node] -> gr a b -> [Tree Node]
- dff' :: Graph gr => gr a b -> [Tree Node]
- dfsWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [c]
- dfsWith' :: Graph gr => CFun a b c -> gr a b -> [c]
- dffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]
- dffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]
- xdfsWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [c]
- xdfWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c], gr a b)
- xdffWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]
- udfs :: Graph gr => [Node] -> gr a b -> [Node]
- udfs' :: Graph gr => gr a b -> [Node]
- udff :: Graph gr => [Node] -> gr a b -> [Tree Node]
- udff' :: Graph gr => gr a b -> [Tree Node]
- rdff :: Graph gr => [Node] -> gr a b -> [Tree Node]
- rdff' :: Graph gr => gr a b -> [Tree Node]
- rdfs :: Graph gr => [Node] -> gr a b -> [Node]
- rdfs' :: Graph gr => gr a b -> [Node]
- topsort :: Graph gr => gr a b -> [Node]
- topsort' :: Graph gr => gr a b -> [a]
- scc :: Graph gr => gr a b -> [[Node]]
- reachable :: Graph gr => Node -> gr a b -> [Node]
- components :: Graph gr => gr a b -> [[Node]]
- noComponents :: Graph gr => gr a b -> Int
- isConnected :: Graph gr => gr a b -> Bool

# Documentation

type CFun a b c = Context a b -> cSource

dfs :: Graph gr => [Node] -> gr a b -> [Node]Source

dfs' :: Graph gr => gr a b -> [Node]Source

dff :: Graph gr => [Node] -> gr a b -> [Tree Node]Source

dff' :: Graph gr => gr a b -> [Tree Node]Source

dfsWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [c]Source

dfsWith' :: Graph gr => CFun a b c -> gr a b -> [c]Source

dffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]Source

dffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]Source

xdfsWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [c]Source

xdfWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c], gr a b)Source

xdffWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]Source

# Undirected DFS

udfs :: Graph gr => [Node] -> gr a b -> [Node]Source

udfs' :: Graph gr => gr a b -> [Node]Source

udff :: Graph gr => [Node] -> gr a b -> [Tree Node]Source

udff' :: Graph gr => gr a b -> [Tree Node]Source

# Reverse DFS

rdff :: Graph gr => [Node] -> gr a b -> [Tree Node]Source

rdff' :: Graph gr => gr a b -> [Tree Node]Source

rdfs :: Graph gr => [Node] -> gr a b -> [Node]Source

rdfs' :: Graph gr => gr a b -> [Node]Source

# Applications of DFS/DFF

topsort :: Graph gr => gr a b -> [Node]Source

topsort' :: Graph gr => gr a b -> [a]Source

scc :: Graph gr => gr a b -> [[Node]]Source

reachable :: Graph gr => Node -> gr a b -> [Node]Source

# Applications of UDFS/UDFF

components :: Graph gr => gr a b -> [[Node]]Source

noComponents :: Graph gr => gr a b -> Int Source

isConnected :: Graph gr => gr a b -> Bool Source