Graph.Reducers.Dfs (libgraph v0.16.0)
This reducer traverses the graph using Depth-First Search.
Link to this section Summary
Functions
Performs a depth-first traversal of the graph, applying the provided mapping function to each new vertex encountered.
Performs a depth-first traversal of the graph, applying the provided reducer function to each new vertex encountered and the accumulator.
Link to this section Functions
map(g, fun)
Performs a depth-first traversal of the graph, applying the provided mapping function to each new vertex encountered.
NOTE: The algorithm will follow lower-weighted edges first.
Returns a list of values returned from the mapper in the order they were encountered.
example
Example
iex> g = Graph.new |> Graph.add_vertices([1, 2, 3, 4])
...> g = Graph.add_edges(g, [{1, 3}, {1, 4}, {3, 2}, {2, 4}])
...> Elixir.Graph.Reducers.Dfs.map(g, fn v -> v end)
[1, 3, 2, 4]reduce(g, acc, fun)
Performs a depth-first traversal of the graph, applying the provided reducer function to each new vertex encountered and the accumulator.
NOTE: The algorithm will follow lower-weighted edges first.
The result will be the state of the accumulator after the last reduction.
example
Example
iex> g = Graph.new |> Graph.add_vertices([1, 2, 3, 4])
...> g = Graph.add_edges(g, [{1, 3}, {1, 4}, {3, 2}, {2, 4}])
...> Elixir.Graph.Reducers.Dfs.reduce(g, [], fn v, acc -> {:next, [v|acc]} end)
[4, 2, 3, 1]
iex> g = Graph.new |> Graph.add_vertices([1, 2, 3, 4, 5])
...> g = Graph.add_edges(g, [{1, 3}, {1, 4}, {3, 2}, {2, 4}, {4, 5}])
...> Elixir.Graph.Reducers.Dfs.reduce(g, [], fn 5, acc -> {:skip, acc}; v, acc -> {:next, [v|acc]} end)
[4, 2, 3, 1]
iex> g = Graph.new |> Graph.add_vertices([1, 2, 3, 4, 5])
...> g = Graph.add_edges(g, [{1, 3}, {1, 4}, {3, 2}, {2, 4}, {4, 5}])
...> Elixir.Graph.Reducers.Dfs.reduce(g, [], fn 4, acc -> {:halt, acc}; v, acc -> {:next, [v|acc]} end)
[2, 3, 1]