Loading...
Searching...
No Matches
filtered_zigzag_persistence.h
Go to the documentation of this file.
/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* Author(s): Clément Maria
*
* Copyright (C) 2021 Inria
*
* Modification(s):
* - 2023/05 Hannah Schreiber: Rework of the interface, reorganization and debug
* - 2023/05 Hannah Schreiber: Addition of infinite bars
* - 2024/06 Hannah Schreiber: Separation of the zigzag algorithm from the filtration value management
* - YYYY/MM Author: Description of the modification
*/
#ifndef FILTERED_ZIGZAG_PERSISTENCE_H_
#define FILTERED_ZIGZAG_PERSISTENCE_H_
#include <cmath>
#include <limits>
#include <unordered_map>
#include <utility>
#include <vector>
#include <gudhi/Debug_utils.h>
#include <gudhi/zigzag_persistence.h>
#include <gudhi/persistence_interval.h>
namespace Gudhi {
namespace zigzag_persistence {
struct Default_filtered_zigzag_options : Default_zigzag_options {
using Cell_key = int;
using Filtration_value = double;
};
template <class FilteredZigzagOptions = Default_filtered_zigzag_options>
class Filtered_zigzag_persistence_with_storage
{
public:
using Options = FilteredZigzagOptions;
using Internal_key = typename Options::Internal_key;
using Cell_key = typename Options::Cell_key;
using Filtration_value = typename Options::Filtration_value;
using Dimension = typename Options::Dimension;
using Index_interval = Gudhi::persistence_matrix::Persistence_interval<Dimension,Internal_key>;
using Filtration_value_interval = Gudhi::persistence_matrix::Persistence_interval<Dimension,Filtration_value>;
Filtered_zigzag_persistence_with_storage(unsigned int preallocationSize = 0, int ignoreCyclesAboveDim = -1)
: dimMax_(ignoreCyclesAboveDim),
persistenceDiagram_(),
numArrow_(-1),
previousFiltrationValue_(std::numeric_limits<Filtration_value>::infinity()),
pers_(
[&](Dimension dim, Internal_key birth, Internal_key death) {
if (dimMax_ == -1 || (dimMax_ != -1 && dim < dimMax_)) { // don't record intervals over max dim
persistenceDiagram_.emplace_back(birth, death, dim);
}
},
preallocationSize) {}
template <class BoundaryRange = std::initializer_list<Cell_key> >
Internal_key insert_cell(Cell_key cellID,
const BoundaryRange& boundary,
Dimension dimension,
Filtration_value filtrationValue)
{
if (dimMax_ != -1 && dimension > dimMax_) {
return apply_identity();
}
++numArrow_;
_store_filtration_value(filtrationValue);
[[maybe_unused]] auto res = handleToKey_.try_emplace(cellID, numArrow_);
GUDHI_CHECK(res.second, "Zigzag_persistence::insert_cell - cell already in the complex");
// Compute the keys of the cells of the boundary.
std::vector<Internal_key> translatedBoundary;
translatedBoundary.reserve(dimension * 2); // boundary does not have to have `size()`
for (auto b : boundary) {
translatedBoundary.push_back(handleToKey_.at(b)); // TODO: add possibilities of coefficients
}
std::sort(translatedBoundary.begin(), translatedBoundary.end());
pers_.insert_cell(translatedBoundary, dimension);
return numArrow_;
}
Internal_key remove_cell(Cell_key cellID, Filtration_value filtrationValue) {
auto it = handleToKey_.find(cellID);
if (it == handleToKey_.end()) {
return apply_identity();
}
++numArrow_;
_store_filtration_value(filtrationValue);
pers_.remove_cell(it->second);
handleToKey_.erase(it);
return numArrow_;
}
Internal_key apply_identity() {
++numArrow_;
pers_.apply_identity();
return numArrow_;
}
const std::vector<Index_interval>& get_index_persistence_diagram() const { return persistenceDiagram_; }
Filtration_value get_filtration_value_from_index(Internal_key idx) {
// lower_bound(x) returns leftmost y s.t. x <= y
auto itBirth =
std::lower_bound(filtrationValues_.begin(),
filtrationValues_.end(),
idx,
[](std::pair<Internal_key, Filtration_value> p, Internal_key k) { return p.first < k; });
if (itBirth == filtrationValues_.end() || itBirth->first > idx) {
--itBirth;
}
return itBirth->second;
};
std::vector<Filtration_value_interval> get_persistence_diagram(Filtration_value shortestInterval = 0.,
bool includeInfiniteBars = true) {
std::vector<Filtration_value_interval> diag = _get_persistence_diagram(shortestInterval);
if (includeInfiniteBars) {
_retrieve_infinite_bars(diag);
}
return diag;
}
private:
std::unordered_map<Cell_key, Internal_key> handleToKey_;
Dimension dimMax_;
std::vector<Index_interval> persistenceDiagram_;
Internal_key numArrow_;
Filtration_value previousFiltrationValue_;
std::vector<std::pair<Internal_key, Filtration_value> > filtrationValues_;
Zigzag_persistence<FilteredZigzagOptions> pers_;
void _store_filtration_value(Filtration_value filtrationValue) {
if (filtrationValue != previousFiltrationValue_) // check whether the filt value has changed
{
// consecutive pairs (i,f), (j,f') mean cells of index k in [i,j-1] have filtration value f
previousFiltrationValue_ = filtrationValue;
filtrationValues_.emplace_back(numArrow_, previousFiltrationValue_);
}
}
std::vector<Filtration_value_interval> _get_persistence_diagram(Filtration_value shortestInterval) {
std::vector<Filtration_value_interval> diag;
diag.reserve(persistenceDiagram_.size());
// std::stable_sort(filtrationValues_.begin(), filtrationValues_.end(),
// [](std::pair<Internal_key, Filtration_value> p1, std::pair<Internal_key, Filtration_value> p2) {
// return p1.first < p2.first;
// });
for (auto bar : persistenceDiagram_) {
Filtration_value birth = get_filtration_value_from_index(bar.birth);
Filtration_value death = get_filtration_value_from_index(bar.death);
if (birth > death) {
std::swap(birth, death);
}
if (death - birth > shortestInterval) {
diag.emplace_back(birth, death, bar.dim);
}
}
return diag;
}
void _retrieve_infinite_bars(std::vector<Filtration_value_interval>& diag) {
auto stream_infinite_interval = [&](Dimension dim, Internal_key birthIndex) {
if (dimMax_ == -1 || (dimMax_ != -1 && dim < dimMax_))
diag.emplace_back(get_filtration_value_from_index(birthIndex), Filtration_value_interval::inf, dim);
};
pers_.get_current_infinite_intervals(stream_infinite_interval);
}
}; // end class Filtered_zigzag_persistence_with_storage
template <class FilteredZigzagOptions = Default_filtered_zigzag_options>
class Filtered_zigzag_persistence {
public:
using Options = FilteredZigzagOptions;
using Internal_key = typename Options::Internal_key;
using Cell_key = typename Options::Cell_key;
using Filtration_value = typename Options::Filtration_value;
using Dimension = typename Options::Dimension;
template <typename F>
Filtered_zigzag_persistence(F&& stream_interval, unsigned int preallocationSize = 0)
: handleToKey_(preallocationSize),
numArrow_(-1),
keyToFiltrationValue_(preallocationSize),
pers_(
[&, stream_interval = std::forward<F>(stream_interval)](Dimension dim,
Internal_key birth,
Internal_key death) {
auto itB = keyToFiltrationValue_.find(birth);
auto itD = keyToFiltrationValue_.find(death);
if (itB->second != itD->second) stream_interval(dim, itB->second, itD->second);
keyToFiltrationValue_.erase(itB);
keyToFiltrationValue_.erase(itD);
},
preallocationSize) {}
template <class BoundaryRange = std::initializer_list<Cell_key> >
Internal_key insert_cell(Cell_key cellID,
const BoundaryRange& boundary,
Dimension dimension,
Filtration_value filtrationValue)
{
++numArrow_;
[[maybe_unused]] auto res = handleToKey_.try_emplace(cellID, numArrow_);
GUDHI_CHECK(res.second, "Zigzag_persistence::insert_cell - cell already in the complex");
keyToFiltrationValue_.try_emplace(numArrow_, filtrationValue);
// Compute the keys of the cells of the boundary.
std::vector<Internal_key> translatedBoundary;
translatedBoundary.reserve(dimension * 2); // boundary does not have to have `size()`
for (auto b : boundary) {
translatedBoundary.push_back(handleToKey_.at(b)); // TODO: add possibilities of coefficients
}
std::sort(translatedBoundary.begin(), translatedBoundary.end());
pers_.insert_cell(translatedBoundary, dimension);
return numArrow_;
}
Internal_key remove_cell(Cell_key cellID, Filtration_value filtrationValue) {
++numArrow_;
auto it = handleToKey_.find(cellID);
GUDHI_CHECK(it != handleToKey_.end(), "Zigzag_persistence::remove_cell - cell not in the complex");
keyToFiltrationValue_.try_emplace(numArrow_, filtrationValue);
pers_.remove_cell(it->second);
handleToKey_.erase(it);
return numArrow_;
}
Internal_key apply_identity() {
++numArrow_;
pers_.apply_identity();
return numArrow_;
}
template <typename F>
void get_current_infinite_intervals(F&& stream_infinite_interval) {
pers_.get_current_infinite_intervals(
[&](Dimension dim, Internal_key birth) { stream_infinite_interval(dim, keyToFiltrationValue_.at(birth)); });
}
private:
template <typename key_type, typename value_type>
using Dictionary = std::unordered_map<key_type, value_type>; // TODO: benchmark with other map types
Dictionary<Cell_key, Internal_key> handleToKey_;
Internal_key numArrow_;
Dictionary<Internal_key, Filtration_value> keyToFiltrationValue_;
Zigzag_persistence<FilteredZigzagOptions> pers_;
}; // end class Filtered_zigzag_persistence
} // namespace zigzag_persistence
} // namespace Gudhi
#endif // FILTERED_ZIGZAG_PERSISTENCE_H_
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::remove_cell
Internal_key remove_cell(Cell_key cellID, Filtration_value filtrationValue)
Updates the zigzag persistence diagram after the removal of the given cell if the cell was contained ...
Definition filtered_zigzag_persistence.h:221
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Internal_key
typename Options::Internal_key Internal_key
Definition filtered_zigzag_persistence.h:124
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Filtered_zigzag_persistence_with_storage
Filtered_zigzag_persistence_with_storage(unsigned int preallocationSize=0, int ignoreCyclesAboveDim=-1)
Constructor.
Definition filtered_zigzag_persistence.h:152
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Options
FilteredZigzagOptions Options
Definition filtered_zigzag_persistence.h:123
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Filtration_value
typename Options::Filtration_value Filtration_value
Definition filtered_zigzag_persistence.h:126
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::apply_identity
Internal_key apply_identity()
To use when a cell is neither inserted nor removed, but the filtration moves along the identity opera...
Definition filtered_zigzag_persistence.h:244
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Filtration_value_interval
Gudhi::persistence_matrix::Persistence_interval< Dimension, Filtration_value > Filtration_value_interval
Persistence filtration interval type.
Definition filtered_zigzag_persistence.h:136
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::get_persistence_diagram
std::vector< Filtration_value_interval > get_persistence_diagram(Filtration_value shortestInterval=0., bool includeInfiniteBars=true)
Returns the current persistence diagram.
Definition filtered_zigzag_persistence.h:286
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Dimension
typename Options::Dimension Dimension
Definition filtered_zigzag_persistence.h:127
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Cell_key
typename Options::Cell_key Cell_key
Definition filtered_zigzag_persistence.h:125
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::Index_interval
Gudhi::persistence_matrix::Persistence_interval< Dimension, Internal_key > Index_interval
Persistence index interval type.
Definition filtered_zigzag_persistence.h:132
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::get_index_persistence_diagram
const std::vector< Index_interval > & get_index_persistence_diagram() const
Returns the "index persistence diagram" of the current filtration, that is, the pairs of atomic arrow...
Definition filtered_zigzag_persistence.h:257
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::insert_cell
Internal_key insert_cell(Cell_key cellID, const BoundaryRange &boundary, Dimension dimension, Filtration_value filtrationValue)
Updates the zigzag persistence diagram after the insertion of the given cell.
Definition filtered_zigzag_persistence.h:180
Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage::get_filtration_value_from_index
Filtration_value get_filtration_value_from_index(Internal_key idx)
Returns the filtration value associated to the index returned by get_index_persistence_diagram.
Definition filtered_zigzag_persistence.h:266
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::get_current_infinite_intervals
void get_current_infinite_intervals(F &&stream_infinite_interval)
Outputs through the given callback method all current infinite bars.
Definition filtered_zigzag_persistence.h:565
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Cell_key
typename Options::Cell_key Cell_key
Definition filtered_zigzag_persistence.h:446
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Filtration_value
typename Options::Filtration_value Filtration_value
Definition filtered_zigzag_persistence.h:447
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::remove_cell
Internal_key remove_cell(Cell_key cellID, Filtration_value filtrationValue)
Updates the zigzag persistence diagram after the removal of the given cell. preallocationSize.
Definition filtered_zigzag_persistence.h:532
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Dimension
typename Options::Dimension Dimension
Definition filtered_zigzag_persistence.h:448
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Internal_key
typename Options::Internal_key Internal_key
Definition filtered_zigzag_persistence.h:445
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Filtered_zigzag_persistence
Filtered_zigzag_persistence(F &&stream_interval, unsigned int preallocationSize=0)
Constructor.
Definition filtered_zigzag_persistence.h:468
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::insert_cell
Internal_key insert_cell(Cell_key cellID, const BoundaryRange &boundary, Dimension dimension, Filtration_value filtrationValue)
Updates the zigzag persistence diagram after the insertion of the given cell.
Definition filtered_zigzag_persistence.h:498
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Options
FilteredZigzagOptions Options
Definition filtered_zigzag_persistence.h:444
Gudhi::zigzag_persistence::Filtered_zigzag_persistence::apply_identity
Internal_key apply_identity()
To use when a cell is neither inserted nor removed, but the filtration moves along the identity opera...
Definition filtered_zigzag_persistence.h:551
Gudhi::zigzag_persistence::Zigzag_persistence
Class computing the zigzag persistent homology of a zigzag sequence. Algorithm based on zigzag.
Definition zigzag_persistence.h:150
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14
std
STL namespace.
persistence_interval.h
Contains Gudhi::persistence_matrix::Persistence_interval class.
Gudhi::persistence_matrix::Persistence_interval
Type for an interval in a persistent diagram or barcode. Stores the birth, death and dimension of the...
Definition persistence_interval.h:40
Gudhi::persistence_matrix::Persistence_interval< Dimension, Filtration_value >::inf
static constexpr Filtration_value inf
Definition persistence_interval.h:50
Gudhi::zigzag_persistence::Default_filtered_zigzag_options
Default options for Filtered_zigzag_persistence_with_storage and Filtered_zigzag_persistence.
Definition filtered_zigzag_persistence.h:43
Gudhi::zigzag_persistence::Default_filtered_zigzag_options::Cell_key
int Cell_key
Definition filtered_zigzag_persistence.h:44
Gudhi::zigzag_persistence::Default_filtered_zigzag_options::Filtration_value
double Filtration_value
Definition filtered_zigzag_persistence.h:45
Gudhi::zigzag_persistence::Default_zigzag_options
Default options for Zigzag_persistence.
Definition zigzag_persistence.h:65
Gudhi::zigzag_persistence::FilteredZigzagOptions
List of options used for the filtered zigzag persistence computation.
Definition ZigzagOptions.h:27
Gudhi::zigzag_persistence::FilteredZigzagOptions::Dimension
unspecified Dimension
Type for the dimension values.
Definition ZigzagOptions.h:47
Gudhi::zigzag_persistence::FilteredZigzagOptions::Filtration_value
unspecified Filtration_value
Type for filtration values.
Definition ZigzagOptions.h:42
Gudhi::zigzag_persistence::FilteredZigzagOptions::Internal_key
unspecified Internal_key
Numerical type for the cell IDs used internally and other indexations. It must be signed.
Definition ZigzagOptions.h:31
Gudhi::zigzag_persistence::FilteredZigzagOptions::Cell_key
unspecified Cell_key
Type for the cell IDs used at insertion and in the boundaries given as argument. Has to be usable as ...
Definition ZigzagOptions.h:37
zigzag_persistence.h
Contains the implementation of the Gudhi::zigzag_persistence::Zigzag_persistence class.