dfs

A spanning forest of the part of the graph reachable from the listed vertices, obtained from a depth-first search of the graph starting at each of the listed vertices in order.

Depth-first search.

Return the list vertices visited by the depth-first search in a graph, starting from the given seed vertices. Adjacent vertices are explored in the increasing order. Complexity: O((L + m) * log n) time and O(n) space, where L is the number of seed vertices.

dfs empty      vs    == []
dfs (edge 1 1) [1]   == [1]
dfs (edge 1 2) [0]   == []
dfs (edge 1 2) [1]   == [1,2]
dfs (edge 1 2) [2]   == [2]
dfs (edge 1 2) [1,2] == [1,2]
dfs (edge 1 2) [2,1] == [2,1]
dfs x          []    == []

and [ hasVertex v x | v <- dfs x vs ]       == True
dfs (3 * (1 + 4) * (1 + 5)) [1,4]           == [1,5,4]
dfs (circuit [1..5] + circuit [5,4..1]) [3] == [3,2,1,5,4]

Return the list vertices visited by the depth-first search in a graph, starting from the given seed vertices. Adjacent vertices are explored in the increasing order according to their Ord instance. Complexity: O((L + m) * log n) time and O(n) space, where L is the number of seed vertices.

dfs empty      vs    == []
dfs (edge 1 1) [1]   == [1]
dfs (edge 1 2) [0]   == []
dfs (edge 1 2) [1]   == [1,2]
dfs (edge 1 2) [2]   == [2]
dfs (edge 1 2) [1,2] == [1,2]
dfs (edge 1 2) [2,1] == [2,1]
dfs x          []    == []

and [ hasVertex v x | v <- dfs x vs ]       == True
dfs (3 * (1 + 4) * (1 + 5)) [1,4]           == [1,5,4]
dfs (circuit [1..5] + circuit [5,4..1]) [3] == [3,2,1,5,4]

Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order.

dfs == Algebra.Graph.AdjacencyMap.dfs . toAdjacencyMap

Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order. In the following examples we will use the helper function:

(%) :: Ord a => (GraphKL a -> b) -> AdjacencyMap a -> b
f % x = f (fromAdjacencyMap x)

for greater clarity.

dfs % edge 1 1 $ [1]   == [1]
dfs % edge 1 2 $ [0]   == []
dfs % edge 1 2 $ [1]   == [1,2]
dfs % edge 1 2 $ [2]   == [2]
dfs % edge 1 2 $ [1,2] == [1,2]
dfs % edge 1 2 $ [2,1] == [2,1]
dfs % x        $ []    == []

dfs % (3 * (1 + 4) * (1 + 5)) $ [1,4]     == [1,5,4]
and [ hasVertex v x | v <- dfs % x $ vs ] == True

dfs next found initial performs a depth-first search over a set of states, starting with initial and generating neighboring states with next. It returns a depth-first path to a state for which found returns True. Returns Nothing if no path is possible.

Example: Simple directed graph search

>>> import qualified Data.Map as Map

>>> graph = Map.fromList [(1, [2, 3]), (2, [4]), (3, [4]), (4, [])]

>>> dfs (graph Map.!) (== 4) 1
Just [3,4]

Iterate a tree in DFS pre-order. (Depth First Search)

Depth-first paths starting at a vertex.

>>> runG example $ \g@G{..} -> fmap3 gFromVertex $ dfs g <$> gToVertex 'x'
Right (Just ["xde","xe"])

Depth-first search algorithms. Names consist of:

1. 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

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

DFS implementation of MonadSearch.

Apply a Pattern transformation function depth first.

Monadic graph algorithms are defined in two steps:

1. define the (possibly parameterized) graph transformer (e.g., dfsGT)
2. run the graph transformer (applied to arguments) (e.g., dfsM)

depth-first search yielding number of nodes

Compute the depth-first search forest of a graph, where adjacent vertices are explored in the increasing order. Complexity: O((n + m) * min(n,W)) time and O(n) space.

