org.appliedtopology.tda4j.streams

Attributes

Experimental: true
Supertypes: trait SpatialQuery[VertexT]

class Object

trait Matchable

class Any

The Cech complex, built the same way RipserCofaceSimplexStream builds Vietoris-Rips: dimension by dimension, extending only cofaces of the PREVIOUS dimension's already-accepted simplices (never the full binomial(n, d+1) power set) -- valid for Cech for a real, checked reason, not by analogy to VR: Cech is downward-closed (if a point witnesses a simplex's balls having a common intersection, that same point trivially witnesses every subset's balls having one too), so a valid Cech (d+1)-simplex's canonical generating facet (obtained by removing its own minimum vertex, RipserCofaceSimplexStream's own convention) is GUARANTEED to already be sitting in the accepted d-dimensional cache -- the enumeration cannot silently skip a real Cech simplex. CechStreamSpec's enumeration-completeness check pins this empirically (brute-force combinations(d+1).filter(cechValid) count vs. this class's own count), not just by the proof above.

Deliberately NOT built on IncrementalVietorisRipsSimplexStream ("New-VR")'s Table-Lookup optimization (Algorithm 2): that optimization's entire speed advantage comes from VR being a FLAG complex (simplex membership fully determined by which vertex PAIRS are edges) -- Cech is not a flag complex (three balls can pairwise-overlap in three different places with no common triple intersection), so pruning candidate vertices via graph structure the way Table-Lookup does isn't valid here without its own from-scratch proof, for uncertain benefit. RipserCofaceSimplexStream's plainer "try every remaining vertex against every accepted lower-dimensional simplex, filtered by the real criterion" shape needs no such proof: it stays correct for ANY downward-closed criterion, VR's or Cech's.

maxFiltrationValue is in CECH RADIUS units directly (not a VR diameter to be internally doubled) -- RipserCofaceSimplexStream's inherited coface loop gates every candidate through filtrationValue directly (no separate VR-diameter-based edge-graph precomputation is used once iterateDimension is overridden, so there is no VR-units quantity anywhere in this class to convert from).

Attributes

Experimental: true
Supertypes: class RipserCofaceSimplexStream

class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

The Cech radius of a simplex: the true minimum-enclosing-ball radius of its vertices' coordinates, computed once per simplex and cached forever -- a deliberate departure from RipserCohomologyContext's "don't cache filtration values by default" doctrine, since (unlike VR's diameter, which insertionDiameter recomputes incrementally in O(d)) there is no incremental shortcut for a minimum-enclosing-ball radius: every filter check, sort, and filtrationOrdering comparison would otherwise re-run a full Miniball solve.

Caching is also a correctness safeguard, not just a speed one: Miniball is a randomized-incremental algorithm, so two separate calls on the identical input can in principle round differently and return bit-different radii. filtrationOrdering needs one consistent answer per simplex to stay a total order; caching guarantees that without needing to trust a third-party library's determinism.

Cech's own value over Vietoris-Rips is exactly this quantity: unlike VR's purely combinatorial max-pairwise- distance, the Cech radius needs the vertices' real coordinates and a minimum-enclosing-ball computation (Welzl's algorithm, via Miniball) -- not alpha.AlphaComplexDQP's dual active-set QP, which answers a different question (restricted-Delaunay membership, dependent on the whole point cloud, not just a simplex's own vertices).

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: CechFiltration.type

Attributes

Experimental: true
Supertypes: trait IterableOnce[CellT]

trait Filtration[CellT, FiltrationT]

trait Filterable[FiltrationT]

class Object

trait Matchable

class Any
Show all
Known subtypes: trait SimplexStream[VertexT, FiltrationT]

class ExplicitStream[VertexT, FiltrationT]

class SimplicialSetStream[G]

trait StratifiedCellStream[CellT, FiltrationT]

class CubicalGridStream

class ExplicitCubicalStream

class FilteredSimplicialSetStream[G]

class LimitedCubicalGridStream

trait StratifiedSimplexStream[VertexT, FiltrationT]

class AlphaShapes

class AlphaComplexDQPStream

class AlphaShapeDQP

class HelixDelaunay

class LimitedAlphaShapesStream

trait CofaceSimplexStream[VertexT, FiltrationT]

class EnumeratingCofaceSimplexStream

class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream

class LimitedCofaceSimplexStream

class RecursiveStackVietorisRipsSimplexStream
Show all

Attributes

Experimental: true
Supertypes: trait StratifiedSimplexStream[VertexT, FiltrationT]

trait StratifiedCellStream[Simplex[VertexT], FiltrationT]

trait CellStream[Simplex[VertexT], FiltrationT]

trait IterableOnce[Simplex[VertexT]]

trait Filtration[Simplex[VertexT], FiltrationT]

trait Filterable[FiltrationT]

class Object

trait Matchable

class Any
Show all
Known subtypes: class EnumeratingCofaceSimplexStream

class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream

class LimitedCofaceSimplexStream
Show all

******* Optimized Vietoris-Rips cofacet generation for fast coboundary computation *******

Attributes

Experimental: true
Supertypes: trait Iterator[VertexT]

trait IterableOnceOps[VertexT, Iterator, Iterator[VertexT]]

trait IterableOnce[VertexT]

class Object

trait Matchable

class Any
Show all

Dense cubical complex over a full rectangular grid, filtration values assigned via the T-construction: a caller-supplied topCellValue gives every top-dimensional cube (pixel/voxel) its own value directly, and every lower-dimensional cube's value is the min over all top cells that contain it as a face -- exactly the "sublevel set of a piecewise-constant function on pixels" convention GUDHI/DIPHA/Perseus all use for image persistence (see .claude/WORKLOG-cubical.md for the monotonicity proof: since every top cell containing an immediate coface of c also contains c, fv(coface) >= fv(c) always holds by construction, which is exactly what CellularHomologyContext.processingOrder's ascending sort requires).

