Betti_numbers

Authors: F. Cazals and T. Dreyfus

Introduction

Betti numbers are easy accessible values for representing the topology of a combinatorial data structure, such as a graph. The Betti numbers represent:

$\beta_0$ : the number of 0-cycles (i.e connected components in 2D and 3D),

$\beta_1$ : the number of 1-cycles (i.e cycles in 2D, tunnels in 3D),

$\beta_2$ : the number of 2-cycles (i.e voids in 3D).

In particular, it has been shown that the topology of the union of a family of 3D balls is exactly the topology of its $\alpha$ -complex for $\alpha=0$ , giving a combinatorial way to compute the topology of this family. This package provides functors for computing the Betti numbers of a graph, of a 3D weighted $\alpha$ -complex or of the union of a family of 3D balls.

Algorithms

The computation of Betti numbers is performed using the incremental algorithm from [68] , on the $\alpha$ -complex of the union of balls.

Functionality

Betti numbers for Graph

The Betti numbers of a graph can be simply computed using a simple Union-Find algorithm. Consider a Union-Find data structure such that each independent set is initialized to a vertex of the input graph, and for each edge of the input graph, the corresponding independent sets are union. It follows that:

one connected component is created for each vertex,

for each edge, if it union two different sets, it kills one connected component; otherwise, it creates one cycle.

It is exactly the algorithm implemented by the class SBL::GT::T_Betti_numbers_1< Graph >. The template parameter is a graph from the Boost Graph Library, and object of the type SBL::GT::T_Betti_numbers_1< Graph > is a functor that takes as input a graph, and returns a Boost tuple of two numbers, namely $\beta_0$ and $\beta_1$ .

See Betti numbers of a graph for an example.

Betti numbers for 3D weighted alpha-complex

In order to compute the Betti numbers of a 3D weighted $\alpha$ -complex, a Union-Find algorithm is also used over the simplices. When adding the simplices in the 3D weighted $\alpha$ -complex by increasing $\alpha$ value, each -simplex creates a -cycle, or kills a -cycle (for k > 0). We use this property for computing the Betti numbers:

$\beta_0$ is simply computed from the 1-skeleton of the 3D weighted $\alpha$ -complex, as for a graph.

$\beta_1$ is the number of 1-cycles of the 1-skeleton not killed by the faces of the 3D weighted $\alpha$ -complex.

$\beta_2$ is guessed from the number of connected components of exterior tetrahedra, i.e tetrahedra of the underlying triangulation that are not in the $\alpha$ -complex; more precisely, the CGAL triangulation contains an abstract vertex called the infinite vertex: all tetrahedra containing the infinite vertex are exterior and make a connected component, while the exterior tetrahedra in the voids of the $\alpha$ -complex cannot be connected to these infinite tetrahedra. Thus, there is one connected component of exterior tetrahedra containing the infinite tetrahedra, and one connected component of exterior tetrahedra per void in the $\alpha$ -complex.

The algorithm is implemented by the class SBL::GT::T_Betti_numbers_2< AlphaComplex3 >: the template argument is a representation of a 3D $\alpha$ -complex (even not weighted) and can be any of the data structures from the CGAL library. An object of the class SBL::GT::T_Betti_numbers_2< AlphaComplex3 > is a functor that takes as input a 3D $\alpha$ -complex, and returns a Boost tuple of three numbers, namely $\beta_0$ , $\beta_1$ . and $\beta_2$ .

See Betti numbers of alpha-complex for an example.

Since the topology of the 3D weighted $\alpha$ -complex is the topology of the union of its family of 3D balls, it is also possible to directly compute the Betti numbers of a family of 3D balls, as shown in Betti numbers of family of 3D balls .

Examples

Betti numbers of a graph

This example illustrates how the Betti numbers of a graph evolves when adding edges to the graph: it first create a graph with four vertices and no edge; then, it adds three edges one by one, printing at each step the number of connected components and cycles.

#include <iostream>
#include <SBL/GT/Betti_numbers_1.hpp>
 
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor                       Vertex;
typedef SBL::GT::T_Betti_numbers_1<Graph>                                   Betti_numbers_1;
 
int main(int argc, char *argv[])
{
  Graph G;
 
  Vertex u = boost::add_vertex(G);
  Vertex v = boost::add_vertex(G);
  Vertex w = boost::add_vertex(G);
 
  Betti_numbers_1 betti;
  Betti_numbers_1::result_type res = betti(G);
  std::cout << "four vertices, Betti numbers: "  << res.get<0>() << " " << res.get<1>() << std::endl;
  boost::add_edge(u, v, G);
  res = betti(G);
  std::cout << "four vertices, one edge, Betti numbers: "  << res.get<0>() << " " << res.get<1>() << std::endl;
  boost::add_edge(u, w, G);
  res = betti(G);
  std::cout << "four vertices, two edges, Betti numbers: "  << res.get<0>() << " " << res.get<1>() << std::endl;
  boost::add_edge(v, w, G);
  res = betti(G);
  std::cout << "four vertices, three edges, one cycle, Betti numbers: "  << res.get<0>() << " " << res.get<1>() << std::endl;
 
  return 0;
}

