ViteBetti is an algorithm for computing the Betti numbers of a 3D cubical complex. It exploits the Euler-Poincaré characteristic and Alexander duality.
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:
- A first line with the size of the bounding box along each axis;
- 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.
Our software includes four algorithms for computing the Betti numbers:
- A sequential algorithm that performs breadth first search in the complex.
- A recursive algorithm that use a divide-and-conquer approach. The complex is cut into pieces of size greater than a given threshold.
- A parallel implementation of the previous algorithm with Threading Building Blocks.
- An algorithm that treats the complex slice by slice.
Download and compile
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
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.
License and citation
ViteBetti is a free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.