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

Unified facade for pathfinding algorithms.

This module provides a single entry point for all pathfinding and distance
computation algorithms. Each function delegates to a specialized submodule.

## Submodules

- `Yog.Pathfinding.Dijkstra` — Single-source shortest paths (non-negative weights)
- `Yog.Pathfinding.AStar` — Heuristic-guided shortest paths
- `Yog.Pathfinding.BellmanFord` — Shortest paths with negative weights, cycle detection
- `Yog.Pathfinding.Bidirectional` — Bidirectional BFS/Dijkstra for faster convergence
- `Yog.Pathfinding.FloydWarshall` — All-pairs shortest paths (dense graphs)
- `Yog.Pathfinding.Johnson` — All-pairs shortest paths (sparse graphs, negative weights)
- `Yog.Pathfinding.Matrix` — Distance matrix computation
- `Yog.Pathfinding.Path` — Path struct for representing results

## All-Pairs Functions

- `all_pairs_shortest_paths_unweighted/1` — Parallel BFS for unweighted graphs
- `floyd_warshall/1` — Floyd-Warshall for weighted graphs
- `johnson/5` — Johnson's algorithm for sparse graphs with negative weights
- `distance_matrix/6` — Distance matrix between specific points of interest

## Special Path Types

- `widest_path/3` — Maximum capacity path (bottleneck routing)
- `k_shortest_paths/5` — Yen's algorithm for k shortest loopless paths

## Algorithm Selection Guide

| Algorithm | Use When | Time Complexity |
|-----------|----------|-----------------|
| **Dijkstra** | Non-negative weights, single pair | O((V+E) log V) |
| **A*** | Non-negative weights + good heuristic | O((V+E) log V) |
| **Bellman-Ford** | Negative weights OR cycle detection | O(VE) |
| **Bidirectional** | Large graphs, unweighted or uniform weights | O((V+E) log V) |
| **All-Pairs Unweighted** | All-pairs, unweighted graphs (parallel) | O(V² + VE) |
| **Floyd-Warshall** | All-pairs, dense weighted graphs | O(V³) |
| **Johnson's** | All-pairs, sparse graphs, negative weights | O(V² log V + VE) |
| **Widest Path** | Maximize minimum edge capacity | O((V+E) log V) |

# `a_star`

Finds the shortest path using A* search with a heuristic.

## Options
  * `:in` - The graph to search
  * `:from` - Starting node ID
  * `:to` - Target node ID
  * `:zero` - Zero value for weights (default: 0)
  * `:add` - Addition function for weights (default: &Kernel.+/2)
  * `:compare` - Comparison function for weights (default: &Yog.Utils.compare/2)
  * `:heuristic` - Heuristic function `(node, goal) -> weight` (Mandatory)

# `all_pairs_shortest_paths_unweighted`

```elixir
@spec all_pairs_shortest_paths_unweighted(Yog.graph()) :: %{
  required(Yog.node_id()) => %{required(Yog.node_id()) => non_neg_integer()}
}
```

Computes all-pairs shortest paths in an unweighted graph using parallel BFS.

Returns a map of `%{source => %{target => distance}}` where distances are the
number of edges in the shortest path.

## Parameters

- `graph` - The unweighted graph to analyze

## Returns

- A map from source nodes to distance maps: `%{source => %{target => distance}}`
- Each inner map contains distances from the source to all reachable nodes
- Distance from a node to itself is always 0
- Unreachable nodes have `nil` distance (note: this differs from `floyd_warshall/1`
  which omits unreachable pairs entirely)

## Complexity

- **Time:** O(V × (V + E)) = O(V² + VE) overall, but parallelized across CPU cores
- **Space:** O(V²) for the result matrix

## When to Use

- **Unweighted graphs only** - For weighted graphs, use `floyd_warshall/1` or `johnson/1`
- **All-pairs needed** - When you need distances between all node pairs
- **Large graphs** - Parallelization makes this efficient on multi-core systems

