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

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]
Link to this function

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]