ru_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
19#ifndef PM_RU_VINE_SWAP_H
20#define PM_RU_VINE_SWAP_H
21
22#include <utility> //std::move
23#include <type_traits> //std::conditional
24#include <cassert>
25#include <stdexcept> //std::invalid_argument
26
27#include "ru_pairing.h"
29
30namespace Gudhi {
31namespace persistence_matrix {
32
40{
41 friend void swap([[maybe_unused]] Dummy_ru_vine_swap& d1, [[maybe_unused]] Dummy_ru_vine_swap& d2) {}
42};
43
51{
52 friend void swap([[maybe_unused]] Dummy_ru_vine_pairing& d1, [[maybe_unused]] Dummy_ru_vine_pairing& d2) {}
53};
54
63template <class Master_matrix>
64class RU_vine_swap : public std::conditional<Master_matrix::Option_list::has_column_pairings,
65 RU_pairing<Master_matrix>,
66 Dummy_ru_vine_pairing
67 >::type,
68 public std::conditional<Master_matrix::Option_list::has_column_pairings &&
69 Master_matrix::Option_list::has_removable_columns,
70 Dummy_pos_mapper,
71 Cell_position_to_ID_mapper<typename Master_matrix::ID_index,
72 typename Master_matrix::Pos_index>
73 >::type
74{
75 public:
76 using Index = typename Master_matrix::Index;
77 using ID_index = typename Master_matrix::ID_index;
78 using Pos_index = typename Master_matrix::Pos_index;
89 RU_vine_swap(const RU_vine_swap& matrixToCopy);
95 RU_vine_swap(RU_vine_swap&& other) noexcept;
96
118 bool vine_swap(Pos_index index);
119
127 friend void swap(RU_vine_swap& swap1, RU_vine_swap& swap2) {
128 if constexpr (Master_matrix::Option_list::has_column_pairings) {
129 swap(static_cast<RU_pairing<Master_matrix>&>(swap1), static_cast<RU_pairing<Master_matrix>&>(swap2));
130 }
131 if (!Master_matrix::Option_list::has_column_pairings || !Master_matrix::Option_list::has_removable_columns) {
132 swap(static_cast<Cell_position_to_ID_mapper<ID_index, Pos_index>&>(swap1),
133 static_cast<Cell_position_to_ID_mapper<ID_index, Pos_index>&>(swap2));
134 }
135 }
136
137 protected:
138 //RUP = RU matrix Pairing
139 using RUP = typename std::conditional<Master_matrix::Option_list::has_column_pairings,
142 >::type;
143 //RUM = RU matrix position to id Map
144 using RUM = typename std::conditional<Master_matrix::Option_list::has_column_pairings &&
145 Master_matrix::Option_list::has_removable_columns,
146 Dummy_pos_mapper,
147 Cell_position_to_ID_mapper<ID_index, Pos_index>
148 >::type;
149 constexpr auto& _positionToRowIdx();
150
151 private:
152 using Master_RU_matrix = typename Master_matrix::Master_RU_matrix;
153
154 bool _is_paired(Index columnIndex);
155
156 void _swap_at_index(Index columnIndex);
157 void _add_to(Index sourceIndex, Index targetIndex);
158 void _positive_transpose(Index columnIndex);
159 void _negative_transpose(Index columnIndex);
160 void _positive_negative_transpose(Index columnIndex);
161 void _negative_positive_transpose(Index columnIndex);
162 bool _positive_vine_swap(Index columnIndex);
163 bool _negative_vine_swap(Index columnIndex);
164 bool _positive_negative_vine_swap(Index columnIndex);
165 bool _negative_positive_vine_swap(Index columnIndex);
166
167 Pos_index& _death(Pos_index simplexIndex);
168 Pos_index& _birth(Pos_index simplexIndex);
169 Pos_index _get_death(Index simplexIndex);
170 Pos_index _get_birth(Index simplexIndex);
171
172 ID_index _get_row_id_from_position(Pos_index position);
173
174 constexpr Master_RU_matrix* _matrix() { return static_cast<Master_RU_matrix*>(this); }
175 constexpr const Master_RU_matrix* _matrix() const { return static_cast<const Master_RU_matrix*>(this); }
176};
177
178template <class Master_matrix>
180{}
181
182template <class Master_matrix>
184 : RUP(static_cast<const RUP&>(matrixToCopy)),
185 RUM(static_cast<const RUM&>(matrixToCopy))
186{}
187
188template <class Master_matrix>
190 : RUP(std::move(static_cast<RUP&>(other))),
191 RUM(std::move(static_cast<RUM&>(other)))
192{}
193
194template <class Master_matrix>
196{
197 GUDHI_CHECK(index < _matrix()->reducedMatrixR_.get_number_of_columns() - 1,
198 std::invalid_argument("RU_vine_swap::vine_swap_with_z_eq_1_case - Index to swap out of bound."));
199
200 bool iIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index);
201 bool iiIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index + 1);
202
203 if (iIsPositive && iiIsPositive) {
204 _matrix()->mirrorMatrixU_.zero_entry(index, _get_row_id_from_position(index + 1));
205 return _positive_vine_swap(index);
206 } else if (!iIsPositive && !iiIsPositive) {
207 return _negative_vine_swap(index);
208 } else if (iIsPositive && !iiIsPositive) {
209 return _positive_negative_vine_swap(index);
210 } else {
211 return _negative_positive_vine_swap(index);
212 }
213}
214
215template <class Master_matrix>
217{
218 GUDHI_CHECK(index < _matrix()->reducedMatrixR_.get_number_of_columns() - 1,
219 std::invalid_argument("RU_vine_swap::vine_swap - Index to swap out of bound."));
220
221 bool iIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index);
222 bool iiIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index + 1);
223
224 if (iIsPositive && iiIsPositive) {
225 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
226 _matrix()->reducedMatrixR_.get_column_dimension(index + 1)) {
227 _positive_transpose(index);
228 _swap_at_index(index);
229 return true;
230 }
231 if (!_matrix()->mirrorMatrixU_.is_zero_entry(index, _get_row_id_from_position(index + 1))) {
232 _matrix()->mirrorMatrixU_.zero_entry(index, _get_row_id_from_position(index + 1));
233 }
234 return _positive_vine_swap(index);
235 } else if (!iIsPositive && !iiIsPositive) {
236 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
237 _matrix()->reducedMatrixR_.get_column_dimension(index + 1) ||
238 _matrix()->mirrorMatrixU_.is_zero_entry(index, _get_row_id_from_position(index + 1))) {
239 _negative_transpose(index);
240 _swap_at_index(index);
241 return true;
242 }
243 return _negative_vine_swap(index);
244 } else if (iIsPositive && !iiIsPositive) {
245 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
246 _matrix()->reducedMatrixR_.get_column_dimension(index + 1) ||
247 _matrix()->mirrorMatrixU_.is_zero_entry(index, _get_row_id_from_position(index + 1))) {
248 _positive_negative_transpose(index);
249 _swap_at_index(index);
250 return true;
251 }
252 return _positive_negative_vine_swap(index);
253 } else {
254 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
255 _matrix()->reducedMatrixR_.get_column_dimension(index + 1) ||
256 _matrix()->mirrorMatrixU_.is_zero_entry(index, _get_row_id_from_position(index + 1))) {
257 _negative_positive_transpose(index);
258 _swap_at_index(index);
259 return true;
260 }
261 return _negative_positive_vine_swap(index);
262 }
263}
264
265template <class Master_matrix>
267{
268 RUP::operator=(other);
269 RUM::operator=(other);
270 return *this;
271}
272
273template <class Master_matrix>
274inline bool RU_vine_swap<Master_matrix>::_is_paired(Index columnIndex)
275{
276 if constexpr (Master_matrix::Option_list::has_column_pairings) {
277 return _get_death(columnIndex) != Master_matrix::template get_null_value<Pos_index>();
278 } else {
279 if (!_matrix()->reducedMatrixR_.is_zero_column(columnIndex)) return true;
280
281 if constexpr (Master_matrix::Option_list::has_map_column_container) {
282 if (_matrix()->pivotToColumnIndex_.find(columnIndex) == _matrix()->pivotToColumnIndex_.end()) return false;
283 } else {
284 if (_matrix()->pivotToColumnIndex_[columnIndex] == Master_matrix::template get_null_value<Index>())
285 return false;
286 }
287
288 return true;
289 }
290}
291
292template <class Master_matrix>
293inline void RU_vine_swap<Master_matrix>::_swap_at_index(Index columnIndex)
294{
295 _matrix()->reducedMatrixR_.swap_columns(columnIndex, columnIndex + 1);
296 _matrix()->reducedMatrixR_.swap_rows(_get_row_id_from_position(columnIndex),
297 _get_row_id_from_position(columnIndex + 1));
298 _matrix()->mirrorMatrixU_.swap_columns(columnIndex, columnIndex + 1);
299 _matrix()->mirrorMatrixU_.swap_rows(_get_row_id_from_position(columnIndex),
300 _get_row_id_from_position(columnIndex + 1));
301}
302
303template <class Master_matrix>
304inline void RU_vine_swap<Master_matrix>::_add_to(Index sourceIndex, Index targetIndex)
305{
306 _matrix()->reducedMatrixR_.add_to(sourceIndex, targetIndex);
307 _matrix()->mirrorMatrixU_.add_to(targetIndex, sourceIndex);
308}
309
310template <class Master_matrix>
311inline void RU_vine_swap<Master_matrix>::_positive_transpose(Index columnIndex)
312{
313 if constexpr (Master_matrix::Option_list::has_map_column_container) {
314 if (_is_paired(columnIndex) && _is_paired(columnIndex + 1)) {
315 std::swap(_matrix()->pivotToColumnIndex_.at(columnIndex), _matrix()->pivotToColumnIndex_.at(columnIndex + 1));
316 } else if (_is_paired(columnIndex)) {
317 _matrix()->pivotToColumnIndex_.emplace(columnIndex + 1, _matrix()->pivotToColumnIndex_.at(columnIndex));
318 _matrix()->pivotToColumnIndex_.erase(columnIndex);
319 } else if (_is_paired(columnIndex + 1)) {
320 _matrix()->pivotToColumnIndex_.emplace(columnIndex, _matrix()->pivotToColumnIndex_.at(columnIndex + 1));
321 _matrix()->pivotToColumnIndex_.erase(columnIndex + 1);
322 }
323 } else {
324 std::swap(_matrix()->pivotToColumnIndex_[columnIndex],
325 _matrix()->pivotToColumnIndex_[columnIndex + 1]);
326 }
327
328 if constexpr (Master_matrix::Option_list::has_column_pairings) {
329 _birth(columnIndex) = columnIndex + 1;
330 _birth(columnIndex + 1) = columnIndex;
331 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
332 }
333}
334
335template <class Master_matrix>
336inline void RU_vine_swap<Master_matrix>::_negative_transpose(Index columnIndex)
337{
338 if constexpr (Master_matrix::Option_list::has_column_pairings) {
339 _death(columnIndex) = columnIndex + 1;
340 _death(columnIndex + 1) = columnIndex;
341 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
342 }
343 std::swap(_matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex)),
344 _matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex + 1)));
345}
346
347template <class Master_matrix>
348inline void RU_vine_swap<Master_matrix>::_positive_negative_transpose(Index columnIndex)
349{
350 _matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex + 1)) = columnIndex;
351 if constexpr (Master_matrix::Option_list::has_map_column_container) {
352 if (_is_paired(columnIndex)) {
353 _matrix()->pivotToColumnIndex_.emplace(columnIndex + 1, _matrix()->pivotToColumnIndex_.at(columnIndex));
354 _matrix()->pivotToColumnIndex_.erase(columnIndex);
355 }
356 } else {
357 _matrix()->pivotToColumnIndex_[columnIndex + 1] = _matrix()->pivotToColumnIndex_[columnIndex];
358 _matrix()->pivotToColumnIndex_[columnIndex] = Master_matrix::template get_null_value<Index>();
359 }
360
361 if constexpr (Master_matrix::Option_list::has_column_pairings) {
362 _birth(columnIndex) = columnIndex + 1;
363 _death(columnIndex + 1) = columnIndex;
364 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
365 }
366}
367
368template <class Master_matrix>
369inline void RU_vine_swap<Master_matrix>::_negative_positive_transpose(Index columnIndex)
370{
371 _matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex)) = columnIndex + 1;
372 if constexpr (Master_matrix::Option_list::has_map_column_container) {
373 if (_is_paired(columnIndex + 1)) {
374 _matrix()->pivotToColumnIndex_.emplace(columnIndex, _matrix()->pivotToColumnIndex_.at(columnIndex + 1));
375 _matrix()->pivotToColumnIndex_.erase(columnIndex + 1);
376 }
377 } else {
378 _matrix()->pivotToColumnIndex_[columnIndex] = _matrix()->pivotToColumnIndex_[columnIndex + 1];
379 _matrix()->pivotToColumnIndex_[columnIndex + 1] = Master_matrix::template get_null_value<Index>();
380 }
381
382 if constexpr (Master_matrix::Option_list::has_column_pairings) {
383 _death(columnIndex) = columnIndex + 1;
384 _birth(columnIndex + 1) = columnIndex;
385 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
386 }
387}
388
389template <class Master_matrix>
390inline bool RU_vine_swap<Master_matrix>::_positive_vine_swap(Index columnIndex)
391{
392 const Pos_index iDeath = _get_death(columnIndex);
393 const Pos_index iiDeath = _get_death(columnIndex + 1);
394
395 if (iDeath != Master_matrix::template get_null_value<Pos_index>() &&
396 iiDeath != Master_matrix::template get_null_value<Pos_index>() &&
397 !(_matrix()->reducedMatrixR_.is_zero_entry(iiDeath, _get_row_id_from_position(columnIndex)))) {
398 if (iDeath < iiDeath) {
399 _swap_at_index(columnIndex);
400 _add_to(iDeath, iiDeath);
401 _positive_transpose(columnIndex);
402 return true;
403 }
404
405 _swap_at_index(columnIndex);
406 _add_to(iiDeath, iDeath);
407 return false;
408 }
409
410 _swap_at_index(columnIndex);
411
412 if (iDeath != Master_matrix::template get_null_value<Pos_index>() ||
413 iiDeath == Master_matrix::template get_null_value<Pos_index>() ||
414 _matrix()->reducedMatrixR_.is_zero_entry(iiDeath, _get_row_id_from_position(columnIndex + 1))) {
415 _positive_transpose(columnIndex);
416 return true;
417 }
418 return false;
419}
420
421template <class Master_matrix>
422inline bool RU_vine_swap<Master_matrix>::_negative_vine_swap(Index columnIndex)
423{
424 const Pos_index iBirth = _get_birth(columnIndex);
425 const Pos_index iiBirth = _get_birth(columnIndex + 1);
426
427 _add_to(columnIndex, columnIndex + 1);
428 _swap_at_index(columnIndex);
429
430 if (iBirth < iiBirth) {
431 _negative_transpose(columnIndex);
432 return true;
433 }
434
435 _add_to(columnIndex, columnIndex + 1);
436
437 return false;
438}
439
440template <class Master_matrix>
441inline bool RU_vine_swap<Master_matrix>::_positive_negative_vine_swap(Index columnIndex)
442{
443 _matrix()->mirrorMatrixU_.zero_entry(columnIndex, _get_row_id_from_position(columnIndex + 1));
444
445 _swap_at_index(columnIndex);
446 _positive_negative_transpose(columnIndex);
447
448 return true;
449}
450
451template <class Master_matrix>
452inline bool RU_vine_swap<Master_matrix>::_negative_positive_vine_swap(Index columnIndex)
453{
454 _add_to(columnIndex, columnIndex + 1); // useless for R?
455 _swap_at_index(columnIndex); // if additions not made for R, do not swap R columns, just rows
456 _add_to(columnIndex, columnIndex + 1); // useless for R?
457
458 return false;
459}
460
461template <class Master_matrix>
462inline typename RU_vine_swap<Master_matrix>::Pos_index& RU_vine_swap<Master_matrix>::_death(Pos_index simplexIndex)
463{
464 static_assert(Master_matrix::Option_list::has_column_pairings, "Pairing necessary to modify death value.");
465
466 if constexpr (Master_matrix::Option_list::has_removable_columns) {
467 return RUP::indexToBar_.at(simplexIndex)->death;
468 } else {
469 return RUP::barcode_.at(RUP::indexToBar_.at(simplexIndex)).death;
470 }
471}
472
473template <class Master_matrix>
474inline typename RU_vine_swap<Master_matrix>::Pos_index& RU_vine_swap<Master_matrix>::_birth(Pos_index simplexIndex)
475{
476 static_assert(Master_matrix::Option_list::has_column_pairings, "Pairing necessary to modify birth value.");
477
478 if constexpr (Master_matrix::Option_list::has_removable_columns) {
479 return RUP::indexToBar_.at(simplexIndex)->birth;
480 } else {
481 return RUP::barcode_.at(RUP::indexToBar_.at(simplexIndex)).birth;
482 }
483}
484
485template <class Master_matrix>
486inline typename RU_vine_swap<Master_matrix>::Pos_index RU_vine_swap<Master_matrix>::_get_death(Index simplexIndex)
487{
488 if constexpr (Master_matrix::Option_list::has_column_pairings) {
489 if constexpr (Master_matrix::Option_list::has_removable_columns) {
490 return RUP::indexToBar_.at(simplexIndex)->death;
491 } else {
492 return RUP::barcode_.at(RUP::indexToBar_.at(simplexIndex)).death;
493 }
494 } else {
495 if (!_matrix()->reducedMatrixR_.is_zero_column(simplexIndex))
496 return _matrix()->reducedMatrixR_.get_column(simplexIndex).get_pivot();
497
498 if constexpr (Master_matrix::Option_list::has_map_column_container) {
499 auto it = _matrix()->pivotToColumnIndex_.find(simplexIndex);
500 if (it == _matrix()->pivotToColumnIndex_.end()) return Master_matrix::template get_null_value<Pos_index>();
501 return it->second;
502 } else {
503 return _matrix()->pivotToColumnIndex_[simplexIndex];
504 }
505 }
506}
507
508template <class Master_matrix>
509inline typename RU_vine_swap<Master_matrix>::Pos_index RU_vine_swap<Master_matrix>::_get_birth(
510 Index negativeSimplexIndex)
511{
512 if constexpr (Master_matrix::Option_list::has_column_pairings) {
513 if constexpr (Master_matrix::Option_list::has_removable_columns) {
514 return RUP::indexToBar_.at(negativeSimplexIndex)->birth;
515 } else {
516 return RUP::barcode_.at(RUP::indexToBar_.at(negativeSimplexIndex)).birth;
517 }
518 } else {
519 return _matrix()->reducedMatrixR_.get_pivot(negativeSimplexIndex);
520 }
521}
522
523template <class Master_matrix>
524inline typename RU_vine_swap<Master_matrix>::ID_index RU_vine_swap<Master_matrix>::_get_row_id_from_position(
525 Pos_index position)
526{
527 auto it = _positionToRowIdx().find(position);
528 return it == _positionToRowIdx().end() ? position : it->second;
529}
530
531template <class Master_matrix>
532inline constexpr auto& RU_vine_swap<Master_matrix>::_positionToRowIdx()
533{
534 if constexpr (Master_matrix::Option_list::has_column_pairings && Master_matrix::Option_list::has_removable_columns)
535 return RUP::PIDM::map_;
536 else
537 return RUM::map_;
538}
539
540} // namespace persistence_matrix
541} // namespace Gudhi
542
543#endif // PM_RU_VINE_SWAP_H
Contains the Gudhi::persistence_matrix::Cell_position_to_ID_mapper class and Gudhi::persistence_matri...
Class managing the barcode for RU_matrix if the option was enabled.
Definition: ru_pairing.h:54
Class managing the vine swaps for RU_matrix.
Definition: ru_vine_swap.h:74
friend void swap(RU_vine_swap &swap1, RU_vine_swap &swap2)
Swap operator.
Definition: ru_vine_swap.h:127
RU_vine_swap & operator=(RU_vine_swap other)
Assign operator.
Definition: ru_vine_swap.h:266
typename Master_matrix::ID_index ID_index
Definition: ru_vine_swap.h:77
RU_vine_swap()
Default constructor.
Definition: ru_vine_swap.h:179
typename Master_matrix::Index Index
Definition: ru_vine_swap.h:76
bool vine_swap_with_z_eq_1_case(Pos_index index)
Does the same than vine_swap, but assumes that the swap is non trivial and therefore skips a part of ...
Definition: ru_vine_swap.h:195
typename Master_matrix::Pos_index Pos_index
Definition: ru_vine_swap.h:78
bool vine_swap(Pos_index index)
Does a vine swap between two cells which are consecutive in the filtration. Roughly,...
Definition: ru_vine_swap.h:216
Gudhi namespace.
Definition: SimplicialComplexForAlpha.h:14
Contains the Gudhi::persistence_matrix::RU_pairing class and Gudhi::persistence_matrix::Dummy_ru_pair...
Empty structure. Inherited instead of RU_pairing, when the barcode is not stored.
Definition: ru_vine_swap.h:51
Empty structure. Inherited instead of RU_vine_swap, when vine swaps are not enabled.
Definition: ru_vine_swap.h:40