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

Traversal operations for multigraphs.

Unlike simple graphs, multigraph traversals use edge IDs to correctly
handle parallel edges — each **edge** is traversed at most once, but a
node may be reached via multiple edges.

# `walk_control`

```elixir
@type walk_control() :: :continue | :stop | :halt
```

Control flow for fold_walk traversal

# `walk_metadata`

```elixir
@type walk_metadata() :: %{
  depth: integer(),
  parent: {Yog.node_id(), Yog.Multi.Model.edge_id()} | nil
}
```

Metadata provided during fold_walk traversal

# `bfs`

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

Performs a Breadth-First Search from `source`, returning visited node IDs
in BFS order.

Unlike simple-graph BFS, this traversal uses edge IDs to correctly handle
parallel edges — each **edge** is traversed at most once, but a node may be
reached via multiple edges (the first visit wins for ordering purposes).

## Time Complexity

O(V + E)

## Examples

    nodes = Yog.Multi.Traversal.bfs(multi, :a)
    #=> [:a, :b, :c, :d]

# `dfs`

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

Performs a Depth-First Search from `source`, returning visited node IDs
in DFS pre-order.

## Time Complexity

O(V + E)

## Examples

    nodes = Yog.Multi.Traversal.dfs(multi, :a)
    #=> [:a, :b, :d, :c]

# `fold_walk`

```elixir
@spec fold_walk(
  Yog.Multi.Model.t(),
  Yog.node_id(),
  acc,
  (acc, Yog.node_id(), walk_metadata() -> {walk_control(), acc})
) :: acc
when acc: var
```

Folds over nodes during multigraph traversal, accumulating state with metadata.

This function combines traversal with state accumulation, providing metadata
about each visited node including which specific edge was used to reach it.
The folder function controls the traversal flow:

- `:continue` - Explore successors of the current node normally
- `:stop` - Skip successors of this node, but continue with other queued nodes
- `:halt` - Stop the entire traversal immediately and return the accumulator

For multigraphs, the metadata includes the specific `EdgeId` used to reach
each node, which is important when parallel edges exist.

## Time Complexity

O(V + E)

## Examples

    # Build a parent map tracking which edge led to each node
    parents = Yog.Multi.Traversal.fold_walk(multi, :a, %{}, fn acc, node_id, meta ->
      new_acc = case meta.parent do
        {parent_node, edge_id} -> Map.put(acc, node_id, {parent_node, edge_id})
        nil -> acc
      end
      {:continue, new_acc}
    end)

    # Find all nodes within distance 3
    nearby = Yog.Multi.Traversal.fold_walk(multi, :a, [], fn acc, node_id, meta ->
      if meta.depth <= 3 do
        {:continue, [node_id | acc]}
      else
        {:stop, acc}
      end
    end)

---

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