bfs_step

std.linalg.bfs_step · Level L2

One layer of breadth-first search on a 0/1 matrix of open edges: every unvisited vertex with an edge from a visited one is visited, with the smallest such vertex as its parent. The body residual_bfs scans; it does not read its sequence element.

new = unvisited ∩ out(visited); parent(v) = min{u visited : open(u, v)}

Signature

bfs_step(visited: f64[n], parent: f64[n], t: f64[], open: f64[n, n]) → f64[n], f64[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 for each unvisited v: the smallest visited u with an open edge to v in exact rational arithmetic, on all 40 test cases.
All 256 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

residual_bfs

sha256:2c45071463e57387306be3097f2d6780e911333b2d43a8898da2d78be925a887

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

Control handle

Symbol: Ω:std.linalg.bfs_step · Ω:bfs_step
Pins: sha256:97738a0aa0728b1c262da5792676243a6f6e686d12d6236a070a118ed2b338aathis graph alone
Evidence: sha256:2017227bef09fd9d55496d905885cb9f018778d60df18705684d9a0300040571the 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.