Yog.Flow.MaxFlow (YogEx v0.97.1)

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

This module solves the 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, this equals the capacity of the minimum cut separating source from sink.

Algorithm

Algorithm	Function	Complexity	Best For
Edmonds-Karp	`edmonds_karp/8`	O(VE²)	General networks, guaranteed polynomial time
Dinic	`dinic/8`	O(V²E)	Dense networks, unit capacities O(E√V)
Push-Relabel	`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

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]; }

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.

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]; }

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

Summary

Types

algorithm()

max_flow_result()

Result of a max flow computation.

min_cut()

Represents a minimum cut in the network.

Functions

calculate(graph, source, sink)

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

dinic(graph, source, sink, zero \\ 0, add \\ &Kernel.+/2, subtract \\ &Kernel.-/2, compare \\ &Yog.Utils.compare/2, min_fn \\ &min/2)

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

edmonds_karp(graph, source, sink, zero \\ 0, add \\ &Kernel.+/2, subtract \\ &Kernel.-/2, compare \\ &Yog.Utils.compare/2, min_fn \\ &min/2)

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

extract_min_cut(result)

Extracts the minimum cut from a max flow result.

max_flow(graph, source, sink, algorithm \\ :edmonds_karp)

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

min_cut(max_flow_result, zero \\ 0, compare \\ &Yog.Utils.compare/2)

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

push_relabel(graph, source, sink, zero \\ 0, add \\ &Kernel.+/2, subtract \\ &Kernel.-/2, compare \\ &Yog.Utils.compare/2, min_fn \\ &min/2)

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

Types

algorithm()

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

max_flow_result()

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

@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.

Functions

calculate(graph, source, sink)

@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(graph, source, sink, zero \\ 0, add \\ &Kernel.+/2, subtract \\ &Kernel.-/2, compare \\ &Yog.Utils.compare/2, min_fn \\ &min/2)

@spec dinic(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  any(),
  (any(), any() -> any()),
  (any(), any() -> any()),
  (any(), any() -> :lt | :eq | :gt),
  (any(), any() -> 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(graph, source, sink, zero \\ 0, add \\ &Kernel.+/2, subtract \\ &Kernel.-/2, compare \\ &Yog.Utils.compare/2, min_fn \\ &min/2)

@spec edmonds_karp(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  any(),
  (any(), any() -> any()),
  (any(), any() -> any()),
  (any(), any() -> :lt | :eq | :gt),
  (any(), any() -> 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(result)

@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(graph, source, sink, algorithm \\ :edmonds_karp)

@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(max_flow_result, zero \\ 0, compare \\ &Yog.Utils.compare/2)

@spec min_cut(max_flow_result(), any(), (any(), any() -> :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(graph, source, sink, zero \\ 0, add \\ &Kernel.+/2, subtract \\ &Kernel.-/2, compare \\ &Yog.Utils.compare/2, min_fn \\ &min/2)

@spec push_relabel(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  any(),
  (any(), any() -> any()),
  (any(), any() -> any()),
  (any(), any() -> :lt | :eq | :gt),
  (any(), any() -> 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