max_flow

std.linalg.max_flow · Level L3

The maximum flow from vertex 0 to vertex n − 1 in a network with capacities C, by Edmonds–Karp: a While over augment until no augmenting path is left. Returns the value, the flow on each edge, and the source side of a minimum cut, the vertices still reachable in the final residual network. By the max-flow min-cut theorem the cut's capacity equals the value. The reference is Ford–Fulkerson with depth-first paths, a different route to the same value and cut.

max{ value(f) : 0 ≤ f ≤ C, conservation }

Signature

max_flow(C: f64[n, n]) → f64[], f64[n, n], f64[n]

Requires: n ≥ 2

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size with n ≥ 2.
Equal to the reference Ford–Fulkerson with depth-first augmenting paths in exact rational arithmetic, on all 40 test cases.
All 1,564 float64 results are exact: the error is zero.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.

Accuracy in detail

correctly rounded (the float64 nearest the exact value): 100%
bit-equal to the NumPy formula in float64: 100%
largest error, in units in the last place: 0

Note

The flow on each edge is the positive part of the net flow, so on a pair of antiparallel edges only one direction carries flow. With integer capacities every quantity is an exact integer.

Identity

Calls

augment augmentable residual_bfs

Called by

—

sha256:db99cf4f776558abdce09f2daf1e53182c95dd7ae02825a0cbae89f99fc980f4

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.linalg.max_flow · Ω:max_flow
Pins: sha256:9b8ac34fed96cf4d141eafb15d572a4f52b2b2f7a5a034a1d08fac7a6a8979d2this graph and the 5 it reaches through calls
Evidence: sha256:97f6ebf4e9bc75bcf730e87f4761cee470b1f2646db5a18fff9a43570e9821adthe hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.