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 simplicial_complex.)

Background

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.

Simplicial complex

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.¹ In libstick, a simplicial complex is an object of the following type:

template<int MAXDIM, class IT> class simplicial_complex;

Here MAXDIM denotes the maximal dimension of all the simplices and IT is 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.

libstick::simplicial_complex<2, int32_t> c;
libstick::simplicial_complex<2, int32_t>::simplex simplices [] = {
    /* {dimension, {indices of faces}}, */
    {0, {}},  /* The first of three vertices */
    {0, {}},
    {0, {}},
    {1, {1, 2}},  /* The first of three edges */
    {1, {2, 3}},
    {1, {3, 1}},
    {2, {4, 5, 6}},
    };
c.add_simplices(simplices, 7);

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:

class simplicial_complex<MAXDIM, IT>::simplicial_order;
libstick::simplicial_complex<2, int32_t>::simplicial_order o(c);

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.

assert(o.is_filtration());
std::cout << o.get_boundary_matrix() << std::endl;

Persistence

From (the boundary matrix of) a simplicial order we can compute persistent homology. In libstick, persistence computation is encapsulated into a dedicated class:

template<int MAXDIM, class IT> class persistence;
libstick::persistence<2, int32_t> p(o);

When we create a persistence object, no homology computation is performed yet.

p.compute_matrices();
std::cout << p.get_reduced_boundary_matrix() << std::endl;
std::cout << p.get_transformation_matrix() << std::endl;
p.interpret_reduction(std::cout);   // Illustrate the reduction steps

For convenience, also persistent diagrams are encapsulated in their own classes:

class persistence<MAXDIM, IT>::diagram;
p.get_persistence_diagram(0);
p.get_persistence_diagram(1);
p.get_persistence_diagram(2);

Simplicial function

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:

template<int MAXDIM, class IT, class VT> class simplicial_function;
libstick::simplicial_function<2, int32_t, float> f(c);

Here 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 simplices:

c.clear();
libstick::simplicial_function<2, int32_t, float>::valuedsimplex simplices [] = {
    /* {dimension, {indices of faces}, scalar value}, */
    {0, {}, 2.0f},
    {0, {}, 1.0f},
    {0, {}, 3.0f},
    {1, {1, 2}, 5.0f},
    {1, {2, 3}, 6.0f},
    {1, {3, 1}, 4.0f},
    {2, {4, 5, 6}, 7.0f},
    };
f.add_simplices(simplices, 7);

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:

assert(f.is_monotone());
assert(!f.is_order_monotonefiltration(o));
f.make_order_monotonefiltration(o);
assert(f.is_order_monotonefiltration(o));

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..

More examples

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.