# `Yog.Functional.Traversal`
[🔗](https://github.com/code-shoily/yog_ex/blob/v1.0.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 | Return value |
|-----------|----------|----------------|--------------|
| [DFS](https://en.wikipedia.org/wiki/Depth-first_search) | `dfs/2` | Stack (list) | Node contexts |
| [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) | `bfs/2` | Queue (`:queue`) | Node contexts |
| Preorder | `preorder/2` | DFS wrapper | Node IDs in visit order |
| Postorder | `postorder/2` | Recursive finishing order | Node IDs in finish order |
| Reachable | `reachable/2` | DFS wrapper | Reachable node IDs |

## Key Principle

Iterating with the shrunken graph naturally prevents revisiting nodes and
terminates when no queued start/candidate nodes remain — no `MapSet` of visited
nodes is needed.

## Semantics

- Traversal starts can be a single node ID or a list of node IDs.
- Missing start nodes are skipped.
- Duplicate start nodes or duplicate neighbor discoveries are visited at most once
  because already-matched nodes are absent from the remaining graph.
- Directed graphs follow outgoing edges only. Undirected graphs store edges
  symmetrically, so outgoing edges represent all adjacent nodes.
- Neighbor order follows map key iteration order and should be treated as
  unspecified.

## Complexity

BFS and DFS are `O(V + E)` over the reachable portion of the graph. Because this
is an inductive/persistent representation, traversals allocate shrunken graph
versions as they progress; use adjacency-based `Yog.Traversal.Walk` for raw
traversal throughput on large production graphs.

## 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 or node IDs.

Returns a list of node contexts in the order they were visited. Missing start
nodes are skipped.

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 or node IDs.

Returns a list of node contexts in the order they were visited. Missing start
nodes are skipped.

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]

# `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).

## 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 (DFS 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 or node IDs.

This is a thin wrapper around `dfs/2`, returning IDs instead of contexts.

## 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*