Betti numbers of alpha-complex

This example shows how to compute the Betti numbers of a 3D weighted $\alpha$ -complex : it first builds the 3D regular triangulation of an input family of 3D balls loaded from a text file (note that the CGAL library works with a CGAL::Weighted_point data structure for representing the 3D balls); then, it computes the 3D weighted $\alpha$ -complex of this regular triangulation, and print the associated Betti numbers.

#include <iostream>
#include <fstream>
 
#include <SBL/GT/Betti_numbers_2.hpp>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Regular_triangulation_3.h>
#include <CGAL/Alpha_shape_3.h>
#include <CGAL/Alpha_shape_vertex_base_3.h>
#include <CGAL/Alpha_shape_cell_base_3.h>
 
//Instantiation of the 3D weighted alpha-complex with CGAL, using
//rational number types.
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Alpha_shape_cell_base_3<K, CGAL::Regular_triangulation_cell_base_3<K> > Cb;
typedef CGAL::Alpha_shape_vertex_base_3<K, CGAL::Regular_triangulation_vertex_base_3<K>> Vb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb> Tds;
typedef CGAL::Regular_triangulation_3<K, Tds> Regular_triangulation_3;
typedef CGAL::Alpha_shape_3<Regular_triangulation_3> Alpha_complex_3;
typedef SBL::GT::T_Betti_numbers_2<Alpha_complex_3> Betti_numbers_2;
 
int main(int argc, char *argv[])
{
 
  if (argc < 2) {
    return -1;
  }
 
  std::ifstream in(argv[1]);
  Regular_triangulation_3 T;
  while (!in.eof()) {
    CGAL::Weighted_point_3<K> wp;
    in >> wp;
    if(!in.eof()) {
      T.insert(wp);
    }
  }
  in.close();
  Alpha_complex_3 A(T);
 
  Betti_numbers_2 betti;
  Betti_numbers_2::result_type res = betti(A);
  std::cout << "Number of input spheres: " << A.number_of_vertices() << std::endl;
  std::cout << "Betti numbers: " 
            << res.get<0>() << " " << res.get<1>() << " " << res.get<2>() << std::endl;
 
  return 0;
}

Betti numbers of family of 3D balls

This example shows how to compute the Betti numbers of the union of a family of 3D balls : it first loads the 3D balls from a text file (note that the CGAL library works with a CGAL::Weighted_point data structure for representing 3D balls); then, it computes the Betti numbers of the input family of 3D balls. Note that it is the same to compute the 3D weighted $\alpha$ -complex of the input family of 3D balls, for $\alpha = 0$ , except that the $\alpha$ -complex data structure is internal to the computation of the Betti numbers.

#include <iostream>
#include <fstream>
 
#include <SBL/GT/Betti_numbers_2.hpp>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Regular_triangulation_3.h>
#include <CGAL/Alpha_shape_3.h>
#include <CGAL/Alpha_shape_vertex_base_3.h>
#include <CGAL/Alpha_shape_cell_base_3.h>
 
//Instantiation of the 3D weighted alpha-complex with CGAL, using
//rational number types.
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Alpha_shape_cell_base_3<K, CGAL::Regular_triangulation_cell_base_3<K> > Cb;
typedef CGAL::Alpha_shape_vertex_base_3<K, CGAL::Regular_triangulation_vertex_base_3<K>> Vb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb> Tds;
typedef CGAL::Regular_triangulation_3<K, Tds> Regular_triangulation_3;
typedef CGAL::Alpha_shape_3<Regular_triangulation_3> Alpha_complex_3;
typedef SBL::GT::T_Betti_numbers_2<Alpha_complex_3> Betti_numbers_2;
 
int main(int argc, char *argv[])
{
 
  if (argc < 2) {
    return -1;
  }
 
  std::ifstream in(argv[1]);
  std::vector<CGAL::Weighted_point_3<K>> weighted_points;
  while (!in.eof()) {
    CGAL::Weighted_point_3<K> wp;
    in >> wp;
    if(!in.eof()) {
      weighted_points.push_back(wp);
    }
  }
  in.close();
  
  Betti_numbers_2 betti;
  Betti_numbers_2::result_type res = betti(weighted_points.begin(), weighted_points.end());
  std::cout << "Number of input spheres: " << weighted_points.size() << std::endl;
  std::cout << "Betti numbers: " 
            << res.get<0>() << " " << res.get<1>() << " " << res.get<2>() << std::endl;
  
  return 0;
}