Loading...
Searching...
No Matches
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
18#ifndef PM_RU_VINE_SWAP_H
19#define PM_RU_VINE_SWAP_H
20
21#include <utility> //std::move
22#include <type_traits> //std::conditional
23#include <cassert>
24#include <vector>
25#include <stdexcept> //std::invalid_argument
26
27#include "ru_pairing.h"
28
29namespace Gudhi {
30namespace persistence_matrix {
31
39 friend void swap([[maybe_unused]] Dummy_ru_vine_swap& d1, [[maybe_unused]] Dummy_ru_vine_swap& d2) {}
40};
41
49 friend void swap([[maybe_unused]] Dummy_ru_vine_pairing& d1, [[maybe_unused]] Dummy_ru_vine_pairing& d2) {}
50};
51
60template <class Master_matrix>
61class RU_vine_swap : public std::conditional<Master_matrix::Option_list::has_column_pairings,
62 RU_pairing<Master_matrix>,
63 Dummy_ru_vine_pairing
64 >::type
65{
66 public:
67 using index = typename Master_matrix::index;
68 using id_index = typename Master_matrix::id_index;
69 using pos_index = typename Master_matrix::pos_index;
80 RU_vine_swap(const RU_vine_swap& matrixToCopy);
86 RU_vine_swap(RU_vine_swap&& other) noexcept;
87
110
118 friend void swap(RU_vine_swap& swap1, RU_vine_swap& swap2) {
119 if constexpr (Master_matrix::Option_list::has_column_pairings) {
120 swap(static_cast<RU_pairing<Master_matrix>&>(swap1), static_cast<RU_pairing<Master_matrix>&>(swap2));
121 }
122 swap1.positionToRowIdx_.swap(swap2.positionToRowIdx_);
123 }
124
125 protected:
126 // only usefull when simplex id does not corresponds to position, so feels kinda useless most of the time...
127 // TODO: as it takes up some non trivial memory, see if this should not be optional
128 // or only remember the positions with a difference. but then a map is needed, ie find instead of [].
129 std::vector<id_index> positionToRowIdx_;
131 private:
132 using RUP = typename std::conditional<Master_matrix::Option_list::has_column_pairings,
135 >::type;
136 using ru_matrix = typename Master_matrix::RU_matrix_type;
137
138 bool _is_paired(index columnIndex);
139
140 void _swap_at_index(index columnIndex);
141 void _add_to(index sourceIndex, index targetIndex);
142 void _positive_transpose(index columnIndex);
143 void _negative_transpose(index columnIndex);
144 void _positive_negative_transpose(index columnIndex);
145 void _negative_positive_transpose(index columnIndex);
146 bool _positive_vine_swap(index columnIndex);
147 bool _negative_vine_swap(index columnIndex);
148 bool _positive_negative_vine_swap(index columnIndex);
149 bool _negative_positive_vine_swap(index columnIndex);
150
151 pos_index& _death(pos_index simplexIndex);
152 pos_index& _birth(pos_index simplexIndex);
153 pos_index _get_death(index simplexIndex);
154 pos_index _get_birth(index simplexIndex);
155
156 constexpr ru_matrix* _matrix() { return static_cast<ru_matrix*>(this); }
157 constexpr const ru_matrix* _matrix() const { return static_cast<const ru_matrix*>(this); }
158};
159
160template <class Master_matrix>
163
164template <class Master_matrix>
166 : RUP(static_cast<const RUP&>(matrixToCopy)), positionToRowIdx_(matrixToCopy.positionToRowIdx_)
167{}
168
169template <class Master_matrix>
171 : RUP(std::move(static_cast<RUP&>(other))), positionToRowIdx_(std::move(other.positionToRowIdx_))
172{}
173
174template <class Master_matrix>
176{
177 GUDHI_CHECK(index < _matrix()->reducedMatrixR_.get_number_of_columns() - 1,
178 std::invalid_argument("RU_vine_swap::vine_swap_with_z_eq_1_case - Index to swap out of bound."));
179
180 bool iIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index);
181 bool iiIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index + 1);
182
183 if (iIsPositive && iiIsPositive) {
184 _matrix()->mirrorMatrixU_.zero_cell(index, positionToRowIdx_[index + 1]);
185 return _positive_vine_swap(index);
186 } else if (!iIsPositive && !iiIsPositive) {
187 return _negative_vine_swap(index);
188 } else if (iIsPositive && !iiIsPositive) {
189 return _positive_negative_vine_swap(index);
190 } else {
191 return _negative_positive_vine_swap(index);
192 }
193}
194
195template <class Master_matrix>
197{
198 GUDHI_CHECK(index < _matrix()->reducedMatrixR_.get_number_of_columns() - 1,
199 std::invalid_argument("RU_vine_swap::vine_swap - Index to swap out of bound."));
200
201 bool iIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index);
202 bool iiIsPositive = _matrix()->reducedMatrixR_.is_zero_column(index + 1);
203
204 if (iIsPositive && iiIsPositive) {
205 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
206 _matrix()->reducedMatrixR_.get_column_dimension(index + 1)) {
207 _positive_transpose(index);
208 _swap_at_index(index);
209 return true;
210 }
211 if (!_matrix()->mirrorMatrixU_.is_zero_cell(index, positionToRowIdx_[index + 1])) {
212 _matrix()->mirrorMatrixU_.zero_cell(index, positionToRowIdx_[index + 1]);
213 }
214 return _positive_vine_swap(index);
215 } else if (!iIsPositive && !iiIsPositive) {
216 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
217 _matrix()->reducedMatrixR_.get_column_dimension(index + 1) ||
218 _matrix()->mirrorMatrixU_.is_zero_cell(index, positionToRowIdx_[index + 1])) {
219 _negative_transpose(index);
220 _swap_at_index(index);
221 return true;
222 }
223 return _negative_vine_swap(index);
224 } else if (iIsPositive && !iiIsPositive) {
225 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
226 _matrix()->reducedMatrixR_.get_column_dimension(index + 1) ||
227 _matrix()->mirrorMatrixU_.is_zero_cell(index, positionToRowIdx_[index + 1])) {
228 _positive_negative_transpose(index);
229 _swap_at_index(index);
230 return true;
231 }
232 return _positive_negative_vine_swap(index);
233 } else {
234 if (_matrix()->reducedMatrixR_.get_column_dimension(index) !=
235 _matrix()->reducedMatrixR_.get_column_dimension(index + 1) ||
236 _matrix()->mirrorMatrixU_.is_zero_cell(index, positionToRowIdx_[index + 1])) {
237 _negative_positive_transpose(index);
238 _swap_at_index(index);
239 return true;
240 }
241 return _negative_positive_vine_swap(index);
242 }
243}
244
245template <class Master_matrix>
247{
248 RUP::operator=(other);
249 positionToRowIdx_.swap(other.positionToRowIdx_);
250 return *this;
251}
252
253template <class Master_matrix>
254inline bool RU_vine_swap<Master_matrix>::_is_paired(index columnIndex)
255{
256 if constexpr (Master_matrix::Option_list::has_column_pairings) {
257 return _get_death(columnIndex) != static_cast<pos_index>(-1);
258 } else {
259 if (!_matrix()->reducedMatrixR_.is_zero_column(columnIndex)) return true;
260
261 if constexpr (Master_matrix::Option_list::has_map_column_container) {
262 if (_matrix()->pivotToColumnIndex_.find(columnIndex) == _matrix()->pivotToColumnIndex_.end()) return false;
263 } else {
264 if (_matrix()->pivotToColumnIndex_.operator[](columnIndex) == static_cast<index>(-1)) return false;
265 }
266
267 return true;
268 }
269}
270
271template <class Master_matrix>
272inline void RU_vine_swap<Master_matrix>::_swap_at_index(index columnIndex)
273{
274 _matrix()->reducedMatrixR_.swap_columns(columnIndex, columnIndex + 1);
275 _matrix()->reducedMatrixR_.swap_rows(positionToRowIdx_[columnIndex], positionToRowIdx_[columnIndex + 1]);
276 _matrix()->mirrorMatrixU_.swap_columns(columnIndex, columnIndex + 1);
277 _matrix()->mirrorMatrixU_.swap_rows(positionToRowIdx_[columnIndex], positionToRowIdx_[columnIndex + 1]);
278}
279
280template <class Master_matrix>
281inline void RU_vine_swap<Master_matrix>::_add_to(index sourceIndex, index targetIndex)
282{
283 _matrix()->reducedMatrixR_.add_to(sourceIndex, targetIndex);
284 _matrix()->mirrorMatrixU_.add_to(targetIndex, sourceIndex);
285}
286
287template <class Master_matrix>
288inline void RU_vine_swap<Master_matrix>::_positive_transpose(index columnIndex)
289{
290 if constexpr (Master_matrix::Option_list::has_map_column_container) {
291 if (_is_paired(columnIndex) && _is_paired(columnIndex + 1)) {
292 std::swap(_matrix()->pivotToColumnIndex_.at(columnIndex), _matrix()->pivotToColumnIndex_.at(columnIndex + 1));
293 } else if (_is_paired(columnIndex)) {
294 _matrix()->pivotToColumnIndex_.emplace(columnIndex + 1, _matrix()->pivotToColumnIndex_.at(columnIndex));
295 _matrix()->pivotToColumnIndex_.erase(columnIndex);
296 } else if (_is_paired(columnIndex + 1)) {
297 _matrix()->pivotToColumnIndex_.emplace(columnIndex, _matrix()->pivotToColumnIndex_.at(columnIndex + 1));
298 _matrix()->pivotToColumnIndex_.erase(columnIndex + 1);
299 }
300 } else {
301 std::swap(_matrix()->pivotToColumnIndex_.operator[](columnIndex),
302 _matrix()->pivotToColumnIndex_.operator[](columnIndex + 1));
303 }
304
305 if constexpr (Master_matrix::Option_list::has_column_pairings) {
306 _birth(columnIndex) = columnIndex + 1;
307 _birth(columnIndex + 1) = columnIndex;
308 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
309 }
310}
311
312template <class Master_matrix>
313inline void RU_vine_swap<Master_matrix>::_negative_transpose(index columnIndex)
314{
315 if constexpr (Master_matrix::Option_list::has_column_pairings) {
316 _death(columnIndex) = columnIndex + 1;
317 _death(columnIndex + 1) = columnIndex;
318 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
319 }
320 std::swap(_matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex)),
321 _matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex + 1)));
322}
323
324template <class Master_matrix>
325inline void RU_vine_swap<Master_matrix>::_positive_negative_transpose(index columnIndex)
326{
327 _matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex + 1)) = columnIndex;
328 if constexpr (Master_matrix::Option_list::has_map_column_container) {
329 if (_is_paired(columnIndex)) {
330 _matrix()->pivotToColumnIndex_.emplace(columnIndex + 1, _matrix()->pivotToColumnIndex_.at(columnIndex));
331 _matrix()->pivotToColumnIndex_.erase(columnIndex);
332 }
333 } else {
334 _matrix()->pivotToColumnIndex_.operator[](columnIndex + 1) = _matrix()->pivotToColumnIndex_.operator[](columnIndex);
335 _matrix()->pivotToColumnIndex_.operator[](columnIndex) = -1;
336 }
337
338 if constexpr (Master_matrix::Option_list::has_column_pairings) {
339 _birth(columnIndex) = columnIndex + 1;
340 _death(columnIndex + 1) = columnIndex;
341 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
342 }
343}
344
345template <class Master_matrix>
346inline void RU_vine_swap<Master_matrix>::_negative_positive_transpose(index columnIndex)
347{
348 _matrix()->pivotToColumnIndex_.at(_get_birth(columnIndex)) = columnIndex + 1;
349 if constexpr (Master_matrix::Option_list::has_map_column_container) {
350 if (_is_paired(columnIndex + 1)) {
351 _matrix()->pivotToColumnIndex_.emplace(columnIndex, _matrix()->pivotToColumnIndex_.at(columnIndex + 1));
352 _matrix()->pivotToColumnIndex_.erase(columnIndex + 1);
353 }
354 } else {
355 _matrix()->pivotToColumnIndex_.operator[](columnIndex) = _matrix()->pivotToColumnIndex_.operator[](columnIndex + 1);
356 _matrix()->pivotToColumnIndex_.operator[](columnIndex + 1) = -1;
357 }
358
359 if constexpr (Master_matrix::Option_list::has_column_pairings) {
360 _death(columnIndex) = columnIndex + 1;
361 _birth(columnIndex + 1) = columnIndex;
362 std::swap(RUP::indexToBar_.at(columnIndex), RUP::indexToBar_.at(columnIndex + 1));
363 }
364}
365
366template <class Master_matrix>
367inline bool RU_vine_swap<Master_matrix>::_positive_vine_swap(index columnIndex)
368{
369 const pos_index iDeath = _get_death(columnIndex);
370 const pos_index iiDeath = _get_death(columnIndex + 1);
371
372 if (iDeath != static_cast<pos_index>(-1) && iiDeath != static_cast<pos_index>(-1) &&
373 !(_matrix()->reducedMatrixR_.is_zero_cell(iiDeath, positionToRowIdx_[columnIndex]))) {
374 if (iDeath < iiDeath) {
375 _swap_at_index(columnIndex);
376 _add_to(iDeath, iiDeath);
377 _positive_transpose(columnIndex);
378 return true;
379 }
380
381 _swap_at_index(columnIndex);
382 _add_to(iiDeath, iDeath);
383 return false;
384 }
385
386 _swap_at_index(columnIndex);
387
388 if (iDeath != static_cast<pos_index>(-1) || iiDeath == static_cast<pos_index>(-1) ||
389 _matrix()->reducedMatrixR_.is_zero_cell(iiDeath, positionToRowIdx_[columnIndex + 1])) {
390 _positive_transpose(columnIndex);
391 return true;
392 }
393 return false;
394}
395
396template <class Master_matrix>
397inline bool RU_vine_swap<Master_matrix>::_negative_vine_swap(index columnIndex)
398{
399 const pos_index iBirth = _get_birth(columnIndex);
400 const pos_index iiBirth = _get_birth(columnIndex + 1);
401
402 _add_to(columnIndex, columnIndex + 1);
403 _swap_at_index(columnIndex);
404
405 if (iBirth < iiBirth) {
406 _negative_transpose(columnIndex);
407 return true;
408 }
409
410 _add_to(columnIndex, columnIndex + 1);
411
412 return false;
413}
414
415template <class Master_matrix>
416inline bool RU_vine_swap<Master_matrix>::_positive_negative_vine_swap(index columnIndex)
417{
418 _matrix()->mirrorMatrixU_.zero_cell(columnIndex, positionToRowIdx_[columnIndex + 1]);
419
420 _swap_at_index(columnIndex);
421 _positive_negative_transpose(columnIndex);
422
423 return true;
424}
425
426template <class Master_matrix>
427inline bool RU_vine_swap<Master_matrix>::_negative_positive_vine_swap(index columnIndex)
428{
429 _add_to(columnIndex, columnIndex + 1); // useless for R?
430 _swap_at_index(columnIndex); // if additions not made for R, do not swap R columns, just rows
431 _add_to(columnIndex, columnIndex + 1); // useless for R?
432
433 return false;
434}
435
436template <class Master_matrix>
437inline typename RU_vine_swap<Master_matrix>::pos_index& RU_vine_swap<Master_matrix>::_death(pos_index simplexIndex)
438{
439 static_assert(Master_matrix::Option_list::has_column_pairings, "Pairing necessary to modify death value.");
440
441 if constexpr (Master_matrix::Option_list::has_removable_columns) {
442 return RUP::indexToBar_.at(simplexIndex)->death;
443 } else {
444 return RUP::barcode_.at(RUP::indexToBar_.at(simplexIndex)).death;
445 }
446}
447
448template <class Master_matrix>
449inline typename RU_vine_swap<Master_matrix>::pos_index& RU_vine_swap<Master_matrix>::_birth(pos_index simplexIndex)
450{
451 static_assert(Master_matrix::Option_list::has_column_pairings, "Pairing necessary to modify birth value.");
452
453 if constexpr (Master_matrix::Option_list::has_removable_columns) {
454 return RUP::indexToBar_.at(simplexIndex)->birth;
455 } else {
456 return RUP::barcode_.at(RUP::indexToBar_.at(simplexIndex)).birth;
457 }
458}
459
460template <class Master_matrix>
461inline typename RU_vine_swap<Master_matrix>::pos_index RU_vine_swap<Master_matrix>::_get_death(index simplexIndex)
462{
463 if constexpr (Master_matrix::Option_list::has_column_pairings) {
464 if constexpr (Master_matrix::Option_list::has_removable_columns) {
465 return RUP::indexToBar_.at(simplexIndex)->death;
466 } else {
467 return RUP::barcode_.at(RUP::indexToBar_.at(simplexIndex)).death;
468 }
469 } else {
470 if (!_matrix()->reducedMatrixR_.is_zero_column(simplexIndex))
471 return _matrix()->reducedMatrixR_.get_column(simplexIndex).get_pivot();
472
473 if constexpr (Master_matrix::Option_list::has_map_column_container) {
474 auto it = _matrix()->pivotToColumnIndex_.find(simplexIndex);
475 if (it == _matrix()->pivotToColumnIndex_.end()) return -1;
476 return it->second;
477 } else {
478 return _matrix()->pivotToColumnIndex_.operator[](simplexIndex);
479 }
480 }
481}
482
483template <class Master_matrix>
484inline typename RU_vine_swap<Master_matrix>::pos_index RU_vine_swap<Master_matrix>::_get_birth(
485 index negativeSimplexIndex)
486{
487 if constexpr (Master_matrix::Option_list::has_column_pairings) {
488 if constexpr (Master_matrix::Option_list::has_removable_columns) {
489 return RUP::indexToBar_.at(negativeSimplexIndex)->birth;
490 } else {
491 return RUP::barcode_.at(RUP::indexToBar_.at(negativeSimplexIndex)).birth;
492 }
493 } else {
494 return _matrix()->reducedMatrixR_.get_pivot(negativeSimplexIndex);
495 }
496}
497
498} // namespace persistence_matrix
499} // namespace Gudhi
500
501#endif // PM_RU_VINE_SWAP_H
Class managing the barcode for RU_matrix if the option was enabled.
Definition ru_pairing.h:46
Class managing the vine swaps for RU_matrix.
Definition ru_vine_swap.h:65
typename Master_matrix::index index
Definition ru_vine_swap.h:67
typename Master_matrix::id_index id_index
Definition ru_vine_swap.h:68
friend void swap(RU_vine_swap &swap1, RU_vine_swap &swap2)
Swap operator.
Definition ru_vine_swap.h:118
RU_vine_swap & operator=(RU_vine_swap other)
Assign operator.
Definition ru_vine_swap.h:246
RU_vine_swap()
Default constructor.
Definition ru_vine_swap.h:161
bool vine_swap(pos_index index)
Does a vine swap between two faces which are consecutives in the filtration. Roughly,...
Definition ru_vine_swap.h:196
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:175
typename Master_matrix::pos_index pos_index
Definition ru_vine_swap.h:69
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14
Contains the RU_pairing class and Dummy_ru_pairing structure.
Empty structure. Inheritated instead of RU_pairing, when the barcode is not stored.
Definition ru_vine_swap.h:48
Empty structure. Inheritated instead of RU_vine_swap, when vine swappes are not enabled.
Definition ru_vine_swap.h:38