Yog.Flow.SuccessiveShortestPath (YogEx v0.97.0)

Minimum cost flow algorithms for network flow optimization.

This module solves the 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	`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

Summary

Types

flow_map()

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

min_cost_flow_error()

Errors that can occur during minimum cost flow optimization.

min_cost_flow_result()

Result of a successful minimum cost flow computation.

Functions

min_cost_flow(graph, get_demand, get_capacity, get_cost)

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

Types

flow_map()

@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()

@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()

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

Result of a successful minimum cost flow computation.

Functions

min_cost_flow(graph, get_demand, get_capacity, get_cost)

@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