Yog.FSharp
Getting Started Examples API Reference GitHub

MaxFlow Module

Namespace: Yog.Flow
Assembly: Yog.FSharp.dll

Maximum flow and minimum cut algorithms for network flow problems.

Provides the Edmonds-Karp algorithm for computing maximum flow in a flow network, and the max-flow min-cut theorem for extracting minimum cuts.

When to Use

  • Network flow optimization problems
  • Finding bottlenecks in transportation networks
  • Bipartite matching (via max flow)
  • Image segmentation (via min cut)
  • Project selection problems

Key Concepts

Flow Network

A directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed its capacity.

Maximum Flow

The maximum amount of flow that can be sent from a source node to a sink node without violating capacity constraints.

Minimum Cut

A partition of nodes into two sets (S, T) where source ∈ S and sink ∈ T, minimizing the sum of capacities of edges from S to T.

Complexity

  • Time: O(V × E²) for Edmonds-Karp
  • Space: O(V + E) for residual graph

Max-Flow Min-Cut Theorem

The maximum flow value equals the capacity of the minimum cut. This fundamental result connects optimization on flows to graph partitioning.

Types

Type Description

MaxFlowResult<'e>

Result of a max flow computation.

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

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

Functions and values

Function or value Description

edmondsKarp zero add subtract compare minVal source sink graph

Full Usage: edmondsKarp zero add subtract compare minVal source sink graph

Parameters:
    zero : 'e
    add : 'e -> 'e -> 'e
    subtract : 'e -> 'e -> 'e
    compare : 'e -> 'e -> int
    minVal : 'e -> 'e -> 'e
    source : NodeId
    sink : NodeId
    graph : Graph<'n, 'e>

Returns: MaxFlowResult<'e>

MaxFlowResult containing maximum flow value and residual graph.

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.

Type Parameters

  • 'e: The flow/capacity type

Parameters

  • zero: Identity element (0 for numeric types)
  • add: Addition function for accumulating flow
  • subtract: Subtraction function for updating residual capacities
  • compare: Comparison function for weights
  • minVal: Minimum function for finding bottleneck capacity
  • source: Source node ID (flow originates here)
  • sink: Sink node ID (flow terminates here)
  • graph: Input graph with edge capacities

Algorithm

  1. Initialize residual graph with original capacities
  2. While there exists an augmenting path from source to sink: a. Find shortest augmenting path using BFS b. Compute bottleneck capacity (minimum residual capacity on path) c. Augment flow along path d. Update residual capacities
  3. Return total flow and final residual graph

Complexity

  • Time: O(V × E²) - polynomial, unlike basic Ford-Fulkerson
  • Space: O(V + E)

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 

// Simple flow network
let graph =
    empty Directed
    |> addNode 0 () |> addNode 1 () |> addNode 2 ()
    |> addEdge 0 1 10  // Capacity 10 from 0 to 1
    |> addEdge 1 2 5   // Capacity 5 from 1 to 2
    |> addEdge 0 2 3   // Capacity 3 from 0 to 2

let result = edmondsKarp 0 (+) (-) compare min 0 2 graph
// result.MaxFlow = 8 (5 through 0->1->2, 3 through 0->2)

Applications

  • Transportation: Maximize goods transported through a network
  • Network reliability: Find minimum edges to cut to disconnect network
  • Bipartite matching: Model as flow with capacity 1 edges
  • Image segmentation: Min cut separates foreground from background
val graph: obj
val result: obj
val compare: e1: 'T -> e2: 'T -> int (requires comparison)
val min: e1: 'T -> e2: 'T -> 'T (requires comparison)

zero : 'e
add : 'e -> 'e -> 'e
subtract : 'e -> 'e -> 'e
compare : 'e -> 'e -> int
minVal : 'e -> 'e -> 'e
source : NodeId
sink : NodeId
graph : Graph<'n, 'e>
Returns: MaxFlowResult<'e>

MaxFlowResult containing maximum flow value and residual graph.

edmondsKarpInt source sink graph

Full Usage: edmondsKarpInt source sink graph

Parameters:
Returns: MaxFlowResult<int>

MaxFlowResult<int> with maximum flow and residual graph.

Finds maximum flow with integer capacities.

Parameters

  • source: Source node ID
  • sink: Sink node ID
  • graph: Input graph with integer capacities

Example

1: 
2: 

let result = edmondsKarpInt 0 5 myGraph
printfn "Maximum flow: %d" result.MaxFlow
val result: obj
val printfn: format: Printf.TextWriterFormat<'T> -> 'T

source : NodeId
sink : NodeId
graph : Graph<'n, int>
Returns: MaxFlowResult<int>

MaxFlowResult<int> with maximum flow and residual graph.

minCut zero compare result

Full Usage: minCut zero compare result

Parameters:
Returns: MinCut

MinCut containing source and sink side node sets.

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.

Parameters

  • zero: Identity element for flow type
  • compare: Comparison function for weights
  • result: The MaxFlowResult from a max flow computation

Algorithm

  1. Perform BFS from source in residual graph
  2. Follow edges with positive residual capacity
  3. All visited nodes form the source side
  4. Unvisited nodes form the sink side

Example

1: 
2: 
3: 
4: 
5: 

let flowResult = edmondsKarpInt 0 5 graph
let cut = minCut 0 compare flowResult

// cut.SourceSide = nodes reachable from 0 in residual graph
// cut.SinkSide = remaining nodes

Property

The sum of capacities of edges from SourceSide to SinkSide equals the maximum flow value (max-flow min-cut theorem).

val flowResult: obj
val cut: obj
val compare: e1: 'T -> e2: 'T -> int (requires comparison)

zero : 'e
compare : 'e -> 'e -> int
result : MaxFlowResult<'e>
Returns: MinCut

MinCut containing source and sink side node sets.