components

std.topology.components · Level L2

The connected components of a finite topological space, each point labelled by the smallest point of its component; and how many there are. τ must be a topology, which is_topology decides. A point's component is the union of every connected subset that contains it, connected in the subspace topology. In a finite space it is found through the smallest open set U_x of each point: x and y lie in one component when a chain of points joins them, each two comparable, one in the other's smallest open set. These are components of the topology, not of a graph; and every component of a finite space is both open and closed, which fails in general (in ℚ the components are points, which are not open).

x ~ y ⇔ a chain x = z₀, …, z_r = y with zᵢ ∈ U_(zᵢ₊₁) or zᵢ₊₁ ∈ U_(zᵢ)

Signature

components(tau: f64[m, n]) → f64[n], f64[]

Requires: m ≥ 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 m ≥ 2.
Equal to the reference for each point, the union of every connected subset that contains it, all 2ⁿ subsets enumerated in exact rational arithmetic, on all 40 test cases.
All 180 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%
largest error, in units in the last place: 0

Identity

Calls

component_count component_labels

Called by

—

sha256:71f9b9d80a093d9b52777c7cd24213ae1fc960657db4f5801b4ed86ef2aae45c

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

Control handle

Symbol: Ω:std.topology.components · Ω:components
Pins: sha256:93c9b61e6c589203f216bc21ca6d9be20e9ecdc9d5aad0beb33e8a1b93b3b08cthis graph and the 4 it reaches through calls
Evidence: sha256:f87d78dbdbd8d6d7e795f6df0fa715892115f6a3b684b28641d43f1174d8c544the 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.