Safe Haskell	Safe
Language	Haskell98

Data.Graph.Inductive.Query.DFS

Contents

Standard
Undirected
Reversed
Applications of depth first search/forest
Applications of undirected depth first search/forest

Description

Depth-first search algorithms.

Names consist of:

An optional direction parameter, specifying which nodes to visit next.

u: undirectional: ignore edge direction
r: reversed: walk edges in reverse
x: user defined: speciy which paths to follow

"df" for depth-first
A structure parameter, specifying the type of the result.
s
Flat list of results
f
Structured Tree of results
An optional "With", which instead of putting the found nodes directly into the result, adds the result of a computation on them into it.
An optional prime character, in which case all nodes of the graph will be visited, instead of a user-given subset.

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]
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]
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]
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
condensation :: Graph gr => gr a b -> gr [Node] ()

Documentation

type CFun a b c = Context a b -> c Source #

Standard

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

Depth-first search.

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

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

Directed depth-first forest.

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 Source #

Arguments

:: Graph gr
=> CFun a b [Node]	Mapping from a node to its neighbours to be visited as well. `suc'` for example makes `xdfsWith` traverse the graph following the edge directions, while `pre'` means reversed directions.
-> CFun a b c	Mapping from the `Context` of a node to a result value.
-> [Node]	Nodes to be visited.
-> gr a b
-> [c]

Most general DFS algorithm to create a list of results. The other list-returning functions such as dfs are all defined in terms of this one.

xdfsWith d f vs = preorderF . xdffWith d f vs

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

Most general DFS algorithm to create a forest of results, otherwise very similar to xdfsWith. The other forest-returning functions such as dff are all defined in terms of this one.

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

Discard the graph part of the result of xdfWith.

xdffWith d f vs g = fst (xdfWith d f vs g)

Undirected

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

Undirected depth-first search, obtained by following edges regardless of their direction.

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

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

Undirected depth-first forest, obtained by following edges regardless of their direction.

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

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

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

Reversed

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

Reverse depth-first forest, obtained by following predecessors.

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

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

Reverse depth-first search, obtained by following predecessors.

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

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

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

Applications of depth first search/forest

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

Topological sorting, i.e. a list of Nodes so that if there's an edge between a source and a target node, the source appears earlier in the result.

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

topsort, returning only the labels of the nodes.

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

Collection of strongly connected components

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

Collection of nodes reachable from a starting point.

Applications of undirected depth first search/forest

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

Collection of connected components

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

Number of connected components

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

Is the graph connected?

condensation :: Graph gr => gr a b -> gr [Node] () Source #

The condensation of the given graph, i.e., the graph of its strongly connected components.