## Algorithm

1. For each node, run BFS to compute distances to all other nodes
2. BFS from each source is parallelized using `Task.async_stream`
3. Results are aggregated into a nested map structure

## Examples

    # Simple path graph: 1-2-3-4
    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_node(4, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    ...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
    iex> distances = Yog.Pathfinding.all_pairs_shortest_paths_unweighted(graph)
    iex> distances[1][4]
    3
    iex> distances[2][4]
    2
    iex> distances[1][1]
    0

    # Directed graph with unreachable nodes
    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> distances = Yog.Pathfinding.all_pairs_shortest_paths_unweighted(graph)
    iex> distances[1][2]
    1
    iex> distances[3][1]
    nil

## See Also

- `floyd_warshall/1` - For weighted graphs (all-pairs)
- `johnson/5` - For sparse weighted graphs with negative weights
- `distance_matrix/6` - For distances between specific points of interest only

# `astar`

Alias for `a_star/1`.

# `bellman_ford`

Finds the shortest path using Bellman-Ford (supports negative weights).

Returns `{:error, :negative_cycle}` if a negative cycle is reachable.

## Options
  * `:in` - The graph to search
  * `:from` - Starting node ID
  * `:to` - Target node ID
  * `:zero` - Identity value for weights (default: 0)
  * `:add` - Addition function (default: &Kernel.+/2)
  * `:compare` - Comparison function (default: &Yog.Utils.compare/2)

# `bidirectional`

Finds the shortest path using bidirectional Dijkstra.

## Options
  * `:in` - The graph to search
  * `:from` - Starting node ID
  * `:to` - Target node ID
  * `:zero` - Zero value for weights (default: 0)
  * `:add` - Addition function (default: &Kernel.+/2)
  * `:compare` - Comparison function (default: &Yog.Utils.compare/2)

## Example

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "A")
    ...>   |> Yog.add_node(2, "B")
    ...>   |> Yog.add_node(3, "C")
    ...>   |> Yog.add_edges([{1, 2, 5}, {2, 3, 3}, {1, 3, 10}])
    iex> {:ok, path} = Yog.Pathfinding.bidirectional(
    ...>   in: graph, from: 1, to: 3
    ...> )
    iex> path.weight
    8

# `bidirectional_unweighted`

Finds the shortest path using bidirectional BFS (unweighted graphs).

## Options
  * `:in` - The graph to search
  * `:from` - Starting node ID
  * `:to` - Target node ID

# `chinese_postman`

Solves the Chinese Postman Problem (Route Inspection) for undirected graphs.

Finds the shortest closed walk that traverses every edge at least once.

## Example

    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
    iex> {:ok, _path, weight} = Yog.Pathfinding.chinese_postman(graph)
    iex> weight
    4

# `detect_negative_cycle?`

Detects negative cycles in the graph via Floyd-Warshall.

# `distance_matrix`

Computes a distance matrix between specified points of interest.

Uses Dijkstra from each point to compute pairwise distances.

# `floyd_warshall`

Computes all-pairs shortest paths using Floyd-Warshall.

## Options
  * `:in` - The graph
  * `:zero` - Identity element (default: 0)
  * `:add` - Addition function (default: &Kernel.+/2)
  * `:compare` - Comparison function (default: &Yog.Utils.compare/2)

# `johnson`

Computes all-pairs shortest paths using Johnson's algorithm.

More efficient than Floyd-Warshall for sparse graphs. Supports negative
edge weights (but not negative cycles).

# `k_shortest_paths`

```elixir
@spec k_shortest_paths(
  Yog.Graph.t(),
  Yog.node_id(),
  Yog.node_id(),
  pos_integer(),
  keyword()
) ::
  {:ok, [Path.t()]} | :error
```

Finds the k shortest loopless paths from `source` to `target` using Yen's algorithm.

## Options

