pulsatrix 1.1.0
Loading...
Searching...
No Matches
h0.hpp File Reference

H0 persistence, the clusters of a point cloud across scales, from its minimum spanning tree. More...

#include <cstdint>
#include <vector>
#include "pulsatrix/tda/distance_matrix.hpp"
#include "pulsatrix/tda/persistence_diagram.hpp"
Include dependency graph for h0.hpp:

Go to the source code of this file.

Classes

struct  pulsatrix::MstEdge
 One edge of a minimum spanning tree. More...
 
struct  pulsatrix::H0Result
 ComputeH0()'s result. More...
 

Namespaces

namespace  pulsatrix
 

Functions

H0Result pulsatrix::ComputeH0 (const DistanceMatrix &distances)
 H0 persistence of the Vietoris-Rips filtration on the given distances.
 
std::vector< int64_t > pulsatrix::SingleLinkageClusters (const std::vector< MstEdge > &edges, int64_t points, double threshold)
 The clusters of single linkage cut at a scale: points joined by tree edges no longer than threshold share a label.
 

Detailed Description

H0 persistence, the clusters of a point cloud across scales, from its minimum spanning tree.

In the Vietoris-Rips filtration every point is a component at scale 0, and two components merge when the shortest edge between them appears. That is single-linkage clustering, and the merge scales are the edge lengths of a minimum spanning tree (Carlsson and Memoli, JMLR 2010, show single linkage is the one stable clustering of this kind). So H0 needs no boundary matrices: Prim's algorithm on the distance matrix gives it exactly, in O(n^2) time and O(n) extra memory.

H0 only sees the tree. Research notes for this epic warn that many recent "LLM topology" results use H0 alone; check such a result against plain nearest-neighbor statistics (nearest_neighbors.hpp), which see much of the same thing.