For a SUPERLEVEL-set convention instead, negate topCellValue before constructing (the standard trick -- see CubicalImage.scala's sublevel parameter, which does exactly this): sublevel persistence of -f is superlevel persistence of f, reparametrized, so this type deliberately does not carry its own sign-direction flag -- one code path, always "min over cofaces," is easier to get right and to verify than baking a direction switch into the core stream.

shape(i) is the number of PIXELS along axis i (not lattice points -- there are shape(i) + 1 of those). The full grid complex has prod_i (2*shape(i)+1) cells total (totalCellCount) -- e.g. a 256x256 image has 513*513 = 263169 cells, not 65536.

Attributes

Experimental: true
Supertypes: trait DoubleFiltration[Cube]

trait StratifiedCellStream[Cube, Double]

trait CellStream[Cube, Double]

trait IterableOnce[Cube]

trait Filtration[Cube, Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Converting greyscale images and dense voxel grids into CubicalGridStreams. Every constructor here reduces to fromFlatArray: a dense n-dimensional grid from a flat, row-major array of values plus an explicit shape.

sublevel = true (the default, matching GUDHI/DIPHA/Perseus's own convention) treats pixel intensity directly as filtration value -- ascending intensity = later in the filtration. sublevel = false negates every value before handing it to CubicalGridStream -- the standard "sublevel of -f is superlevel of f, reparametrized" trick (see CubicalStream.scala's own doc for why CubicalGridStream itself deliberately carries no direction flag). Reported birth/death values under sublevel = false are then in NEGATED-intensity units, not raw 0..255 -- documented, expected behavior of this trick, not a bug to "fix" by flipping signs back.

No image-I/O dependency is added for voxel (3D+) data -- there is no single standard JDK-readable volumetric format, so voxel constructors here take an already-in-memory array; callers with a specific file format (NRRD, NIfTI, a raw slice stack, ...) are expected to load it into an array upstream, with whatever library that needs, and hand the result to fromFlatArray/fromVoxelGrid3D directly.

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: CubicalImage.type

The empirical distance-to-measure function (Chazal, Cohen-Steiner & Merigot, "Geometric inference for probability measures", Foundations of Computational Mathematics 11:733-751, 2011): for a point set X with the uniform empirical measure and mass parameter k (equivalently m0 = k/|X|),

f(x) = ( (1/k) * sum over the k nearest neighbours y of x (including x itself) of d(x,y)^q )^(1/q)

q defaults to 2, matching GUDHI's own gudhi.point_cloud.dtm.DistanceToMeasure default. Self-inclusion (x counts as one of its own k neighbours, at distance 0) is likewise GUDHI's own convention -- confirmed both from that class's own docstring ("k: number of neighbors (possibly including the point itself)") and by reproducing its worked doctest byte-for-byte (DistanceToMeasureSpec; see .claude/WORKLOG-dtm-filtrations.md for the full derivation and every oracle value checked against). One consequence: k = 1 always gives f = 0 everywhere (a point's own nearest neighbour, itself, is at distance 0) -- the degenerate case every consumer of this function (DtmRipsSimplexStream, DTM-weighted alpha.PowerDistance) should reduce to its un-weighted construction at.

Takes a SpatialQuery, not a FiniteMetricSpace alone, so callers choose the k-NN strategy: BruteForce is the safe default (apply's own convenience overload) since VP-tree pruning assumes the triangle inequality, which not every FiniteMetricSpace in this codebase actually satisfies (ExplicitMetricSpace enforces nothing -- GUDHI's own docs feed correlation-derived "distance" matrices through exactly this class). JVPTree is only safe over a genuine metric.

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: DistanceToMeasure.type

Attributes

Experimental: true
Supertypes: trait Filtration[CellT, Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Known subtypes: class AlphaShapes

class AlphaComplexDQPStream

class AlphaShapeDQP

class HelixDelaunay

class LimitedAlphaShapesStream

class CubicalGridStream

class EnumeratingCofaceSimplexStream

class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream

class ExplicitCubicalStream

class LimitedCofaceSimplexStream

class LimitedCubicalGridStream

class RecursiveStackVietorisRipsSimplexStream
Show all

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: DowkerCofaceSimplexStream.type

The (filtered) Dowker complex on the LEFT side of geometry -- see the class doc on DowkerGeometry above for the full mathematical picture, monotonicity proof, and non-flag status. maxFiltrationValue defaults to +Infinity, not metricSpace.minimumEnclosingRadius-style truncation (contrast every genuine-flag-complex VR stream in this codebase): an arbitrary relation gives no cone argument to truncate against, the same reasoning WitnessCofaceSimplexStream's general (non-lazy) variant already documents for its own dimension-specific formula.

Vertex ids in every emitted Simplex[Int] are indices into geometry.relation's rows (0 until geometry.numLeft); .dual gives the complex on the other side (geometry.dual's rows, geometry's original columns), which Dowker's theorem guarantees is homotopy equivalent to this one at every threshold.

Attributes

Companion: object
Experimental: true
Supertypes: class RipserCofaceSimplexStream

class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

DowkerGeometry.filtrationValue, memoized -- the same "a caller-supplied filtrationValueOverride is not cached by RipserCofaceSimplexStream itself, so a genuinely expensive one must cache itself" reasoning as CechFiltration/WitnessCofaceSimplexStream.recursiveFiltrationValue. Deliberately no spx.dim 0.0 special case (contrast CechFiltration/MaximumDistanceFiltrationValue): a Dowker vertex's own filtration value is generally nonzero and meaningful, not a VR-style convention-only placeholder -- see the class doc.

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: DowkerFiltration.type

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: DowkerGeometry.type

The (filtered) Dowker complex of a relation R: L x W -> [0, Infinity] between two, generally distinct, finite sets L ("left") and W ("witnesses"), after Dowker's own theorem (C.H. Dowker, "Homology groups of relations", Ann. of Math. 56 (1952)), in the real-valued generalization used e.g. by Chowdhury & Mémoli ("A functorial Dowker theorem and persistent homology of asymmetric networks", 2018): a subset sigma subseteq L is a simplex at filtration value t iff some w in W witnesses every element of sigma by time t, i.e. f(sigma) = min_{w in W} max_{x in sigma} R(x, w) 0.0) (De Silva-Carlsson's nu = 0) is EXACTLY this class's filtrationValue with R = D (the landmark-to-witness distance matrix) -- not implemented by delegating to WitnessGeometry (that class's own shape -- an ambient metric space plus a landmark subset -- doesn't fit a general relation with no shared ambient space at all), but the same formula, independently re-derived, is worth knowing about if the two ever need to be cross-checked against each other.

Attributes

Companion: object
Experimental: true
Supertypes: class Object

trait Matchable

class Any

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: DtmRipsSimplexStream.type

The DTM-based (weighted Rips) filtration of Anai, Chazal, Glisse, Ike, Lecci, Rouvreau, Saulnier & Wasserman, "DTM-based filtrations" (arXiv:1811.04757, Prop. 3.5), checked byte-for-byte against GUDHI's own gudhi.dtm_rips_complex.DTMRipsComplex/gudhi.weighted_rips_complex.WeightedRipsComplex for p = 1 (DtmRipsStreamSpec; see .claude/WORKLOG-dtm-filtrations.md for the fetched source and every oracle value). Values are in the same "doubled"/diameter units every other VR stream in this codebase uses (GUDHI's own choice too, for the identical reason: consistency with plain, unweighted Rips, whose edge filtration is the raw pairwise distance, not half of it).

