path_step

std.linalg.path_step · Level L3

One edge of the walk back from the sink along BFS parents: take the edge (parent(v), v), lower the bottleneck to its residual capacity, mark it, and move to the parent; at the source, stop. The body augment scans.

u = parent(v); b ← min(b, R(u, v)); mark (u, v); v ← u

Signature

path_step(v: f64[], bot: f64[], done: f64[], Pm: f64[n, n], t: f64[], parent: f64[n], R: f64[n, n]) → f64[], f64[], f64[], f64[n, n]

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.
Equal to the reference u = parent[v]; b = min(b, R[u, v]); P[u, v] += 1; v = u, until v = 0 in exact rational arithmetic, on all 40 test cases.
All 1,117 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

Identity

Calls

—

Called by

augment

sha256:92b68dbbf5b294db29420f3078fbe0f51713ecfd42747eba19b26342c7be76b7

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

Control handle

Symbol: Ω:std.linalg.path_step · Ω:path_step
Pins: sha256:ec797775ee43a3d103816f2cf3aa08c4d60976607bd117599f3bc39017366f91this graph alone
Evidence: sha256:df7c8091a8cc01553b47807f68b3a25c87509063c7d2f721afd4ae6263275f24the 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.