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

Disjoint shortest path algorithms.

This module implements algorithms for finding multiple path-disjoint or
edge-disjoint routes of minimum total cost between a source and a target.

## Algorithms

| Algorithm | Function | Purpose | Complexity |
|-----------|----------|---------|------------|
| Suurballe's | `suurballe/4` | Finds two edge-disjoint shortest paths | O((V + E) log V) |

## References

- Suurballe, J. W. (1974). "Disjoint paths in a network". Networks. 4 (2): 125–145.

# `suurballe_result`

```elixir
@type suurballe_result() :: {:ok, [Yog.Pathfinding.Path.t()]} | :error
```

Result type for suurballe query

# `suurballe`

```elixir
@spec suurballe(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  weight,
  (weight, weight -> weight),
  (weight, weight -> :lt | :eq | :gt),
  (weight, weight -> weight),
  (any() -> weight)
) :: suurballe_result()
when weight: var
```

Finds two edge-disjoint paths of minimum total weight between `from` and `to`.

Uses Suurballe's algorithm, which executes Dijkstra's algorithm twice:
1. Computes the first shortest path $P_1$ and vertex potentials.
2. Modifies the edge weights to non-negative reduced costs, reverses the direction
   of the edges in $P_1$, and sets their weights to $0$.
3. Computes the second shortest path $P_2$ in the modified graph.
4. Cancels overlapping/antiparallel edges to produce the final two disjoint paths.

## Parameters

  * `graph` - The input graph (directed or undirected)
  * `from` - Starting source node
  * `to` - Target destination node
  * `zero` - Zero value for the weight type (default: `0`)
  * `add` - Addition function for weights (default: `&Kernel.+/2`)
  * `compare` - Comparison function for weights (default: `&Yog.Utils.compare/2`)
  * `subtract` - Subtraction function for weights (default: `&Kernel.-/2`)
  * `weight_fn` - Function extracting a numeric weight from edge data (default: checks for nil, then returns 1 or edge value)

## Returns

  * `{:ok, [path1, path2]}` - Two disjoint paths sorted by weight/nodes on success
  * `:error` - Less than two edge-disjoint paths exist between `from` and `to`

## Examples

    iex> alias Yog.Pathfinding.Disjoint
    iex> graph = Yog.from_edges(:directed, [
    ...>   {1, 2, 1}, {2, 4, 1},
    ...>   {1, 3, 1}, {3, 4, 1},
    ...>   {2, 3, 0.5}
    ...> ])
    iex> {:ok, [p1, p2]} = Disjoint.suurballe(graph, 1, 4)
    iex> p1.nodes
    [1, 2, 4]
    iex> p2.nodes
    [1, 3, 4]

---

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