iso_step

std.linalg.iso_step · Level L3

One move of a backtracking search for an isomorphism: give vertex p its next candidate image; if none is left, clear it and step back; if the image is already used, or the edges and non-edges to the earlier vertices do not match, try the next one; otherwise go on to vertex p + 1. The body are_isomorphic runs.

image(p) ← next; none left: back; used or mismatch: stay; else: p + 1

Signature

iso_step(p: f64[], assign: f64[n], A: f64[n, n], B: f64[n, n]) → f64[], 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 next image for p; back when none is left; stay on a clash; else forward in exact rational arithmetic, on all 40 test cases.
All 221 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

are_isomorphic

sha256:396145d9dc6916623fa57d05d9fbf7ff2151d836d5a6c5d02bdea5f96b6a2ccd

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

Control handle

Symbol: Ω:std.linalg.iso_step · Ω:iso_step
Pins: sha256:93dadca1b5a1ad70ae2b4e316168d4513d8b3b26c79c976d3016433a405bce46this graph alone
Evidence: sha256:12e59dbd1d7e7626c7180788512ea0884e2f60232134fe48f4b7c787fa3e9887the 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.