hologram

defmodule Graph.Reducer do
  @moduledoc false

  # Reducers provide a way to traverse a graph while applying a function at each vertex. This
  # can be used for a variety of things, most notably though is pre-processing a graph, for example
  # one might decorate vertices with their distance from some known landmarks for later use in
  # a cost function for A*.

  # The `reduce` function takes a callback which has some control over when to terminate the traversal,
  # to move to the next vertex, return `{:next, acc}`, but to stop traversal and return the accumulator,
  # return `{:halt, acc}`. The `map` function is built on top of `reduce` but does not expose this control,
  # so if you need to map over the graph but stop early, you'll want to build your own `map` implementation
  # on top of `reduce`.

  # Provided out of the box are two reducers, `Graph.Reducers.Bfs` (for breadth-first traversals), and
  # `Graph.Reducers.Dfs` (for depth-first traversals). Simply choose the best one for your use case.

  @callback map(g :: Graph.t(), mapper :: (Graph.vertex() -> term)) :: term
  @callback reduce(g :: Graph.t(), acc :: term, reducer :: (Graph.vertex(), term -> term)) ::
              {:next, term}
              | {:halt, term}

  defmacro __using__(_) do
    quote do
      @behaviour Graph.Reducer
    end
  end
end