Repository files navigation

Copyright © 2015–2021Ulrich Bauer.

Ripser is a lean C++ code for the computation of Vietoris–Rips persistence barcodes. It can do just this one thing, but does it extremely well.

To see a live demo of Ripser's capabilities, go tolive.ripser.org. The computation happens inside the browser (usingEmscripten to compile Ripser toWebAssembly, supported on recent browsers).

The main features of Ripser:

• time- and memory-efficient
• only about 1000 lines of code in a single C++ file
• support for coefficients in prime finite fields
• no external dependencies (optional support for Google's [sparsehash])

Currently, Ripser outperforms other codes (Dionysus,DIPHA,GUDHI,Perseus,PHAT) by a factor of more than 40 in computation time and a factor of more than 15 in memory efficiency (for the example linked atlive.ripser.org). (Note thatPHAT does not contain code for generating Vietoris–Rips filtrations).

Input formats currently supported by Ripser:

• comma-separated values lower triangular distance matrix
• comma-separated values upper triangular distance matrix (MATLAB output from the functionpdist)
• comma-separated values full distance matrix
• DIPHA distance matrix data
• sparse distance matrix in sparse triplet format
• binary lower triangular distance matrix
• point cloud data

Ripser's efficiency is based on a few important concepts and principles, building on key previous and concurrent developments by other researchers in computational topology:

• Compute persistentcohomology (as suggested byVin de Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson)
• Use the chain complex property that boundaries are cycles(employ theclearing optimization, akapersistence with a twist, as suggested byChao Chen and Michael Kerber)
• If no threshold is specified, choose theenclosing radius as the threshold, from which on homology is guaranteed to be trivial (as suggested byGreg Henselman-Petrusek)
• Don't store information that can be readily recomputed (in particular, the original and the reduced boundary matrix)
• Take computational shortcuts (apparent andemergent persistence pairs)

Latest release: 1.2.1 (March 2021)

Ripser requires a C++11 compiler. Here is how to obtain, build, and run Ripser:

git clone https://github.com/Ripser/ripser.gitcd ripsermake./ripser examples/sphere_3_192.lower_distance_matrix

Ripser supports several compile-time options. They are switched on by defining the C preprocessor macros listed below, either using#define in the code or by passing an argument to the compiler. The following options are supported:

• USE_COEFFICIENTS: enable support for coefficients in a prime field
• INDICATE_PROGRESS: indicate the current progress in the console
• PRINT_PERSISTENCE_PAIRS: output the computed persistence pairs (enabled by default in the code; comment out to disable)
• USE_ROBINHOOD_HASHMAP: enable support for Martin Ankerl'srobinhoodhash data structure; may further reduce memory footprint

For example, to build Ripser with support for Martin Ankerl's robin hood hashmap:

$ c++ -std=c++11 ripser.cpp -o ripser -O3 -D NDEBUG -D USE_ROBINHOOD_HASHMAP

A Makefile is provided with some variants of the above options. Usemake all to build them. The defaultmake builds a binary with the default options.

The input is given either in a file whose name is passed as an argument, or through stdin. The following options are supported at the command line:

• --format: use the specified file format for the input. The following formats are supported:
  • lower-distance: lower triangular distance matrix; a comma (or whitespace, or other non-numerical character) separated list of the distance matrix entries below the diagonal, sorted lexicographically by row index, then column index.
  • upper-distance: upper triangular distance matrix; similar to the previous, but for the entries above the diagonal; suitable for output from the MATLAB functionspdist orseqpdist, exported to a CSV file.
  • distance (default if no format is specified): full distance matrix; similar to the above, but for all entries of the distance matrix. One line per row of the matrix; only the part below the diagonal is actually read.
  • dipha: DIPHA distance matrix as described on theDIPHA website.
  • point-cloud: point cloud; a comma (or whitespace, or other non-numerical character) separated list of coordinates of the points in some Euclidean space, one point per line.
  • binary: lower distance matrix in binary file format; a sequence of the distance matrix entries below the diagonal in 32 bit float format (IEEE 754, single, little endian).
  • sparse: sparse triplet format; a whitespace separated list of entries of a sparse distance matrix, one entry per line, each of the formi j d(i,j) specifying the distance between pointsi andj. Each pair of points should appear in the file at most once.
• --dim k: compute persistent homology up to dimensionk.
• --threshold t: compute Rips complexes up to diametert.
• --modulus p: compute homology with coefficients in the prime field Z/pZ (only available when built with the optionUSE_COEFFICIENTS).
• --ratio r: only show persistence pairs with death/birth ratio >r.

The following experimental features are currently available in separate branches:

• representative-cocycles: output of representative cocycles for persistent cohomology.
• representative-cycles: computation and output of representative cycles for persistent homology (in the standard version, onlycocycles are computed).
• simple: a simplified version of Ripser, without support for sparse distance matrices and coefficients. This might be a good starting point for exploring the code.

If you use Ripser in your research or if you want to give a reference to Ripser in a paper, you may use the following bibtex entry (will be updated with complete publication data):

@article{Bauer2021Ripser,    AUTHOR = {Bauer, Ulrich},     TITLE = {Ripser: efficient computation of {V}ietoris-{R}ips persistence              barcodes},   JOURNAL = {J. Appl. Comput. Topol.},  FJOURNAL = {Journal of Applied and Computational Topology},    VOLUME = {5},      YEAR = {2021},    NUMBER = {3},     PAGES = {391--423},      ISSN = {2367-1726},   MRCLASS = {55N31 (55-04)},  MRNUMBER = {4298669},       DOI = {10.1007/s41468-021-00071-5},       URL = {https://doi.org/10.1007/s41468-021-00071-5},}

Ripser is licensed under theMIT license (COPYING.txt), with an extra clause (CONTRIBUTING.txt) clarifying the license for modifications released without an explicit written license agreement. Please contact the author if you want to use Ripser in your software under a different license.