f(x) is the empirical distance-to-measure per ambient point (streams.DistanceToMeasure); at f = 0 everywhere (in particular at k = 1, DistanceToMeasure's own degenerate case) this reduces EXACTLY to plain Vietoris-Rips, threshold included -- DtmRipsStreamSpec checks this too.

p selects the ball-radius exponent of Def. 3.1 -- NOT DistanceToMeasure's own exponent q, a different knob entirely. Only p = 1 and p = 2 are implemented:

p = 1: t(f_x, f_y, d) = max(f_x, f_y, (d + f_x + f_y) / 2). The only variant GUDHI's own Python bindings implement, and the one every published worked example (including this class's own regression oracle) targets.
p = 2: closed form t(f_x, f_y, d) = max(f_x, f_y, sqrt(u^2 + f_x^2)) where u = (d^2 + f_y^2 - f_x^2) / (2d), valid (and symmetric in x/y -- verified algebraically, not just numerically) whenever |f_y^2 - f_x^2| = 1 -- the inherited default "max pairwise distance" filtration functional is already exactly the flag-complex extension this construction wants (same relationship WitnessMetricSpace has to LazyWitnessSimplexStream). The only override needed is at dimension 0: unlike plain VR (where every vertex is born at filtration 0, so the base class's hardcoded dim 0.0 and its unsorted, unfiltered case 0 vertex emission are both harmless -- see .claude/WORKLOG-dtm-filtrations.md for why), THIS is the first coface stream in this codebase whose vertices have distinct, nonzero filtration values, so case 0 MUST be sorted by filtrationOrdering.reverse and filtered by threshold like every other dimension (ordering contract rule 2 in CLAUDE.md) -- silently violating that would corrupt Chain's pivot table exactly like the historical "no tie-break" bugs did, and would let vertices past maxFiltrationValue leak into the complex as spurious isolated components.

maxFiltrationValue defaults (via None) to the reified space's own minimumEnclosingRadius, the same convention every other flag-complex VR stream in this codebase uses (not GUDHI's own max_filtration = +Infinity default) -- valid here for a real, checked reason, not just by analogy: t(f_x, f_y, d) >= max(f_x, f_y) by construction for both p = 1 and p = 2 (immediate for p=1's outer max; for p=2, t^2 = u^2 + f_x^2 >= f_x^2 and the symmetric v = d - u form gives t^2 = v^2 + f_y^2 >= f_y^2 too), so taking x* = argmin_x max_y distance(x,y) and R = distance(x*,·)'s own max: for every vertex z, 2*f(z) = 2*f_z) -- every vertex's own birth is <= R, so truncating there cannot silently drop a vertex, and beyond R the complex is a cone from x* exactly as in the unweighted case. Refuses engine=ripser in matlab.TDA4j's dispatch (both Ripser engines assume vertex births at 0 and a diameter-only incremental formula); naive/chunks/cohomology all consume this like any other CofaceSimplexStream[Int, Double].

Attributes

Companion: object
Experimental: true
Supertypes: class RipserCofaceSimplexStream

class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Flag-complex edge collapse (Boissonnat-Pritam, "Edge Collapse and Persistence of Flag Complexes," SoCG 2020; Glisse-Pritam, "Swap, Shift and Trim to Edge Collapse a Filtration," SoCG 2022): reduces a Vietoris-Rips filtration's own 1-skeleton to a smaller weighted graph whose flag complex has the SAME persistent homology at every filtration level, using only the graph itself (no higher simplices ever built). .claude/WORKLOG- mainstream-feature-gap-analysis.md item 5. Definitions verified directly against GUDHI's own edge-collapse module (Gudhi::collapse, the reference implementation, co-authored by the same Pritam/Glisse -- fetched and read directly via a throwaway clone of GUDHI/gudhi-devel, not recalled from memory, matching this codebase's own io-module verification ethos; the actual arXiv/Dagstuhl PDFs were unreachable from this session's network policy), not the mainstream-feature-gap-analysis worklog's own first-draft phrasing -- see this file's own worklog for the one correction that came out of that (the operation removes dominated EDGES, not dominated VERTICES; vertex domination is a different construction, "strong collapse," arXiv:1809.10945).

'''Dominated edge''' (GUDHI's own definition, restated for a flag complex where it depends only on the graph): an edge e = {u, v} is dominated by a vertex w ∉ e iff every vertex adjacent to BOTH u and v is also adjacent to w -- equivalently, w's closed neighborhood contains every common neighbor of u and v. An elementary edge collapse removes a dominated edge (and, implicitly, every simplex containing it) from the flag complex; domination is a simple sufficient condition for this removal to be an elementary simplicial collapse (a strong deformation retraction, hence a simple-homotopy equivalence).

'''Across a whole filtration''' (not one fixed threshold): an edge dominated at its own birth may stop being dominated once the filtration admits more vertices -- so instead of an outright removal, its own entry time is pushed forward to the largest time at which it remains dominated (by, in general, a succession of different dominating vertices as new common neighbors arrive) -- GUDHI's own doc states this plainly: "an edge collapse may translate into an increase of the filtration value of an edge, or its removal if it already had the largest filtration value." If no such largest time exists (the edge stays dominated all the way through the complex), it is removed outright. The resulting smaller weighted graph is, again, a flag complex, and its persistent homology (every bar, at every dimension) agrees with the original's exactly.

'''Representatives transfer for free through inclusion''' (this codebase's own design principle requires representatives from every engine, so this matters, and is not addressed by the papers' own barcode-only framing): at every filtration level t, the collapsed complex is a literal SUBCOMPLEX of the original (an edge collapse only ever removes cells or defers their entry to a later t, never adds or identifies any) -- so the inclusion of the collapsed complex into the original is a well-defined chain map at every level, and a cycle/cocycle representative computed on the SMALLER complex is automatically a valid representative of the SAME homology class in the ORIGINAL complex, simply by reinterpreting the same chain as living in the bigger complex. No separate lifting machinery is needed (contrast the MST-based simplicial-set collapse this same worklog item considered and declined -- see the worklog -- where the analogous complex is a QUOTIENT, not a subcomplex, and lifting a representative back is a real additional step).

'''This implementation IS a faithful port of GUDHI's own single-pass, descending-filtration-value sweep''' (process_edges/common_neighbors/is_dominated_by in Flag_complex_edge_collapser.h) -- a first attempt at an independently-designed "iterate a batch-scan resolution to a whole-graph fixed point" alternative was tried and CONFIRMED WRONG (WORKLOG-edge-collapse.md): it over-collapsed a 5-point fixture, permanently removing every chord of a pentagon whose flag complex genuinely has a persistent (non-zero-persistence) H¹ class, silently turning that class essential. The bug was letting an edge's own "dominated forever, remove" decision stand permanently even after a LATER decision (elsewhere in the graph) invalidated the very common-neighbor edge that removal decision had relied on -- a removed edge is never reconsidered, so nothing could ever correct it. GUDHI's own SPECIFIC processing order (descending by ORIGINAL filtration value, one pass, each edge decided exactly once against the live, progressively-mutating graph) is not an arbitrary implementation choice, as this class's own first (wrong) draft assumed -- it is what the published algorithm actually requires, and this port follows it exactly rather than re-deriving a substitute. This session could not fetch the actual proof (the arXiv/Dagstuhl hosts were unreachable from this session's network policy -- see the worklog) justifying WHY that specific order is sound; this implementation trusts the verified reference implementation's own structure on that point, the same way this codebase trusts a fetched GUDHI/DREiMac docstring or worked example elsewhere, and instead cross-validates the OUTPUT empirically (barcode agreement against plain, uncollapsed VR, across property-tested random point clouds, a tie-heavy fixture, and hand-built fixtures) rather than the algorithm's own internal reasoning -- see the spec.

