# `Yog.Flow.NetworkSimplex`
[🔗](https://github.com/code-shoily/yog_ex/blob/v1.0.0/lib/yog/flow/network_simplex.ex#L1)

Minimum cost flow algorithm using the Network Simplex method.

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

The Network Simplex algorithm is a specialized primal simplex method for network flows.
In practice, it runs extremely fast (polynomial-like time) and handles arbitrary flows/demands.
Unlike pseudo-polynomial algorithms (like Successive Shortest Path), its performance is
independent of the total flow capacity (F), making it suitable for large networks.

## 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
- **Reduced Costs**: Modified costs ensuring optimality conditions
- **Spanning Tree**: Basis for the simplex method on networks

## Implementation Notes

- Internal state is stored in maps keyed by integer indices (nodes and edges).
  For very dense graphs, switching to Erlang `:array` could reduce memory and
  lookup overhead, but it would be a sizeable refactor.
- The pivot step uses `Enum.find_index/2` to locate the entering and leaving
  edges inside the fundamental cycle. Each call is O(cycle length); building a
  position map would speed up hot paths on large instances.
- The unboundedness test checks whether any original edge flow is at least
  half of the artificial big-M cost (`faux_inf / 2`). This 2x buffer is a
  defensive choice; NetworkX uses `flow >= faux_inf` directly.
- Zero-capacity edges are filtered out before solving. Self-loops are kept and
  treated as non-tree edges, so finite negative-cost self-loops are saturated
  when beneficial.

# `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}`.

Note: the name `flow_map` is historical; the type is a list of flow tuples,
not a map.

# `min_cost_flow_error`

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

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
- `:unbounded` - The network contains a negative-cost cycle with infinite capacity
- `:timeout` - The algorithm did not converge within the allowed number of pivots

# `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 Network Simplex 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
- `{:error, :unbounded}` - Negative cycle with infinite capacity found
- `{:error, :timeout}` - Maximum pivot limit exceeded

## Examples

```elixir
graph = Yog.directed()
  |> Yog.add_node(1, {-20, nil})
  |> Yog.add_node(2, {10, nil})
  |> Yog.add_node(3, {10, nil})
  |> Yog.add_edges([
    {1, 2, {10, 3}},
    {1, 3, {15, 2}},
    {2, 3, {5, 1}}
  ])

get_demand = fn {d, _} -> d end
get_capacity = fn {c, _} -> c end
get_cost = fn {_, c} -> c end

{:ok, result} = Yog.Flow.NetworkSimplex.min_cost_flow(graph, get_demand, get_capacity, get_cost)
```

---

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