# ViteBetti

ViteBetti is an algorithm for computing the Betti numbers of a 3D cubical complex. It exploits the Euler-PoincarĂ© characteristic and Alexander duality.

Take a look at our paper in the CTIC 2016 proceedings. We are submitting also an extended version to this Special Issue in "Discrete Geometry and Topology and their Applications to Imaging Sciences".

## Data format

The cubical cells of a 3D cubical complex are of the form [x, x+d1]✕[y, y+d2]✕[z, z+d3] where di is 1 or 0. Thus, a cubical cell can be unequivocally identified to a vector (2x+d1, 2y+d2, 2z+d3). Therefore, a 3D cubical complex can be easily encoded as a binary three-dimensional array A where the position A(i,j,k) is 1 if the corresponding cubical cell belongs to the complex or 0 otherwise.

A text file describing a 3D cubical complex consists in:

1. A first line with the size of the bounding box along each axis;
2. The content of the tree-dimensional array A running first in the z-coordinate, next in the y-coordinate and last in the x-coordinate.

You can see here a small 3D cubical complex with Betti numbers (1,1,1).

### Algorithms

Our software includes four algorithms for computing the Betti numbers:

1. A sequential algorithm that performs breadth first search in the complex.
2. A recursive algorithm that use a divide-and-conquer approach. The complex is cut into pieces of size greater than a given threshold.
3. A parallel implementation of the previous algorithm with TBB.
4. An algorithm that treats the complex slice by slice.

You can download the source code here. You need to install Threading Building Blocks before compiling. For this, you just need to type `sudo apt-get install libtbb-dev`

Then, after extracting the source files you can compile them on Linux as follows: `g++ main.cpp fullcomplex.cpp scancomplex.cpp unionfind.cpp -ltbb -std=c++11 -O3 -o ViteBetti`

### Usage

Once you have compiled ViteBetti, you just need to type on your terminal:
`./ViteBetti fileName -a algorithm`
where fileName is the name of the file encoding the 3D cubical complex and algorithm is the number of the algorithm you want to use.

The threshold for the two recursive algorithms 2 and 3 can be introduced as follows:
`./ViteBetti fileName -a 2 -t threshold`

The third algorithm is faster than the second, which is faster than the first one. The fourth algorithm is recommended for huge complexes (in the order of 10013), since it consumes less memory.

You can generate random 3D cubical complexes with RandCubComplex in order to test the performance of the algorithms.