GUDHI's own doc notes the single pass does not necessarily produce a MINIMAL filtration -- applying collapse again to its own output (this class's EdgeCollapsedMetricSpace is itself a FiniteMetricSpace[Int], so this needs no special support) may simplify it further; neither this class nor GUDHI's own promises idempotence in one application.

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: EdgeCollapse.type

The collapsed graph, reified as a FiniteMetricSpace[Int] over the SAME vertex ids as originalMetricSpace -- exactly the pattern WitnessMetricSpace already established for a non-metric, collapse-derived weighted graph, so it slots directly into EnumeratingCofaceSimplexStream/RipserCofaceSimplexStream unchanged. +Infinity for a collapsed-away (or never-present) pair, matching SparseMetricSpace's own "+Infinity past the cutoff, not excluded" convention.

'''Not a real metric''': collapsed edges can violate the triangle inequality freely (that is the entire point -- a shortcut through a dominating vertex is exactly what gets removed). Never hand this to JVPTree, SparseMetricSpace, RecursiveStackVietorisRipsSimplexStream, or the alpha package, same restriction WitnessMetricSpace's own doc states for the identical reason.

'''The enclosing-radius hazard''' (.claude/WORKLOG-mainstream-feature-gap-analysis.md item 5's own flagged risk, confirmed real): FiniteMetricSpace's default minimumEnclosingRadius is elements.map(x => elements.map(y => distance(x,y)).max).min -- computed against a graph that now has genuine +Infinity entries, that formula can itself evaluate to +Infinity the moment every vertex has at least one collapsed-away incident pair, silently disabling truncation for any downstream consumer that relies on the None default. Fixed structurally, not by caller discipline: minimumEnclosingRadius is overridden here to validUpTo (the bound EdgeCollapse.collapse actually used, itself defaulted from originalMetricSpace's own OWN enclosing radius when the caller passed no explicit bound) -- so a downstream maxFiltrationValue = None is always safe by construction, with nothing for a caller to remember.

Attributes

Experimental: true
Supertypes: trait FiniteMetricSpace[Int]

class Object

trait Matchable

class Any

Attributes

Experimental: true
Supertypes: trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all
Known subtypes: class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream
Show all

Takes in an point cloud and computes the Euclidean distance on demand.

Value parameters

pts

Point cloud matrix represented as a Seq[Seq[Double]]. The class expects but does not enforce:

pts(x1).size == pts(x2).size for all x1,x2

Attributes

Companion: object
Experimental: true
Supertypes: trait FiniteMetricSpace[Int]

class Object

trait Matchable

class Any

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: EuclideanMetricSpace.type

A sparse/arbitrary finite set of cubes with explicit filtration values -- mirrors ExplicitStream for simplices. Useful for hand-built fixtures and for genuinely non-grid cubical complexes (arbitrary unions of products of intervals, per the original ask -- CubicalGridStream is the important special case for images, not the only shape a cubical complex can take).

Attributes

Companion: object
Experimental: true
Supertypes: trait DoubleFiltration[Cube]

trait StratifiedCellStream[Cube, Double]

trait CellStream[Cube, Double]

trait IterableOnce[Cube]

trait Filtration[Cube, Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: ExplicitCubicalStream.type

Takes in an explicit distance matrix, and performs lookups in this distance matrix.

Value parameters

dist

Distance matrix represented as a Seq[Seq[Double]]. The class expects but does not enforce:

dist(x1).size == dist(x2).size for all x1,x2
dist(x).size == dist.size for all x
dist(x)(x) == 0 for all x
The triangle inequality

Attributes

Experimental: true
Supertypes: trait FiniteMetricSpace[Int]

class Object

trait Matchable

class Any

Attributes

Experimental: true
Supertypes: trait SimplexStream[VertexT, FiltrationT]

trait CellStream[Simplex[VertexT], FiltrationT]

trait IterableOnce[Simplex[VertexT]]

trait Filtration[Simplex[VertexT], FiltrationT]

trait Filterable[FiltrationT]

class Object

trait Matchable

class Any
Show all
Self type: ExplicitStream[VertexT, FiltrationT]

Attributes

Experimental: true
Supertypes: trait ReusableBuilder[(FiltrationT, Simplex[VertexT]), ExplicitStream[VertexT, FiltrationT]]

trait Builder[(FiltrationT, Simplex[VertexT]), ExplicitStream[VertexT, FiltrationT]]

trait Growable[(FiltrationT, Simplex[VertexT])]

trait Clearable

class Object

trait Matchable

class Any
Show all
Self type: ExplicitStreamBuilder[VertexT, FiltrationT]

Attributes

Companion: object
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Known subtypes: trait Filtration[CellT, FiltrationT]

trait CellStream[CellT, FiltrationT]

trait SimplexStream[VertexT, FiltrationT]

class ExplicitStream[VertexT, FiltrationT]

class SimplicialSetStream[G]

trait StratifiedCellStream[CellT, FiltrationT]

class CubicalGridStream

class ExplicitCubicalStream

class FilteredSimplicialSetStream[G]

class LimitedCubicalGridStream

trait StratifiedSimplexStream[VertexT, FiltrationT]

class AlphaShapes

class AlphaComplexDQPStream

class AlphaShapeDQP

class HelixDelaunay

class LimitedAlphaShapesStream

trait CofaceSimplexStream[VertexT, FiltrationT]

class EnumeratingCofaceSimplexStream

class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream

class LimitedCofaceSimplexStream

class RecursiveStackVietorisRipsSimplexStream

trait DoubleFiltration[CellT]
Show all

The stdlib-numeric-type instances live here, on Filterable's own companion, rather than as bare top-level package givens: found via ordinary implicit-scope search (the companion of either side of Filterable[Double]) regardless of import, rather than being ambient to every file that happens to do import streams.{given, *}.

Attributes

Companion: trait
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: Filterable.type

Attributes

Experimental: true
Supertypes: trait Ordering[Simplex[VertexT]]

trait PartialOrdering[Simplex[VertexT]]

trait Equiv[Simplex[VertexT]]

trait Serializable

trait Comparator[Simplex[VertexT]]

class Object

trait Matchable

class Any
Show all

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: FilteredSimplicialSetStream.type

A FiniteSimplicialSet with a real, caller-supplied filtration -- unlike SimplicialSetStream (every generator at filtration 0, ordinary homology only), this is a genuine StratifiedCellStream[G, Double], so it plugs into CellularPersistenceInChunksContext/PersistenceInChunksContext as well as CellularHomologyContext. filtrationValue is defined only on generators (never on arbitrary, possibly degenerate SSetElements) -- correct because every engine here only ever queries a stream's filtrationValue on the actual CellT values it iterates, and SimplicialSetStream/this class both only ever iterate generators, never degenerate elements (finiteSimplicialSetIsOrderedCell.boundary resolves degeneracy internally via faces, without the engine ever seeing an SSetElement directly).

iterateDimension sorts each dimension's bucket by filtrationOrdering.reverse -- oldest first, the SAME Ordering object reversed, not an independently-built comparator -- matching the established convention this codebase has broken and fixed three separate times when two independently-tie-broken orders disagreed (see CLAUDE.md). Positional index within PersistenceInChunksContext's allCells (built by dimension-major concatenation of iterateDimension's buckets) stands in for chunk-boundary/local-reduction "how old is this cell" logic, so a bucket sorted any other way corrupts chunking even though it would still look like a valid total order in isolation -- FilteredSimplicialSetStreamSpec asserts this directly rather than only checking the resulting barcode.

Attributes

Companion: object
Experimental: true
Supertypes: trait StratifiedCellStream[G, Double]

trait CellStream[G, Double]

trait IterableOnce[G]

trait Filtration[G, Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Attributes

Experimental: true
Supertypes: trait Filterable[FiltrationT]

class Object

trait Matchable

class Any
Known subtypes: trait CellStream[CellT, FiltrationT]

trait SimplexStream[VertexT, FiltrationT]

class ExplicitStream[VertexT, FiltrationT]

class SimplicialSetStream[G]

trait StratifiedCellStream[CellT, FiltrationT]

class CubicalGridStream

class ExplicitCubicalStream

class FilteredSimplicialSetStream[G]

class LimitedCubicalGridStream

trait StratifiedSimplexStream[VertexT, FiltrationT]

class AlphaShapes

class AlphaComplexDQPStream

class AlphaShapeDQP

class HelixDelaunay

class LimitedAlphaShapesStream

trait CofaceSimplexStream[VertexT, FiltrationT]

class EnumeratingCofaceSimplexStream

class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream

class LimitedCofaceSimplexStream

class RecursiveStackVietorisRipsSimplexStream

trait DoubleFiltration[CellT]
Show all

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: FiltrationOrdering.type

Convenience functionality for metric spaces.

Attributes

Companion: trait
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: FiniteMetricSpace.type

Interface for being a finite metric space

Type parameters

VertexT: Type of the vertex indices for the metric space

Attributes

Companion: object
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Known subtypes: class DtmMetricSpace

class EdgeCollapsedMetricSpace

class EuclideanMetricSpace

class ExplicitMetricSpace

class IntMetricSpace[VertexT]

class SparseMetricSpace[VertexT]

class WitnessMetricSpace
Show all

A full greedy permutation (farthest-point / "maxmin" sampling) of an ENTIRE finite metric space -- as opposed to streams.LandmarkSelection, which picks a SUBSET. order is every ambient index in selection order (order(0) is the seed point); insertionRadius(p) is p's own lambda_p = d(p, {points ordered before p}), with insertionRadius(order(0)) = Double.PositiveInfinity by convention (there is no "distance to the empty set", and the seed point must never be pruned away by any downstream sparsification). Built by LandmarkSelector.maxmin run to numLandmarks = metricSpace.size (see that method's own doc) -- this type just names the result's intended use (SheehyRipsSimplexStream) distinctly from a landmark subset.

Attributes

Experimental: true
Supertypes: trait Serializable

trait Product

trait Equals

class Object

trait Matchable

class Any
Show all

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
Supertypes: class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

An alternate Vietoris-Rips coface-generation strategy, independent of EnumeratingCofaceSimplexStream's combinatorial-number-system enumeration: cofaces are generated "in order" directly from the metric space's own structure. A cross-validation baseline for the canonical VR streams, not a speed-competitive production engine in its own right.

Attributes

Experimental: true
Supertypes: class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Wrapper class to make any metricspace into a metricspace defined on indices 0 through metricSpace.size. This way, code can assume that the index set is contiguous.

Type parameters

VertexT: Type of the vertex indices for the wrapped metric space

Value parameters

metricSpace: Wrapped metric space

Attributes

Experimental: true
Supertypes: trait FiniteMetricSpace[Int]

class Object

trait Matchable

class Any

Attributes

Experimental: true
Supertypes: trait SpatialQuery[VertexT]

class Object

trait Matchable

class Any

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: Kruskal.type

This implementation of Kruskal's algorithm will return two iterators of vertex pairs: the first iterator is a Minimal Spanning Tree in increasing weight order, while the second iterator gives all the non-included

Attributes

Companion: object
Experimental: true
Supertypes: class Object

trait Matchable

class Any

landmarks(i) is the ambient index of the i-th landmark -- the mapping every witness-stream class below needs to translate its own LOCAL 0 until landmarks.size simplex vertex indices back to the caller's original point cloud (matlab.TDA4j does this for cycleVertices). coveringRadius is R = max_x min_l d(x,l). insertionRadius maps an ambient index to its own greedy-permutation lambda (see maxmin's doc); empty for random (no meaningful lambda) and for a hand-built selection not routed through maxmin.

Attributes

Experimental: true
Supertypes: trait Serializable

trait Product

trait Equals

class Object

trait Matchable

class Any
Show all

Greedy landmark-selection strategies over a FiniteMetricSpace[Int] -- the first step of building any witness complex (De Silva & Carlsson, "Topological estimation using witness complexes", 2004; see .claude/WORKLOG-witness-complex.md, checked against JavaPlex's own LandmarkSelector implementations). Landmarks are always a SUBSET of the ambient point set (their own ambient indices), matching JavaPlex's convention -- not arbitrary points outside it, which the original paper allows but no downstream tool actually uses.

Both selectors assume metricSpace's own elements are the contiguous range 0 until metricSpace.size -- the same assumption every other coface stream in this codebase already makes of its own FiniteMetricSpace[Int] (via SimplexIndexing's combinatorial-number-system enumeration; see IntMetricSpace's own doc), not a new one introduced here.

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: LandmarkSelector.type

The lazy witness complex (De Silva & Carlsson 2004; JavaPlex's LazyWitnessStream): the flag/clique complex of WitnessMetricSpace's own weighted 1-skeleton. A thin RipserCofaceSimplexStream subclass -- exactly the same relationship CechCofaceSimplexStream has to RipserCofaceSimplexStream, except no filtrationValueOverride is needed here at all: WitnessMetricSpace.distance already IS the edge filtration value, and the inherited default ("max pairwise distance") is exactly the flag-complex extension to higher dimensions this construction wants.

maxFiltrationValue inherits EnumeratingCofaceSimplexStream's own default: metricSpace.minimumEnclosingRadius under WitnessMetricSpace.distance. This IS a valid truncation here (unlike for WitnessCofaceSimplexStream below): any flag complex is a cone past min_x max_y d'(x,y) regardless of whether d' is a genuine metric -- the cone argument (Ripser paper p.412) only needs symmetry of d' and the flag property, both of which hold here -- see .claude/WORKLOG-witness-complex.md.

Vertex ids in every emitted Simplex[Int] are LOCAL landmark indices (0 until landmarks.size) -- translate back through landmarks(i) for the caller's own ambient point cloud (matlab.TDA4j does this for cycleVertices).

Attributes

Experimental: true
Supertypes: class RipserCofaceSimplexStream

class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Attributes

Experimental: true
Supertypes: trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Hides every cell of dimension > maxDim from stream -- the Cube analogue of LimitedCofaceSimplexStream (SimplexStream.scala), needed because that class is hardcoded to CofaceSimplexStream[Int, Double] and doesn't fit Cube at all. Used by homology.FastCubicalHomologyContext's own d >= 3 path (.claude/DESIGN-fast-engines-hybrid-middle-dimensions.md) to hand CellularPersistenceInChunksContext a view of the grid that never contains a real top-dimensional cell, so that engine's own general Chain reduction never touches them -- the whole point being to let the (cheaper) dual union-find handle the top dimension instead.

Delegates filtrationOrdering/filtrationValue to stream unchanged (removing higher-dimensional cells from the DOMAIN doesn't change either), and preserves StratifiedCellStream.iterator's own contiguous-from-0 contract for free: truncating a contiguous 0..stream.ambientDim domain to 0..maxDim is still contiguous from 0.

Attributes

Experimental: true
Supertypes: trait DoubleFiltration[Cube]

trait StratifiedCellStream[Cube, Double]

trait CellStream[Cube, Double]

trait IterableOnce[Cube]

trait Filtration[Cube, Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Attributes

Experimental: true
Supertypes: trait Iterator[Simplex[Int]]

trait IterableOnceOps[Simplex[Int], Iterator, Iterator[Simplex[Int]]]

trait IterableOnce[Simplex[Int]]

class Object

trait Matchable

class Any
Show all

A third, independent Vietoris-Rips coface-enumeration strategy, built on a recursive stack and spatial (VP-tree) neighbor query rather than SimplexIndexing's combinatorial-number-system enumeration. A cross-validation baseline for the canonical VR streams, not a speed-competitive production engine in its own right.

Attributes

Experimental: true
Supertypes: trait DoubleFiltration[Simplex[Int]]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Attributes

Experimental: true
Supertypes: class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all
Known subtypes: class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream
Show all

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: SheehyRipsSimplexStream.type

The linear-size approximate/sparse Vietoris-Rips filtration of Cavanna, Jahanseir & Sheehy, "A Geometric Perspective on Sparse Filtrations" (arXiv:1506.03797, CCCG 2015) -- checked directly against the paper's own Definitions/Algorithm 1-4 and Lemma 1/Corollary 2/Theorem 5 (.claude/WORKLOG-sheehy-rips.md has the fetched PDF pages and the derivation). This is the GREEDY-PERMUTATION reformulation of Sheehy's original net-tree-based construction (D.R. Sheehy, "Linear-Size Approximations to the Vietoris-Rips Filtration," Discrete & Computational Geometry 49(4), 2013, arXiv:1203.6786) -- simpler to implement correctly and to verify, at the cost of the two papers' own epsilon parameters NOT being directly comparable (Sheehy 2013's approximation factor is 1/(1-2*epsilon); this class's, following CJS 2015, is (1+epsilon)).

'''What this buys you''': a filtration whose persistence barcode is a genuine (1+epsilon)-multiplicative approximation (Theorem 5) to the plain Vietoris-Rips barcode, built from a complex whose SIZE is linear in n (CJS 2015 Lemma 6/7/Theorem 9/10) for point sets of bounded doubling dimension -- dramatically fewer simplices to reduce than plain VR at the same scale range, in exchange for a controlled, quantified loss of precision.

'''What this class does NOT do''': the paper's own O(n log n) algorithm (Section 5, Algorithms 1-4) builds the edges of the sparse filtration directly from the greedy permutation's neighbor structure, touching only kappa^O(d) candidates per point. This class instead computes every pairwise edgeBirth directly (O(n^2), like plain VietorisRips/RipserCofaceSimplexStream's own default candidate enumeration) and lets RipserCofaceSimplexStream's ordinary combinatorial coface generation do the rest. The payoff here is a SMALLER complex to reduce, not a faster one to build -- see the class doc's own honest framing on this point in every other "not the fastest construction" case in this codebase (Cech, Witness, alpha).

==The construction==

Given a greedy permutation (streams.GreedyPermutation, computed by LandmarkSelector.maxmin run to numLandmarks = ambientMetricSpace.size) with insertion radii lambda_p (lambda of the very first point is Double.PositiveInfinity by convention -- it must never be pruned away, since it anchors the whole construction), and a sparsity parameter epsilon in (0,1):

each point p's ball radius at scale alpha is r_p(alpha) := min(alpha, lambda_p*(1+epsilon)/epsilon) (CJS 2015 Section 3) -- grows with alpha until it saturates;
p's ball becomes and stays EMPTY once alpha > lambda_p*(1+epsilon)^2/epsilon (vanish(p) below) -- no new simplex may use p past that scale, though the filtration itself never removes anything already present (S^alpha := union_{delta = 1) is born at max over its own edges' birth times, PROVIDED that value is <= min_{p in sigma} vanish(p) -- otherwise it never appears at all (CJS 2015 Section 5.3, "SimplexBirthTime" -- the max/min intersection is valid because balls are convex and pairwise-intersecting convex sets have a common intersection, the same Helly-type fact that makes plain Rips itself a flag/nerve complex).

'''A real gap in CJS 2015's own Algorithm 3, verified, not just suspected''': that algorithm computes an edge's birth from only the TWO endpoints' own thresholds, with no check against vanish -- but Section 5.3's own SimplexBirthTime definition (the general k-simplex rule above) requires exactly that check, and an edge is simply its k=1 case, not a special one. Two independent counterexamples confirm this is a real gap in the published algorithm, not an artifact of skipping its neighbor-search prefilter: epsilon=1, lambda_p=1, lambda_q=10, d=10 (raw formula gives 8, but p vanishes at 4); and, checked directly against the paper's OWN Lemma 6/7 neighbor bound (kappa = (epsilon^2+3*epsilon+2)/epsilon, d(p_i,p_j) <= kappa*2^ceil(lg lambda_i) puts p_j in p_i's own candidate neighbor list), epsilon=1, lambda_p=1.1, lambda_q=10, d=10 -- this pair passes the paper's own restricted neighbor search AND its Algorithm 3 (returning 7.8), while p vanishes at 4.4. Whether the paper's full O(n log n) pipeline compensates for this some other way was not checked; only the gap itself was verified. edgeBirth here applies the vanish clamp Section 5.3 describes to every edge, not just higher simplices.

'''Units''': every OTHER stream in this codebase records filtration values in "diameter" units (an edge's own value is the raw ambient distance, not half of it) -- but CJS 2015's own alpha is a RADIUS parameter (R_alpha := {J : max d(p,q) <= 2*alpha}; their own Algorithm 3 literally returns d/2 in its first branch). Every output this class reports -- edgeBirth's return value and vanish -- is therefore the paper's own value DOUBLED, never lambda itself (an ordinary ambient distance already in diameter-comparable units, entering the formulas unchanged). After doubling, the first (unsparsified) branch collapses to exactly d, matching plain VR's own edge value -- a useful internal sanity check, exercised directly by SheehyRipsStreamSpec's "reduces to plain VR" fixture.

'''maxFiltrationValue''' is always clamped to maxFiniteFiltrationValue -- the largest FINITE simplex birth this construction can ever produce (an honest, data-dependent bound: any finite simplex's value is a max over its own edges, so the largest finite EDGE birth bounds every finite simplex) -- REGARDLESS of what the caller passes (None resolves to exactly that bound; an explicit Some(x) is min(x, maxFiniteFiltrationValue)). This is deliberately NOT metricSpace.minimumEnclosingRadius (this is not a cone construction -- an edge to the anchor point can be unboundedly large, so no point has a finite max distance to every other point), and the clamp is unconditional rather than only a None-default specifically so that an explicit Some(Double.PositiveInfinity) -- how every other stream in this codebase spells "untruncated" -- stays safe here too: keptByThresholdAndCriterion's own <= comparison is plain IEEE-754 Double comparison, under which Double.PositiveInfinity <= Double.PositiveInfinity is true, so an UNCLAMPED literal infinite threshold would silently readmit every simplex this construction is supposed to exclude forever.

'''Not a diameter-only construction''': unlike plain VR (and like the general, non-flag WitnessCofaceSimplexStream and DtmRipsSimplexStream), a simplex's value here is not simply the maximum ambient pairwise distance among its vertices, so matlab.TDA4j refuses engine=ripser for this complex (both Ripser engines' incremental insertionDiameter/apparent-pairs machinery assume the filtration functional literally IS MaximumDistanceFiltrationValue on the metric space handed to them). naive/chunks/cohomology all consume it like any other CofaceSimplexStream[Int, Double]; chunks is cross-validated fresh against naive (SheehyRipsStreamSpec), not assumed to carry over.

Attributes

Companion: object
Experimental: true
Supertypes: class RipserCofaceSimplexStream

class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Attributes

Companion: object
Experimental: true
Supertypes: trait Serializable

trait Product

trait Equals

class Object

trait Matchable

class Any
Show all

Attributes

Companion: class
Experimental: true
Supertypes: trait Product

trait Mirror

class Object

trait Matchable

class Any
Self type: SimplexEdge.type

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: SimplexIndexing.type

Attributes

Companion: object
Experimental: true
Supertypes: class Object

trait Matchable

class Any

Abstract trait for representing a sequence of simplices.

Type parameters

FiltrationT: Type of the filtration values.
VertexT: Type of vertices of the contained simplices.

Attributes

Todo: We may want to change this to inherit instead from IterableOnce[Simplex[VertexT]], so that a lazy computed simplex stream can be created and fit in the type hierarchy.
Companion: object
Experimental: true
Supertypes: trait CellStream[Simplex[VertexT], FiltrationT]

trait IterableOnce[Simplex[VertexT]]

trait Filtration[Simplex[VertexT], FiltrationT]

trait Filterable[FiltrationT]

class Object

trait Matchable

class Any
Show all
Known subtypes: class ExplicitStream[VertexT, FiltrationT]

Attributes

Companion: trait
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: SimplexStream.type

Adapts a FiniteSimplicialSet[G] into the CellStream[G, Int] the existing homology engines actually require (CellularHomologyContext takes a stream: CellStream[CellT, FiltrationT], never a bare OrderedCell -- confirmed by reading Homology.scala). Every generator sits at the same nominal filtration value 0: this is ordinary (unfiltered) homology of one fixed finite simplicial set, not real persistence -- the adapter exists only because the engine has no entry point that skips the stream interface.

filtrationOrdering is Ordering.by(dimOf) ascending, then ord as tiebreak -- traced from Homology.scala's own CellularHomologyContext.HomologyState.processingOrder derivation comment (the reverted first attempt at that comparator used filtrationOrdering.reverse wholesale and got faces-before-cofaces backwards precisely because filtrationOrdering itself already sorts smaller dimension as smaller, un-negated): this matches that established convention exactly, not a fresh interpretation for this new case. With every generator's filtration value tied, processingOrder collapses to exactly this ascending-dimension order, so it alone determines faces-before-cofaces here.

G is OrderedCell is threaded explicitly (via the companion apply) rather than resolved as an ambient global given: unlike Simplex/Cube, a FiniteSimplicialSet's OrderedCell instance depends on that one simplicial set's own faces data, not on G alone, so it cannot be a single global instance for a given G.

Attributes

Companion: object
Experimental: true
Supertypes: trait CellStream[G, Int]

trait IterableOnce[G]

trait Filtration[G, Int]

trait Filterable[Int]

class Object

trait Matchable

class Any
Show all

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: SimplicialSetStream.type

****** Sparse Metric Spaces and the Dory storage *******

Attributes

Experimental: true
Supertypes: trait FiniteMetricSpace[VertexT]

class Object

trait Matchable

class Any

******* Efficient Spatial Queries *******

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any
Known subtypes: class BruteForce[VertexT]

class JVPTree[VertexT]

Attributes

Experimental: true
Supertypes: trait CellStream[CellT, FiltrationT]

trait IterableOnce[CellT]

trait Filtration[CellT, FiltrationT]

trait Filterable[FiltrationT]

class Object

trait Matchable

class Any
Show all
Known subtypes: class CubicalGridStream

class ExplicitCubicalStream

class FilteredSimplicialSetStream[G]

class LimitedCubicalGridStream

trait StratifiedSimplexStream[VertexT, FiltrationT]

class AlphaShapes

class AlphaComplexDQPStream

class AlphaShapeDQP

class HelixDelaunay

class LimitedAlphaShapesStream

trait CofaceSimplexStream[VertexT, FiltrationT]

class EnumeratingCofaceSimplexStream

class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream

class LimitedCofaceSimplexStream

class RecursiveStackVietorisRipsSimplexStream
Show all

Attributes

Experimental: true
Supertypes: trait StratifiedCellStream[Simplex[VertexT], FiltrationT]

trait CellStream[Simplex[VertexT], FiltrationT]

trait IterableOnce[Simplex[VertexT]]

trait Filtration[Simplex[VertexT], FiltrationT]

trait Filterable[FiltrationT]

class Object

trait Matchable

class Any
Show all
Known subtypes: class AlphaShapes

class AlphaComplexDQPStream

class AlphaShapeDQP

class HelixDelaunay

class LimitedAlphaShapesStream

trait CofaceSimplexStream[VertexT, FiltrationT]

class EnumeratingCofaceSimplexStream

class IncrementalVietorisRipsSimplexStream

class InorderCofaceSimplexStream

class RipserCofaceSimplexStream

class CechCofaceSimplexStream

class DowkerCofaceSimplexStream

class DtmRipsSimplexStream

class LazyWitnessSimplexStream

class SheehyRipsSimplexStream

class WitnessCofaceSimplexStream

class LimitedCofaceSimplexStream

class RecursiveStackVietorisRipsSimplexStream
Show all

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any

Attributes

Companion: class
Experimental: true
Supertypes: class Object

trait Matchable

class Any
Self type: WitnessCofaceSimplexStream.type

The general witness complex (De Silva & Carlsson 2004; JavaPlex's plain WitnessStream): unlike the lazy variant above, NOT a flag complex -- a higher simplex's own witness condition uses a DIMENSION-SPECIFIC threshold m_k (the (k+1)-th nearest landmark, k = the simplex's own dimension) that need not be monotone facet-to-coface on its own, so every simplex's recorded filtration value is max(own_k(sigma), max over its own facets' filtration values) (JavaPlex's own addCofaces_: filtrationIndex = max(filtrationIndex, ...) over the boundary, then maxed again with the simplex's own witness value). This recursive max is what makes "the complex at threshold R" automatically downward-closed for every R -- the same way VR's own "max pairwise distance" does -- and it also makes JavaPlex's separate containsElement(face) gate redundant here (any facet whose own value exceeds a threshold forces its coface's value above that threshold too, via the max): see .claude/WORKLOG-witness-complex.md for the proof. So, unlike the eager reference implementation, RipserCofaceSimplexStream's plain "generate from the canonical (min-vertex-removed) facet, filter by filtrationValue <= threshold" shape is already correct once fed this recursive filtration value -- no extra "are all my facets already accepted" check needed.

nu plays no role here (each dimension has its own fixed m_k, not a caller-chosen parameter) -- the WitnessMetricSpace handed to the superclass exists only to satisfy RipserCofaceSimplexStream's constructor; its distance is never actually read (see that class's own "lazy, not eager" note), since filtrationValueOverride replaces filtrationValue for every dimension including edges, and maxFiltrationValue is always supplied explicitly (default +Infinity, i.e. untruncated) rather than left None -- None would fall back to minimumEnclosingRadius, NOT a valid truncation for a non-flag complex like this one (see .claude/WORKLOG-witness-complex.md).

'''Fact used to cross-validate against the lazy stream''' (WitnessStreamSpec): this class's own 1-skeleton is IDENTICAL to LazyWitnessSimplexStream(..., nu = 2)'s -- both use the 2nd-nearest-landmark threshold for edges (m_1 here, m_nu there with its sentinel-shifted index), reached via different code paths.

Built via the companion apply (below), not new, so the shared WitnessGeometry (O(L*N) to build) is computed exactly once and reused both for the superclass's WitnessMetricSpace and for recursiveFiltrationValue -- constructing it twice from raw (ambientMetricSpace, landmarks) would silently duplicate that work.

'''Performance hazard, standing for any unbounded coface stream, not specific to this one''': iterating this stream at its default maxFiltrationValue = +Infinity enumerates EVERY dimension up to landmarks.size - 1 -- the full 2^L power set for L landmarks, since nothing about the recursive filtration value ever prunes a candidate at an unbounded threshold. matlab.TDA4j's own facade avoids this by always wrapping in LimitedCofaceSimplexStream (its maxDimension option defaults to reporting H_0..H_2, i.e. simplices up to 4 vertices); a caller driving this class directly should do the same, or pass a finite maxFiltrationValue -- see .claude/WORKLOG-witness-complex.md for tutorial-scale timing measurements (machine-specific, kept there rather than here).

Attributes

Companion: object
Experimental: true
Supertypes: class RipserCofaceSimplexStream

class EnumeratingCofaceSimplexStream

trait DoubleFiltration[Simplex[Int]]

trait CofaceSimplexStream[Int, Double]

trait StratifiedSimplexStream[Int, Double]

trait StratifiedCellStream[Simplex[Int], Double]

trait CellStream[Simplex[Int], Double]

trait IterableOnce[Simplex[Int]]

trait Filtration[Simplex[Int], Double]

trait Filterable[Double]

class Object

trait Matchable

class Any
Show all

Precomputes and exposes the landmarkwitness distance geometry a witness complex is built from (De Silva & Carlsson 2004; checked against JavaPlex's own WitnessStream/LazyWitnessStream -- see .claude/WORKLOG-witness-complex.md). Every point of ambientMetricSpace is a witness (landmarks included, matching JavaPlex's own plex3Compatible = true default), and landmarks is a subset of ambientMetricSpace's own ambient indices -- LOCAL landmark index i (0 until landmarks.size) corresponds to ambient index landmarks(i). Assumes ambientMetricSpace.elements == 0 until ambientMetricSpace.size (see LandmarkSelector's own doc for why that's not a new assumption).

D(l)(n) is the distance from landmark l (local index) to witness n (ambient index) -- built once, eagerly: an L x N matrix, exactly JavaPlex's own D. O(L*N) space/time, unavoidable since the witness-value formula below reads a whole row per candidate landmark.

Attributes

Experimental: true
Supertypes: class Object

trait Matchable

class Any

The lazy witness complex's own 1-skeleton (De Silva & Carlsson 2004; JavaPlex's LazyWitnessStream), reified as a FiniteMetricSpace[Int] over LOCAL landmark indices so it slots directly into RipserCofaceSimplexStream unchanged (LazyWitnessSimplexStream below) -- the lazy witness complex IS, by definition, the flag/clique complex of this weighted graph (JavaPlex's own LazyWitnessStream derives from FlagComplexStream for exactly this reason), so distance(a,b) here doubles as both the edge filtration value AND (via the inherited MaximumDistanceFiltrationValue "max pairwise distance" formula) every higher simplex's filtration value too -- no filtrationValueOverride needed anywhere.

'''Not a real metric''': distance can be zero for two distinct landmarks (whenever some witness sees both within its own m_nu threshold) and need not obey the triangle inequality. NEVER hand this to JVPTree, SparseMetricSpace, RecursiveStackVietorisRipsSimplexStream, or anything in the alpha package -- only to EnumeratingCofaceSimplexStream/RipserCofaceSimplexStream's own combinatorial (not spatial) candidate generation, which assumes neither property.

nu (JavaPlex's own name) selects the per-witness threshold m_nu: 0 means no threshold (m = 0 everywhere -- the strictest/smallest complex), 1 the nearest-landmark distance, 2 (JavaPlex's own default) the 2nd-nearest. Capped at [0, 2], matching JavaPlex's own verifyLessThan(nu, 3) -- beyond nu = 2 the per-witness clamp stops being a no-op for every landmark pair, an unstudied regime this class deliberately doesn't offer (see .claude/WORKLOG-witness-complex.md).

Attributes

Experimental: true
Supertypes: trait FiniteMetricSpace[Int]

class Object

trait Matchable

class Any

org.appliedtopology.tda4j.streams

Members list

Type members

Experimental classlikes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Value parameters

Attributes

Attributes

Attributes

Attributes

Value parameters

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Type parameters

Attributes

Attributes

Attributes

Attributes

Type parameters

Value parameters

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Type parameters

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes