IncrementalVietorisRipsSimplexStream
A straightforward, non-optimized reference implementation of a Vietoris-Rips coface stream, following Antonio Rieser's New-VR algorithm ("A New Construction of the Vietoris-Rips Complex", arXiv:2301.07191v3) -- an explicit refinement of Zomorodian's own Incremental-VR algorithm (Algorithms 6/7 in that paper's Section 4; the algorithm EnumeratingCofaceSimplexStream and its siblings above are alternate, independently-optimized engines for the same construction). Kept intentionally close to the paper's own Algorithms 1-4, as a solid baseline the other, more experimental streams in this file can be cross-validated against, rather than as a speed-competitive engine in its own right.
The paper phrases the construction as a depth-first recursion over a simplex tree (New-Add-Cofaces, Algorithm 3), but its own prose description of the "inductive step" (Section 3, immediately above Algorithm 1) is equivalently a breadth-first, layer-by-layer construction: layer D(k+1) is built entirely from layer D(k) and each of that layer's own candidate/sibling lists. This class uses that framing so it can slot into iterateDimension's per-dimension contract like every other CofaceSimplexStream here. Since iterateDimension is a PartialFunction that may be called for any dimension in any order (unlike a genuinely incremental engine such as RipserCofaceSimplexStream, which depends on being driven dimension-by-dimension), the whole complex is built eagerly, once, into byDimension, and every call just serves a bucket from it -- simpler and safer than making the recursive construction itself resumable/order-independent.
maxFiltrationValue (default +Infinity) is the threshold defining the graph G whose clique complex the paper's algorithm builds: {i,j} ∈ E iff metricSpace.distance(i,j) v, {v,w} ∈ E}) -- see IncrementalVietorisRipsSpec for a pinned test that including it changes nothing about the output.
No deduplication is needed anywhere in this construction: every simplex is reached via exactly one recursive path, built by always appending vertices in increasing order from a candidate list that only ever contains vertices greater than every vertex already in tau (Theorem 2.5's minimal-pair bijection, in the paper's own terms). If a bug ever makes a simplex appear twice, that is a sign the recursion itself is wrong, not a reason to add a dedup step.
One deliberate departure from Algorithm 4 as written: the paper's own pseudocode does Σ ← V ∪ E unconditionally, before the main loop, so the full 1-skeleton is always present regardless of d. Here maxDimension instead behaves exactly like LimitedCofaceSimplexStream's maxDim -- the highest dimension iterateDimension will ever serve -- so maxDimension = 0 yields vertices only, with no edges, unlike the paper's own Σ. This matches every other bounded stream in this codebase and is what a caller building up dimension-by-dimension would expect.
Attributes
- Experimental
- true
- Graph
-
- Supertypes