libstick: Getting started
The following documentation refers to the current version 0.2 of libstick. (Version 0.1 had no concept of a
simplicial_function, but incorporated it into
In persistent homology a growing sequence (i.e., a filtration) of shapes is considered. Holes of different dimensions (e.g., gaps between components, tunnels, voids, etc.) are created and eliminated (i.e., filled out) as the shape grows. Persistent homology is a tool from algebraic topology to that keeps track of the birth and death of these holes in terms of homology classes. The \(k\)-dimensional persistence diagram is a summary of this topological information. It is a multi-set of points in the plane: each point \((b, d)\) depicts a \(k\)-dimensional hole that is born at time \(b\) and killed at time \(d\).
The shapes are here modeled as simplicial complexes. A simplicial complex is a set of (abstract) simplices that contains for each simplex also its boundary simplices. A typical way in order to obtain filtration on a simplicial complex is to consider a simplicial function and then consider the sub-level sets of the simplicial complex.
Exactly these objects – the simplicial complex, a filtration, a function on the complex – are embodied as template classes in libstick, as the following picture illustrates.
A simplicial complex is a collection of simplices (points, edges, triangles, etc.) such that for each simplex the boundary simplices (three edges of a triangle, two endpoints of an edge, etc.) are contained in the complex too. For technical reasons, every complex has one single (-1)-dimensional dummy simplex, and all 0-dimensional simplices have this dummy simplex as boundary.1 In libstick, a simplicial complex is an object of the following type:
MAXDIM denotes the maximal dimension of all the simplices and
the type of the indices of the simplices. Each simplex is called by its index
and a simplicial complex carries an array of its simplices. In the following
code listing we generate a simplicial complex with the one triangle and its
edges and vertices, as illustrated in the figure below.
Note that we make use of the fact that a simplex is an aggregate type, which allows for aggregate initialization of an array of simplex objects. We first have three simplices of dimension zero, then we have three simplices of dimension 1, and then one simplex of dimension 2. The first 1-simplex has the simplices 1 and 2 as boundary. The 2-simplex has simplices 4, 5 and 6 as boundary. We therefore built the complex illustrated in the figure below:
Note that it is not necessary to explicitly specify the (-1)-dimensional dummy simplex with index 0 as boundary for the three 0-dimensional simplices.
Simplicial order and filtration
On a simplicial complex, one can define a simplicial order. A simplicial order can be seen as a permutation of the simplices of a simplicial complex or as a total order on the simplices of a complex. In algebraic topology, a filtration on a simplicial complex is a nested sequence of sub-complexes. We represent filtrations as the sequence of prefix-lists of a simplicial order, starting from the sub-complex that contains only the (-1)-dimensional dummy simplex, up to the complete original complex. In libstick, a simplicial order is a nested class of a simplicial complex:
A simplicial order can be asked whether its prefix-lists actually constitute a filtration, i.e., for each simplex its boundary simplices appear first in the order. Also, we can obtain the boundary matrix from a simplicial order.
From (the boundary matrix of) a simplicial order we can compute persistent homology. In libstick, persistence computation is encapsulated into a dedicated class:
When we create a persistence object, no homology computation is performed yet.
For convenience, also persistent diagrams are encapsulated in their own classes:
A convenient way in order to obtain a simplicial order on a simplicial complex is to define a function on the simplicial complex, i.e., we assign each simplex a scalar value. In libstick, a simplicial function is encapsulated into a template class:
VT is the type of the scalar values. Then we can take a simplicial
order and reorder the simplices such that their values are monotonically
increasing. If the function itself is monotone – i.e., for each simplex with
value \(v\) the boundary simplices have values at most \(v\) – then we can
obtain a monotone filtration. In our demo example, we could simply set the
scalar values of
f, or we start over and use valued simplices instead of
If we add valued simplices to a function, then a simplex is added to the underlying complex and its scalar value is added to the function object at the same time. Note that the standard order on the complex is not monotone with the given scalar values. However, we can easily obtain a monotone filtration:
From images to complexes and functions
For convenience, libstick also allows to easily obtain simplicial complexes and simplicial functions from pixel images. See the demonstration page for further instructions..
If you are looking for more examples, such as computing the homology of a torus or a ball, you may look into the code of the unit tests, such as tests/persistence.h.