23 #ifndef BITMAP_CUBICAL_COMPLEX_BASE_H_ 24 #define BITMAP_CUBICAL_COMPLEX_BASE_H_ 26 #include <gudhi/Bitmap_cubical_complex/counter.h> 39 namespace cubical_complex {
63 typedef T filtration_type;
69 total_number_of_cells(0) { }
152 return this->data.size();
159 template <
typename K>
160 friend std::ostream& operator<<(std::ostream & os, const Bitmap_cubical_complex_base<K>& b);
219 if (this->
counter != rhs.counter)
return false;
224 return !(*
this == rhs);
255 a.counter = this->data.size();
286 typedef typename std::vector< size_t > Boundary_range;
300 typedef typename std::vector< size_t > Coboundary_range;
324 while ((dim != this->b.
dimension()) && (this->
counter[dim] == this->b.sizes[dim] - 1))++dim;
328 for (
size_t i = 0; i != dim; ++i) {
350 if (&this->b != &rhs.b)
return false;
351 if (this->
counter.size() != rhs.counter.size())
return false;
352 for (
size_t i = 0; i != this->
counter.size(); ++i) {
353 if (this->
counter[i] != rhs.counter[i])
return false;
359 return !(*
this == rhs);
370 return this->compute_index_in_bitmap();
373 size_t compute_index_in_bitmap()
const {
375 for (
size_t i = 0; i != this->
counter.size(); ++i) {
376 index += (2 * this->
counter[i] + 1) * this->b.multipliers[i];
381 void print_counter()
const {
382 for (
size_t i = 0; i != this->
counter.size(); ++i) {
383 std::cout << this->
counter[i] <<
" ";
405 for (
size_t i = 0; i != this->
dimension(); ++i) {
406 a.counter[i] = this->sizes[i] - 1;
440 inline size_t number_cells()
const {
441 return this->total_number_of_cells;
450 std::vector<unsigned> sizes;
451 std::vector<unsigned> multipliers;
453 size_t total_number_of_cells;
455 void set_up_containers(
const std::vector<unsigned>& sizes) {
456 unsigned multiplier = 1;
457 for (
size_t i = 0; i != sizes.size(); ++i) {
458 this->sizes.push_back(sizes[i]);
459 this->multipliers.push_back(multiplier);
460 multiplier *= 2 * sizes[i] + 1;
462 this->data = std::vector<T>(multiplier, std::numeric_limits<T>::max());
463 this->total_number_of_cells = multiplier;
466 size_t compute_position_in_bitmap(
const std::vector< unsigned >&
counter) {
468 for (
size_t i = 0; i != this->multipliers.size(); ++i) {
469 position += this->multipliers[i] * counter[i];
474 std::vector<unsigned> compute_counter_for_given_cell(
size_t cell)
const {
475 std::vector<unsigned> counter;
476 counter.reserve(this->sizes.size());
477 for (
size_t dim = this->sizes.size(); dim != 0; --dim) {
478 counter.push_back(cell / this->multipliers[dim - 1]);
479 cell = cell % this->multipliers[dim - 1];
481 std::reverse(counter.begin(), counter.end());
484 void read_perseus_style_file(
const char* perseus_style_file);
485 void setup_bitmap_based_on_top_dimensional_cells_list(
const std::vector<unsigned>& sizes_in_following_directions,
486 const std::vector<T>& top_dimensional_cells);
490 const std::vector<T>& top_dimensional_cells,
491 std::vector<bool> directions);
494 template <
typename T>
499 T dx = (min_max.second - min_max.first) / (T) number_of_bins;
502 for (
size_t i = 0; i != this->data.size(); ++i) {
504 std::cerr <<
"Before binning : " << this->data[i] << std::endl;
506 this->data[i] = min_max.first + dx * (this->data[i] - min_max.first) / number_of_bins;
508 std::cerr <<
"After binning : " << this->data[i] << std::endl;
514 template <
typename T>
519 size_t number_of_bins = (min_max.second - min_max.first) / diameter_of_bin;
521 for (
size_t i = 0; i != this->data.size(); ++i) {
523 std::cerr <<
"Before binning : " << this->data[i] << std::endl;
525 this->data[i] = min_max.first + diameter_of_bin * (this->data[i] - min_max.first) / number_of_bins;
527 std::cerr <<
"After binning : " << this->data[i] << std::endl;
533 template <
typename T>
535 std::pair< T, T > min_max(std::numeric_limits<T>::max(), std::numeric_limits<T>::min());
536 for (
size_t i = 0; i != this->data.size(); ++i) {
537 if (this->data[i] < min_max.first)min_max.first = this->data[i];
538 if (this->data[i] > min_max.second)min_max.second = this->data[i];
543 template <
typename K>
544 std::ostream& operator<<(std::ostream & out, const Bitmap_cubical_complex_base<K>& b) {
546 it = b.all_cells_const_begin(); it != b.all_cells_const_end(); ++it) {
552 template <
typename T>
554 (
const std::vector<unsigned>& sizes) {
555 this->set_up_containers(sizes);
558 template <
typename T>
560 const std::vector<T>& top_dimensional_cells) {
561 this->set_up_containers(sizes_in_following_directions);
563 size_t number_of_top_dimensional_elements = 1;
564 for (
size_t i = 0; i != sizes_in_following_directions.size(); ++i) {
565 number_of_top_dimensional_elements *= sizes_in_following_directions[i];
567 if (number_of_top_dimensional_elements != top_dimensional_cells.size()) {
568 std::cerr <<
"Error in constructor Bitmap_cubical_complex_base ( std::vector<size_t> sizes_in_following_directions" 569 <<
", std::vector<T> top_dimensional_cells ). Number of top dimensional elements that follow from " 570 <<
"sizes_in_following_directions vector is different than the size of top_dimensional_cells vector." 572 throw(
"Error in constructor Bitmap_cubical_complex_base( std::vector<size_t> sizes_in_following_directions," 573 "std::vector<T> top_dimensional_cells ). Number of top dimensional elements that follow from " 574 "sizes_in_following_directions vector is different than the size of top_dimensional_cells vector.");
586 template <
typename T>
588 (
const std::vector<unsigned>& sizes_in_following_directions,
const std::vector<T>& top_dimensional_cells) {
589 this->setup_bitmap_based_on_top_dimensional_cells_list(sizes_in_following_directions, top_dimensional_cells);
592 template <
typename T>
595 std::ifstream inFiltration;
596 inFiltration.open(perseus_style_file);
597 unsigned dimensionOfData;
598 inFiltration >> dimensionOfData;
601 std::cerr <<
"dimensionOfData : " << dimensionOfData << std::endl;
605 std::vector<unsigned> sizes;
606 sizes.reserve(dimensionOfData);
607 for (
size_t i = 0; i != dimensionOfData; ++i) {
608 unsigned size_in_this_dimension;
609 inFiltration >> size_in_this_dimension;
610 sizes.push_back(size_in_this_dimension);
612 std::cerr <<
"size_in_this_dimension : " << size_in_this_dimension << std::endl;
615 this->set_up_containers(sizes);
620 while (!inFiltration.eof()) {
622 inFiltration >> filtrationLevel;
624 std::cerr <<
"Cell of an index : " 625 << it.compute_index_in_bitmap()
626 <<
" and dimension: " 628 <<
" get the value : " << filtrationLevel << std::endl;
633 inFiltration.close();
637 template <
typename T>
639 std::vector<bool> directions) {
643 this->read_perseus_style_file(perseus_style_file);
646 template <
typename T>
648 std::vector<bool> directions) {
652 this->set_up_containers(sizes);
655 template <
typename T>
657 const std::vector<T>& top_dimensional_cells,
658 std::vector<bool> directions) {
662 this->setup_bitmap_based_on_top_dimensional_cells_list(dimensions, top_dimensional_cells);
665 template <
typename T>
667 this->read_perseus_style_file(perseus_style_file);
670 template <
typename T>
672 std::vector< size_t > boundary_elements;
675 boundary_elements.reserve(this->
dimension()*2);
678 for (
size_t i = this->multipliers.size(); i != 0; --i) {
679 unsigned position = cell1 / this->multipliers[i - 1];
680 if (position % 2 == 1) {
681 boundary_elements.push_back(cell - this->multipliers[ i - 1 ]);
682 boundary_elements.push_back(cell + this->multipliers[ i - 1 ]);
684 cell1 = cell1 % this->multipliers[i - 1];
686 return boundary_elements;
689 template <
typename T>
691 std::vector<unsigned>
counter = this->compute_counter_for_given_cell(cell);
692 std::vector< size_t > coboundary_elements;
694 for (
size_t i = this->multipliers.size(); i != 0; --i) {
695 unsigned position = cell1 / this->multipliers[i - 1];
696 if (position % 2 == 0) {
697 if ((cell > this->multipliers[i - 1]) && (counter[i - 1] != 0)) {
698 coboundary_elements.push_back(cell - this->multipliers[i - 1]);
701 (cell + this->multipliers[i - 1] < this->data.size()) && (counter[i - 1] != 2 * this->sizes[i - 1])) {
702 coboundary_elements.push_back(cell + this->multipliers[i - 1]);
705 cell1 = cell1 % this->multipliers[i - 1];
707 return coboundary_elements;
710 template <
typename T>
713 if (dbg) std::cerr <<
"\n\n\n Computing position o a cell of an index : " << cell << std::endl;
715 for (
size_t i = this->multipliers.size(); i != 0; --i) {
716 unsigned position = cell / this->multipliers[i - 1];
719 std::cerr <<
"i-1 :" << i - 1 << std::endl;
720 std::cerr <<
"cell : " << cell << std::endl;
721 std::cerr <<
"position : " << position << std::endl;
722 std::cerr <<
"multipliers[" << i - 1 <<
"] = " << this->multipliers[i - 1] << std::endl;
726 if (position % 2 == 1) {
727 if (dbg) std::cerr <<
"Nonzero length in this direction \n";
730 cell = cell % this->multipliers[i - 1];
735 template <
typename T>
737 return this->data[cell];
740 template <
typename T>
745 std::vector<bool> is_this_cell_considered(this->data.size(),
false);
747 size_t size_to_reserve = 1;
748 for (
size_t i = 0; i != this->multipliers.size(); ++i) {
749 size_to_reserve *= (size_t) ((this->multipliers[i] - 1) / 2);
752 std::vector<size_t> indices_to_consider;
753 indices_to_consider.reserve(size_to_reserve);
758 indices_to_consider.push_back(it.compute_index_in_bitmap());
761 while (indices_to_consider.size()) {
763 std::cerr <<
"indices_to_consider in this iteration \n";
764 for (
size_t i = 0; i != indices_to_consider.size(); ++i) {
765 std::cout << indices_to_consider[i] <<
" ";
769 std::vector<size_t> new_indices_to_consider;
770 for (
size_t i = 0; i != indices_to_consider.size(); ++i) {
772 for (
size_t boundaryIt = 0; boundaryIt != bd.size(); ++boundaryIt) {
774 std::cerr <<
"filtration of a cell : " << bd[boundaryIt] <<
" is : " << this->data[ bd[boundaryIt] ]
775 <<
" while of a cell: " << indices_to_consider[i] <<
" is: " << this->data[ indices_to_consider[i] ]
779 if (this->data[ bd[boundaryIt] ] > this->data[ indices_to_consider[i] ]) {
780 this->data[ bd[boundaryIt] ] = this->data[ indices_to_consider[i] ];
782 std::cerr <<
"Setting the value of a cell : " << bd[boundaryIt] <<
" to : " 783 << this->data[ indices_to_consider[i] ] << std::endl;
787 if (is_this_cell_considered[ bd[boundaryIt] ] ==
false) {
788 new_indices_to_consider.push_back(bd[boundaryIt]);
789 is_this_cell_considered[ bd[boundaryIt] ] =
true;
793 indices_to_consider.swap(new_indices_to_consider);
797 template <
typename T>
798 bool compareFirstElementsOfTuples(
const std::pair< std::pair< T, size_t >,
char >& first,
799 const std::pair< std::pair< T, size_t >,
char >& second) {
800 if (first.first.first < second.first.first) {
803 if (first.first.first > second.first.first) {
807 return first.second < second.second;
813 namespace Cubical_complex = cubical_complex;
817 #endif // BITMAP_CUBICAL_COMPLEX_BASE_H_ void impose_lower_star_filtration()
Definition: Bitmap_cubical_complex_base.h:741
virtual std::vector< size_t > get_boundary_of_a_cell(size_t cell) const
Definition: Bitmap_cubical_complex_base.h:671
Cubical complex represented as a bitmap, class with basic implementation.
Definition: Bitmap_cubical_complex_base.h:61
virtual ~Bitmap_cubical_complex_base()
Definition: Bitmap_cubical_complex_base.h:93
All_cells_iterator all_cells_iterator_begin()
Definition: Bitmap_cubical_complex_base.h:245
std::vector< size_t >::const_iterator Boundary_iterator
Definition: Bitmap_cubical_complex_base.h:285
Definition: SimplicialComplexForAlpha.h:26
This is an implementation of a counter being a vector of integers.
Definition: counter.h:43
Bitmap_cubical_complex_base()
Definition: Bitmap_cubical_complex_base.h:68
unsigned size() const
Definition: Bitmap_cubical_complex_base.h:151
unsigned get_dimension_of_a_cell(size_t cell) const
Definition: Bitmap_cubical_complex_base.h:711
Top_dimensional_cells_iterator top_dimensional_cells_iterator_end()
Definition: Bitmap_cubical_complex_base.h:403
virtual std::vector< size_t > get_coboundary_of_a_cell(size_t cell) const
Definition: Bitmap_cubical_complex_base.h:690
Top_dimensional_cells_iterator top_dimensional_cells_iterator_begin()
Definition: Bitmap_cubical_complex_base.h:395
void put_data_to_bins(size_t number_of_bins)
Definition: Bitmap_cubical_complex_base.h:495
Top_dimensional_cells_iterator_range class provides ranges for Top_dimensional_cells_iterator_range.
Definition: Bitmap_cubical_complex_base.h:415
Coboundary_range coboundary_range(size_t sh)
Definition: Bitmap_cubical_complex_base.h:306
Boundary_range boundary_range(size_t sh)
Definition: Bitmap_cubical_complex_base.h:292
All_cells_iterator all_cells_iterator_end()
Definition: Bitmap_cubical_complex_base.h:253
Iterator through all cells in the complex (in order they appear in the structure – i...
Definition: Bitmap_cubical_complex_base.h:195
std::vector< size_t >::const_iterator Coboundary_iterator
Definition: Bitmap_cubical_complex_base.h:299
std::pair< T, T > min_max_filtration()
Definition: Bitmap_cubical_complex_base.h:534
T & get_cell_data(size_t cell)
Definition: Bitmap_cubical_complex_base.h:736
All_cells_range class provides ranges for All_cells_iterator.
Definition: Bitmap_cubical_complex_base.h:262
unsigned dimension() const
Definition: Bitmap_cubical_complex_base.h:144
Iterator through top dimensional cells of the complex. The cells appear in order they are stored in t...
Definition: Bitmap_cubical_complex_base.h:314