- `:with` - Function to extract/transform edge weight
- `:zero` - Zero value for weights (default: `0`)
- `:add` - Addition function for weights (default: `&Kernel.+/2`)
- `:compare` - Comparison function for weights (default: `&Yog.Utils.compare/2`)

## Example

    iex> graph = Yog.directed() |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil) |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {1, 3, 2}])
    iex> {:ok, paths} = Yog.Pathfinding.k_shortest_paths(graph, 1, 3, 2)
    iex> length(paths)
    2

# `lca`

```elixir
@spec lca(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, Yog.node_id()} | {:error, :node_not_found}
```

Returns the lowest common ancestor of two nodes.

## Returns

  * `{:ok, node_id}` - The LCA node
  * `{:error, :node_not_found}` - One or both nodes not in the tree

# `lca_preprocess`

```elixir
@spec lca_preprocess(Yog.Graph.t(), Yog.node_id()) ::
  {:ok, Yog.Pathfinding.LCA.State.t()} | {:error, :root_not_found | :not_a_tree}
```

Preprocesses a tree for LCA queries using binary lifting.

## Parameters

  * `graph` - The tree graph
  * `root` - The root node for the tree

## Returns

  * `{:ok, LCA.State.t()}` - Preprocessed state for LCA queries
  * `{:error, :root_not_found}` - Root node not in graph
  * `{:error, :not_a_tree}` - Graph contains a cycle or is disconnected

## Example

    iex> tree =
    ...>   Yog.undirected()
    ...>   |> Yog.add_node(1, nil)
    ...>   |> Yog.add_node(2, nil)
    ...>   |> Yog.add_node(3, nil)
    ...>   |> Yog.add_edges!([{1, 2, 1}, {1, 3, 1}])
    iex> {:ok, state} = Yog.Pathfinding.lca_preprocess(tree, 1)
    iex> Yog.Pathfinding.lca(state, 2, 3)
    {:ok, 1}

# `shortest_path`

Finds the shortest path between two nodes using Dijkstra's algorithm.

## Options
  * `:in` - The graph to search
  * `:from` - Starting node ID
  * `:to` - Target node ID
  * `:zero` - Zero value for weights (default: 0)
  * `:add` - Addition function for weights (default: &Kernel.+/2)
  * `:compare` - Comparison function for weights (:lt, :eq, :gt) (default: &Yog.Utils.compare/2)

## Example

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "A")
    ...>   |> Yog.add_node(2, "B")
    ...>   |> Yog.add_node(3, "C")
    ...>   |> Yog.add_edges([{1, 2, 5}, {2, 3, 3}, {1, 3, 10}])
    iex> {:ok, path} = Yog.Pathfinding.shortest_path(
    ...>   in: graph, from: 1, to: 3
    ...> )
    iex> path.weight
    8

# `shortest_path_unweighted`

```elixir
@spec shortest_path_unweighted(Yog.graph(), Yog.node_id(), Yog.node_id()) ::
  {:ok, [Yog.node_id()]} | {:error, :no_path}
```

Finds the shortest path between two nodes in an unweighted graph using BFS.

This is significantly faster than Dijkstra for unweighted graphs because:
1. Uses BFS instead of Dijkstra's algorithm (no heap overhead)
2. Stops as soon as the target is found (early termination)
3. Works for both directed and undirected graphs
4. Handles nil weights or uniform weights (e.g., all weight=1)

## Parameters

  * `graph` - The unweighted graph (directed or undirected)
  * `source` - Starting node ID
  * `target` - Target node ID

## Returns

  * `{:ok, [node_id]}` - List of nodes representing the shortest path from source to target
  * `{:ok, [source]}` - When source == target
  * `{:error, :no_path}` - When target is unreachable from source

## Complexity

  * **Time:** O(V + E) worst case, but typically much less due to early termination
  * **Space:** O(V) for the queue and visited set

