Module parametric_maxflow 

Parametric maximum flow (Gallo-Grigoriadis-Tarjan 1989 / Hochbaum 2008).

Solves a family of s-t maximum-flow problems in which some arc capacities vary monotonically with a scalar parameter lambda. Each arc capacity is modelled as an affine function cap(lambda) = base + slope * lambda (clamped at 0). The Gallo-Grigoriadis-Tarjan (GGT) monotone structure is enforced:

• arcs leaving the source (from == source) have non-decreasing capacity (slope >= 0),
• arcs entering the sink (to == sink) have non-increasing capacity (slope <= 0),
• every other arc has a constant capacity (slope == 0).

Under this structure the minimal source side S(lambda) of the minimum cut is a non-decreasing (nested) function of lambda: for l1 <= l2 we have S(l1) ⊆ S(l2). This module exposes

• ParametricMaxFlow::solve_at — a single (value, source-set) solve at one lambda, reusing the crate’s Edmonds-Karp / residual-reachability min-cut,
• ParametricMaxFlow::solve_grid — the whole family over a lambda grid,
• ParametricMaxFlow::find_breakpoints — the GGT divide-and-conquer “slicing” that locates every lambda at which the minimal min-cut changes, exploiting the nested-cut structure (one max-flow solve per slice).

The per-lambda solves are exact single-parameter max-flows, so they agree with an independent solve at every lambda.

Structs

ParametricArc

An arc whose capacity is affine in the parameter: cap(lambda) = base + slope * lambda.

ParametricBreakpoint

A lambda value at which the optimal minimal min-cut source side changes.

ParametricMaxFlow

A parametric s-t flow network with affine, GGT-monotone arc capacities.

ParametricSolution

Result of one single-lambda parametric solve.