Loading [MathJax]/extensions/TeX/AMSsymbols.js
All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
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#include <tbb/parallel_sort.h>
19#endif
20
21#include <limits>
22#include <utility> // for pair<>
23#include <algorithm> // for sort
24#include <vector>
25#include <numeric> // for iota
26#include <cstddef>
27
28namespace Gudhi {
29
30namespace cubical_complex {
31
32// global variable, was used just for debugging.
33const bool globalDbg = false;
34
35template <typename T>
36class is_before_in_filtration;
37
47template <typename T>
48class Bitmap_cubical_complex : public T {
49 public:
50 //*********************************************//
51 // Typedefs and typenames
52 //*********************************************//
53 typedef std::size_t Simplex_key;
54 typedef typename T::filtration_type Filtration_value;
55 typedef Simplex_key Simplex_handle;
56
57 //*********************************************//
58 // Constructors
59 //*********************************************//
60 // Over here we need to define various input types. I am proposing the following ones:
61 // Perseus style
62 // TODO(PD) H5 files?
63 // TODO(PD) binary files with little endiangs / big endians ?
64 // TODO(PD) constructor from a vector of elements of a type T. ?
65
69 Bitmap_cubical_complex(const char* perseus_style_file)
70 : T(perseus_style_file), key_associated_to_simplex(this->total_number_of_cells + 1) {
71 if (globalDbg) {
72 std::clog << "Bitmap_cubical_complex( const char* perseus_style_file )\n";
73 }
74 for (std::size_t i = 0; i != this->total_number_of_cells; ++i) {
75 this->key_associated_to_simplex[i] = i;
76 }
77 // we initialize this only once, in each constructor, when the bitmap is constructed.
78 // If the user decide to change some elements of the bitmap, then this procedure need
79 // to be called again.
81 }
82
88 Bitmap_cubical_complex(const std::vector<unsigned>& dimensions,
89 const std::vector<Filtration_value>& top_dimensional_cells)
90 : T(dimensions, top_dimensional_cells), key_associated_to_simplex(this->total_number_of_cells + 1) {
91 for (std::size_t i = 0; i != this->total_number_of_cells; ++i) {
92 this->key_associated_to_simplex[i] = i;
93 }
94 // we initialize this only once, in each constructor, when the bitmap is constructed.
95 // If the user decide to change some elements of the bitmap, then this procedure need
96 // to be called again.
98 }
99
107 Bitmap_cubical_complex(const std::vector<unsigned>& dimensions,
108 const std::vector<Filtration_value>& top_dimensional_cells,
109 std::vector<bool> directions_in_which_periodic_b_cond_are_to_be_imposed)
110 : T(dimensions, top_dimensional_cells, directions_in_which_periodic_b_cond_are_to_be_imposed),
111 key_associated_to_simplex(this->total_number_of_cells + 1) {
112 for (std::size_t i = 0; i != this->total_number_of_cells; ++i) {
113 this->key_associated_to_simplex[i] = i;
114 }
115 // we initialize this only once, in each constructor, when the bitmap is constructed.
116 // If the user decide to change some elements of the bitmap, then this procedure need
117 // to be called again.
119 }
120
125
126 //*********************************************//
127 // Other 'easy' functions
128 //*********************************************//
129
133 std::size_t num_simplices() const { return this->total_number_of_cells; }
134
138 static Simplex_handle null_simplex() {
139 if (globalDbg) {
140 std::clog << "Simplex_handle null_simplex()\n";
141 }
142 return std::numeric_limits<Simplex_handle>::max();
143 }
144
148 inline std::size_t dimension() const { return this->sizes.size(); }
149
153 inline unsigned dimension(Simplex_handle sh) const {
154 if (globalDbg) {
155 std::clog << "unsigned dimension(const Simplex_handle& sh)\n";
156 }
157 if (sh != null_simplex()) return this->get_dimension_of_a_cell(sh);
158 return -1;
159 }
160
164 Filtration_value filtration(Simplex_handle sh) {
165 if (globalDbg) {
166 std::clog << "Filtration_value filtration(const Simplex_handle& sh)\n";
167 }
168 // Returns the filtration value of a simplex.
169 if (sh != null_simplex()) return this->data[sh];
170 return std::numeric_limits<Filtration_value>::infinity();
171 }
172
176 static Simplex_key null_key() {
177 if (globalDbg) {
178 std::clog << "Simplex_key null_key()\n";
179 }
180 return std::numeric_limits<Simplex_handle>::max();
181 }
182
186 Simplex_key key(Simplex_handle sh) const {
187 if (globalDbg) {
188 std::clog << "Simplex_key key(const Simplex_handle& sh)\n";
189 }
190 if (sh != null_simplex()) {
191 return this->key_associated_to_simplex[sh];
192 }
193 return this->null_key();
194 }
195
199 Simplex_handle simplex(Simplex_key key) {
200 if (globalDbg) {
201 std::clog << "Simplex_handle simplex(Simplex_key key)\n";
202 }
203 if (key != null_key()) {
204 return this->simplex_associated_to_key[key];
205 }
206 return null_simplex();
207 }
208
212 void assign_key(Simplex_handle sh, Simplex_key key) {
213 if (globalDbg) {
214 std::clog << "void assign_key(Simplex_handle& sh, Simplex_key key)\n";
215 }
216 if (key == null_key()) return;
217 this->key_associated_to_simplex[sh] = key;
218 this->simplex_associated_to_key[key] = sh;
219 }
220
225
226 //*********************************************//
227 // Iterators
228 //*********************************************//
229
233 typedef typename std::vector<Simplex_handle>::iterator Boundary_simplex_iterator;
234 typedef typename std::vector<Simplex_handle> Boundary_simplex_range;
235
243
244 class Filtration_simplex_iterator : std::iterator<std::input_iterator_tag, Simplex_handle> {
245 // Iterator over all simplices of the complex in the order of the indexing scheme.
246 // 'value_type' must be 'Simplex_handle'.
247 public:
248 Filtration_simplex_iterator(Bitmap_cubical_complex* b) : b(b), position(0) {}
249
250 Filtration_simplex_iterator() : b(NULL), position(0) {}
251
252 Filtration_simplex_iterator operator++() {
253 if (globalDbg) {
254 std::clog << "Filtration_simplex_iterator operator++\n";
255 }
256 ++this->position;
257 return (*this);
258 }
259
260 Filtration_simplex_iterator operator++(int) {
261 Filtration_simplex_iterator result = *this;
262 ++(*this);
263 return result;
264 }
265
266 Filtration_simplex_iterator& operator=(const Filtration_simplex_iterator& rhs) {
267 if (globalDbg) {
268 std::clog << "Filtration_simplex_iterator operator =\n";
269 }
270 this->b = rhs.b;
271 this->position = rhs.position;
272 return (*this);
273 }
274
275 bool operator==(const Filtration_simplex_iterator& rhs) const {
276 if (globalDbg) {
277 std::clog << "bool operator == ( const Filtration_simplex_iterator& rhs )\n";
278 }
279 return (this->position == rhs.position);
280 }
281
282 bool operator!=(const Filtration_simplex_iterator& rhs) const {
283 if (globalDbg) {
284 std::clog << "bool operator != ( const Filtration_simplex_iterator& rhs )\n";
285 }
286 return !(*this == rhs);
287 }
288
289 Simplex_handle operator*() {
290 if (globalDbg) {
291 std::clog << "Simplex_handle operator*()\n";
292 }
293 return this->b->simplex_associated_to_key[this->position];
294 }
295
296 friend class Filtration_simplex_range;
297
298 private:
299 Bitmap_cubical_complex<T>* b;
300 std::size_t position;
301 };
302
307 // Range over the simplices of the complex in the order of the filtration.
308 // .begin() and .end() return type Filtration_simplex_iterator.
309 public:
310 typedef Filtration_simplex_iterator const_iterator;
311 typedef Filtration_simplex_iterator iterator;
312
314
315 Filtration_simplex_iterator begin() {
316 if (globalDbg) {
317 std::clog << "Filtration_simplex_iterator begin() \n";
318 }
319 return Filtration_simplex_iterator(this->b);
320 }
321
322 Filtration_simplex_iterator end() {
323 if (globalDbg) {
324 std::clog << "Filtration_simplex_iterator end()\n";
325 }
326 Filtration_simplex_iterator it(this->b);
327 it.position = this->b->simplex_associated_to_key.size();
328 return it;
329 }
330
331 private:
333 };
334
335 //*********************************************//
336 // Methods to access iterators from the container:
337
342 Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) { return this->get_boundary_of_a_cell(sh); }
343
349 if (globalDbg) {
350 std::clog << "Filtration_simplex_range filtration_simplex_range()\n";
351 }
352 // Returns a range over the simplices of the complex in the order of the filtration
353 return Filtration_simplex_range(this);
354 }
355 //*********************************************//
356
357 //*********************************************//
358 // Elements which are in Gudhi now, but I (and in all the cases I asked also Marc) do not understand why they are
359 // there.
360 // TODO(PD) the file IndexingTag.h in the Gudhi library contains an empty structure, so
361 // I understand that this is something that was planned (for simplicial maps?)
362 // but was never finished. The only idea I have here is to use the same empty structure from
363 // IndexingTag.h file, but only if the compiler needs it. If the compiler
364 // do not need it, then I would rather not add here elements which I do not understand.
365 // typedef Indexing_tag
366
370 std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
371 std::vector<std::size_t> bdry = this->get_boundary_of_a_cell(sh);
372 if (globalDbg) {
373 std::clog << "std::pair<Simplex_handle, Simplex_handle> endpoints( Simplex_handle sh )\n";
374 std::clog << "bdry.size() : " << bdry.size() << "\n";
375 }
376 // this method returns two first elements from the boundary of sh.
377 if (bdry.size() < 2)
378 throw(
379 "Error in endpoints in Bitmap_cubical_complex class. The cell have less than two elements in the "
380 "boundary.");
381 return std::make_pair(bdry[0], bdry[1]);
382 }
383
387 class Skeleton_simplex_range;
388
389 class Skeleton_simplex_iterator : std::iterator<std::input_iterator_tag, Simplex_handle> {
390 // Iterator over all simplices of the complex in the order of the indexing scheme.
391 // 'value_type' must be 'Simplex_handle'.
392 public:
393 Skeleton_simplex_iterator(Bitmap_cubical_complex* b, std::size_t d) : b(b), dimension(d) {
394 if (globalDbg) {
395 std::clog << "Skeleton_simplex_iterator ( Bitmap_cubical_complex* b , std::size_t d )\n";
396 }
397 // find the position of the first simplex of a dimension d
398 this->position = 0;
399 while ((this->position != b->data.size()) &&
400 (this->b->get_dimension_of_a_cell(this->position) != this->dimension)) {
401 ++this->position;
402 }
403 }
404
405 Skeleton_simplex_iterator() : b(NULL), position(0), dimension(0) {}
406
407 Skeleton_simplex_iterator operator++() {
408 if (globalDbg) {
409 std::clog << "Skeleton_simplex_iterator operator++()\n";
410 }
411 // increment the position as long as you did not get to the next element of the dimension dimension.
412 ++this->position;
413 while ((this->position != this->b->data.size()) &&
414 (this->b->get_dimension_of_a_cell(this->position) != this->dimension)) {
415 ++this->position;
416 }
417 return (*this);
418 }
419
420 Skeleton_simplex_iterator operator++(int) {
421 Skeleton_simplex_iterator result = *this;
422 ++(*this);
423 return result;
424 }
425
426 Skeleton_simplex_iterator& operator=(const Skeleton_simplex_iterator& rhs) {
427 if (globalDbg) {
428 std::clog << "Skeleton_simplex_iterator operator =\n";
429 }
430 this->b = rhs.b;
431 this->position = rhs.position;
432 this->dimension = rhs.dimension;
433 return (*this);
434 }
435
436 bool operator==(const Skeleton_simplex_iterator& rhs) const {
437 if (globalDbg) {
438 std::clog << "bool operator ==\n";
439 }
440 return (this->position == rhs.position);
441 }
442
443 bool operator!=(const Skeleton_simplex_iterator& rhs) const {
444 if (globalDbg) {
445 std::clog << "bool operator != ( const Skeleton_simplex_iterator& rhs )\n";
446 }
447 return !(*this == rhs);
448 }
449
450 Simplex_handle operator*() {
451 if (globalDbg) {
452 std::clog << "Simplex_handle operator*() \n";
453 }
454 return this->position;
455 }
456
457 friend class Skeleton_simplex_range;
458
459 private:
460 Bitmap_cubical_complex<T>* b;
461 std::size_t position;
462 unsigned dimension;
463 };
464
469 // Range over the simplices of the complex in the order of the filtration.
470 // .begin() and .end() return type Filtration_simplex_iterator.
471 public:
472 typedef Skeleton_simplex_iterator const_iterator;
473 typedef Skeleton_simplex_iterator iterator;
474
475 Skeleton_simplex_range(Bitmap_cubical_complex<T>* b, unsigned dimension) : b(b), dimension(dimension) {}
476
477 Skeleton_simplex_iterator begin() {
478 if (globalDbg) {
479 std::clog << "Skeleton_simplex_iterator begin()\n";
480 }
481 return Skeleton_simplex_iterator(this->b, this->dimension);
482 }
483
484 Skeleton_simplex_iterator end() {
485 if (globalDbg) {
486 std::clog << "Skeleton_simplex_iterator end()\n";
487 }
488 Skeleton_simplex_iterator it(this->b, this->dimension);
489 it.position = this->b->data.size();
490 return it;
491 }
492
493 private:
495 unsigned dimension;
496 };
497
502 if (globalDbg) {
503 std::clog << "Skeleton_simplex_range skeleton_simplex_range( unsigned dimension )\n";
504 }
505 return Skeleton_simplex_range(this, dimension);
506 }
507
508 friend class is_before_in_filtration<T>;
509
510 protected:
511 std::vector<std::size_t> key_associated_to_simplex;
512 std::vector<std::size_t> simplex_associated_to_key;
513}; // Bitmap_cubical_complex
514
515template <typename T>
517 if (globalDbg) {
518 std::clog << "void Bitmap_cubical_complex<T>::initialize_elements_ordered_according_to_filtration() \n";
519 }
520 this->simplex_associated_to_key = std::vector<std::size_t>(this->data.size());
521 std::iota(std::begin(simplex_associated_to_key), std::end(simplex_associated_to_key), 0);
522#ifdef GUDHI_USE_TBB
523 tbb::parallel_sort(simplex_associated_to_key.begin(), simplex_associated_to_key.end(),
524 is_before_in_filtration<T>(this));
525#else
526 std::sort(simplex_associated_to_key.begin(), simplex_associated_to_key.end(), is_before_in_filtration<T>(this));
527#endif
528
529 // we still need to deal here with a key_associated_to_simplex:
530 for (std::size_t i = 0; i != simplex_associated_to_key.size(); ++i) {
531 this->key_associated_to_simplex[simplex_associated_to_key[i]] = i;
532 }
533}
534
535template <typename T>
536class is_before_in_filtration {
537 public:
538 explicit is_before_in_filtration(Bitmap_cubical_complex<T>* CC) : CC_(CC) {}
539
540 bool operator()(const typename Bitmap_cubical_complex<T>::Simplex_handle& sh1,
541 const typename Bitmap_cubical_complex<T>::Simplex_handle& sh2) const {
542 // Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
543 typedef typename T::filtration_type Filtration_value;
544 Filtration_value fil1 = CC_->data[sh1];
545 Filtration_value fil2 = CC_->data[sh2];
546 if (fil1 != fil2) {
547 return fil1 < fil2;
548 }
549 // in this case they are on the same filtration level, so the dimension decide.
550 std::size_t dim1 = CC_->get_dimension_of_a_cell(sh1);
551 std::size_t dim2 = CC_->get_dimension_of_a_cell(sh2);
552 if (dim1 != dim2) {
553 return dim1 < dim2;
554 }
555 // in this case both filtration and dimensions of the considered cubes are the same. To have stable sort, we simply
556 // compare their positions in the bitmap:
557 return sh1 < sh2;
558 }
559
560 protected:
561 Bitmap_cubical_complex<T>* CC_;
562};
563
564} // namespace cubical_complex
565
566namespace Cubical_complex = cubical_complex;
567
568} // namespace Gudhi
569
570#endif // BITMAP_CUBICAL_COMPLEX_H_
Filtration_simplex_range provides the ranges for Filtration_simplex_iterator.
Definition: Bitmap_cubical_complex.h:306
Class needed for compatibility with Gudhi. Not useful for other purposes.
Definition: Bitmap_cubical_complex.h:468
Cubical complex represented as a bitmap.
Definition: Bitmap_cubical_complex.h:48
std::pair< Simplex_handle, Simplex_handle > endpoints(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:370
Bitmap_cubical_complex(const std::vector< unsigned > &dimensions, const std::vector< Filtration_value > &top_dimensional_cells)
Definition: Bitmap_cubical_complex.h:88
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:107
Filtration_simplex_range filtration_simplex_range()
Definition: Bitmap_cubical_complex.h:348
Bitmap_cubical_complex(const char *perseus_style_file)
Definition: Bitmap_cubical_complex.h:69
Simplex_key key(Simplex_handle sh) const
Definition: Bitmap_cubical_complex.h:186
std::size_t dimension() const
Definition: Bitmap_cubical_complex.h:148
std::vector< Simplex_handle >::iterator Boundary_simplex_iterator
Definition: Bitmap_cubical_complex.h:233
Filtration_value filtration(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:164
Boundary_simplex_range boundary_simplex_range(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:342
void assign_key(Simplex_handle sh, Simplex_key key)
Definition: Bitmap_cubical_complex.h:212
static Simplex_key null_key()
Definition: Bitmap_cubical_complex.h:176
Simplex_handle simplex(Simplex_key key)
Definition: Bitmap_cubical_complex.h:199
unsigned dimension(Simplex_handle sh) const
Definition: Bitmap_cubical_complex.h:153
void initialize_simplex_associated_to_key()
Definition: Bitmap_cubical_complex.h:516
std::size_t num_simplices() const
Definition: Bitmap_cubical_complex.h:133
Skeleton_simplex_range skeleton_simplex_range(unsigned dimension)
Definition: Bitmap_cubical_complex.h:501
static Simplex_handle null_simplex()
Definition: Bitmap_cubical_complex.h:138
virtual ~Bitmap_cubical_complex()
Definition: Bitmap_cubical_complex.h:124
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
GUDHI  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Thu Jan 13 2022 08:34:27 for GUDHI by Doxygen 1.9.2