Topological Data Analysis

The module topology implements Vietoris–Rips persistent homology and the bottleneck distance between persistence diagrams.

Vietoris–Rips Filtration

For a finite point cloud \(X = \{x_1, \dots, x_n\} \subset \mathbb{R}^d\) and scale \(\varepsilon \ge 0\), the Vietoris–Rips complex is

\[\mathrm{VR}_\varepsilon(X) \;=\; \big\{ \sigma \subseteq X : \mathrm{diam}(\sigma) \le \varepsilon \big\}.\]

Increasing \(\varepsilon\) yields a filtration; the persistent homology of this filtration produces, for each homological degree \(k\), a multiset of birth/death pairs

\[D_k(X) = \big\{ (b_i, d_i) : 0 \le b_i < d_i \le \infty \big\}.\]

Persistence Algorithm

The boundary matrix \(\partial\) is built over \(\mathbb{Z}/2\) and reduced left-to-right: for each column \(j\) we cancel its lowest entry by adding any earlier column with the same low. Pairs \((\mathrm{low}(j), j)\) give birth/death pairs.

Bottleneck Distance

For two diagrams \(D\) and \(D'\),

\[d_B(D, D') \;=\; \inf_{\eta : D \to D'}\; \sup_{x \in D}\, \|x - \eta(x)\|_\infty,\]

where matchings may pair points with the diagonal \(\Delta = \{(t, t) : t \ge 0\}\) at cost \((d - b)/2\).

The implementation binary-searches the threshold \(\varepsilon\) and certifies a perfect matching by Hopcroft–Karp on the bipartite graph of admissible edges.

API

pub struct PersistencePair { pub dim: usize, pub birth: f64, pub death: f64 }
pub struct PersistenceDiagram { pub pairs: Vec<PersistencePair> }

pub fn vietoris_rips_filtration(points: &[Vec<f64>], max_dim: usize, max_eps: f64)
    -> Result<Vec<Simplex>>;
pub fn persistent_homology(points: &[Vec<f64>], max_dim: usize, max_eps: f64)
    -> Result<PersistenceDiagram>;
pub fn bottleneck_distance(d1: &[PersistencePair], d2: &[PersistencePair])
    -> Result<f64>;