fgl-5.5.2.3: Martin Erwig's Functional Graph Library

Data.Graph.Inductive.Query.DFS

Description

Depth-first search algorithms.

Names consist of:

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

`x`
undirectional: ignore edge direction
`r`
reversed: walk edges in reverse
`x`
user defined: speciy which paths to follow
2. "df" for depth-first
3. A structure parameter, specifying the type of the result.

`s`
Flat list of results
`f`
Structured `Tree` of results
4. An optional "With", which instead of putting the found nodes directly into the result, adds the result of a computation on them into it.
5. An optional prime character, in which case all nodes of the graph will be visited, instead of a user-given subset.

Synopsis

# 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

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 `Node`s 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.