topo_step

std.linalg.topo_step · Level L3

One step of Kahn's algorithm: take the smallest vertex with no incoming edge left among those not yet taken, remove its outgoing edges from the in-degrees, and record it. If none is left, the graph has a cycle and ok becomes 0. The body topological_order scans.

j = min{i : indeg(i) = 0, not taken}; indeg −= Aⱼ

Signature

topo_step(indeg: f64[n], removed: f64[n], ok: f64[], pick: f64[], t: f64[], A: f64[n, n]) → f64[n], f64[n], f64[], f64[]

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 the smallest untaken source; subtract its row; a cycle sets ok to 0 in exact rational arithmetic, on all 40 test cases.
All 402 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

topological_order

sha256:4f3662479de9080c81a165b012b0129b36768e14b89825615d3def5a16d19895

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

Control handle

Symbol: Ω:std.linalg.topo_step · Ω:topo_step
Pins: sha256:6d4577911bd58d34206413309864234b8bee66a96b881cd592c0b0e5234618eethis graph alone
Evidence: sha256:87c6acc89bd086a765ed1f3fc3574f22a9a0e361241c819db3d04ac90d5e0531the 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.