fgl-5.4.1.1: Martin Erwig's Functional Graph Library

Data.Graph.Inductive.Query.DFS

Contents

Description

Depth-First Search

Synopsis

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

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 -> IntSource

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