Yog.Flow.MaxFlow (YogEx v0.70.0)

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

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

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

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

References

Summary

Types

max_flow_result()

Result of a max flow computation.

min_cut()

Represents a minimum cut in the network.

Functions

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

Extracts the minimum cut from a max flow result.

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.

Types

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

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(max_flow_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> MapSet.member?(cut.source_side, 1)
true
iex> MapSet.member?(cut.sink_side, 3)
true

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
zero - Zero value for the capacity type
compare - Comparison function for capacities (returns true if a <= b)

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, 0, &(&1 + &2), &(&1 - &2), fn a, b -> a <= b end, &min/2
...> )
iex> cut = Yog.Flow.MaxFlow.min_cut(result, 0, fn a, b -> a <= b end)
iex> MapSet.member?(cut.source_side, 1)
true