Loading...
Searching...
No Matches
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/Debug_utils.h>
15#include <gudhi/Bitmap_cubical_complex_base.h>
16#include <gudhi/Bitmap_cubical_complex_periodic_boundary_conditions_base.h>
17
18#ifdef GUDHI_USE_TBB
19#include <tbb/parallel_sort.h>
20#endif
21
22#include <limits>
23#include <utility> // for pair<>
24#include <algorithm> // for sort
25#include <vector>
26#include <numeric> // for iota
27#include <cstddef>
28
29namespace Gudhi {
30
31namespace cubical_complex {
32
33template <typename T>
34class is_before_in_filtration;
35
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 endians / big endians ?
64 // TODO(PD) constructor from a vector of elements of a type T. ?
65
69 explicit Bitmap_cubical_complex(const char* perseus_style_file)
70 : T(perseus_style_file), key_associated_to_simplex(num_simplices()) {
71#ifdef DEBUG_TRACES
72 std::clog << "Bitmap_cubical_complex( const char* perseus_style_file )\n";
73#endif
74 }
75
82 Bitmap_cubical_complex(const std::vector<unsigned>& dimensions,
83 const std::vector<Filtration_value>& cells,
84 bool input_top_cells = true)
85 : T(dimensions, cells, input_top_cells), key_associated_to_simplex(num_simplices()) {
86 }
87
95 Bitmap_cubical_complex(const std::vector<unsigned>& dimensions,
96 const std::vector<Filtration_value>& cells,
97 const std::vector<bool>& directions_in_which_periodic_b_cond_are_to_be_imposed,
98 bool input_top_cells = true)
99 : T(dimensions, cells, directions_in_which_periodic_b_cond_are_to_be_imposed, input_top_cells),
100 key_associated_to_simplex(num_simplices()) {
101 }
102
107
108 //*********************************************//
109 // Other 'easy' functions
110 //*********************************************//
111
115 std::size_t num_simplices() const { return this->total_number_of_cells; }
116
120 static Simplex_handle null_simplex() {
121#ifdef DEBUG_TRACES
122 std::clog << "Simplex_handle null_simplex()\n";
123#endif
124 return std::numeric_limits<Simplex_handle>::max();
125 }
126
130 inline std::size_t dimension() const { return this->sizes.size(); }
131
135 inline unsigned dimension(Simplex_handle sh) const {
136#ifdef DEBUG_TRACES
137 std::clog << "unsigned dimension(const Simplex_handle& sh)\n";
138#endif
139 if (sh != null_simplex()) return this->get_dimension_of_a_cell(sh);
140 return -1;
141 }
142
146 Filtration_value filtration(Simplex_handle sh) {
147#ifdef DEBUG_TRACES
148 std::clog << "Filtration_value filtration(const Simplex_handle& sh)\n";
149#endif
150 // Returns the filtration value of a simplex.
151 if (sh != null_simplex()) return this->data[sh];
152 return std::numeric_limits<Filtration_value>::infinity();
153 }
154
158 static Simplex_key null_key() {
159#ifdef DEBUG_TRACES
160 std::clog << "Simplex_key null_key()\n";
161#endif
162 return std::numeric_limits<Simplex_handle>::max();
163 }
164
168 Simplex_key key(Simplex_handle sh) const {
169#ifdef DEBUG_TRACES
170 std::clog << "Simplex_key key(const Simplex_handle& sh)\n";
171#endif
172 GUDHI_CHECK(sh != null_simplex(), std::invalid_argument("key(null_simplex()) is not supported"));
173 return this->key_associated_to_simplex[sh];
174 }
175
181 Simplex_handle simplex(Simplex_key k) {
182#ifdef DEBUG_TRACES
183 std::clog << "Simplex_handle simplex(Simplex_key key)\n";
184#endif
185 GUDHI_CHECK (k != null_key(), std::invalid_argument("simplex(null_key()) is not supported"));
186 GUDHI_CHECK (!sorted_cells.empty(), std::logic_error("initialize_filtration() or filtration_simplex_range() must be called before simplex()"));
187 return this->sorted_cells[k];
188 }
189
193 void assign_key(Simplex_handle sh, Simplex_key key) {
194#ifdef DEBUG_TRACES
195 std::clog << "void assign_key(Simplex_handle& sh, Simplex_key key)\n";
196#endif
197 GUDHI_CHECK(sh != null_simplex(), std::invalid_argument("assign_key(null_simplex()) is not supported"));
198 this->key_associated_to_simplex[sh] = key;
199 }
200
206
207 //*********************************************//
208 // Iterators
209 //*********************************************//
210
214 typedef typename std::vector<Simplex_handle>::iterator Boundary_simplex_iterator;
215 typedef typename std::vector<Simplex_handle> Boundary_simplex_range;
216
223 typedef std::vector<Simplex_handle> Filtration_simplex_range;
224
225 //*********************************************//
226 // Methods to access iterators from the container:
227
232 Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) { return this->get_boundary_of_a_cell(sh); }
233
241#ifdef DEBUG_TRACES
242 std::clog << "Filtration_simplex_range filtration_simplex_range()\n";
243#endif
244 if (sorted_cells.empty()) initialize_filtration();
245 return sorted_cells;
246 }
247 //*********************************************//
248
249 //*********************************************//
250 // Elements which are in Gudhi now, but I (and in all the cases I asked also Marc) do not understand why they are
251 // there.
252 // TODO(PD) the file IndexingTag.h in the Gudhi library contains an empty structure, so
253 // I understand that this is something that was planned (for simplicial maps?)
254 // but was never finished. The only idea I have here is to use the same empty structure from
255 // IndexingTag.h file, but only if the compiler needs it. If the compiler
256 // do not need it, then I would rather not add here elements which I do not understand.
257 // typedef Indexing_tag
258
262 std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle e) {
263 std::vector<std::size_t> bdry = this->get_boundary_of_a_cell(e);
264#ifdef DEBUG_TRACES
265 std::clog << "std::pair<Simplex_handle, Simplex_handle> endpoints( Simplex_handle e )\n";
266 std::clog << "bdry.size() : " << bdry.size() << "\n";
267#endif
268 if (bdry.size() != 2)
269 throw(
270 "Error in endpoints in Bitmap_cubical_complex class. The cell is not an edge.");
271 return std::make_pair(bdry[0], bdry[1]);
272 }
273
277 class Skeleton_simplex_range;
278
279 class Skeleton_simplex_iterator {
280 // Iterator over all simplices of the complex in the order of the indexing scheme.
281 public:
282 typedef std::input_iterator_tag iterator_category;
283 typedef Simplex_handle value_type;
284 typedef std::ptrdiff_t difference_type;
285 typedef value_type* pointer;
286 typedef value_type reference;
287
288 Skeleton_simplex_iterator(Bitmap_cubical_complex* b, std::size_t d) : b(b), dimension(d) {
289#ifdef DEBUG_TRACES
290 std::clog << "Skeleton_simplex_iterator ( Bitmap_cubical_complex* b , std::size_t d )\n";
291#endif
292 // find the position of the first simplex of a dimension d
293 this->position = 0;
294 while ((this->position != b->data.size()) &&
295 (this->b->get_dimension_of_a_cell(this->position) != this->dimension)) {
296 ++this->position;
297 }
298 }
299
300 Skeleton_simplex_iterator() : b(NULL), position(0), dimension(0) {}
301
302 Skeleton_simplex_iterator operator++() {
303#ifdef DEBUG_TRACES
304 std::clog << "Skeleton_simplex_iterator operator++()\n";
305#endif
306 // increment the position as long as you did not get to the next element of the dimension dimension.
307 ++this->position;
308 while ((this->position != this->b->data.size()) &&
309 (this->b->get_dimension_of_a_cell(this->position) != this->dimension)) {
310 ++this->position;
311 }
312 return (*this);
313 }
314
315 Skeleton_simplex_iterator operator++(int) {
316 Skeleton_simplex_iterator result = *this;
317 ++(*this);
318 return result;
319 }
320
321 bool operator==(const Skeleton_simplex_iterator& rhs) const {
322#ifdef DEBUG_TRACES
323 std::clog << "bool operator ==\n";
324#endif
325 return (this->position == rhs.position);
326 }
327
328 bool operator!=(const Skeleton_simplex_iterator& rhs) const {
329#ifdef DEBUG_TRACES
330 std::clog << "bool operator != ( const Skeleton_simplex_iterator& rhs )\n";
331#endif
332 return !(*this == rhs);
333 }
334
335 Simplex_handle operator*() {
336#ifdef DEBUG_TRACES
337 std::clog << "Simplex_handle operator*() \n";
338#endif
339 return this->position;
340 }
341
342 friend class Skeleton_simplex_range;
343
344 private:
345 Bitmap_cubical_complex<T>* b;
346 std::size_t position;
347 unsigned dimension;
348 };
349
354 // Range over the simplices of the complex in the order of the filtration.
355 // .begin() and .end() return type Skeleton_simplex_iterator.
356 public:
357 typedef Skeleton_simplex_iterator const_iterator;
358 typedef Skeleton_simplex_iterator iterator;
359
360 Skeleton_simplex_range(Bitmap_cubical_complex<T>* b, unsigned dimension) : b(b), dimension(dimension) {}
361
362 Skeleton_simplex_iterator begin() {
363#ifdef DEBUG_TRACES
364 std::clog << "Skeleton_simplex_iterator begin()\n";
365#endif
366 return Skeleton_simplex_iterator(this->b, this->dimension);
367 }
368
369 Skeleton_simplex_iterator end() {
370#ifdef DEBUG_TRACES
371 std::clog << "Skeleton_simplex_iterator end()\n";
372#endif
373 Skeleton_simplex_iterator it(this->b, this->dimension);
374 it.position = this->b->data.size();
375 return it;
376 }
377
378 private:
380 unsigned dimension;
381 };
382
387#ifdef DEBUG_TRACES
388 std::clog << "Skeleton_simplex_range skeleton_simplex_range( unsigned dimension )\n";
389#endif
390 return Skeleton_simplex_range(this, dimension);
391 }
392
393 friend class is_before_in_filtration<T>;
394
395 protected:
396 std::vector<std::size_t> key_associated_to_simplex;
397 std::vector<std::size_t> sorted_cells;
398}; // Bitmap_cubical_complex
399
400template <typename T>
402#ifdef DEBUG_TRACES
403 std::clog << "void Bitmap_cubical_complex<T>::initialize_elements_ordered_according_to_filtration() \n";
404#endif
405 this->sorted_cells.resize(this->data.size());
406 std::iota(std::begin(sorted_cells), std::end(sorted_cells), 0);
407#ifdef GUDHI_USE_TBB
408 tbb::parallel_sort(sorted_cells.begin(), sorted_cells.end(),
409 is_before_in_filtration<T>(this));
410#else
411 std::sort(sorted_cells.begin(), sorted_cells.end(), is_before_in_filtration<T>(this));
412#endif
413}
414
415template <typename T>
416class is_before_in_filtration {
417 public:
418 explicit is_before_in_filtration(Bitmap_cubical_complex<T>* CC) : CC_(CC) {}
419
420 bool operator()(const typename Bitmap_cubical_complex<T>::Simplex_handle& sh1,
421 const typename Bitmap_cubical_complex<T>::Simplex_handle& sh2) const {
422 // Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
423 typedef typename T::filtration_type Filtration_value;
424 Filtration_value fil1 = CC_->data[sh1];
425 Filtration_value fil2 = CC_->data[sh2];
426 if (fil1 != fil2) {
427 return fil1 < fil2;
428 }
429 // in this case they are on the same filtration level, so the dimension decide.
430 std::size_t dim1 = CC_->get_dimension_of_a_cell(sh1);
431 std::size_t dim2 = CC_->get_dimension_of_a_cell(sh2);
432 if (dim1 != dim2) {
433 return dim1 < dim2;
434 }
435 // in this case both filtration and dimensions of the considered cubes are the same. To have stable sort, we simply
436 // compare their positions in the bitmap:
437 return sh1 < sh2;
438 }
439
440 protected:
441 Bitmap_cubical_complex<T>* CC_;
442};
443
444} // namespace cubical_complex
445
446namespace Cubical_complex = cubical_complex;
447
448} // namespace Gudhi
449
450#endif // BITMAP_CUBICAL_COMPLEX_H_
Class needed for compatibility with Gudhi. Not useful for other purposes.
Definition: Bitmap_cubical_complex.h:353
Cubical complex represented as a bitmap.
Definition: Bitmap_cubical_complex.h:48
Filtration_simplex_range const & filtration_simplex_range()
Definition: Bitmap_cubical_complex.h:240
Bitmap_cubical_complex(const std::vector< unsigned > &dimensions, const std::vector< Filtration_value > &cells, const std::vector< bool > &directions_in_which_periodic_b_cond_are_to_be_imposed, bool input_top_cells=true)
Definition: Bitmap_cubical_complex.h:95
std::pair< Simplex_handle, Simplex_handle > endpoints(Simplex_handle e)
Definition: Bitmap_cubical_complex.h:262
Simplex_handle simplex(Simplex_key k)
Definition: Bitmap_cubical_complex.h:181
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:168
std::size_t dimension() const
Definition: Bitmap_cubical_complex.h:130
std::vector< Simplex_handle >::iterator Boundary_simplex_iterator
Definition: Bitmap_cubical_complex.h:214
std::vector< Simplex_handle > Filtration_simplex_range
Definition: Bitmap_cubical_complex.h:223
Filtration_value filtration(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:146
Boundary_simplex_range boundary_simplex_range(Simplex_handle sh)
Definition: Bitmap_cubical_complex.h:232
void assign_key(Simplex_handle sh, Simplex_key key)
Definition: Bitmap_cubical_complex.h:193
static Simplex_key null_key()
Definition: Bitmap_cubical_complex.h:158
unsigned dimension(Simplex_handle sh) const
Definition: Bitmap_cubical_complex.h:135
Bitmap_cubical_complex(const std::vector< unsigned > &dimensions, const std::vector< Filtration_value > &cells, bool input_top_cells=true)
Definition: Bitmap_cubical_complex.h:82
std::size_t num_simplices() const
Definition: Bitmap_cubical_complex.h:115
Skeleton_simplex_range skeleton_simplex_range(unsigned dimension)
Definition: Bitmap_cubical_complex.h:386
void initialize_filtration()
Definition: Bitmap_cubical_complex.h:401
static Simplex_handle null_simplex()
Definition: Bitmap_cubical_complex.h:120
virtual ~Bitmap_cubical_complex()
Definition: Bitmap_cubical_complex.h:106
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20