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

Minimum cost flow algorithms for network flow optimization.

This module solves the [minimum cost flow problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem):
find the cheapest way to send a given amount of flow through a network where
edges have both capacities and costs per unit of flow.

## Algorithm

| Algorithm | Function | Complexity | Best For |
|-----------|----------|------------|----------|
| [Successive Shortest Path](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem) | `min_cost_flow/4` | O(F · (E + V log V)) | Small to medium networks |

The implementation uses the Successive Shortest Path algorithm with Dijkstra and
node potentials (reduced costs). One initial Bellman-Ford pass computes valid
potentials; every subsequent shortest-path query runs Dijkstra using
`Yog.PairingHeap` on non-negative reduced costs.

## Key Concepts

- **Minimum Cost Flow**: Route flow to satisfy demands at minimum total cost
- **Node Demands**: Supply nodes (negative demand) and demand nodes (positive demand)
- **Edge Costs**: Price per unit of flow on each edge

## Problem Formulation

Given:
- Graph G = (V, E) with capacities u(e) and costs c(e)
- Node demands b(v) where Σb(v) = 0 (conservation)

Find flow f(e) that:
- Minimizes: Σ c(e) × f(e)  (total cost)
- Subject to: 0 ≤ f(e) ≤ u(e)  (capacity constraints)
- And: flow conservation at each node

## Use Cases

- **Transportation planning**: Minimize shipping costs with vehicle capacities
- **Supply chain**: Optimize distribution from warehouses to retailers
- **Telecommunications**: Route calls at minimum cost with link capacities

## Example

    # Store demand/capacity/cost data in node and edge data tuples
    graph =
      Yog.directed()
      # Node data: {demand, nil} where negative=supply, positive=demand
      |> Yog.add_node(1, {-20, nil})   # warehouse: supply 20
      |> Yog.add_node(2, {10, nil})    # store_a: demand 10
      |> Yog.add_node(3, {10, nil})    # store_b: demand 10
      # Edge data: {capacity, cost_per_unit}
      |> Yog.add_edges([
        {1, 2, {10, 3}},   # capacity 10, cost $3
        {1, 3, {15, 2}},   # capacity 15, cost $2
        {2, 3, {5, 1}}     # capacity 5, cost $1
      ])

    # Extract demand from node data
    get_demand = fn {d, _} -> d end

    # Extract capacity from edge data
    get_capacity = fn {c, _} -> c end

    # Extract cost from edge data
    get_cost = fn {_, c} -> c end

    case Yog.Flow.SuccessiveShortestPath.min_cost_flow(graph, get_demand, get_capacity, get_cost) do
      {:ok, result} ->
        IO.puts("Min cost: #{result.cost}")
        IO.inspect(result.flow)

      {:error, :infeasible} ->
        IO.puts("Cannot satisfy demands with given capacities")

      {:error, :unbalanced_demands} ->
        IO.puts("Total demand does not equal total supply")
    end

## References

- [Wikipedia: Minimum-Cost Flow Problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem)
- [CP-Algorithms: Min-Cost Flow](https://cp-algorithms.com/graph/min_cost_flow.html)

# `flow_map`

```elixir
@type flow_map() :: [{Yog.node_id(), Yog.node_id(), integer()}]
```

A flow vector assigning an amount of flow to each edge.

Each tuple is `{from_node, to_node, flow_amount}`.

# `min_cost_flow_error`

```elixir
@type min_cost_flow_error() :: :infeasible | :unbalanced_demands
```

Errors that can occur during minimum cost flow optimization.

- `:infeasible` - The demands cannot be satisfied given the edge capacities
- `:unbalanced_demands` - The sum of all node demands does not equal 0

# `min_cost_flow_result`

```elixir
@type min_cost_flow_result() :: %{cost: integer(), flow: flow_map()}
```

Result of a successful minimum cost flow computation.

# `min_cost_flow`

```elixir
@spec min_cost_flow(Yog.graph(), (any() -> integer()), (any() -> integer()), (any() ->
                                                                          integer())) ::
  {:ok, min_cost_flow_result()} | {:error, min_cost_flow_error()}
```

Solves the minimum cost flow problem using the Successive Shortest Path algorithm.

Given a network with edge capacities and costs, and node demands/supplies,
finds the flow assignment that satisfies all demands at minimum total cost.

## Parameters

- `graph` - The flow network (directed graph with edge data representing capacities)
- `get_demand` - Function `(node_data) -> demand` where negative = supply, positive = demand
- `get_capacity` - Function `(edge_data) -> capacity`
- `get_cost` - Function `(edge_data) -> cost_per_unit`

Note: These functions take the node/edge **data** stored in the graph, not node IDs.

## Returns

- `{:ok, result}` - Successful computation with `%{cost: integer(), flow: flow_map()}`
- `{:error, :infeasible}` - Demands cannot be satisfied
- `{:error, :unbalanced_demands}` - Total supply ≠ total demand

## Examples

    iex> graph = Yog.directed()
    ...>   |> Yog.add_node(1, "s")
    ...>   |> Yog.add_node(2, "t")
    ...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
    iex> get_demand = fn
    ...>   "s" -> -5   # supply 5
    ...>   "t" -> 5    # demand 5
    ...>   _ -> 0
    ...> end
    iex> get_capacity = fn w -> w end
    iex> get_cost = fn _ -> 1 end
    iex> result = Yog.Flow.SuccessiveShortestPath.min_cost_flow(
    ...>   graph, get_demand, get_capacity, get_cost
    ...> )
    iex> match?({:ok, _} , result) or match?({:error, _}, result)
    true

## Notes

- All demands must sum to 0 (conservation of flow)
- Costs and capacities must be integers

---

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