Module closure 

Bounded-depth graph closure over a sparse matrix’s adjacency.

ADR-001 roadmap item #6 (phase-2A): the closure primitive that turns a sparse RHS delta into the candidate set of rows whose solution might have changed. Composes with crate::incremental::SparseDelta and crate::contrastive::find_anomalous_rows_in_subset to get a sub-linear contrastive solve when the delta is small and the matrix is sparse + diagonally dominant.

What this does

Given a sparse matrix A and a set of seed row indices S, returns the bounded-depth closure of S in the row-graph of A:

  closure_0 = S
  closure_{d+1} = closure_d ∪ { j : ∃ i ∈ closure_d, A[i,j] ≠ 0 }

For diagonally dominant A, the magnitude of A⁻¹[i,j] decays geometrically with hop distance between i and j in this graph (the Neumann support shrinkage observation from §2.2 of “Sublinear time approximation of weighted set cover”, and the basis for the sublinear-Neumann solver in crate::sublinear). So the candidate set above conservatively over-covers the set of rows whose solution entries changed by more than O(ρ^depth · ‖delta‖), where ρ is the spectral radius of I − D⁻¹A (strictly < 1 for DD).

Practical implication: passing depth = ⌈log_{1/ρ}(‖delta‖/ε)⌉ to closure_indices gives you the exact candidate set needed for an ε-accurate contrastive solve, and on a sparse matrix with bounded degree this set is O(branch^depth) — sub-linear in n when the delta is small.

Complexity

• Time: O(depth · branch · |closure|), where branch is the maximum out-degree across visited rows. Bounded by O(nnz) worst case (depth ≥ diameter); sub-linear in n when depth · branch ≪ n.
• Space: O(|closure|) for the visited bit-set + the output vec.
• ComplexityClass: crate::complexity::ComplexityClass::SubLinear under the standard “sparse-A + bounded-depth” regime; degrades to Linear when depth ≥ diameter. The op-marker ClosureIndicesOp declares SubLinear and is the contract the caller’s budget should match.

Structs

ClosureIndicesOp

Op marker for the bounded-depth closure operation. Implements Complexity so callers can budget against this class without running the op first.

Functions

closure_indices

Return the bounded-depth row-graph closure of seeds in matrix.