yog - v5.1.1

yog/flow/max_flow

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

AlgorithmFunctionComplexityBest For
Edmonds-Karpedmonds_karp/8O(VE²)General networks, guaranteed polynomial time

Edmonds-Karp is a specific implementation of the Ford-Fulkerson method that uses BFS to find the shortest augmenting path, guaranteeing polynomial time complexity regardless of capacities.

Key Concepts

Use Cases

References

Types

MaxFlowResult

</>

Result of a max flow computation.

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

pub type MaxFlowResult(e) {
  MaxFlowResult(
    max_flow: e,
    residual_graph: model.Graph(Nil, e),
    source: Int,
    sink: Int,
  )
}

Constructors 

  • MaxFlowResult(
  max_flow: e,
  residual_graph: model.Graph(Nil, e),
  source: Int,
  sink: Int,
)

    Arguments

    max_flow

    The maximum flow value from source to sink

    residual_graph

    The residual graph after flow computation (has remaining capacities)

    source

    The source node

    sink

    The sink node

MinCut

</>

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.

pub type MinCut {
  MinCut(source_side: set.Set(Int), sink_side: set.Set(Int))
}

Constructors 

  • MinCut(source_side: set.Set(Int), sink_side: set.Set(Int))

    Arguments

    source_side

    Nodes reachable from source (source side of cut)

    sink_side

    Nodes on sink side of cut

Values

edmonds_karp

</> 
pub fn edmonds_karp(
  in graph: model.Graph(n, e),
  from source: Int,
  to sink: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_subtract subtract: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
  with_min min: fn(e, e) -> e,
) -> MaxFlowResult(e)

Finds the maximum flow using the Edmonds-Karp algorithm.

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.

Time Complexity: O(VE²)

Parameters

  • in - The flow network (directed graph where edge weights are capacities)
  • from - The source node
  • to - The sink node
  • with_zero - The zero element for the capacity type
  • with_add - Function to add two capacity values
  • with_subtract - Function to subtract capacity values
  • with_compare - Function to compare capacity values
  • with_min - Function to find minimum of two capacity values

Returns

A MaxFlowResult containing the max flow value and residual graph.

Example

let result = max_flow.edmonds_karp(
  in: network,
  from: 0,
  to: 5,
  with_zero: 0,
  with_add: int.add,
  with_subtract: int.subtract,
  with_compare: int.compare,
  with_min: int.min,
)

edmonds_karp_int

</> 
pub fn edmonds_karp_int(
  in graph: model.Graph(n, Int),
  from source: Int,
  to sink: Int,
) -> MaxFlowResult(Int)

Finds maximum flow with integer capacities.

This is a convenience wrapper around edmonds_karp that uses:

  • 0 as the zero element
  • int.add for addition
  • int.subtract for subtraction
  • int.compare for comparison
  • int.min for minimum

Example

let result = max_flow.edmonds_karp_int(network, from: 0, to: 5)
// => MaxFlowResult(max_flow: 25, ...)

When to Use

Use this for flow networks with integer capacities (bandwidth in Mbps, vehicle capacity, number of lanes, etc.). This is the most common case for network flow problems.

min_cut

</> 
pub fn min_cut(
  result: MaxFlowResult(e),
  with_zero zero: e,
  with_compare compare: fn(e, e) -> order.Order,
) -> MinCut

Extracts the minimum cut from a max flow result.

Uses the max-flow min-cut theorem identifying nodes reachable from source in the final residual graph.

Example

let cut = max_flow.min_cut(result, with_zero: 0, with_compare: int.compare)
✨ Search Document