TDA4j
API
Generated with
TDA4j/org.appliedtopology.tda4j/org.appliedtopology.tda4j.alpha

org.appliedtopology.tda4j.alpha

package org.appliedtopology.tda4j.alpha

Members list

Type members

Experimental classlikes

final class AlphaComplexDQP(val space: PowerDistance, val maxPower: Double, val maxDimension: Int, cellsByDim: IndexedSeq[IndexedBuffer[Simplex[Int]]], weights: HashMap[Simplex[Int], Double], witnesses: HashMap[Simplex[Int], Array[Double]])

A computed weighted alpha complex.

A computed weighted alpha complex.

Simplices are Simplex[Int] of site indices in increasing order. cells is in a valid filtration order: faces always precede cofaces.

Attributes

Companion
object
Experimental
true
Supertypes
class Object
trait Matchable
class Any
object AlphaComplexDQP

Attributes

Companion
class
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
class AlphaComplexDQPBuilder(val space: PowerDistance, val maxPower: Double, val maxDimension: Int, val settings: AlphaDQPSettings = ...)

Algorithm 1: compute the d-skeleton of Alpha(S, p, a1).

Algorithm 1: compute the d-skeleton of Alpha(S, p, a1).

Outer loop over dimension, inner loop over base vertex. B and U are built once per (dimension, vertex) rather than once per simplex, which is the only place ambient dimension enters the cost at all.

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
final class AlphaComplexDQPException(message: String) extends RuntimeException

Thrown when the inner QP fails to converge. In practice this means a genuinely near-degenerate configuration (see the rankTolerance doc on AlphaDQPSettings and WORKLOG.md at the repo root for the full derivation) -- not simply "too tight a tolerance", since no fixed tolerance safely eliminates every such case. Loosening AlphaDQPSettings may help but isn't guaranteed to; AlphaComplexDQPBuilder.solveAtVertex already catches this per-candidate (excluding just that candidate, logged to stderr) so it should only reach a caller from a direct DualQP.solve call.

Thrown when the inner QP fails to converge. In practice this means a genuinely near-degenerate configuration (see the rankTolerance doc on AlphaDQPSettings and WORKLOG.md at the repo root for the full derivation) -- not simply "too tight a tolerance", since no fixed tolerance safely eliminates every such case. Loosening AlphaDQPSettings may help but isn't guaranteed to; AlphaComplexDQPBuilder.solveAtVertex already catches this per-candidate (excluding just that candidate, logged to stderr) so it should only reach a caller from a direct DualQP.solve call.

Attributes

Experimental
true
Supertypes
class RuntimeException
class Exception
class Throwable
trait Serializable
class Object
trait Matchable
class Any
Show all
class AlphaComplexDQPStream(val points: Array[Array[Double]], val alphaComplexDQP: AlphaComplexDQP) extends AlphaShapes

