Loading...
Searching...
No Matches
overlay_posidx_to_matidx.h
Go to the documentation of this file.
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): Hannah Schreiber
4 *
5 * Copyright (C) 2022-24 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
17#ifndef PM_POS_TO_ID_TRANSLATION_H
18#define PM_POS_TO_ID_TRANSLATION_H
19
20#include <vector>
21#include <utility> //std::swap, std::move & std::exchange
22#include <algorithm> //std::transform
23
24namespace Gudhi {
25namespace persistence_matrix {
26
38template <class Matrix_type, class Master_matrix_type>
40{
41 public:
42 using index = typename Master_matrix_type::index;
43 using id_index = typename Master_matrix_type::id_index;
44 using pos_index = typename Master_matrix_type::pos_index;
45 using dimension_type = typename Master_matrix_type::dimension_type;
49 using Field_operators = typename Master_matrix_type::Field_operators;
50 using Field_element_type = typename Master_matrix_type::element_type;
51 using boundary_type = typename Master_matrix_type::boundary_type;
52 using Column_type = typename Master_matrix_type::Column_type;
53 using Row_type = typename Master_matrix_type::Row_type;
55 using bar_type = typename Master_matrix_type::Bar;
56 using barcode_type = typename Master_matrix_type::barcode_type;
57 using cycle_type = typename Master_matrix_type::cycle_type;
58 using cell_rep_type = typename Master_matrix_type::cell_rep_type;
59 using Cell_constructor = typename Master_matrix_type::Cell_constructor;
60 using Column_settings = typename Master_matrix_type::Column_settings;
90 template <class Boundary_type = boundary_type>
91 Position_to_index_overlay(const std::vector<Boundary_type>& orderedBoundaries,
92 Column_settings* colSettings);
100 Position_to_index_overlay(unsigned int numberOfColumns,
101 Column_settings* colSettings);
124 template <typename BirthComparatorFunction, typename DeathComparatorFunction>
126 const BirthComparatorFunction& birthComparator,
127 const DeathComparatorFunction& deathComparator);
164 template <typename BirthComparatorFunction, typename DeathComparatorFunction, class Boundary_type>
165 Position_to_index_overlay(const std::vector<Boundary_type>& orderedBoundaries,
166 Column_settings* colSettings,
167 const BirthComparatorFunction& birthComparator,
168 const DeathComparatorFunction& deathComparator);
192 template <typename BirthComparatorFunction, typename DeathComparatorFunction>
193 Position_to_index_overlay(unsigned int numberOfColumns,
194 Column_settings* colSettings,
195 const BirthComparatorFunction& birthComparator,
196 const DeathComparatorFunction& deathComparator);
207 Column_settings* colSettings = nullptr);
214
234 template <class Boundary_type = boundary_type>
235 void insert_boundary(const Boundary_type& boundary, dimension_type dim = -1);
252 template <class Boundary_type = boundary_type>
253 void insert_boundary(id_index faceIndex, const Boundary_type& boundary, dimension_type dim = -1);
269 const Column_type& get_column(pos_index position) const;
278 Row_type& get_row(id_index rowIndex);
287 const Row_type& get_row(id_index rowIndex) const;
302 void erase_empty_row(id_index rowIndex);
316 void remove_maximal_face(pos_index position);
325 void remove_last();
326
347
358 void add_to(pos_index sourcePosition, pos_index targetPosition);
371 void multiply_target_and_add_to(pos_index sourcePosition,
372 const Field_element_type& coefficient,
373 pos_index targetPosition);
386 void multiply_source_and_add_to(const Field_element_type& coefficient,
387 pos_index sourcePosition,
388 pos_index targetPosition);
389
398 bool is_zero_cell(pos_index position, id_index rowIndex) const;
409 bool is_zero_column(pos_index position);
410
418 pos_index get_column_with_pivot(id_index faceIndex) const; // assumes that pivot exists
425 id_index get_pivot(pos_index position);
426
433 void reset(Column_settings* colSettings) {
434 matrix_.reset(colSettings);
435 positionToIndex_.clear();
436 nextPosition_ = 0;
437 nextIndex_ = 0;
438 }
439
440 // void set_operators(Field_operators* operators) { matrix_.set_operators(operators); }
441
450 swap(matrix1.matrix_, matrix2.matrix_);
451 matrix1.positionToIndex_.swap(matrix2.positionToIndex_);
452 std::swap(matrix1.nextPosition_, matrix2.nextPosition_);
453 std::swap(matrix1.nextIndex_, matrix2.nextIndex_);
454 }
455
456 void print(); // for debug
457
458 // access to optionnal methods
459
469 const barcode_type& get_current_barcode() const;
470
485 const std::vector<cycle_type>& get_representative_cycles();
494
518 bool vine_swap(pos_index position);
519
520 private:
521 Matrix_type matrix_;
522 std::vector<index> positionToIndex_;
523 pos_index nextPosition_;
524 index nextIndex_;
525};
526
527template <class Matrix_type, class Master_matrix_type>
529 Column_settings* colSettings)
530 : matrix_(colSettings), nextPosition_(0), nextIndex_(0)
531{}
532
533template <class Matrix_type, class Master_matrix_type>
534template <class Boundary_type>
536 const std::vector<Boundary_type>& orderedBoundaries, Column_settings* colSettings)
537 : matrix_(orderedBoundaries, colSettings),
538 positionToIndex_(orderedBoundaries.size()),
539 nextPosition_(orderedBoundaries.size()),
540 nextIndex_(orderedBoundaries.size())
541{
542 for (index i = 0; i < orderedBoundaries.size(); i++) {
543 positionToIndex_[i] = i;
544 }
545}
546
547template <class Matrix_type, class Master_matrix_type>
549 unsigned int numberOfColumns, Column_settings* colSettings)
550 : matrix_(numberOfColumns, colSettings),
551 positionToIndex_(numberOfColumns),
552 nextPosition_(0),
553 nextIndex_(0)
554{}
555
556template <class Matrix_type, class Master_matrix_type>
557template <typename BirthComparatorFunction, typename DeathComparatorFunction>
559 Column_settings* colSettings,
560 const BirthComparatorFunction& birthComparator,
561 const DeathComparatorFunction& deathComparator)
562 : matrix_(colSettings, birthComparator, deathComparator), nextPosition_(0), nextIndex_(0)
563{}
564
565template <class Matrix_type, class Master_matrix_type>
566template <typename BirthComparatorFunction, typename DeathComparatorFunction, class Boundary_type>
568 const std::vector<Boundary_type>& orderedBoundaries,
569 Column_settings* colSettings,
570 const BirthComparatorFunction& birthComparator,
571 const DeathComparatorFunction& deathComparator)
572 : matrix_(orderedBoundaries, colSettings, birthComparator, deathComparator),
573 positionToIndex_(orderedBoundaries.size()),
574 nextPosition_(orderedBoundaries.size()),
575 nextIndex_(orderedBoundaries.size())
576{
577 for (index i = 0; i < orderedBoundaries.size(); i++) {
578 positionToIndex_[i] = i;
579 }
580}
581
582template <class Matrix_type, class Master_matrix_type>
583template <typename BirthComparatorFunction, typename DeathComparatorFunction>
585 unsigned int numberOfColumns,
586 Column_settings* colSettings,
587 const BirthComparatorFunction& birthComparator,
588 const DeathComparatorFunction& deathComparator)
589 : matrix_(numberOfColumns, colSettings, birthComparator, deathComparator),
590 positionToIndex_(numberOfColumns),
591 nextPosition_(0),
592 nextIndex_(0)
593{}
594
595template <class Matrix_type, class Master_matrix_type>
597 const Position_to_index_overlay& matrixToCopy, Column_settings* colSettings)
598 : matrix_(matrixToCopy.matrix_, colSettings),
599 positionToIndex_(matrixToCopy.positionToIndex_),
600 nextPosition_(matrixToCopy.nextPosition_),
601 nextIndex_(matrixToCopy.nextIndex_)
602{}
603
604template <class Matrix_type, class Master_matrix_type>
606 Position_to_index_overlay&& other) noexcept
607 : matrix_(std::move(other.matrix_)),
608 positionToIndex_(std::move(other.positionToIndex_)),
609 nextPosition_(std::exchange(other.nextPosition_, 0)),
610 nextIndex_(std::exchange(other.nextIndex_, 0))
611{}
612
613template <class Matrix_type, class Master_matrix_type>
614template <class Boundary_type>
616 dimension_type dim)
617{
618 if (positionToIndex_.size() <= nextPosition_) {
619 positionToIndex_.resize(nextPosition_ * 2 + 1);
620 }
621
622 positionToIndex_[nextPosition_++] = nextIndex_++;
623
624 matrix_.insert_boundary(boundary, dim);
625}
626
627template <class Matrix_type, class Master_matrix_type>
628template <class Boundary_type>
630 const Boundary_type& boundary,
631 dimension_type dim)
632{
633 if (positionToIndex_.size() <= nextPosition_) {
634 positionToIndex_.resize(nextPosition_ * 2 + 1);
635 }
636
637 positionToIndex_[nextPosition_++] = nextIndex_++;
638
639 matrix_.insert_boundary(faceIndex, boundary, dim);
640}
641
642template <class Matrix_type, class Master_matrix_type>
645{
646 return matrix_.get_column(positionToIndex_[position]);
647}
648
649template <class Matrix_type, class Master_matrix_type>
652{
653 return matrix_.get_column(positionToIndex_[position]);
654}
655
656template <class Matrix_type, class Master_matrix_type>
659{
660 return matrix_.get_row(rowIndex);
661}
662
663template <class Matrix_type, class Master_matrix_type>
666{
667 return matrix_.get_row(rowIndex);
668}
669
670template <class Matrix_type, class Master_matrix_type>
672{
673 return matrix_.erase_empty_row(rowIndex);
674}
675
676template <class Matrix_type, class Master_matrix_type>
678{
679 --nextPosition_;
680
681 id_index pivot = matrix_.get_pivot(positionToIndex_[position]);
682 std::vector<index> columnsToSwap(nextPosition_ - position);
683
684 if (nextPosition_ != position) {
685 positionToIndex_[position] = positionToIndex_[position + 1];
686 for (pos_index p = position + 1; p < nextPosition_; ++p) {
687 columnsToSwap[p - position - 1] = positionToIndex_[p];
688 positionToIndex_[p] = positionToIndex_[p + 1];
689 }
690 columnsToSwap.back() = positionToIndex_[nextPosition_];
691 }
692
693 matrix_.remove_maximal_face(pivot, columnsToSwap);
694}
695
696template <class Matrix_type, class Master_matrix_type>
698{
699 --nextPosition_;
700 if constexpr (Master_matrix_type::Option_list::has_vine_update) {
701 std::vector<index> columnsToSwap;
702 matrix_.remove_maximal_face(matrix_.get_pivot(positionToIndex_[nextPosition_]), columnsToSwap);
703 } else {
704 matrix_.remove_last(); // linear with vine updates, so it is better to use remove_maximal_face
705 }
706}
707
708template <class Matrix_type, class Master_matrix_type>
711{
712 return matrix_.get_max_dimension();
713}
714
715template <class Matrix_type, class Master_matrix_type>
718{
719 return matrix_.get_number_of_columns();
720}
721
722template <class Matrix_type, class Master_matrix_type>
725{
726 return matrix_.get_column_dimension(positionToIndex_[position]);
727}
728
729template <class Matrix_type, class Master_matrix_type>
731 pos_index targetPosition)
732{
733 return matrix_.add_to(positionToIndex_[sourcePosition], positionToIndex_[targetPosition]);
734}
735
736template <class Matrix_type, class Master_matrix_type>
738 pos_index sourcePosition, const Field_element_type& coefficient, pos_index targetPosition)
739{
740 return matrix_.multiply_target_and_add_to(positionToIndex_[sourcePosition],
741 coefficient,
742 positionToIndex_[targetPosition]);
743}
744
745template <class Matrix_type, class Master_matrix_type>
747 const Field_element_type& coefficient, pos_index sourcePosition, pos_index targetPosition)
748{
749 return matrix_.multiply_source_and_add_to(coefficient,
750 positionToIndex_[sourcePosition],
751 positionToIndex_[targetPosition]);
752}
753
754template <class Matrix_type, class Master_matrix_type>
756 id_index rowIndex) const
757{
758 return matrix_.is_zero_cell(positionToIndex_[position], rowIndex);
759}
760
761template <class Matrix_type, class Master_matrix_type>
763{
764 return matrix_.is_zero_column(positionToIndex_[position]);
765}
766
767template <class Matrix_type, class Master_matrix_type>
770{
771 index id = matrix_.get_column_with_pivot(faceIndex);
772 pos_index i = 0;
773 while (positionToIndex_[i] != id) ++i;
774 return i;
775}
776
777template <class Matrix_type, class Master_matrix_type>
780{
781 return matrix_.get_pivot(positionToIndex_[position]);
782}
783
784template <class Matrix_type, class Master_matrix_type>
787{
788 matrix_ = other.matrix_;
789 positionToIndex_ = other.positionToIndex_;
790 nextPosition_ = other.nextPosition_;
791 nextIndex_ = other.nextIndex_;
792
793 return *this;
794}
795
796template <class Matrix_type, class Master_matrix_type>
798{
799 return matrix_.print();
800}
801
802template <class Matrix_type, class Master_matrix_type>
805{
806 return matrix_.get_current_barcode();
807}
808
809template <class Matrix_type, class Master_matrix_type>
811{
812 matrix_.update_representative_cycles();
813}
814
815template <class Matrix_type, class Master_matrix_type>
816inline const std::vector<typename Position_to_index_overlay<Matrix_type, Master_matrix_type>::cycle_type>&
818{
819 return matrix_.get_representative_cycles();
820}
821
822template <class Matrix_type, class Master_matrix_type>
825{
826 return matrix_.get_representative_cycle(bar);
827}
828
829template <class Matrix_type, class Master_matrix_type>
831{
832 index next = matrix_.vine_swap_with_z_eq_1_case(positionToIndex_[position], positionToIndex_[position + 1]);
833 if (next == positionToIndex_[position]) {
834 std::swap(positionToIndex_[position], positionToIndex_[position + 1]);
835 return true;
836 }
837
838 return false;
839}
840
841template <class Matrix_type, class Master_matrix_type>
843{
844 index next = matrix_.vine_swap(positionToIndex_[position], positionToIndex_[position + 1]);
845 if (next == positionToIndex_[position]) {
846 std::swap(positionToIndex_[position], positionToIndex_[position + 1]);
847 return true;
848 }
849
850 return false;
851}
852
853} // namespace persistence_matrix
854} // namespace Gudhi
855
856#endif // PM_POS_TO_ID_TRANSLATION_H
Overlay for chain matrices replacing all input and output MatIdx indices of the original methods with...
Definition overlay_posidx_to_matidx.h:40
typename Master_matrix_type::Bar bar_type
Definition overlay_posidx_to_matidx.h:55
typename Master_matrix_type::cell_rep_type cell_rep_type
Definition overlay_posidx_to_matidx.h:58
void multiply_target_and_add_to(pos_index sourcePosition, const Field_element_type &coefficient, pos_index targetPosition)
Multiplies the target column with the coefficiant and then adds the source column to it....
Definition overlay_posidx_to_matidx.h:737
void insert_boundary(const Boundary_type &boundary, dimension_type dim=-1)
Inserts at the end of the matrix a new ordered column corresponding to the given boundary....
Definition overlay_posidx_to_matidx.h:615
friend void swap(Position_to_index_overlay &matrix1, Position_to_index_overlay &matrix2)
Swap operator.
Definition overlay_posidx_to_matidx.h:449
bool vine_swap(pos_index position)
Only available if PersistenceMatrixOptions::has_vine_update is true. Does a vine swap between two fac...
Definition overlay_posidx_to_matidx.h:842
typename Master_matrix_type::index index
Definition overlay_posidx_to_matidx.h:42
typename Master_matrix_type::Cell_constructor Cell_constructor
Definition overlay_posidx_to_matidx.h:59
bool vine_swap_with_z_eq_1_case(pos_index position)
Only available if PersistenceMatrixOptions::has_vine_update is true. Does the same than vine_swap,...
Definition overlay_posidx_to_matidx.h:830
typename Master_matrix_type::boundary_type boundary_type
Definition overlay_posidx_to_matidx.h:51
const std::vector< cycle_type > & get_representative_cycles()
Only available if PersistenceMatrixOptions::can_retrieve_representative_cycles is true....
Definition overlay_posidx_to_matidx.h:817
dimension_type get_max_dimension() const
Returns the maximal dimension of a face stored in the matrix. Only available if PersistenceMatrixOpti...
Definition overlay_posidx_to_matidx.h:710
void remove_maximal_face(pos_index position)
Only available if PersistenceMatrixOptions::has_removable_columns, PersistenceMatrixOptions::has_vine...
Definition overlay_posidx_to_matidx.h:677
const barcode_type & get_current_barcode() const
Returns the current barcode of the matrix. Available only if PersistenceMatrixOptions::has_column_pai...
Definition overlay_posidx_to_matidx.h:804
index get_number_of_columns() const
Returns the current number of columns in the matrix.
Definition overlay_posidx_to_matidx.h:717
void multiply_source_and_add_to(const Field_element_type &coefficient, pos_index sourcePosition, pos_index targetPosition)
Multiplies the source column with the coefficiant before adding it to the target column....
Definition overlay_posidx_to_matidx.h:746
typename Master_matrix_type::element_type Field_element_type
Definition overlay_posidx_to_matidx.h:50
void update_representative_cycles()
Only available if PersistenceMatrixOptions::can_retrieve_representative_cycles is true....
Definition overlay_posidx_to_matidx.h:810
void reset(Column_settings *colSettings)
Resets the matrix to an empty matrix.
Definition overlay_posidx_to_matidx.h:433
id_index get_pivot(pos_index position)
Returns the row index of the pivot of the given column.
Definition overlay_posidx_to_matidx.h:779
Column_type & get_column(pos_index position)
Returns the column at the given PosIdx index. The type of the column depends on the choosen options,...
Definition overlay_posidx_to_matidx.h:644
void erase_empty_row(id_index rowIndex)
Only available if PersistenceMatrixOptions::has_row_access and PersistenceMatrixOptions::has_removabl...
Definition overlay_posidx_to_matidx.h:671
typename Master_matrix_type::Column_type Column_type
Definition overlay_posidx_to_matidx.h:52
void remove_last()
Only available if PersistenceMatrixOptions::has_removable_columns is true and, if PersistenceMatrixOp...
Definition overlay_posidx_to_matidx.h:697
typename Master_matrix_type::id_index id_index
Definition overlay_posidx_to_matidx.h:43
typename Master_matrix_type::dimension_type dimension_type
Definition overlay_posidx_to_matidx.h:45
typename Master_matrix_type::Row_type Row_type
Definition overlay_posidx_to_matidx.h:54
typename Master_matrix_type::barcode_type barcode_type
Definition overlay_posidx_to_matidx.h:56
Position_to_index_overlay(Column_settings *colSettings)
Constructs an empty matrix.
Definition overlay_posidx_to_matidx.h:528
typename Master_matrix_type::cycle_type cycle_type
Definition overlay_posidx_to_matidx.h:57
typename Master_matrix_type::Column_settings Column_settings
Definition overlay_posidx_to_matidx.h:61
bool is_zero_cell(pos_index position, id_index rowIndex) const
Indicates if the cell at given coordinates has value zero.
Definition overlay_posidx_to_matidx.h:755
dimension_type get_column_dimension(pos_index position) const
Returns the dimension of the given face.
Definition overlay_posidx_to_matidx.h:724
typename Master_matrix_type::Field_operators Field_operators
Field operators class. Necessary only if PersistenceMatrixOptions::is_z2 is false.
Definition overlay_posidx_to_matidx.h:49
const cycle_type & get_representative_cycle(const bar_type &bar)
Only available if PersistenceMatrixOptions::can_retrieve_representative_cycles is true....
Definition overlay_posidx_to_matidx.h:824
pos_index get_column_with_pivot(id_index faceIndex) const
Returns the PosIdx index of the column which has the given row index as pivot. Assumes that the pivot...
Definition overlay_posidx_to_matidx.h:769
typename Master_matrix_type::pos_index pos_index
Definition overlay_posidx_to_matidx.h:44
bool is_zero_column(pos_index position)
Indicates if the column at given index has value zero.
Definition overlay_posidx_to_matidx.h:762
Position_to_index_overlay & operator=(const Position_to_index_overlay &other)
Assign operator.
Definition overlay_posidx_to_matidx.h:786
void add_to(pos_index sourcePosition, pos_index targetPosition)
Adds column corresponding to sourcePosition onto the column corresponding to targetPosition.
Definition overlay_posidx_to_matidx.h:730
Row_type & get_row(id_index rowIndex)
Only available if PersistenceMatrixOptions::has_row_access is true. Returns the row at the given row ...
Definition overlay_posidx_to_matidx.h:658
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14