Loading...
Searching...
No Matches
Gudhi::cubical_complex::Bitmap_cubical_complex_base< T > Class Template Reference
Cubical complex

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

`#include <include/gudhi/Bitmap_cubical_complex_base.h>`

## Classes

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
| Range corresponding to Top_dimensional_cells_iterator. More...

## Public Types

typedef boost::counting_iterator< std::size_t > | All_cells_iterator
| Iterator through all cells in the complex (in order they appear in the structure – i.e. in lexicographical order).
typedef boost::iterator_range< All_cells_iterator > | All_cells_range
| Range corresponding to All_cells_iterator.
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 > &cells, bool input_top_cells=true)
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
size_t | get_top_dimensional_coface_of_a_cell (size_t splx)
size_t | get_vertex_of_a_cell (size_t splx)
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 ()
void | impose_lower_star_filtration_from_vertices ()
unsigned | dimension () const
std::size_t | 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 () const
All_cells_iterator | all_cells_iterator_end () const
All_cells_range | all_cells_range () const
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 ()
Top_dimensional_cells_range | top_dimensional_cells_range ()

## 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 information 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
  Random_bitmap_cubical_complex.cpp, and cubical_complex_persistence.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]

template<typename T>

Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::Bitmap_cubical_complex_base | ( |  | ) |

inline

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

explicit

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

explicit

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 > & | cells,
|  | bool | input_top_cells = true )

The last constructor of a Bitmap_cubical_complex_base class accepts vector of dimensions (as the first one) with vector of filtration values of vertices or top dimensional cells depending on the input_top_cells flag.

## ~Bitmap_cubical_complex_base()

template<typename T>

virtual Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::~Bitmap_cubical_complex_base | ( |  | ) |

inline virtual

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 | ( |  | ) | const

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 | ( |  | ) | const

inline

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

## all_cells_range()

template<typename T>

All_cells_range Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::all_cells_range | ( |  | ) | const

inline

Returns a range over all cells.

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

inline virtual

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_error | In case when the cube \(B\) is not n-1 dimensional face of a cube \(A\).

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

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

inline virtual

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

inline virtual

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

## get_top_dimensional_coface_of_a_cell()

template<typename T>

size_t Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::get_top_dimensional_coface_of_a_cell | ( | size_t | splx | ) |

inline

This function finds a top-dimensional cell that is incident to the input cell and has the same filtration value. In case several cells are suitable, an arbitrary one is returned. Note that the input parameter can be a cell of any dimension (vertex, edge, etc). On the other hand, the output is always indicating the position of a top-dimensional cube in the data structure.

Precondition
  The filtration values are assigned as per impose_lower_star_filtration().

## get_vertex_of_a_cell()

template<typename T>

size_t Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::get_vertex_of_a_cell | ( | size_t | splx | ) |

inline

This function finds a vertex that is incident to the input cell and has the same filtration value. In case several cells are suitable, an arbitrary one is returned. Note that the input parameter can be a cell of any dimension (vertex, edge, etc). On the other hand, the output is always indicating the position of a vertex in the data structure.

Precondition
  The filtration values are assigned as per impose_lower_star_filtration_from_vertices().

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

## impose_lower_star_filtration_from_vertices()

template<typename T>

void Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::impose_lower_star_filtration_from_vertices | ( |  | ) |

Set cells filtrations given those of the vertices, and based on lower star filtration. This is already called by the relevant constructors.

## 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 | ( | T | 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>

std::size_t 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 beyond the last top dimensional cell of the bitmap.

## top_dimensional_cells_range()

template<typename T>

Top_dimensional_cells_range Gudhi::cubical_complex::Bitmap_cubical_complex_base< T >::top_dimensional_cells_range | ( |  | ) |

inline

Returns a range over all top-dimensional cells.

The documentation for this class was generated from the following file:

- include/gudhi/Bitmap_cubical_complex_base.h