Modulefgl-5.8.3.1Haskell98

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.

Contents

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

Synopsis

type CFun
value dfs
value dfs'
value dff
value dff'
value dfsWith
value dfsWith'
value dffWith
value dffWith'
value xdfsWith
value xdfWith
value xdffWith
value udfs
value udfs'
value udff
value udff'
value udffWith
value udffWith'
value rdff
value rdff'
value rdfs
value rdfs'
value rdffWith
value rdffWith'
value topsort
value topsort'
value scc
value reachable
value components
value noComponents
value isConnected
value condensation

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

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

Standard

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

Source#

Depth-first search.

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

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

Source#

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]

Source#

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)

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.

valuexdffWith

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

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

Source#

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]

Source#

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

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

Source#

Reverse depth-first forest, obtained by following predecessors.

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

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

Source#

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

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

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

Source#

topsort, returning only the labels of the nodes.

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

Source#

Collection of strongly connected components

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

Source#

Collection of nodes reachable from a starting point.

Applications of undirected depth first search/forest

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

Source#

Collection of connected components

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

Source#

Number of connected components

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

Source#

Is the graph connected?

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

Source#

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