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

Maximum flow algorithms and min-cut extraction for network flow problems.

This module solves the [maximum flow problem](https://en.wikipedia.org/wiki/Maximum_flow_problem):
given a flow network with capacities on edges, find the maximum flow from a source
node to a sink node. By the [max-flow min-cut theorem](https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem),
this equals the capacity of the minimum cut separating source from sink.

## Algorithm

| Algorithm | Function | Complexity | Best For |
|-----------|----------|------------|----------|
| [Edmonds-Karp](https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm) | `edmonds_karp/8` | O(VE²) | General networks, guaranteed polynomial time |
| [Dinic](https://en.wikipedia.org/wiki/Dinic%27s_algorithm) | `dinic/8` | O(V²E) | Dense networks, unit capacities O(E√V) |
| [Push-Relabel](https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm) | `push_relabel/8` | O(V²√E)–O(V³) | Large/dense networks |

## Key Concepts

- **Flow Network**: Directed graph where edges have capacities (max flow allowed)
- **Source**: Node where flow originates (no incoming flow in net balance)
- **Sink**: Node where flow terminates (no outgoing flow in net balance)
- **Residual Graph**: Shows remaining capacity after current flow assignment
- **Augmenting Path**: Path from source to sink with available capacity
- **Minimum Cut**: Partition separating source from sink with minimum total capacity
- **Level Graph**: BFS layering of nodes used by Dinic's algorithm

## Use Cases

- **Network routing**: Maximize data throughput in communication networks
- **Transportation**: Optimize goods flow through logistics networks
- **Bipartite matching**: Convert to flow problem for max cardinality matching
- **Image segmentation**: Min-cut/max-flow for foreground/background separation
- **Project selection**: Maximize profit with prerequisite constraints

## Example

    graph =
      Yog.directed()
      |> Yog.add_node(1, "source")
      |> Yog.add_node(2, "A")
      |> Yog.add_node(3, "B")
      |> Yog.add_node(4, "sink")
      |> Yog.add_edges([
        {1, 2, 10},
        {1, 3, 5},
        {2, 3, 15},
        {2, 4, 10},
        {3, 4, 10}
      ])

## Example: Maximum Flow

<div class="graphviz">
digraph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];
  S [label="S"]; A [label="A"]; B [label="B"]; T [label="T"];

  S -> A [label="10", color="#6366f1", penwidth=2];
  S -> B [label="10", color="#6366f1", penwidth=2];
  A -> B [label="2", color="#6366f1", penwidth=2];
  A -> T [label="4", color="#6366f1", penwidth=2];
  B -> T [label="10", color="#6366f1", penwidth=2];
}
</div>

    iex> alias Yog.Flow.MaxFlow
    iex> graph = Yog.from_edges(:directed, [
    ...>   {"S", "A", 10}, {"S", "B", 10}, {"A", "B", 2},
    ...>   {"A", "T", 4}, {"B", "T", 10}
    ...> ])
    iex> result = MaxFlow.calculate(graph, "S", "T")
    iex> result.max_flow
    14

    result = Yog.Flow.MaxFlow.calculate(graph, 1, 4)
    # => %MaxFlowResult{max_flow: 15, residual_graph: ..., source: 1, sink: 4}

## Example: Dinic's Algorithm

Dinic's algorithm builds a level graph via BFS and pushes blocking flows
via DFS, making it efficient for dense networks.

<div class="graphviz">
digraph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];
  S [label="S"]; A [label="A"]; B [label="B"]; C [label="C"]; T [label="T"];

  { rank=same; S; }
  { rank=same; A; B; }
  { rank=same; C; }
  { rank=same; T; }

  S -> A [label="10", color="#6366f1", penwidth=2];
  S -> B [label="5", color="#6366f1", penwidth=2];
  A -> C [label="8", color="#6366f1", penwidth=2];
  B -> C [label="3", color="#6366f1", penwidth=2];
  C -> T [label="7", color="#6366f1", penwidth=2];
}
</div>

    iex> graph = Yog.from_edges(:directed, [
    ...>   {"S", "A", 10}, {"S", "B", 5}, {"A", "C", 8},
    ...>   {"B", "C", 3}, {"C", "T", 7}
    ...> ])
    iex> result = Yog.Flow.MaxFlow.dinic(graph, "S", "T")
    iex> result.max_flow
    7