Wraps an ALREADY-BUILT AlphaComplexDQP (any space/maxPower/maxDimension, e.g. AlphaComplexDQP.dtm's DTM-weighted output, or a radius-truncated .weighted/.euclidean call) as an AlphaShapes stream -- the exact same iterateDimension/filtrationOrdering/filtrationValue shape AlphaShapeDQP uses for its own always-untruncated, always-unweighted build, just parameterized over a caller-supplied one instead of building a fresh untruncated AlphaComplexDQP.euclidean internally. points is needed only to satisfy AlphaShapes's own metricSpace contract (unused by homology engines, see that trait's doc); it must be the SAME points alphaComplexDQP was built from.

Wraps an ALREADY-BUILT AlphaComplexDQP (any space/maxPower/maxDimension, e.g. AlphaComplexDQP.dtm's DTM-weighted output, or a radius-truncated .weighted/.euclidean call) as an AlphaShapes stream -- the exact same iterateDimension/filtrationOrdering/filtrationValue shape AlphaShapeDQP uses for its own always-untruncated, always-unweighted build, just parameterized over a caller-supplied one instead of building a fresh untruncated AlphaComplexDQP.euclidean internally. points is needed only to satisfy AlphaShapes's own metricSpace contract (unused by homology engines, see that trait's doc); it must be the SAME points alphaComplexDQP was built from.

Attributes

Experimental
true
Supertypes
class AlphaShapes
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
final case class AlphaDQPSettings(rankTolerance: Double = ..., feasibilityTolerance: Double = ..., zeroTolerance: Double = ..., equalityTolerance: Double = ..., maxIterationsPerQP: Int = ..., workingSetCapacity: Int = ..., enforceMonotonicity: Boolean = ..., parallel: Boolean = ..., verbose: Boolean = ...)

All tolerances are relative; absolute ones silently break when the point cloud is rescaled.

All tolerances are relative; absolute ones silently break when the point cloud is rescaled.

Value parameters

enforceMonotonicity

clamp each w(sigma) up to the max over its facets. Mathematically a no-op (see below) but removes ~1e-16 violations that would upset a persistence algorithm.

equalityTolerance

consistency threshold for dependent equality constraints (relative to max|U|).

feasibilityTolerance

a constraint counts as violated when its slack exceeds this fraction of max|U|.

maxIterationsPerQP

iteration cap per QP; 0 means 20n + 200.

parallel

run the per-vertex loop on the common ForkJoinPool. Output is deterministic.

rankTolerance

a candidate constraint is treated as linearly dependent on the working set when its Schur complement drops below this fraction of B_jj. 1e-12 is too tight to be safe: a commit can clear that bar while still leaving a Cholesky pivot many orders of magnitude below the problem's natural scale, which silently poisons the factorisation and manifests later as either non-convergence (degenerate cycling between near-duplicate working sets) or, worse, a garbage-but-finite answer. 1e-8 (the textbook sqrt-of-machine-epsilon rule of thumb) is still not always enough margin in practice -- found a case where the poisoning commit's ratio was 1.03e-8, clearing that bar by a hair. 1e-6 sits in the middle of the empirically-verified safe range [1e-7, 1e-5]: 1e-4 starts rejecting genuinely non-degenerate directions and gives a different (wrong) answer.

verbose

print a diagnostic to stderr each time a candidate is dropped for QP non-convergence (see solveAtVertex's "defense in depth" comment). Off by default: this is an accepted, recurring limitation of the active-set method on near-degenerate configurations, not an actionable-every-time event, so a caller running many builds (e.g. a property test) would otherwise get stderr spam proportional to trial count rather than a signal worth reading.

workingSetCapacity

max active set size; 0 means "ambient dimension + 2", which is a hard bound since the active rows live in R^m. Raise it only if you hit the corresponding exception.

zeroTolerance

threshold on multipliers in the ratio tests.

Attributes

Experimental
true
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
class AlphaShapeDQP(val points: Array[Array[Double]]) extends AlphaShapes

Attributes

Experimental
true
Supertypes
class AlphaShapes
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
abstract class AlphaShapes extends StratifiedSimplexStream[Int, Double], DoubleFiltration[Simplex[Int]]

Attributes

Companion
object
Experimental
true
Supertypes
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
object AlphaShapes

apply/Point are scoped here rather than as bare top-level alpha package defs (a generic name like Point, or a dispatch function as central as Alpha used to be, is exactly the kind of top-level-name collision hazard documented elsewhere in this codebase) -- callers write AlphaShapes(points, dispatch). import AlphaShapes.Point below brings both the type and its factory back into unqualified scope for the rest of this file, where Point is used pervasively by Hyperplane/Hypersphere/HelixDelaunay.

apply/Point are scoped here rather than as bare top-level alpha package defs (a generic name like Point, or a dispatch function as central as Alpha used to be, is exactly the kind of top-level-name collision hazard documented elsewhere in this codebase) -- callers write AlphaShapes(points, dispatch). import AlphaShapes.Point below brings both the type and its factory back into unqualified scope for the rest of this file, where Point is used pervasively by Hyperplane/Hypersphere/HelixDelaunay.

Attributes

Companion
class
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
final class CholeskyWorkspace(capacity: Int)

Maintains a Cholesky factor of B_W for the current working set W.

Maintains a Cholesky factor of B_W for the current working set W.

The working set is kept linearly independent, so B_W stays positive definite and a plain Cholesky suffices; DAQP uses LDL^T so that it can represent the singular step, we instead detect it via the Schur complement and restructure the working set immediately (see DualQP).

Appending is the standard bordered update; deleting removes a row of L and rotates the resulting extra superdiagonal away with Givens rotations, which is O(|W|²) rather than a refactorisation.

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
case class DelaunaySimplex(simplex: Simplex[Int], circumsphere: Hypersphere)

Attributes

Experimental
true
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
final class DualQP(val n: Int, workingSetCapacity: Int, settings: AlphaDQPSettings)

Solves

Solves

maximise d(lambda) = -1/2 lambda^t B lambda + U^t lambda subject to lambda_i >= 0 for i not in J

which is the Lagrangian dual of Eq. (9) with H = I. Optimum equals the primal optimum c* = 1/2 ||y* - x||^2; the primal solution is recovered from the KKT conditions (12) as y* = x - sum_i lambda_i (x_i - x).

Reused across every candidate simplex sharing the same base vertex x -- only J changes, which is exactly the observation in the paper that lets B and U be assembled once per vertex rather than once per simplex.

The instance is stateful and not thread safe; give each worker its own.

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
final case class Epsilon(epsilon: Double)

A numerical tolerance, threaded via using through Hyperplane.from/Hypersphere/HelixDelaunay's internal geometric comparisons (near-zero singular values, near-zero circumsphere margins). Deliberately NOT a package- level given (the earlier shape here): Hyperplane/Hypersphere/HelixDelaunay are never constructed from outside this file (every external caller goes through AlphaShapes.apply below), so the one default value this codebase actually uses only needs to live on apply's own using parameter -- an ordinary default value, not an ambient given every file that happens to wildcard-import alpha.{given, *} would otherwise pick up silently.

A numerical tolerance, threaded via using through Hyperplane.from/Hypersphere/HelixDelaunay's internal geometric comparisons (near-zero singular values, near-zero circumsphere margins). Deliberately NOT a package- level given (the earlier shape here): Hyperplane/Hypersphere/HelixDelaunay are never constructed from outside this file (every external caller goes through AlphaShapes.apply below), so the one default value this codebase actually uses only needs to live on apply's own using parameter -- an ordinary default value, not an ambient given every file that happens to wildcard-import alpha.{given, *} would otherwise pick up silently.

Attributes

Experimental
true
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object HelixDelaunay

Attributes

Companion
class
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
class HelixDelaunay(pts: Array[Array[Double]], seed: Long = ..., requireValidTriangulation: Boolean = ...)(using epsilon: Epsilon) extends AlphaShapes

Based on https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10917453&tag=1

Based on https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10917453&tag=1

'''Accepted limitation''': near-cospherical clusters make the frontier walk order-dependent (~1/170 at ambient dimension 4, 20-30 points) -- a real fix needs joint near-tie detection, not attempted here. So Helix is not reliable ground truth for dimension >= 4 fuzzing (AlphaCrossValidationSpec's comparisons stay as unsafeCompare/unsafeFuzzCompare diagnostics, not wired into sbt test). seed makes a given (pts, seed) pair deterministic, but does not remove this order-dependency -- see HelixDelaunayBuilder's own doc.

Value parameters

pts

the input points to triangulate

requireValidTriangulation

OFF by default -- changes nothing above when false. When true, and compute() produces a facet- multiplicity violation (FastAlphaHomologyContext's own precondition), runs HelixDelaunay.repairByJitterRetriangulation (.claude/DESIGN-helix-triangulation-repair.md): a "simulation of simplicity"-style repair that nudges exactly the offending, near-tied points by a tiny random perturbation and re-runs this SAME HelixDelaunayBuilder on the full (mostly unperturbed) point set, then recomputes every resulting simplex's own circumsphere from the ORIGINAL, un-nudged coordinates so the perturbation never leaks into a real filtration value -- only into the combinatorial tie-break, plus a direct check that the repaired result has no interior gap (see that method's own doc for why the facet-count check alone was found insufficient). Two other designs (discarding the conflicting region and re-filling it via coning from an arbitrary apex; discarding the extra claimants outright with no replacement) were tried first and rejected after being checked against the actual failing fixture -- see the design note's own "First"/"Second design attempt (rejected)" sections. Validated by targeted stress sweep at d=2 and d=3 (FastAlphaHomologyContext's own primary use case); d>=4 is untested -- HelixDelaunayBuilder itself is already "not reliable ground truth" there for unrelated reasons (this class's own doc above), so this repair inherits that pre-existing limitation rather than introducing a new one.

seed

seeds the bootstrap frontier-selection shuffle (HelixDelaunayBuilder); same pts and seed always produce the same triangulation.

Attributes

Companion
object
Experimental
true
Supertypes
class AlphaShapes
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
case class Hyperplane(normal: Point, offset: Double)

Attributes

Companion
object
Experimental
true
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object Hyperplane

Attributes

Companion
class
Experimental
true
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
Hyperplane.type
case class Hypersphere(center: Point, radius: Double)(using epsilon: Epsilon)

Attributes

Companion
object
Experimental
true
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object Hypersphere

Attributes

Companion
class
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
class LimitedAlphaShapesStream(helix: HelixDelaunay, maxDim: Int) extends StratifiedSimplexStream[Int, Double], DoubleFiltration[Simplex[Int]]

Hides every simplex of dimension > maxDim from helix -- the HelixDelaunay analogue of streams.LimitedCubicalGridStream (itself needed because streams.LimitedCofaceSimplexStream is hardcoded to CofaceSimplexStream[Int, Double], which AlphaShapes/HelixDelaunay is not -- it's the smaller StratifiedSimplexStream[Int, Double], with no currentDimension/keepCriterion/etc. to forward). Used by homology.FastAlphaHomologyContext's own d >= 3 path (.claude/DESIGN-fast-engines-hybrid-middle-dimensions.md) to hand CellularPersistenceInChunksContext a view of the triangulation that never contains a real top-dimensional simplex, 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.

Hides every simplex of dimension > maxDim from helix -- the HelixDelaunay analogue of streams.LimitedCubicalGridStream (itself needed because streams.LimitedCofaceSimplexStream is hardcoded to CofaceSimplexStream[Int, Double], which AlphaShapes/HelixDelaunay is not -- it's the smaller StratifiedSimplexStream[Int, Double], with no currentDimension/keepCriterion/etc. to forward). Used by homology.FastAlphaHomologyContext's own d >= 3 path (.claude/DESIGN-fast-engines-hybrid-middle-dimensions.md) to hand CellularPersistenceInChunksContext a view of the triangulation that never contains a real top-dimensional simplex, 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 helix unchanged (removing higher-dimensional simplices from the DOMAIN doesn't change either), and preserves StratifiedCellStream.iterator's own contiguous-from-0 contract for free: truncating a contiguous 0..helix.ambientDimension domain to 0..maxDim is still contiguous from 0.

Attributes

Experimental
true
Supertypes
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
object PowerDistance

Attributes

Companion
trait
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
trait PowerDistance

The data the algorithm needs: a finite set of sites with power weights.

The data the algorithm needs: a finite set of sites with power weights.

Everything in the QP is expressible through squared distances alone, because

B_ij = (x_i - x)·(x_j - x) = ( d²(i,x) + d²(j,x) - d²(i,j) ) / 2 U_i = ( p(i) - p(x) - d²(i,x) ) / 2

so the solver never sees coordinates. Coordinates are optional and used only to materialise the witness map Phi (Definition 11).

Caveat: the QP is convex only if B is positive semidefinite, i.e. only if the squared distances come from a Euclidean embedding. Feeding in a non-Euclidean metric (as Vietoris-Rips happily allows) is not supported; the notion of "alpha complex" is not defined there either.

Attributes

Companion
object
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
Generated with