# `Yog.Functional.Traversal`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.98.0/lib/yog/functional/traversal.ex#L1)

Inductive graph traversals — BFS and DFS without explicit visited sets.

Unlike traditional graph traversals that maintain a separate "visited" set, these
implementations rely on the structural `match/2` operation. When a node is extracted,
it is removed from the graph along with all its incident edges, so the *shrunken*
graph naturally prevents revisits.

## Available Traversals

| Traversal | Function | Data Structure |
|-----------|----------|----------------|
| [DFS](https://en.wikipedia.org/wiki/Depth-first_search) | `dfs/2` | Stack (list) |
| [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) | `bfs/2` | Queue (`:queue`) |
| Preorder | `preorder/2` | Node IDs in visit order |
| Postorder | `postorder/2` | Node IDs in finish order |
| Reachable | `reachable/2` | All reachable node IDs |

## Key Principle

Iterating with the shrunken graph naturally prevents revisiting nodes and
terminates when the graph is empty — no `MapSet` of visited nodes needed.

**Time Complexity:** O(V + E) for both BFS and DFS.

## References

- [Original FGL Paper (Erwig, 2001)](https://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf)
- [Wikipedia: Graph Traversal](https://en.wikipedia.org/wiki/Graph_traversal)

# `bfs`

```elixir
@spec bfs(
  Yog.Functional.Model.t(),
  Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()]
) ::
  [Yog.Functional.Model.Context.t()]
```

Performs a Breadth-First Search starting from the given node ID(s).

Returns a list of node contexts in the order they were visited.

This is an inductive BFS: each step calls `match/2` to extract a node
and obtain the shrunken graph, ensuring nodes are visited at most once.

## Examples

    iex> alias Yog.Functional.{Model, Traversal}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2)
    iex> visited = Traversal.bfs(graph, 1)
    iex> Enum.map(visited, & &1.id)
    [1, 2]

# `dfs`

```elixir
@spec dfs(
  Yog.Functional.Model.t(),
  Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()]
) ::
  [Yog.Functional.Model.Context.t()]
```

Performs a Depth-First Search starting from the given node ID(s).

Returns a list of node contexts in the order they were visited.

This is an inductive DFS: each step calls `match/2` to simultaneously
extract a node and obtain the *shrunken* graph without that node.
Revisit prevention comes naturally from the graph shrinking — a node already
visited simply won't be found in the remaining graph.

For directed graphs, only outgoing edges are followed. For undirected graphs,
edges are stored symmetrically so `out_edges` covers all adjacent nodes.

## Examples

    iex> alias Yog.Functional.{Model, Traversal}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2)
    iex> visited = Traversal.dfs(graph, 1)
    iex> Enum.map(visited, & &1.id)
    [1, 2]

# `finishing_order`

# `postorder`

```elixir
@spec postorder(
  Yog.Functional.Model.t(),
  Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()]
) :: [Yog.Functional.Model.node_id()]
```

Returns node IDs in Postorder (finishing order, last node finishing first).

## Examples

    iex> alias Yog.Functional.{Model, Traversal}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2)
    iex> Traversal.postorder(graph, 1)
    [2, 1]

# `preorder`

```elixir
@spec preorder(
  Yog.Functional.Model.t(),
  Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()]
) :: [Yog.Functional.Model.node_id()]
```

Returns node IDs in Preorder (visit order).

## Examples

    iex> alias Yog.Functional.{Model, Traversal}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2)
    iex> Traversal.preorder(graph, 1)
    [1, 2]

# `reachable`

```elixir
@spec reachable(
  Yog.Functional.Model.t(),
  Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()]
) :: [Yog.Functional.Model.node_id()]
```

Returns all node IDs reachable from the start node(s).

## Examples

    iex> alias Yog.Functional.{Model, Traversal}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2)
    iex> Traversal.reachable(graph, 1) |> Enum.sort()
    [1, 2]

---

*Consult [api-reference.md](api-reference.md) for complete listing*