## References

- [Wikipedia: Maximum Flow Problem](https://en.wikipedia.org/wiki/Maximum_flow_problem)
- [Wikipedia: Edmonds-Karp Algorithm](https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm)
- [Wikipedia: Dinic's Algorithm](https://en.wikipedia.org/wiki/Dinic%27s_algorithm)
- [Wikipedia: Max-Flow Min-Cut Theorem](https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem)

# `algorithm`

```elixir
@type algorithm() :: :edmonds_karp | :dinic | :push_relabel
```

# `max_flow_result`

```elixir
@type max_flow_result() :: Yog.Flow.MaxFlowResult.t()
```

Result of a max flow computation.

Contains both the maximum flow value and information needed to extract
the minimum cut.

# `min_cut`

```elixir
@type min_cut() :: Yog.Flow.MinCutResult.t()
```

Represents a minimum cut in the network.

A cut partitions the nodes into two sets: those reachable from the source
in the residual graph (source_side) and the rest (sink_side).
The capacity of the cut equals the max flow by the max-flow min-cut theorem.

# `calculate`

```elixir
@spec calculate(Yog.graph(), Yog.node_id(), Yog.node_id()) :: max_flow_result()
```

Calculates the maximum flow from source to sink using Edmonds-Karp with standard integers.

This is a convenience wrapper around `edmonds_karp/8` that uses default
integer arithmetic operations.

# `dinic`

```elixir
@spec dinic(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  any(),
  (any(), any() -&gt; any()),
  (any(), any() -&gt; any()),
  (any(), any() -&gt; :lt | :eq | :gt),
  (any(), any() -&gt; any())
) :: max_flow_result()
```

Finds the maximum flow using Dinic's algorithm with custom numeric type.

Dinic's algorithm builds a level graph using BFS, then finds blocking flows
via DFS. For unit capacities it runs in O(E√V). It is generally faster than
Edmonds-Karp for dense networks.

## Parameters

- `graph` - The flow network with edge capacities
- `source` - Source node ID where flow originates
- `sink` - Sink node ID where flow terminates
- `zero` - Zero value for the capacity type
- `add` - Addition function for capacities
- `subtract` - Subtraction function for capacities
- `compare` - Comparison function for capacities
- `min` - Minimum function for capacities

## Examples

Simple example with bottleneck:

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "s")
    ...>   |> Yog.add_node(2, "a")
    ...>   |> Yog.add_node(3, "t")
    ...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
    iex> result = Yog.Flow.MaxFlow.dinic(graph, 1, 3)
    iex> result.max_flow
    5

# `edmonds_karp`

```elixir
@spec edmonds_karp(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  any(),
  (any(), any() -&gt; any()),
  (any(), any() -&gt; any()),
  (any(), any() -&gt; :lt | :eq | :gt),
  (any(), any() -&gt; any())
) :: max_flow_result()
```

Finds the maximum flow using the Edmonds-Karp algorithm with custom numeric type.

Edmonds-Karp is a specific implementation of the Ford-Fulkerson method
that uses BFS to find the shortest augmenting path. This guarantees
O(VE²) time complexity.

## Parameters

- `graph` - The flow network with edge capacities
- `source` - Source node ID where flow originates
- `sink` - Sink node ID where flow terminates
- `zero` - Zero value for the capacity type
- `add` - Addition function for capacities
- `subtract` - Subtraction function for capacities
- `compare` - Comparison function for capacities
- `min` - Minimum function for capacities

## Examples

Simple example with bottleneck:

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "s")
    ...>   |> Yog.add_node(2, "a")
    ...>   |> Yog.add_node(3, "t")
    ...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
    iex> result = Yog.Flow.MaxFlow.edmonds_karp(graph, 1, 3)
    iex> result.max_flow
    5

