Data.Graph.Inductive.Query.DFS

Depth-First Search

Documentation

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]

Undirected DFS

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]

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

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

Reverse DFS

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]

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

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

Applications of DFS/DFF

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]

Applications of UDFS/UDFF

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

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

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