## Examples

    # Simple path: 1-2-3
    iex> graph = Yog.undirected()
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> Yog.Pathfinding.shortest_path_unweighted(graph, 1, 3)
    {:ok, [1, 2, 3]}

    # Same source and target
    iex> graph = Yog.undirected()
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> Yog.Pathfinding.shortest_path_unweighted(graph, 1, 1)
    {:ok, [1]}

    # No path exists
    iex> graph = Yog.directed()
    ...> |> Yog.add_node(:a, nil)
    ...> |> Yog.add_node(:b, nil)
    iex> Yog.Pathfinding.shortest_path_unweighted(graph, :a, :b)
    {:error, :no_path}

    # Directed graph - respects edge direction
    iex> graph = Yog.directed()
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> Yog.Pathfinding.shortest_path_unweighted(graph, 1, 3)
    {:ok, [1, 2, 3]}
    iex> Yog.Pathfinding.shortest_path_unweighted(graph, 3, 1)
    {:error, :no_path}

## When to Use

  * **Unweighted graphs** - All edges have the same cost (or nil weight)
  * **Single pair query** - When you only need one source-target path
  * **Performance critical** - Faster than Dijkstra for unweighted graphs

## See Also

  * `shortest_path/1` - Dijkstra for weighted graphs
  * `bidirectional_unweighted/1` - Bidirectional BFS (potentially faster for large graphs)
  * `all_pairs_shortest_paths_unweighted/1` - When you need all-pairs distances

# `single_source_distances`

Single-source distances from a node to all reachable nodes (Dijkstra).

## Options
  * `:in` - The graph
  * `:from` - Source node
  * `:zero` - Zero value (default: 0)
  * `:add` - Addition function (default: &Kernel.+/2)
  * `:compare` - Comparison function (default: &Yog.Utils.compare/2)

# `tree_distance`

```elixir
@spec tree_distance(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, non_neg_integer()} | {:error, :node_not_found}
```

Calculates the tree distance (number of edges) between two nodes.

## Returns

  * `{:ok, distance}` - Number of edges between the nodes
  * `{:error, :node_not_found}` - One or both nodes not in the tree

# `widest_path`

```elixir
@spec widest_path(Yog.Graph.t(), source :: Yog.node_id(), target :: Yog.node_id()) ::
  {:ok, Path.t()} | :error
```

Finds the widest path (maximum capacity path) between two nodes.

The widest path maximizes the minimum edge weight along the path (the bottleneck).
This is useful for network bandwidth routing, finding reliable paths, and
max-min fair allocation problems.

## Parameters

  * `graph` - The graph to search
  * `source` - Starting node ID
  * `target` - Target node ID

## Returns

  * `{:ok, path}` - A `Path.t()` struct with maximum bottleneck capacity
  * `:error` - If no path exists between the nodes

## Example

    # Network with bandwidths
    graph = Yog.directed()
    |> Yog.add_edges!([
      {:a, :b, 100},  # 100 Mbps link
      {:a, :c, 50},   # 50 Mbps link
      {:b, :d, 80},   # 80 Mbps link
      {:c, :d, 200}   # 200 Mbps link
    ])

    {:ok, path} = Yog.Pathfinding.widest_path(graph, :a, :d)
    # Path via b has bottleneck min(100, 80) = 80
    # Path via c has bottleneck min(50, 200) = 50
    # So widest path is a->b->d with capacity 80

## Algorithm

This is a modification of Dijkstra's algorithm:
- Standard Dijkstra: `distance[v] = min(distance[u] + weight(u,v))`
- Widest Path: `capacity[v] = max(capacity[v], min(capacity[u], weight(u,v)))`

The path's "width" is the minimum edge weight along it. We want to maximize
this minimum (the bottleneck capacity).

## Complexity

- **Time:** O((V + E) log V)
- **Space:** O(V)

## See Also

- `shortest_path/1` - Standard Dijkstra for shortest paths
- Wikipedia: https://en.wikipedia.org/wiki/Widest_path_problem

---

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