# `extract_min_cut`

```elixir
@spec extract_min_cut(max_flow_result()) :: min_cut()
```

Extracts the minimum cut from a max flow result.

Given a max flow result, this function finds the minimum cut by identifying
all nodes reachable from the source in the residual graph.

Returns a map with `source_side` (nodes reachable from source) and
`sink_side` (all other nodes).

## Examples

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "s")
    ...>   |> Yog.add_node(2, "a")
    ...>   |> Yog.add_node(3, "t")
    ...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
    iex> result = Yog.Flow.MaxFlow.edmonds_karp(graph, 1, 3)
    iex> cut = Yog.Flow.MaxFlow.extract_min_cut(result)
    iex> cut.cut_value
    5
    iex> cut.source_side_size + cut.sink_side_size
    3

# `max_flow`

```elixir
@spec max_flow(Yog.graph(), Yog.node_id(), Yog.node_id(), algorithm()) ::
  max_flow_result()
```

Calculates the maximum flow from source to sink using the selected algorithm.

## Parameters

- `graph` - The flow network with edge capacities
- `source` - Source node ID where flow originates
- `sink` - Sink node ID where flow terminates
- `algorithm` - Algorithm to use: `:edmonds_karp` (default), `:dinic`, or `:push_relabel`

## Examples

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "s")
    ...>   |> Yog.add_node(2, "a")
    ...>   |> Yog.add_node(3, "t")
    ...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
    iex> result = Yog.Flow.MaxFlow.max_flow(graph, 1, 3, :push_relabel)
    iex> result.max_flow
    5

# `min_cut`

```elixir
@spec min_cut(max_flow_result(), any(), (any(), any() -&gt; :lt | :eq | :gt)) ::
  min_cut()
```

Extracts the minimum cut from a max flow result with custom numeric type.

This version allows you to specify the zero element and comparison function
for custom numeric types.

## Parameters

- `result` - The max flow result from `edmonds_karp/8` or `dinic/8`
- `zero` - Zero value for the capacity type
- `compare` - Comparison function for capacities (returns `:lt`, `:eq`, or `:gt`)

## Examples

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "s")
    ...>   |> Yog.add_node(2, "a")
    ...>   |> Yog.add_node(3, "t")
    ...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
    iex> result = Yog.Flow.MaxFlow.edmonds_karp(graph, 1, 3)
    iex> cut = Yog.Flow.MaxFlow.min_cut(result)
    iex> cut.cut_value
    5

# `push_relabel`

```elixir
@spec push_relabel(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  any(),
  (any(), any() -&gt; any()),
  (any(), any() -&gt; any()),
  (any(), any() -&gt; :lt | :eq | :gt),
  (any(), any() -&gt; any())
) :: max_flow_result()
```

Finds the maximum flow using the Push-Relabel (Goldberg-Tarjan) algorithm.

Push-Relabel with highest-label selection and the gap heuristic is typically
2–5× faster than Edmonds-Karp on dense graphs.

## Parameters

- `graph` - The flow network with edge capacities
- `source` - Source node ID where flow originates
- `sink` - Sink node ID where flow terminates
- `zero` - Zero value for the capacity type
- `add` - Addition function for capacities
- `subtract` - Subtraction function for capacities
- `compare` - Comparison function for capacities
- `min_fn` - Minimum function for capacities

## Examples

    iex> {:ok, graph} = Yog.directed()
    ...>   |> Yog.add_node(1, "s")
    ...>   |> Yog.add_node(2, "a")
    ...>   |> Yog.add_node(3, "t")
    ...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
    iex> result = Yog.Flow.MaxFlow.push_relabel(graph, 1, 3)
    iex> result.max_flow
    5

---

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