GUDHI documentation

_images/Gudhi_banner.png

Introduction

The Gudhi library (Geometry Understanding in Higher Dimensions) is a generic open source C++ library, with a Python interface, for Computational Topology and Topological Data Analysis (TDA). The GUDHI library intends to help the development of new algorithmic solutions in TDA and their transfer to applications. It provides robust, efficient, flexible and easy to use implementations of state-of-the-art algorithms and data structures.

The current release of the GUDHI library includes:

  • Data structures to represent, construct and manipulate simplicial complexes.
  • Simplication of simplicial complexes by edge contraction.
  • Algorithms to compute persistent homology and bottleneck distance.

We refer to [3] for a detailed description of the design of the library.

Data structures

Alpha complex

Author:Vincent Rouvreau
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
Requires:CGAL \(\geq\) 4.7.0
Eigen3  
Alpha complex representation

Alpha complex representation

Alpha_complex is a simplicial complex constructed from the finite cells of a Delaunay Triangulation.

The filtration value of each simplex is computed as the square of the circumradius of the simplex if the circumsphere is empty (the simplex is then said to be Gabriel), and as the minimum of the filtration values of the codimension 1 cofaces that make it not Gabriel otherwise. All simplices that have a filtration value strictly greater than a given alpha squared value are not inserted into the complex.

This package requires having CGAL version 4.7 or higher (4.8.1 is advised for better perfomances).

Alpha complex user manual Alpha complex reference manual

Cubical complex

Author:Pawel Dlotko
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
Cubical complex representation

Cubical complex representation

The cubical complex is an example of a structured complex useful in computational mathematics (specially rigorous numerics) and image analysis.
Cubical complex user manual

Rips complex

Author:Clément Maria, Pawel Dlotko, Vincent Rouvreau
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
_images/rips_complex_representation.png

Rips complex representation

Rips complex is a simplicial complex constructed from a one skeleton graph.

The filtration value of each edge is computed from a user-given distance function and is inserted until a user-given threshold value.

This complex can be built from a point cloud and a distance function, or from a distance matrix.

Rips complex user manual Rips complex reference manual

Simplex tree

Author:Clément Maria
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
Simplex tree representation

Simplex tree representation

The simplex tree is an efficient and flexible data structure for representing general (filtered) simplicial complexes.

The data structure is described in [4]

Simplex tree user manual Simplex tree reference manual

Tangential complex

Author:Clément Jamin
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
Requires:CGAL \(\geq\) 4.8.0
Eigen3  
_images/tc_examples.png

Tangential complex representation

A Tangential Delaunay complex is a simplicial complex designed to reconstruct a \(k\)-dimensional manifold embedded in \(d\)- dimensional Euclidean space. The input is a point sample coming from an unknown manifold. The running time depends only linearly on the extrinsic dimension \(d\) and exponentially on the intrinsic dimension \(k\).
Tangential complex user manual Tangential complex reference manual

Witness complex

Author:Siargey Kachanovich
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
Euclidean version requires:
 CGAL \(\geq\) 4.6.0
Eigen3  
_images/Witness_complex_representation.png

Witness complex \(Wit(W,L)\) is a simplicial complex defined on two sets of points in \(\mathbb{R}^D\).

The data structure is described in [4].

Witness complex user manual

Toolbox

Bottleneck distance

Author:François Godi
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
Requires:CGAL \(\geq\) 4.8.0
   
_images/perturb_pd.png

Bottleneck distance is the length of the longest edge

Bottleneck distance measures the similarity between two persistence diagrams. It’s the shortest distance b for which there exists a perfect matching between the points of the two diagrams (+ all the diagonal points) such that any couple of matched points are at distance at most b.
Bottleneck distance user manual  

Persistence cohomology

Author:Clément Maria
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
_images/3DTorus_poch.png

Rips Persistent Cohomology on a 3D Torus

The theory of homology consists in attaching to a topological space a sequence of (homology) groups, capturing global topological features like connected components, holes, cavities, etc. Persistent homology studies the evolution – birth, life and death – of these features when the topological space is changing. Consequently, the theory is essentially composed of three elements: topological spaces, their homology groups and an evolution scheme.

Computation of persistent cohomology using the algorithm of [5] and [6] and the Compressed Annotation Matrix implementation of [7].

Persistent cohomology user manual

Please refer to each data structure that contains persistence feature for reference:

Persistence graphical tools

Author:Vincent Rouvreau
Introduced in:GUDHI 2.0.0
Copyright:GPL v3
Requires:Matplotlib
Numpy  
_images/graphical_tools_representation.png
These graphical tools comes on top of persistence results and allows the user to build easily barcode and persistence diagram.
Persistence graphical tools user manual Persistence graphical tools reference manual

Bibliography

[1]T. Kaczynski, K. Mischaikow, and M. Mrozek. Computational Homology. Applied Mathematical Sciences. Springer New York, 2004. ISBN 9780387408538. URL: https://books.google.fr/books?id=AShKtpi3GecC.
[2]Hubert Wagner, Chao Chen, and Erald Vucini. Efficient Computation of Persistent Homology for Cubical Data, pages 91–106. Mathematics and Visualization. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-23175-9_7, doi:10.1007/978-3-642-23175-9_7.
[3]Clément Maria, Jean-Daniel Boissonnat, Marc Glisse, and Mariette Yvinec. The Gudhi library: simplicial complexes and persistent homology. In ICMS. 2014.
[4](1, 2) Jean-Daniel Boissonnat and Clément Maria. The simplex tree: an efficient data structure for general simplicial complexes. Algorithmica, pages 1–22, 2014. URL: http://dx.doi.org/10.1007/s00453-014-9887-3, doi:10.1007/s00453-014-9887-3.
[5]Vin de Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete & Computational Geometry, 45(4):737–759, 2011.
[6]Tamal K. Dey, Fengtao Fan, and Yusu Wang. Computing topological persistence for simplicial maps. CoRR, 2012.
[7]Jean-Daniel Boissonnat, Tamal K. Dey, and Clément Maria. The compressed annotation matrix: an efficient data structure for computing persistent cohomology. In ESA, 695–706. 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_59, doi:10.1007/978-3-642-40450-4_59.