Loading...
Searching...
No Matches
chain_vine_swap.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
18#ifndef PM_CHAIN_VINE_SWAP_H
19#define PM_CHAIN_VINE_SWAP_H
20
21#include <utility> //std::swap & std::move
22#include <cassert>
23#include <functional> //std::function
24#include <stdexcept> //std::invalid_argument
25
26#include "chain_pairing.h"
27
28namespace Gudhi {
29namespace persistence_matrix {
30
41constexpr bool _no_G_death_comparator([[maybe_unused]] unsigned int columnIndex1,
42 [[maybe_unused]] unsigned int columnIndex2)
43{
44 return false;
45}
46
54 friend void swap([[maybe_unused]] Dummy_chain_vine_swap& d1, [[maybe_unused]] Dummy_chain_vine_swap& d2) {}
55
57 template <typename BirthComparatorFunction, typename DeathComparatorFunction>
58 Dummy_chain_vine_swap([[maybe_unused]] const BirthComparatorFunction& birthComparator,
59 [[maybe_unused]] const DeathComparatorFunction& deathComparator) {}
60};
61
69 friend void swap([[maybe_unused]] Dummy_chain_vine_pairing& d1, [[maybe_unused]] Dummy_chain_vine_pairing& d2) {}
70};
71
79template <typename Master_matrix>
80class Chain_barcode_swap : public Chain_pairing<Master_matrix>
81{
82 public:
83 using id_index = typename Master_matrix::id_index;
84 using pos_index = typename Master_matrix::pos_index;
86
97 : CP(static_cast<const CP&>(toCopy)), pivotToPosition_(toCopy.pivotToPosition_){};
104 : CP(std::move(static_cast<CP&>(other))), pivotToPosition_(std::move(other.pivotToPosition_)){};
105
106 protected:
107 using dictionnary_type = typename Master_matrix::template dictionnary_type<pos_index>;
108
109 dictionnary_type pivotToPosition_; // necessary to keep track of the barcode changes
110
111 void swap_positions(id_index pivot1, id_index pivot2) {
112 if constexpr (Master_matrix::Option_list::has_map_column_container) {
113 std::swap(pivotToPosition_.at(pivot1), pivotToPosition_.at(pivot2));
114 } else {
115 std::swap(pivotToPosition_[pivot1], pivotToPosition_[pivot2]);
116 }
117 }
118
119 bool is_negative_in_pair(id_index pivot) const {
120 pos_index pos = _get_pivot_position(pivot);
121 return death(pivot) == pos;
122 }
123
124 void positive_transpose(id_index pivot1, id_index pivot2) {
125 pos_index pos1 = _get_pivot_position(pivot1);
126 pos_index pos2 = _get_pivot_position(pivot2);
127
128 _birth(pos1) = pos2;
129 _birth(pos2) = pos1;
130 std::swap(CP::indexToBar_.at(pos1), CP::indexToBar_.at(pos2));
131 }
132
133 void negative_transpose(id_index pivot1, id_index pivot2) {
134 pos_index pos1 = _get_pivot_position(pivot1);
135 pos_index pos2 = _get_pivot_position(pivot2);
136
137 _death(pos1) = pos2;
138 _death(pos2) = pos1;
139 std::swap(CP::indexToBar_.at(pos1), CP::indexToBar_.at(pos2));
140 }
141
142 void positive_negative_transpose(id_index pivot1, id_index pivot2) {
143 pos_index pos1 = _get_pivot_position(pivot1);
144 pos_index pos2 = _get_pivot_position(pivot2);
145
146 _birth(pos1) = pos2;
147 _death(pos2) = pos1;
148 std::swap(CP::indexToBar_.at(pos1), CP::indexToBar_.at(pos2));
149 }
150
151 void negative_positive_transpose(id_index pivot1, id_index pivot2) {
152 pos_index pos1 = _get_pivot_position(pivot1);
153 pos_index pos2 = _get_pivot_position(pivot2);
154
155 _death(pos1) = pos2;
156 _birth(pos2) = pos1;
157 std::swap(CP::indexToBar_.at(pos1), CP::indexToBar_.at(pos2));
158 }
159
160 bool are_adjacent(id_index pivot1, id_index pivot2) const {
161 pos_index pos1 = _get_pivot_position(pivot1);
162 pos_index pos2 = _get_pivot_position(pivot2);
163 return pos1 < pos2 ? (pos2 - pos1) == 1 : (pos1 - pos2) == 1;
164 }
165
166 Chain_barcode_swap& operator=(Chain_barcode_swap other) {
168 pivotToPosition_.swap(other.pivotToPosition_);
169 }
170 friend void swap(Chain_barcode_swap& swap1, Chain_barcode_swap& swap2) {
171 swap(static_cast<Chain_pairing<Master_matrix>&>(swap1), static_cast<Chain_pairing<Master_matrix>&>(swap2));
172 swap1.pivotToPosition_.swap(swap2.pivotToPosition_);
173 }
174
175 pos_index death(id_index pivot) const {
176 pos_index simplexIndex = _get_pivot_position(pivot);
177
178 if constexpr (Master_matrix::Option_list::has_removable_columns) {
179 return CP::indexToBar_.at(simplexIndex)->death;
180 } else {
181 return CP::barcode_.at(CP::indexToBar_.at(simplexIndex)).death;
182 }
183 }
184
185 pos_index birth(id_index pivot) const {
186 pos_index simplexIndex = _get_pivot_position(pivot);
187
188 if constexpr (Master_matrix::Option_list::has_removable_columns) {
189 return CP::indexToBar_.at(simplexIndex)->birth;
190 } else {
191 return CP::barcode_.at(CP::indexToBar_.at(simplexIndex)).birth;
192 }
193 }
194
195 private:
196 pos_index _get_pivot_position(id_index pivot) const {
197 if constexpr (Master_matrix::Option_list::has_map_column_container) {
198 return pivotToPosition_.at(
199 pivot); // quite often called, make public and pass position instead of pivot to avoid find() everytime?
200 } else {
201 return pivotToPosition_[pivot];
202 }
203 }
204
205 pos_index& _death(pos_index simplexIndex) {
206 if constexpr (Master_matrix::Option_list::has_removable_columns) {
207 return CP::indexToBar_.at(simplexIndex)->death;
208 } else {
209 return CP::barcode_.at(CP::indexToBar_.at(simplexIndex)).death;
210 }
211 }
212
213 pos_index& _birth(pos_index simplexIndex) {
214 if constexpr (Master_matrix::Option_list::has_removable_columns) {
215 return CP::indexToBar_.at(simplexIndex)->birth;
216 } else {
217 return CP::barcode_.at(CP::indexToBar_.at(simplexIndex)).birth;
218 }
219 }
220};
221
230template <class Master_matrix>
231class Chain_vine_swap : public std::conditional<Master_matrix::Option_list::has_column_pairings,
232 Chain_barcode_swap<Master_matrix>,
233 Dummy_chain_vine_pairing
234 >::type
235{
236 public:
237 using index = typename Master_matrix::index;
238 using id_index = typename Master_matrix::id_index;
239 using pos_index = typename Master_matrix::pos_index;
240 using matrix_type = typename Master_matrix::column_container_type;
241 using Column_type = typename Master_matrix::Column_type;
260 Chain_vine_swap(std::function<bool(pos_index,pos_index)> birthComparator,
261 std::function<bool(pos_index,pos_index)> deathComparator = _no_G_death_comparator);
267 Chain_vine_swap(const Chain_vine_swap& matrixToCopy);
273 Chain_vine_swap(Chain_vine_swap&& other) noexcept;
274
285 index vine_swap_with_z_eq_1_case(index columnIndex1, index columnIndex2);
301 index vine_swap(index columnIndex1, index columnIndex2);
302
310 friend void swap(Chain_vine_swap& swap1, Chain_vine_swap& swap2) {
311 if constexpr (Master_matrix::Option_list::has_column_pairings) {
312 swap(static_cast<Chain_barcode_swap<Master_matrix>&>(swap1),
313 static_cast<Chain_barcode_swap<Master_matrix>&>(swap2));
314 }
315 std::swap(swap1.birthComp_, swap2.birthComp_);
316 std::swap(swap1.deathComp_, swap2.deathComp_);
317 }
318
319 protected:
320 using CP = typename std::conditional<Master_matrix::Option_list::has_column_pairings,
323 >::type;
324
325 private:
326 using chain_matrix = typename Master_matrix::Chain_matrix_type;
327
328 std::function<bool(pos_index,pos_index)> birthComp_;
329 std::function<bool(pos_index,pos_index)> deathComp_;
331 bool _is_negative_in_pair(index columnIndex);
332
333 index _positive_vine_swap(index columnIndex1, index columnIndex2);
334 index _positive_negative_vine_swap(index columnIndex1, index columnIndex2);
335 index _negative_positive_vine_swap(index columnIndex1, index columnIndex2);
336 index _negative_vine_swap(index columnIndex1, index columnIndex2);
337
338 constexpr chain_matrix* _matrix() { return static_cast<chain_matrix*>(this); }
339 constexpr const chain_matrix* _matrix() const { return static_cast<const chain_matrix*>(this); }
340};
341
342template <class Master_matrix>
343inline Chain_vine_swap<Master_matrix>::Chain_vine_swap() : CP(), birthComp_(), deathComp_()
344{
345 static_assert(Master_matrix::Option_list::has_column_pairings,
346 "If barcode is not stored, at least a birth comparator has to be specified.");
347}
348
349template <class Master_matrix>
350inline Chain_vine_swap<Master_matrix>::Chain_vine_swap(std::function<bool(pos_index,pos_index)> birthComparator,
351 std::function<bool(pos_index,pos_index)> deathComparator)
352 : CP(), birthComp_(std::move(birthComparator)), deathComp_(std::move(deathComparator))
353{}
354
355template <class Master_matrix>
357 : CP(static_cast<const CP&>(matrixToCopy)),
358 birthComp_(matrixToCopy.birthComp_),
359 deathComp_(matrixToCopy.deathComp_)
360{}
361
362template <class Master_matrix>
364 : CP(std::move(static_cast<CP&>(other))),
365 birthComp_(std::move(other.birthComp_)),
366 deathComp_(std::move(other.deathComp_))
367{}
368
369template <class Master_matrix>
371 index columnIndex1, index columnIndex2)
372{
373 const bool col1IsNeg = _is_negative_in_pair(columnIndex1);
374 const bool col2IsNeg = _is_negative_in_pair(columnIndex2);
375
376 if (col1IsNeg && col2IsNeg) return _negative_vine_swap(columnIndex1, columnIndex2);
377
378 if (col1IsNeg) return _negative_positive_vine_swap(columnIndex1, columnIndex2);
379
380 if (col2IsNeg) return _positive_negative_vine_swap(columnIndex1, columnIndex2);
381
382 return _positive_vine_swap(columnIndex1, columnIndex2);
383}
384
385template <class Master_matrix>
387 index columnIndex2)
388{
389 if constexpr (Master_matrix::Option_list::has_column_pairings) {
390 GUDHI_CHECK(CP::are_adjacent(_matrix()->get_pivot(columnIndex1), _matrix()->get_pivot(columnIndex2)),
391 std::invalid_argument(
392 "Chain_vine_swap::vine_swap - Columns to be swaped need to be adjacent in the 'real' matrix."));
393 }
394
395 const bool col1IsNeg = _is_negative_in_pair(columnIndex1);
396 const bool col2IsNeg = _is_negative_in_pair(columnIndex2);
397
398 if (col1IsNeg && col2IsNeg) {
399 if (_matrix()->is_zero_cell(columnIndex2, _matrix()->get_pivot(columnIndex1))) {
400 if constexpr (Master_matrix::Option_list::has_column_pairings) {
401 id_index pivot1 = _matrix()->get_pivot(columnIndex1);
402 id_index pivot2 = _matrix()->get_pivot(columnIndex2);
403
404 CP::negative_transpose(pivot1, pivot2);
405 CP::swap_positions(pivot1, pivot2);
406 }
407 return columnIndex1;
408 }
409 return _negative_vine_swap(columnIndex1, columnIndex2);
410 }
411
412 if (col1IsNeg) {
413 if (_matrix()->is_zero_cell(columnIndex2, _matrix()->get_pivot(columnIndex1))) {
414 if constexpr (Master_matrix::Option_list::has_column_pairings) {
415 id_index pivot1 = _matrix()->get_pivot(columnIndex1);
416 id_index pivot2 = _matrix()->get_pivot(columnIndex2);
417
418 CP::negative_positive_transpose(pivot1, pivot2);
419 CP::swap_positions(pivot1, pivot2);
420 }
421 return columnIndex1;
422 }
423 return _negative_positive_vine_swap(columnIndex1, columnIndex2);
424 }
425
426 if (col2IsNeg) {
427 if (_matrix()->is_zero_cell(columnIndex2, _matrix()->get_pivot(columnIndex1))) {
428 if constexpr (Master_matrix::Option_list::has_column_pairings) {
429 id_index pivot1 = _matrix()->get_pivot(columnIndex1);
430 id_index pivot2 = _matrix()->get_pivot(columnIndex2);
431
432 CP::positive_negative_transpose(pivot1, pivot2);
433 CP::swap_positions(pivot1, pivot2);
434 }
435 return columnIndex1;
436 }
437 return _positive_negative_vine_swap(columnIndex1, columnIndex2);
438 }
439
440 if (_matrix()->is_zero_cell(columnIndex2, _matrix()->get_pivot(columnIndex1))) {
441 if constexpr (Master_matrix::Option_list::has_column_pairings) {
442 id_index pivot1 = _matrix()->get_pivot(columnIndex1);
443 id_index pivot2 = _matrix()->get_pivot(columnIndex2);
444
445 CP::positive_transpose(pivot1, pivot2);
446 CP::swap_positions(pivot1, pivot2);
447 }
448 return columnIndex1;
449 }
450 return _positive_vine_swap(columnIndex1, columnIndex2);
451}
452
453template <class Master_matrix>
455{
456 CP::operator=(other);
457 std::swap(birthComp_, other.birthComp_);
458 std::swap(deathComp_, other.deathComp_);
459 return *this;
460}
461
462template <class Master_matrix>
463inline bool Chain_vine_swap<Master_matrix>::_is_negative_in_pair(index columnIndex)
464{
465 if constexpr (Master_matrix::Option_list::has_column_pairings) {
466 return CP::is_negative_in_pair(_matrix()->get_pivot(columnIndex));
467 } else {
468 auto& col = _matrix()->get_column(columnIndex);
469 if (!col.is_paired()) return false;
470 return col.get_pivot() > _matrix()->get_pivot(col.get_paired_chain_index());
471 }
472}
473
474template <class Master_matrix>
475inline typename Chain_vine_swap<Master_matrix>::index Chain_vine_swap<Master_matrix>::_positive_vine_swap(
476 index columnIndex1, index columnIndex2)
477{
478 auto& col1 = _matrix()->get_column(columnIndex1);
479 auto& col2 = _matrix()->get_column(columnIndex2);
480
481 if constexpr (Master_matrix::Option_list::has_column_pairings) {
482 CP::swap_positions(col1.get_pivot(), col2.get_pivot());
483 }
484 // TODO: factorize the cases. But for debug it is much more easier to understand what is happening splitted like this
485 if (!col1.is_paired()) { // F x *
486 bool hasSmallerBirth;
487 if constexpr (Master_matrix::Option_list::has_column_pairings) {
488 // this order because position were swapped with CP::swap_positions
489 hasSmallerBirth = (CP::birth(col2.get_pivot()) < CP::birth(col1.get_pivot()));
490 } else {
491 hasSmallerBirth = birthComp_(columnIndex1, columnIndex2);
492 }
493
494 if (!col2.is_paired() && hasSmallerBirth) {
495 _matrix()->add_to(columnIndex1, columnIndex2);
496 if constexpr (Master_matrix::Option_list::has_column_pairings) {
497 CP::positive_transpose(col1.get_pivot(), col2.get_pivot());
498 }
499 return columnIndex1;
500 }
501 _matrix()->add_to(columnIndex2, columnIndex1);
502
503 return columnIndex2;
504 }
505
506 if (!col2.is_paired()) { // G x F
507 static_cast<chain_matrix*>(this)->add_to(columnIndex1, columnIndex2);
508 if constexpr (Master_matrix::Option_list::has_column_pairings) {
509 CP::positive_transpose(col1.get_pivot(), col2.get_pivot());
510 }
511 return columnIndex1;
512 }
513
514 bool hasSmallerDeath;
515 if constexpr (Master_matrix::Option_list::has_column_pairings) {
516 // this order because position were swapped with CP::swap_positions
517 hasSmallerDeath = (CP::death(col2.get_pivot()) < CP::death(col1.get_pivot()));
518 } else {
519 hasSmallerDeath = deathComp_(columnIndex1, columnIndex2);
520 }
521
522 // G x G
523 if (hasSmallerDeath)
524 {
525 _matrix()->add_to(col1.get_paired_chain_index(), col2.get_paired_chain_index());
526 _matrix()->add_to(columnIndex1, columnIndex2);
527 if constexpr (Master_matrix::Option_list::has_column_pairings) {
528 CP::positive_transpose(col1.get_pivot(), col2.get_pivot());
529 }
530 return columnIndex1;
531 }
532
533 _matrix()->add_to(col2.get_paired_chain_index(), col1.get_paired_chain_index());
534 _matrix()->add_to(columnIndex2, columnIndex1);
535
536 return columnIndex2;
537}
538
539template <class Master_matrix>
540inline typename Chain_vine_swap<Master_matrix>::index Chain_vine_swap<Master_matrix>::_positive_negative_vine_swap(
541 index columnIndex1, index columnIndex2)
542{
543 _matrix()->add_to(columnIndex1, columnIndex2);
544
545 if constexpr (Master_matrix::Option_list::has_column_pairings) {
546 id_index pivot1 = _matrix()->get_pivot(columnIndex1);
547 id_index pivot2 = _matrix()->get_pivot(columnIndex2);
548
549 CP::positive_negative_transpose(pivot1, pivot2);
550 CP::swap_positions(pivot1, pivot2);
551 }
552
553 return columnIndex1;
554}
555
556template <class Master_matrix>
557inline typename Chain_vine_swap<Master_matrix>::index Chain_vine_swap<Master_matrix>::_negative_positive_vine_swap(
558 index columnIndex1, index columnIndex2)
559{
560 _matrix()->add_to(columnIndex2, columnIndex1);
561
562 if constexpr (Master_matrix::Option_list::has_column_pairings) {
563 CP::swap_positions(_matrix()->get_pivot(columnIndex1), _matrix()->get_pivot(columnIndex2));
564 }
565
566 return columnIndex2;
567}
568
569template <class Master_matrix>
570inline typename Chain_vine_swap<Master_matrix>::index Chain_vine_swap<Master_matrix>::_negative_vine_swap(
571 index columnIndex1, index columnIndex2)
572{
573 auto& col1 = _matrix()->get_column(columnIndex1);
574 auto& col2 = _matrix()->get_column(columnIndex2);
575
576 index pairedIndex1 = col1.get_paired_chain_index();
577 index pairedIndex2 = col2.get_paired_chain_index();
578
579 bool hasSmallerBirth;
580 if constexpr (Master_matrix::Option_list::has_column_pairings) {
581 hasSmallerBirth = (CP::birth(col1.get_pivot()) < CP::birth(col2.get_pivot()));
582 } else {
583 hasSmallerBirth = birthComp_(pairedIndex1, pairedIndex2);
584 }
585
586 if constexpr (Master_matrix::Option_list::has_column_pairings) {
587 CP::swap_positions(col1.get_pivot(), col2.get_pivot());
588 }
589
590 if (hasSmallerBirth)
591 {
592 _matrix()->add_to(pairedIndex1, pairedIndex2);
593 _matrix()->add_to(columnIndex1, columnIndex2);
594
595 if constexpr (Master_matrix::Option_list::has_column_pairings) {
596 CP::negative_transpose(col1.get_pivot(), col2.get_pivot());
597 }
598
599 return columnIndex1;
600 }
601
602 _matrix()->add_to(pairedIndex2, pairedIndex1);
603 _matrix()->add_to(columnIndex2, columnIndex1);
604
605 return columnIndex2;
606}
607
608} // namespace persistence_matrix
609} // namespace Gudhi
610
611#endif // PM_CHAIN_VINE_SWAP_H
Contains the Chain_pairing class and Dummy_chain_pairing structure.
Class managing the barcode for Chain_vine_swap.
Definition chain_vine_swap.h:81
typename Master_matrix::pos_index pos_index
Definition chain_vine_swap.h:84
Chain_barcode_swap()
Default constructor.
Definition chain_vine_swap.h:90
typename Master_matrix::id_index id_index
Definition chain_vine_swap.h:83
Chain_barcode_swap(const Chain_barcode_swap &toCopy)
Copy constructor.
Definition chain_vine_swap.h:96
Chain_barcode_swap(Chain_barcode_swap &&other)
Move constructor.
Definition chain_vine_swap.h:103
Class managing the barcode for Chain_matrix if the option was enabled.
Definition chain_pairing.h:46
Chain_pairing & operator=(Chain_pairing other)
Assign operator.
Definition chain_pairing.h:123
Class managing the vine swaps for Chain_matrix.
Definition chain_vine_swap.h:235
Chain_vine_swap()
Default constructor. Only available if PersistenceMatrixOptions::has_column_pairings is true.
Definition chain_vine_swap.h:343
index vine_swap_with_z_eq_1_case(index columnIndex1, index columnIndex2)
Does the same than vine_swap, but assumes that the swap is non trivial and therefore skips a part of ...
Definition chain_vine_swap.h:370
Chain_vine_swap & operator=(Chain_vine_swap other)
Assign operator.
Definition chain_vine_swap.h:454
index vine_swap(index columnIndex1, index columnIndex2)
Does a vine swap between two faces which are consecutives in the filtration. Roughly,...
Definition chain_vine_swap.h:386
friend void swap(Chain_vine_swap &swap1, Chain_vine_swap &swap2)
Swap operator.
Definition chain_vine_swap.h:310
typename Master_matrix::column_container_type matrix_type
Definition chain_vine_swap.h:240
typename Master_matrix::Column_type Column_type
Definition chain_vine_swap.h:241
typename Master_matrix::id_index id_index
Definition chain_vine_swap.h:238
typename Master_matrix::pos_index pos_index
Definition chain_vine_swap.h:239
typename Master_matrix::index index
Definition chain_vine_swap.h:237
bool(* EventCompFuncPointer)(pos_index, pos_index)
Definition chain_vine_swap.h:242
constexpr bool _no_G_death_comparator(unsigned int columnIndex1, unsigned int columnIndex2)
Default death comparator. Simply assumes that two positive paired columns are never swapped....
Definition chain_vine_swap.h:41
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14
Empty structure. Inheritated instead of Chain_barcode_swap, when the barcode is not stored.
Definition chain_vine_swap.h:68
Empty structure. Inheritated instead of Chain_vine_swap, when vine swappes are not enabled.
Definition chain_vine_swap.h:53