forest $ dfsForest empty              == empty
forest $ dfsForest (edge 1 1)         == vertex 1
forest $ dfsForest (edge 1 2)         == edge 1 2
forest $ dfsForest (edge 2 1)         == vertices [1,2]
isSubgraphOf (forest $ dfsForest x) x == True
isDfsForestOf (dfsForest x) x         == True
dfsForest . forest . dfsForest        == dfsForest
dfsForest (vertices vs)               == map (\v -> Node v []) (nub $ sort vs)
dfsForest $ 3 * (1 + 4) * (1 + 5)     == [ Node { rootLabel = 1
, subForest = [ Node { rootLabel = 5
, subForest = [] }]}
, Node { rootLabel = 3
, subForest = [ Node { rootLabel = 4
, subForest = [] }]}]
forest (dfsForest $ circuit [1..5] + circuit [5,4..1]) == path [1,2,3,4,5]

Compute the depth-first search forest of a graph starting from the given seed vertices, where adjacent vertices are explored in the increasing order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. The seed vertices which do not belong to the graph are ignored. Complexity: O((L + m) * log n) time and O(n) space, where L is the number of seed vertices.

forest $ dfsForestFrom empty      vs             == empty
forest $ dfsForestFrom (edge 1 1) [1]            == vertex 1
forest $ dfsForestFrom (edge 1 2) [0]            == empty
forest $ dfsForestFrom (edge 1 2) [1]            == edge 1 2
forest $ dfsForestFrom (edge 1 2) [2]            == vertex 2
forest $ dfsForestFrom (edge 1 2) [1,2]          == edge 1 2
forest $ dfsForestFrom (edge 1 2) [2,1]          == vertices [1,2]
isSubgraphOf (forest $ dfsForestFrom x vs) x     == True
isDfsForestOf (dfsForestFrom x (vertexList x)) x == True
dfsForestFrom x (vertexList x)                   == dfsForest x
dfsForestFrom x []                               == []
dfsForestFrom (3 * (1 + 4) * (1 + 5)) [1,4]      == [ Node { rootLabel = 1
, subForest = [ Node { rootLabel = 5
, subForest = [] }
, Node { rootLabel = 4
, subForest = [] }]
forest $ dfsForestFrom (circuit [1..5] + circuit [5,4..1]) [3] == path [3,2,1,5,4]

Compute the depth-first search forest of a graph, where adjacent vertices are explored in the increasing order according to their Ord instance. Complexity: O((n + m) * min(n,W)) time and O(n) space.

forest $ dfsForest empty              == empty
forest $ dfsForest (edge 1 1)         == vertex 1
forest $ dfsForest (edge 1 2)         == edge 1 2
forest $ dfsForest (edge 2 1)         == vertices [1,2]
isSubgraphOf (forest $ dfsForest x) x == True
isDfsForestOf (dfsForest x) x         == True
dfsForest . forest . dfsForest        == dfsForest
dfsForest (vertices vs)               == map (\v -> Node v []) (nub $ sort vs)
dfsForest $ 3 * (1 + 4) * (1 + 5)     == [ Node { rootLabel = 1
, subForest = [ Node { rootLabel = 5
, subForest = [] }]}
, Node { rootLabel = 3
, subForest = [ Node { rootLabel = 4
, subForest = [] }]}]
forest (dfsForest $ circuit [1..5] + circuit [5,4..1]) == path [1,2,3,4,5]

Compute the depth-first search forest of a graph starting from the given seed vertices, where adjacent vertices are explored in the increasing order according to their Ord instance. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. The seed vertices which do not belong to the graph are ignored. Complexity: O((L + m) * log n) time and O(n) space, where L is the number of seed vertices.

forest $ dfsForestFrom empty      vs             == empty
forest $ dfsForestFrom (edge 1 1) [1]            == vertex 1
forest $ dfsForestFrom (edge 1 2) [0]            == empty
forest $ dfsForestFrom (edge 1 2) [1]            == edge 1 2
forest $ dfsForestFrom (edge 1 2) [2]            == vertex 2
forest $ dfsForestFrom (edge 1 2) [1,2]          == edge 1 2
forest $ dfsForestFrom (edge 1 2) [2,1]          == vertices [1,2]
isSubgraphOf (forest $ dfsForestFrom x vs) x     == True
isDfsForestOf (dfsForestFrom x (vertexList x)) x == True
dfsForestFrom x (vertexList x)                   == dfsForest x
dfsForestFrom x []                               == []
dfsForestFrom (3 * (1 + 4) * (1 + 5)) [1,4]      == [ Node { rootLabel = 1
, subForest = [ Node { rootLabel = 5
, subForest = [] }
, Node { rootLabel = 4
, subForest = [] }]
forest $ dfsForestFrom (circuit [1..5] + circuit [5,4..1]) [3] == path [3,2,1,5,4]