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

Graph walking algorithms — BFS, DFS, Best-First, and Random traversals.

This module provides a unified API for exploring graphs starting from a given node.
It supports both standard discovery (BFS, DFS) and informed discovery where the
next nodes are prioritized based on weights, heuristics, or randomness.

## Discovery Visualization

Traversals like BFS explore a graph in layers, prioritizing nodes based on their distance from the source.

<div class="graphviz">
digraph G {
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];

  Root [label="Root", color="#6366f1", penwidth=2.5, style=bold];
  
  // Discovery steps
  Root -> A [label="1"]; Root -> B [label="2"];
  A -> C [label="3"]; A -> D [label="4"];
  B -> E [label="5"];
  
  // BFS Layers
  subgraph cluster_l1 {
    label="Layer 1 (dist=1)"; color="#6366f1"; style=rounded;
    A; B;
  }

  subgraph cluster_l2 {
    label="Layer 2 (dist=2)"; color="#f43f5e"; style=rounded;
    C; D; E;
  }
}
</div>

    iex> alias Yog.Traversal.Walk
    iex> graph = Yog.from_edges(:directed, [
    ...>   {"Root", "A", 1}, {"Root", "B", 1},
    ...>   {"A", "C", 1}, {"A", "D", 1}, {"B", "E", 1}
    ...> ])
    iex> Walk.walk(in: graph, from: "Root", using: :breadth_first)
    ["Root", "A", "B", "C", "D", "E"]

# `order`

```elixir
@type order() :: :breadth_first | :depth_first | :best_first | :random
```

# `priority_fn`

```elixir
@type priority_fn() :: (Yog.node_id(), number(), walk_metadata() -&gt; number())
```

# `walk_control`

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

# `walk_metadata`

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

# `find_path`

```elixir
@spec find_path(Yog.graph(), Yog.node_id(), Yog.node_id()) :: [Yog.node_id()] | nil
```

Finds the shortest path between two nodes using BFS.

# `fold_walk`

```elixir
@spec fold_walk(keyword()) :: any()
```

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

The folder function receives `(accumulator, node_id, metadata)` and should
return `{control, new_accumulator}`.

## Metadata
The metadata map contains:
- `:depth` - Distance from the starting node.
- `:parent` - The node ID that led to this node.

## Control Signals
- `:continue` - Continue traversal normally.
- `:stop` - Do not explore successors of the current node, but continue with the rest of the frontier.
- `:halt` - Stop the entire traversal immediately.

# `fold_walk`

```elixir
@spec fold_walk(
  Yog.graph(),
  Yog.node_id(),
  order(),
  acc,
  (acc, Yog.node_id(), walk_metadata() -&gt; {walk_control(), acc})
) :: acc
when acc: var
```

# `random_walk`

```elixir
@spec random_walk(Yog.graph(), Yog.node_id(), integer()) :: [Yog.node_id()]
```

Performs a random walk of fixed length from the given starting node.

Unlike discovery traversals (BFS/DFS), a random walk does not keep track
of visited nodes and may cross the same node or edge multiple times.

## Parameters
- `graph`: The graph to walk.
- `from`: The starting node ID.
- `steps`: The number of jumps/edges to transition (path length in edges).

## Examples

    iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 1, nil) |> Yog.add_edge_ensure(2, 1, 1, nil)
    iex> path = Yog.Traversal.Walk.random_walk(graph, 1, 3)
    iex> length(path)
    4

# `reachable?`

```elixir
@spec reachable?(Yog.graph(), Yog.node_id(), Yog.node_id()) :: boolean()
```

Checks if there is a path between two nodes.

# `walk`

```elixir
@spec walk(keyword()) :: [Yog.node_id()]
```

Walks the graph starting from the given node, visiting all reachable nodes.

## Options

- `:from` - Starting node ID
- `:in` - The graph to traverse
- `:using` - Traversal order. Options:
  - `:breadth_first` (BFS)
  - `:depth_first` (DFS)
  - `:best_first` - Prioritizes discovery based on a `:priority` function.
  - `:random` - Randomizes discovery order.
- `:priority` - Required if `:using` is `:best_first`. A function taking `(node_id, weight, meta)`.

## Examples

    # Simple BFS walk
    iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 1, nil)
    iex> Yog.Traversal.Walk.walk(in: graph, from: 1, using: :breadth_first)
    [1, 2]

    # Greedy walk using edge weights (lowest weight first)
    iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10, nil) |> Yog.add_edge_ensure(1, 3, 5, nil)
    iex> Yog.Traversal.Walk.walk(in: graph, from: 1, using: :best_first, priority: fn _, w, _ -> w end)
    [1, 3, 2]

# `walk`

```elixir
@spec walk(Yog.graph(), Yog.node_id(), order()) :: [Yog.node_id()]
```

# `walk_until`

```elixir
@spec walk_until(keyword()) :: [Yog.node_id()]
```

Walks the graph but stops early when a condition is met.

# `walk_until`

```elixir
@spec walk_until(Yog.graph(), Yog.node_id(), order(), (Yog.node_id() -&gt; boolean())) ::
  [Yog.node_id()]
```

---

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