Bitmap_cubical_complex.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author(s): Pawel Dlotko
4  *
5  * Copyright (C) 2015 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef BITMAP_CUBICAL_COMPLEX_H_
12 #define BITMAP_CUBICAL_COMPLEX_H_
13 
14 #include <gudhi/Bitmap_cubical_complex_base.h>
15 #include <gudhi/Bitmap_cubical_complex_periodic_boundary_conditions_base.h>
16 
17 #ifdef GUDHI_USE_TBB
18 #ifndef Q_MOC_RUN
19 #include <tbb/parallel_sort.h>
20 #endif
21 #endif
22 
23 #include <limits>
24 #include <utility> // for pair<>
25 #include <algorithm> // for sort
26 #include <vector>
27 #include <numeric> // for iota
28 #include <cstddef>
29 
30 namespace Gudhi {
31 
32 namespace cubical_complex {
33 
34 // global variable, was used just for debugging.
35 const bool globalDbg = false;
36 
37 template <typename T>
38 class is_before_in_filtration;
39 
49 template <typename T>
50 class Bitmap_cubical_complex : public T {
51  public:
52  //*********************************************//
53  // Typedefs and typenames
54  //*********************************************//
55  typedef std::size_t Simplex_key;
56  typedef typename T::filtration_type Filtration_value;
57  typedef Simplex_key Simplex_handle;
58 
59  //*********************************************//
60  // Constructors
61  //*********************************************//
62  // Over here we need to define various input types. I am proposing the following ones:
63  // Perseus style
64  // TODO(PD) H5 files?
65  // TODO(PD) binary files with little endiangs / big endians ?
66  // TODO(PD) constructor from a vector of elements of a type T. ?
67 
71  Bitmap_cubical_complex(const char* perseus_style_file)
72  : T(perseus_style_file), key_associated_to_simplex(this->total_number_of_cells + 1) {
73  if (globalDbg) {
74  std::clog << "Bitmap_cubical_complex( const char* perseus_style_file )\n";
75  }
76  for (std::size_t i = 0; i != this->total_number_of_cells; ++i) {
77  this->key_associated_to_simplex[i] = i;
78  }
79  // we initialize this only once, in each constructor, when the bitmap is constructed.
80  // If the user decide to change some elements of the bitmap, then this procedure need
81  // to be called again.
83  }
84 
90  Bitmap_cubical_complex(const std::vector<unsigned>& dimensions,
91  const std::vector<Filtration_value>& top_dimensional_cells)
92  : T(dimensions, top_dimensional_cells), key_associated_to_simplex(this->total_number_of_cells + 1) {
93  for (std::size_t i = 0; i != this->total_number_of_cells; ++i) {
94  this->key_associated_to_simplex[i] = i;
95  }
96  // we initialize this only once, in each constructor, when the bitmap is constructed.
97  // If the user decide to change some elements of the bitmap, then this procedure need
98  // to be called again.
100  }
101 
109  Bitmap_cubical_complex(const std::vector<unsigned>& dimensions,
110  const std::vector<Filtration_value>& top_dimensional_cells,
111  std::vector<bool> directions_in_which_periodic_b_cond_are_to_be_imposed)
112  : T(dimensions, top_dimensional_cells, directions_in_which_periodic_b_cond_are_to_be_imposed),
113  key_associated_to_simplex(this->total_number_of_cells + 1) {
114  for (std::size_t i = 0; i != this->total_number_of_cells; ++i) {
115  this->key_associated_to_simplex[i] = i;
116  }
117  // we initialize this only once, in each constructor, when the bitmap is constructed.
118  // If the user decide to change some elements of the bitmap, then this procedure need
119  // to be called again.
121  }
122 
127 
128  //*********************************************//
129  // Other 'easy' functions
130  //*********************************************//
131 
135  std::size_t num_simplices() const { return this->total_number_of_cells; }
136 
140  static Simplex_handle null_simplex() {
141  if (globalDbg) {
142  std::clog << "Simplex_handle null_simplex()\n";
143  }
144  return std::numeric_limits<Simplex_handle>::max();
145  }
146 
150  inline std::size_t dimension() const { return this->sizes.size(); }
151 
155  inline unsigned dimension(Simplex_handle sh) const {
156  if (globalDbg) {
157  std::clog << "unsigned dimension(const Simplex_handle& sh)\n";
158  }
159  if (sh != null_simplex()) return this->get_dimension_of_a_cell(sh);
160  return -1;
161  }
162 
166  Filtration_value filtration(Simplex_handle sh) {
167  if (globalDbg) {
168  std::clog << "Filtration_value filtration(const Simplex_handle& sh)\n";
169  }
170  // Returns the filtration value of a simplex.
171  if (sh != null_simplex()) return this->data[sh];
172  return std::numeric_limits<Filtration_value>::infinity();
173  }
174 
178  static Simplex_key null_key() {
179  if (globalDbg) {
180  std::clog << "Simplex_key null_key()\n";
181  }
182  return std::numeric_limits<Simplex_handle>::max();
183  }
184 
188  Simplex_key key(Simplex_handle sh) const {
189  if (globalDbg) {
190  std::clog << "Simplex_key key(const Simplex_handle& sh)\n";
191  }
192  if (sh != null_simplex()) {
193  return this->key_associated_to_simplex[sh];
194  }
195  return this->null_key();
196  }
197 
201  Simplex_handle simplex(Simplex_key key) {
202  if (globalDbg) {
203  std::clog << "Simplex_handle simplex(Simplex_key key)\n";
204  }
205  if (key != null_key()) {
206  return this->simplex_associated_to_key[key];
207  }
208  return null_simplex();
209  }
210 
214  void assign_key(Simplex_handle sh, Simplex_key key) {
215  if (globalDbg) {
216  std::clog << "void assign_key(Simplex_handle& sh, Simplex_key key)\n";
217  }
218  if (key == null_key()) return;
219  this->key_associated_to_simplex[sh] = key;
220  this->simplex_associated_to_key[key] = sh;
221  }
222 
227 
228  //*********************************************//
229  // Iterators
230  //*********************************************//
231 
235  typedef typename std::vector<Simplex_handle>::iterator Boundary_simplex_iterator;
236  typedef typename std::vector<Simplex_handle> Boundary_simplex_range;
237 
245 
246  class Filtration_simplex_iterator : std::iterator<std::input_iterator_tag, Simplex_handle> {
247  // Iterator over all simplices of the complex in the order of the indexing scheme.
248  // 'value_type' must be 'Simplex_handle'.
249  public:
250  Filtration_simplex_iterator(Bitmap_cubical_complex* b) : b(b), position(0) {}
251 
252  Filtration_simplex_iterator() : b(NULL), position(0) {}
253 
254  Filtration_simplex_iterator operator++() {
255  if (globalDbg) {
256  std::clog << "Filtration_simplex_iterator operator++\n";
257  }
258  ++this->position;
259  return (*this);
260  }
261 
262  Filtration_simplex_iterator operator++(int) {
263  Filtration_simplex_iterator result = *this;
264  ++(*this);
265  return result;
266  }
267 
268  Filtration_simplex_iterator& operator=(const Filtration_simplex_iterator& rhs) {
269  if (globalDbg) {
270  std::clog << "Filtration_simplex_iterator operator =\n";
271  }
272  this->b = rhs.b;
273  this->position = rhs.position;
274  return (*this);
275  }
276 
277  bool operator==(const Filtration_simplex_iterator& rhs) const {
278  if (globalDbg) {
279  std::clog << "bool operator == ( const Filtration_simplex_iterator& rhs )\n";
280  }
281  return (this->position == rhs.position);
282  }
283 
284  bool operator!=(const Filtration_simplex_iterator& rhs) const {
285  if (globalDbg) {
286  std::clog << "bool operator != ( const Filtration_simplex_iterator& rhs )\n";
287  }
288  return !(*this == rhs);
289  }
290 
291  Simplex_handle operator*() {
292  if (globalDbg) {
293  std::clog << "Simplex_handle operator*()\n";
294  }
295  return this->b->simplex_associated_to_key[this->position];
296  }
297 
298  friend class Filtration_simplex_range;
299 
300  private:
301  Bitmap_cubical_complex<T>* b;
302  std::size_t position;
303  };
304 
309  // Range over the simplices of the complex in the order of the filtration.
310  // .begin() and .end() return type Filtration_simplex_iterator.
311  public:
312  typedef Filtration_simplex_iterator const_iterator;
313  typedef Filtration_simplex_iterator iterator;
314 
316 
317  Filtration_simplex_iterator begin() {
318  if (globalDbg) {
319  std::clog << "Filtration_simplex_iterator begin() \n";
320  }
321  return Filtration_simplex_iterator(this->b);
322  }
323 
324  Filtration_simplex_iterator end() {
325  if (globalDbg) {
326  std::clog << "Filtration_simplex_iterator end()\n";
327  }
328  Filtration_simplex_iterator it(this->b);
329  it.position = this->b->simplex_associated_to_key.size();
330  return it;
331  }
332 
333  private:
335  };
336 
337  //*********************************************//
338  // Methods to access iterators from the container:
339 
344  Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) { return this->get_boundary_of_a_cell(sh); }
345 
351  if (globalDbg) {
352  std::clog << "Filtration_simplex_range filtration_simplex_range()\n";
353  }
354  // Returns a range over the simplices of the complex in the order of the filtration
355  return Filtration_simplex_range(this);
356  }
357  //*********************************************//
358 
359  //*********************************************//
360  // Elements which are in Gudhi now, but I (and in all the cases I asked also Marc) do not understand why they are
361  // there.
362  // TODO(PD) the file IndexingTag.h in the Gudhi library contains an empty structure, so
363  // I understand that this is something that was planned (for simplicial maps?)
364  // but was never finished. The only idea I have here is to use the same empty structure from
365  // IndexingTag.h file, but only if the compiler needs it. If the compiler
366  // do not need it, then I would rather not add here elements which I do not understand.
367  // typedef Indexing_tag
368 
372  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
373  std::vector<std::size_t> bdry = this->get_boundary_of_a_cell(sh);
374  if (globalDbg) {
375  std::clog << "std::pair<Simplex_handle, Simplex_handle> endpoints( Simplex_handle sh )\n";
376  std::clog << "bdry.size() : " << bdry.size() << "\n";
377  }
378  // this method returns two first elements from the boundary of sh.
379  if (bdry.size() < 2)
380  throw(
381  "Error in endpoints in Bitmap_cubical_complex class. The cell have less than two elements in the "
382  "boundary.");
383  return std::make_pair(bdry[0], bdry[1]);
384  }
385 
389  class Skeleton_simplex_range;
390 
391  class Skeleton_simplex_iterator : std::iterator<std::input_iterator_tag, Simplex_handle> {
392  // Iterator over all simplices of the complex in the order of the indexing scheme.
393  // 'value_type' must be 'Simplex_handle'.
394  public:
395  Skeleton_simplex_iterator(Bitmap_cubical_complex* b, std::size_t d) : b(b), dimension(d) {
396  if (globalDbg) {
397  std::clog << "Skeleton_simplex_iterator ( Bitmap_cubical_complex* b , std::size_t d )\n";
398  }
399  // find the position of the first simplex of a dimension d
400  this->position = 0;
401  while ((this->position != b->data.size()) &&
402  (this->b->get_dimension_of_a_cell(this->position) != this->dimension)) {
403  ++this->position;
404  }
405  }
406 
407  Skeleton_simplex_iterator() : b(NULL), position(0), dimension(0) {}
408 
409  Skeleton_simplex_iterator operator++() {
410  if (globalDbg) {
411  std::clog << "Skeleton_simplex_iterator operator++()\n";
412  }
413  // increment the position as long as you did not get to the next element of the dimension dimension.
414  ++this->position;
415  while ((this->position != this->b->data.size()) &&
416  (this->b->get_dimension_of_a_cell(this->position) != this->dimension)) {
417  ++this->position;
418  }
419  return (*this);
420  }
421 
422  Skeleton_simplex_iterator operator++(int) {
423  Skeleton_simplex_iterator result = *this;
424  ++(*this);
425  return result;
426  }
427 
428  Skeleton_simplex_iterator& operator=(const Skeleton_simplex_iterator& rhs) {
429  if (globalDbg) {
430  std::clog << "Skeleton_simplex_iterator operator =\n";
431  }
432  this->b = rhs.b;
433  this->position = rhs.position;
434  this->dimension = rhs.dimension;
435  return (*this);
436  }
437 
438  bool operator==(const Skeleton_simplex_iterator& rhs) const {
439  if (globalDbg) {
440  std::clog << "bool operator ==\n";
441  }
442  return (this->position == rhs.position);
443  }
444 
445  bool operator!=(const Skeleton_simplex_iterator& rhs) const {
446  if (globalDbg) {
447  std::clog << "bool operator != ( const Skeleton_simplex_iterator& rhs )\n";
448  }
449  return !(*this == rhs);
450  }
451 
452  Simplex_handle operator*() {
453  if (globalDbg) {
454  std::clog << "Simplex_handle operator*() \n";
455  }
456  return this->position;
457  }
458 
459  friend class Skeleton_simplex_range;
460 
461  private:
462  Bitmap_cubical_complex<T>* b;
463  std::size_t position;
464  unsigned dimension;
465  };
466 
471  // Range over the simplices of the complex in the order of the filtration.
472  // .begin() and .end() return type Filtration_simplex_iterator.
473  public:
474  typedef Skeleton_simplex_iterator const_iterator;
475  typedef Skeleton_simplex_iterator iterator;
476 
477  Skeleton_simplex_range(Bitmap_cubical_complex<T>* b, unsigned dimension) : b(b), dimension(dimension) {}
478 
479  Skeleton_simplex_iterator begin() {
480  if (globalDbg) {
481  std::clog << "Skeleton_simplex_iterator begin()\n";
482  }
483  return Skeleton_simplex_iterator(this->b, this->dimension);
484  }
485 
486  Skeleton_simplex_iterator end() {
487  if (globalDbg) {
488  std::clog << "Skeleton_simplex_iterator end()\n";
489  }
490  Skeleton_simplex_iterator it(this->b, this->dimension);
491  it.position = this->b->data.size();
492  return it;
493  }
494 
495  private:
497  unsigned dimension;
498  };
499 
504  if (globalDbg) {
505  std::clog << "Skeleton_simplex_range skeleton_simplex_range( unsigned dimension )\n";
506  }
507  return Skeleton_simplex_range(this, dimension);
508  }
509 
510  friend class is_before_in_filtration<T>;
511 
512  protected:
513  std::vector<std::size_t> key_associated_to_simplex;
514  std::vector<std::size_t> simplex_associated_to_key;
515 }; // Bitmap_cubical_complex
516 
517 template <typename T>
519  if (globalDbg) {
520  std::clog << "void Bitmap_cubical_complex<T>::initialize_elements_ordered_according_to_filtration() \n";
521  }
522  this->simplex_associated_to_key = std::vector<std::size_t>(this->data.size());
523  std::iota(std::begin(simplex_associated_to_key), std::end(simplex_associated_to_key), 0);
524 #ifdef GUDHI_USE_TBB
525  tbb::parallel_sort(simplex_associated_to_key.begin(), simplex_associated_to_key.end(),
526  is_before_in_filtration<T>(this));
527 #else
528  std::sort(simplex_associated_to_key.begin(), simplex_associated_to_key.end(), is_before_in_filtration<T>(this));
529 #endif
530 
531  // we still need to deal here with a key_associated_to_simplex:
532  for (std::size_t i = 0; i != simplex_associated_to_key.size(); ++i) {
533  this->key_associated_to_simplex[simplex_associated_to_key[i]] = i;
534  }
535 }
536 
537 template <typename T>
538 class is_before_in_filtration {
539  public:
540  explicit is_before_in_filtration(Bitmap_cubical_complex<T>* CC) : CC_(CC) {}
541 
542  bool operator()(const typename Bitmap_cubical_complex<T>::Simplex_handle& sh1,
543  const typename Bitmap_cubical_complex<T>::Simplex_handle& sh2) const {
544  // Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
545  typedef typename T::filtration_type Filtration_value;
546  Filtration_value fil1 = CC_->data[sh1];
547  Filtration_value fil2 = CC_->data[sh2];
548  if (fil1 != fil2) {
549  return fil1 < fil2;
550  }
551  // in this case they are on the same filtration level, so the dimension decide.
552  std::size_t dim1 = CC_->get_dimension_of_a_cell(sh1);
553  std::size_t dim2 = CC_->get_dimension_of_a_cell(sh2);
554  if (dim1 != dim2) {
555  return dim1 < dim2;
556  }
557  // in this case both filtration and dimensions of the considered cubes are the same. To have stable sort, we simply
558  // compare their positions in the bitmap:
559  return sh1 < sh2;
560  }
561 
562  protected:
563  Bitmap_cubical_complex<T>* CC_;
564 };
565 
566 } // namespace cubical_complex
567 
568 namespace Cubical_complex = cubical_complex;
569 
570 } // namespace Gudhi
571 
572 #endif // BITMAP_CUBICAL_COMPLEX_H_
Gudhi::cubical_complex::Bitmap_cubical_complex::filtration
Filtration_value filtration(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:166
Gudhi::cubical_complex::Bitmap_cubical_complex::~Bitmap_cubical_complex
virtual ~Bitmap_cubical_complex()
Definition: Bitmap_cubical_complex.h:126
Gudhi::cubical_complex::Bitmap_cubical_complex::filtration_simplex_range
Filtration_simplex_range filtration_simplex_range()
Definition: Bitmap_cubical_complex.h:350
Gudhi::cubical_complex::Bitmap_cubical_complex::assign_key
void assign_key(Simplex_handle sh, Simplex_key key)
Definition: Bitmap_cubical_complex.h:214
Gudhi::cubical_complex::Bitmap_cubical_complex::key
Simplex_key key(Simplex_handle sh) const
Definition: Bitmap_cubical_complex.h:188
Gudhi::cubical_complex::Bitmap_cubical_complex::dimension
std::size_t dimension() const
Definition: Bitmap_cubical_complex.h:150
Gudhi::cubical_complex::Bitmap_cubical_complex::initialize_simplex_associated_to_key
void initialize_simplex_associated_to_key()
Definition: Bitmap_cubical_complex.h:518
Gudhi::cubical_complex::Bitmap_cubical_complex::null_key
static Simplex_key null_key()
Definition: Bitmap_cubical_complex.h:178
Gudhi::cubical_complex::Bitmap_cubical_complex::endpoints
std::pair< Simplex_handle, Simplex_handle > endpoints(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:372
Gudhi::cubical_complex::Bitmap_cubical_complex::Skeleton_simplex_range
Class needed for compatibility with Gudhi. Not useful for other purposes.
Definition: Bitmap_cubical_complex.h:470
Gudhi::cubical_complex::Bitmap_cubical_complex::Filtration_simplex_range
Filtration_simplex_range provides the ranges for Filtration_simplex_iterator.
Definition: Bitmap_cubical_complex.h:308
Gudhi::cubical_complex::Bitmap_cubical_complex::Bitmap_cubical_complex
Bitmap_cubical_complex(const std::vector< unsigned > &dimensions, const std::vector< Filtration_value > &top_dimensional_cells, std::vector< bool > directions_in_which_periodic_b_cond_are_to_be_imposed)
Definition: Bitmap_cubical_complex.h:109
Gudhi::cubical_complex::Bitmap_cubical_complex::Bitmap_cubical_complex
Bitmap_cubical_complex(const std::vector< unsigned > &dimensions, const std::vector< Filtration_value > &top_dimensional_cells)
Definition: Bitmap_cubical_complex.h:90
Gudhi::cubical_complex::Bitmap_cubical_complex::simplex
Simplex_handle simplex(Simplex_key key)
Definition: Bitmap_cubical_complex.h:201
Gudhi::cubical_complex::Bitmap_cubical_complex
Cubical complex represented as a bitmap.
Definition: Bitmap_cubical_complex.h:50
Gudhi::cubical_complex::Bitmap_cubical_complex::boundary_simplex_range
Boundary_simplex_range boundary_simplex_range(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:344
Gudhi::cubical_complex::Bitmap_cubical_complex::null_simplex
static Simplex_handle null_simplex()
Definition: Bitmap_cubical_complex.h:140
Gudhi::cubical_complex::Bitmap_cubical_complex::dimension
unsigned dimension(Simplex_handle sh) const
Definition: Bitmap_cubical_complex.h:155
Gudhi::cubical_complex::Bitmap_cubical_complex::num_simplices
std::size_t num_simplices() const
Definition: Bitmap_cubical_complex.h:135
Gudhi::cubical_complex::Bitmap_cubical_complex::skeleton_simplex_range
Skeleton_simplex_range skeleton_simplex_range(unsigned dimension)
Definition: Bitmap_cubical_complex.h:503
FiltrationValue
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
Gudhi::cubical_complex::Bitmap_cubical_complex::Bitmap_cubical_complex
Bitmap_cubical_complex(const char *perseus_style_file)
Definition: Bitmap_cubical_complex.h:71
Gudhi::cubical_complex::Bitmap_cubical_complex::Boundary_simplex_iterator
std::vector< Simplex_handle >::iterator Boundary_simplex_iterator
Definition: Bitmap_cubical_complex.h:235
GUDHI  Version 3.2.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Jul 10 2020 09:14:03 for GUDHI by Doxygen 1.8.17