Gudhi::cubical_complex::Bitmap_cubical_complex_base< T > Class Template Reference

Cubical complex represented as a bitmap, class with basic implementation. More...

Classes

class  All_cells_iterator
 Iterator through all cells in the complex (in order they appear in the structure – i.e. in lexicographical order). More...
 
class  All_cells_range
 All_cells_range class provides ranges for All_cells_iterator. More...
 
class  Top_dimensional_cells_iterator
 Iterator through top dimensional cells of the complex. The cells appear in order they are stored in the structure (i.e. in lexicographical order) More...
 
class  Top_dimensional_cells_range
 Top_dimensional_cells_iterator_range class provides ranges for Top_dimensional_cells_iterator_range. More...
 

Public Types

typedef std::vector< std::size_t >::const_iterator Boundary_iterator
 
typedef std::vector< std::size_t >::const_iterator Coboundary_iterator
 

Public Member Functions

 Bitmap_cubical_complex_base ()
 
 Bitmap_cubical_complex_base (const std::vector< unsigned > &sizes)
 
 Bitmap_cubical_complex_base (const char *perseus_style_file)
 
 Bitmap_cubical_complex_base (const std::vector< unsigned > &dimensions, const std::vector< T > &top_dimensional_cells)
 
virtual ~Bitmap_cubical_complex_base ()
 
virtual std::vector< std::size_t > get_boundary_of_a_cell (std::size_t cell) const
 
virtual std::vector< std::size_t > get_coboundary_of_a_cell (std::size_t cell) const
 
virtual int compute_incidence_between_cells (std::size_t coface, std::size_t face) const
 
unsigned get_dimension_of_a_cell (std::size_t cell) const
 
T & get_cell_data (std::size_t cell)
 
void impose_lower_star_filtration ()
 
unsigned dimension () const
 
unsigned size () const
 
void put_data_to_bins (std::size_t number_of_bins)
 
void put_data_to_bins (T diameter_of_bin)
 
std::pair< T, T > min_max_filtration ()
 
All_cells_iterator all_cells_iterator_begin ()
 
All_cells_iterator all_cells_iterator_end ()
 
Boundary_range boundary_range (std::size_t sh)
 
Coboundary_range coboundary_range (std::size_t sh)
 
Top_dimensional_cells_iterator top_dimensional_cells_iterator_begin ()
 
Top_dimensional_cells_iterator top_dimensional_cells_iterator_end ()
 

Friends

template<typename K >
std::ostream & operator<< (std::ostream &os, const Bitmap_cubical_complex_base< K > &b)
 

Detailed Description

template<typename T>
class Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >

Cubical complex represented as a bitmap, class with basic implementation.

