Modulefgl-5.8.2.0Haskell98

Data.Graph.Inductive.Query.DFS

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.

1 type
31 values

Packagefgl-5.8.2.0
Exports32
LanguageHaskell98
LicenceBSD-3-Clause
SourceDFS.hs

typetype CFun a b c = Context a b -> c

Standard

11 declarations

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

Depth-first search.

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

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

Directed depth-first forest.

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

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

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

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

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

valuexdfsWith

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

valuexdfWith

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

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.

valuexdffWith

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

Discard the graph part of the result of xdfWith.

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

Undirected

6 declarations

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

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

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

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

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

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

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

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

Reversed

6 declarations

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

Reverse depth-first forest, obtained by following predecessors.

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

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

Reverse depth-first search, obtained by following predecessors.

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

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

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

Applications of depth first search/forest

4 declarations

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

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.

valuetopsort' :: Graph gr => gr a b -> [a]

topsort, returning only the labels of the nodes.

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

Collection of strongly connected components

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

Collection of nodes reachable from a starting point.

Applications of undirected depth first search/forest

4 declarations

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

Collection of connected components

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

Number of connected components

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

Is the graph connected?

valuecondensation :: Graph gr => gr a b -> gr [Node] ()

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