yog - v1.3.0

yog/max_flow

Maximum flow algorithms for network flow problems.

This module provides implementations of maximum flow algorithms, which solve the problem of finding the maximum amount of “flow” that can be sent from a source node to a sink node in a flow network, respecting edge capacity constraints.

Algorithms

Example

import yog
import yog/max_flow
import gleam/int

pub fn main() {
  // Create a flow network
  // Edges represent capacity constraints
  let network =
    yog.directed()
    |> yog.add_edge(from: 0, to: 1, with: 10)  // source to A, capacity 10
    |> yog.add_edge(from: 0, to: 2, with: 10)  // source to B, capacity 10
    |> yog.add_edge(from: 1, to: 3, with: 4)   // A to C, capacity 4
    |> yog.add_edge(from: 1, to: 2, with: 2)   // A to B, capacity 2
    |> yog.add_edge(from: 2, to: 3, with: 9)   // B to C, capacity 9

  let result = max_flow.edmonds_karp(
    in: network,
    from: 0,  // source
    to: 3,    // sink
    with_zero: 0,
    with_add: int.add,
    with_subtract: fn(a, b) { a - b },
    with_compare: int.compare,
    with_min: int.min,
  )

  // result.max_flow => 13
  // result.min_cut => [0] on one side, [1, 2, 3] on other
}

Applications

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 (where flow originates)
  • to - The sink node (where flow terminates)
  • with_zero - The zero element for the capacity type (e.g., 0 for Int)
  • 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 maximum flow value
  • The residual graph (for extracting flow paths or min-cut)
  • Source and sink node IDs

Example

import gleam/int
import yog
import yog/max_flow

let network =
  yog.directed()
  |> yog.add_edge(from: 0, to: 1, with: 16)
  |> yog.add_edge(from: 0, to: 2, with: 13)
  |> yog.add_edge(from: 1, to: 2, with: 10)
  |> yog.add_edge(from: 1, to: 3, with: 12)
  |> yog.add_edge(from: 2, to: 1, with: 4)
  |> yog.add_edge(from: 2, to: 4, with: 14)
  |> yog.add_edge(from: 3, to: 2, with: 9)
  |> yog.add_edge(from: 3, to: 5, with: 20)
  |> yog.add_edge(from: 4, to: 3, with: 7)
  |> yog.add_edge(from: 4, to: 5, with: 4)

let result = max_flow.edmonds_karp(
  in: network,
  from: 0,
  to: 5,
  with_zero: 0,
  with_add: int.add,
  with_subtract: fn(a, b) { a - b },
  with_compare: int.compare,
  with_min: int.min,
)

// result.max_flow => 23

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: the minimum cut can be found by identifying all nodes reachable from the source in the residual graph after computing max flow.

The cut separates nodes reachable from source (source_side) from the rest (sink_side). The capacity of edges crossing from source_side to sink_side equals the max flow value.

Parameters

  • result - The max flow result from edmonds_karp
  • with_zero - The zero element for the capacity type
  • with_compare - Function to compare capacity values

Example

let result = max_flow.edmonds_karp(...)
let cut = max_flow.min_cut(result, with_zero: 0, with_compare: int.compare)
// cut.source_side contains nodes on source side
// cut.sink_side contains nodes on sink side
✨ Search Document