dfs package:fgl
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.
Monadic graph algorithms are defined in two steps:
- define the (possibly parameterized) graph transformer (e.g.,
dfsGT)
- run the graph transformer (applied to arguments) (e.g., dfsM)
depth-first search yielding number of nodes
Reverse depth-first search, obtained by following predecessors.
Undirected depth-first search, obtained by following edges regardless
of their direction.
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