This is a class implementing a basic bitmap data structure to store cubical complexes. It implements only the most basic subroutines. The idea of the bitmap is the following. Our aim is to have a memory efficient data structure to store d-dimensional cubical complex C being a cubical decomposition of a rectangular region of a space. This is achieved by storing C as a vector of bits (this is where the name 'bitmap' came from). Each cell is represented by a single bit (in case of black and white bitmaps, or by a single element of a type T (here T is a filtration type of a bitmap, typically a double). All the informations needed for homology and persistent homology computations (like dimension of a cell, boundary and coboundary elements of a cell, are then obtained from the position of the element in C. The default filtration used in this implementation is the lower star filtration.

Examples:
Bitmap_cubical_complex/cubical_complex_persistence.cpp, and Bitmap_cubical_complex/Random_bitmap_cubical_complex.cpp.

Member Typedef Documentation

◆ Boundary_iterator

template<typename T>
typedef std::vector<std::size_t>::const_iterator Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::Boundary_iterator

Boundary_range class provides ranges for boundary iterators.

◆ Coboundary_iterator

template<typename T>
typedef std::vector<std::size_t>::const_iterator Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::Coboundary_iterator

Coboundary_range class provides ranges for boundary iterators.

Constructor & Destructor Documentation

◆ Bitmap_cubical_complex_base() [1/4]

Default constructor

◆ Bitmap_cubical_complex_base() [2/4]

template<typename T >
Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::Bitmap_cubical_complex_base ( const std::vector< unsigned > &  sizes)

There are a few constructors of a Bitmap_cubical_complex_base class. First one, that takes vector<unsigned>, creates an empty bitmap of a dimension equal the number of elements in the input vector and size in the i-th dimension equal the number in the position i-of the input vector.

◆ Bitmap_cubical_complex_base() [3/4]

template<typename T >
Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::Bitmap_cubical_complex_base ( const char *  perseus_style_file)

The second constructor takes as a input a Perseus style file. For more details, please consult the documentations of Perseus software as well as examples attached to this implementation.

◆ Bitmap_cubical_complex_base() [4/4]

template<typename T >
Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::Bitmap_cubical_complex_base ( const std::vector< unsigned > &  dimensions,
const std::vector< T > &  top_dimensional_cells 
)

The last constructor of a Bitmap_cubical_complex_base class accepts vector of dimensions (as the first one) together with vector of filtration values of top dimensional cells.

◆ ~Bitmap_cubical_complex_base()

template<typename T>
virtual Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::~Bitmap_cubical_complex_base ( )
inlinevirtual

Destructor of the Bitmap_cubical_complex_base class.

Member Function Documentation

◆ all_cells_iterator_begin()

template<typename T>
All_cells_iterator Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::all_cells_iterator_begin ( )
inline

Function returning a All_cells_iterator to the first cell of the bitmap.

◆ all_cells_iterator_end()

template<typename T>
All_cells_iterator Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::all_cells_iterator_end ( )
inline

Function returning a All_cells_iterator to the last cell of the bitmap.

◆ boundary_range()

template<typename T>
Boundary_range Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::boundary_range ( std::size_t  sh)
inline

boundary_simplex_range creates an object of a Boundary_simplex_range class that provides ranges for the Boundary_simplex_iterator.

◆ coboundary_range()

template<typename T>
Coboundary_range Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::coboundary_range ( std::size_t  sh)
inline

boundary_simplex_range creates an object of a Boundary_simplex_range class that provides ranges for the Boundary_simplex_iterator.

◆ compute_incidence_between_cells()

template<typename T>
virtual int Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::compute_incidence_between_cells ( std::size_t  coface,
std::size_t  face 
) const
inlinevirtual

This procedure compute incidence numbers between cubes. For a cube \(A\) of dimension n and a cube \(B \subset A\) of dimension n-1, an incidence between \(A\) and \(B\) is the integer with which \(B\) appears in the boundary of \(A\). Note that first parameter is a cube of dimension n, and the second parameter is an adjusted cube in dimension n-1. Given \(A = [b_1,e_1] \times \ldots \ [b_{j-1},e_{j-1}] \times [b_{j},e_{j}] \times [b_{j+1},e_{j+1}] \times \ldots *\times [b_{n},e_{n}] \) such that \( b_{j} \neq e_{j} \) and \(B = [b_1,e_1] \times \ldots \ [b_{j-1},e_{j-1}] \times [a,a] \times [b_{j+1},e_{j+1}] \times \ldots \times *[b_{n},e_{n}] \) where \( a = b_{j}\) or \( a = e_{j}\), the incidence between \(A\) and \(B\) computed by this procedure is given by formula: \( c\ (-1)^{\sum_{i=1}^{j-1} dim [b_{i},e_{i}]} \) Where \( dim [b_{i},e_{i}] = 0 \) if \( b_{i}=e_{i} \) and 1 in other case. c is -1 if \( a = b_{j}\) and 1 if \( a = e_{j}\).

Exceptions
std::logic_errorIn case when the cube \(B\) is not n-1 dimensional face of a cube \(A\).

◆ dimension()

template<typename T>
unsigned Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::dimension ( ) const
inline

Returns dimension of a complex.

◆ get_boundary_of_a_cell()

template<typename T >
std::vector< std::size_t > Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::get_boundary_of_a_cell ( std::size_t  cell) const
inlinevirtual

The functions get_boundary_of_a_cell, get_coboundary_of_a_cell, get_dimension_of_a_cell and get_cell_data are the basic functions that compute boundary / coboundary / dimension and the filtration value form a position of a cell in the structure of a bitmap. The input parameter of all of those function is a non-negative integer, indicating a position of a cube in the data structure. In the case of functions that compute (co)boundary, the output is a vector if non-negative integers pointing to the positions of (co)boundary element of the input cell. The boundary elements are guaranteed to be returned so that the incidence coefficients of boundary elements are alternating.

Reimplemented in Gudhi::cubical_complex::Bitmap_cubical_complex_periodic_boundary_conditions_base< T >.

◆ get_cell_data()

template<typename T >
T & Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::get_cell_data ( std::size_t  cell)
inline

In the case of get_cell_data, the output parameter is a reference to the value of a cube in a given position. This allows reading and changing the value of filtration. Note that if the value of a filtration is changed, the code do not check if we have a filtration or not. i.e. it do not check if the value of a filtration of a cell is not smaller than the value of a filtration of its boundary and not greater than the value of its coboundary.

◆ get_coboundary_of_a_cell()

template<typename T >
std::vector< std::size_t > Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::get_coboundary_of_a_cell ( std::size_t  cell) const
inlinevirtual

The functions get_coboundary_of_a_cell, get_coboundary_of_a_cell, get_dimension_of_a_cell and get_cell_data are the basic functions that compute boundary / coboundary / dimension and the filtration value form a position of a cell in the structure of a bitmap. The input parameter of all of those function is a non-negative integer, indicating a position of a cube in the data structure. In the case of functions that compute (co)boundary, the output is a vector if non-negative integers pointing to the positions of (co)boundary element of the input cell. Note that unlike in the case of boundary, over here the elements are not guaranteed to be returned with alternating incidence numbers.

Reimplemented in Gudhi::cubical_complex::Bitmap_cubical_complex_periodic_boundary_conditions_base< T >.

◆ get_dimension_of_a_cell()

template<typename T >
unsigned Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::get_dimension_of_a_cell ( std::size_t  cell) const
inline

In the case of get_dimension_of_a_cell function, the output is a non-negative integer indicating the dimension of a cell. Note that unlike in the case of boundary, over here the elements are not guaranteed to be returned with alternating incidence numbers. To compute incidence between cells use compute_incidence_between_cells procedure

◆ impose_lower_star_filtration()

template<typename T >
void Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::impose_lower_star_filtration ( )

Typical input used to construct a baseBitmap class is a filtration given at the top dimensional cells. Then, there are a few ways one can pick the filtration of lower dimensional cells. The most typical one is by so called lower star filtration. This function is always called by any constructor which takes the top dimensional cells. If you use such a constructor, then there is no need to call this function. Call it only if you are putting the filtration of the cells by your own (for instance by using Top_dimensional_cells_iterator).

◆ min_max_filtration()

template<typename T >
std::pair< T, T > Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::min_max_filtration ( )

Functions to find min and max values of filtration.

◆ put_data_to_bins() [1/2]

template<typename T >
void Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::put_data_to_bins ( std::size_t  number_of_bins)

Function that put the input data to bins. By putting data to bins we mean rounding them to a sequence of values equally distributed in the range of data. Sometimes if most of the cells have different birth-death times, the performance of the algorithms to compute persistence gets worst. When dealing with this type of data, one may want to put different values on cells to some number of bins. The function put_data_to_bins( std::size_t number_of_bins ) is designed for that purpose. The parameter of the function is the number of bins (distinct values) we want to have in the cubical complex.

◆ put_data_to_bins() [2/2]

template<typename T >
void Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::put_data_to_bins ( diameter_of_bin)

Function that put the input data to bins. By putting data to bins we mean rounding them to a sequence of values equally distributed in the range of data. Sometimes if most of the cells have different birth-death times, the performance of the algorithms to compute persistence gets worst. When dealing with this type of data, one may want to put different values on cells to some number of bins. The function put_data_to_bins( T diameter_of_bin ) is designed for that purpose. The parameter of it is the diameter of each bin. Note that the bottleneck distance between the persistence diagram of the cubical complex before and after using such a function will be bounded by the parameter diameter_of_bin.

◆ size()

template<typename T>
unsigned Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::size ( ) const
inline

Returns number of all cubes in the data structure.

◆ top_dimensional_cells_iterator_begin()

template<typename T>
Top_dimensional_cells_iterator Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::top_dimensional_cells_iterator_begin ( )
inline

Function returning a Top_dimensional_cells_iterator to the first top dimensional cell of the bitmap.

◆ top_dimensional_cells_iterator_end()

template<typename T>
Top_dimensional_cells_iterator Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::top_dimensional_cells_iterator_end ( )
inline

Function returning a Top_dimensional_cells_iterator to the last top dimensional cell of the bitmap.

Friends And Related Function Documentation

◆ operator<<

template<typename T>
template<typename K >
std::ostream& operator<< ( std::ostream &  os,
const Bitmap_cubical_complex_base< K > &  b 
)
friend

Writing to stream operator. By using it we get the values T of cells in order in which they are stored in the structure. This procedure is used for debugging purposes.


The documentation for this class was generated from the following file:
GUDHI  Version 2.3.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Tue Sep 4 2018 14:33:00 for GUDHI by Doxygen 1.8.13