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

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_iteratorAll_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 ( )
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 ( ) 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
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\).

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

◆ 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 ( 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: