Loading...
Searching...
No Matches
Zigzag Persistence

## Classes

struct | Gudhi::zigzag_persistence::FilteredZigzagOptions
| List of options used for the filtered zigzag persistence computation. More...
struct | Gudhi::zigzag_persistence::ZigzagOptions
| List of options used for the zigzag persistence computation. More...
struct | Gudhi::zigzag_persistence::Default_filtered_zigzag_options
| Default options for Filtered_zigzag_persistence_with_storage and Filtered_zigzag_persistence. More...
class | Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage< FilteredZigzagOptions >
| Class computing the zigzag persistent homology of a zigzag filtration. Algorithm based on [zigzag]. Even though the insertions and removals are given in a "stream-like" way, the barcode and other values are stored during the whole process and not removed. It is therefore suited for smaller filtrations where the clean ups produce a higher overhead than the memory consumption. More...
class | Gudhi::zigzag_persistence::Filtered_zigzag_persistence< FilteredZigzagOptions >
| Class computing the zigzag persistent homology of a zigzag filtration. Algorithm based on [zigzag]. More...
struct | Gudhi::zigzag_persistence::Zigzag_matrix_options< column_type >
| Options for the internal matrix of Zigzag_persistence. More...
struct | Gudhi::zigzag_persistence::Default_zigzag_options
| Default options for Zigzag_persistence. More...
class | Gudhi::zigzag_persistence::Zigzag_persistence< ZigzagOptions >
| Class computing the zigzag persistent homology of a zigzag sequence. Algorithm based on [zigzag]. More...

## Detailed Description

Author
  Clément Maria, Hannah Schreiber

# Zigzag Persistence

We refer to the introduction page Persistent Cohomology for persistent (co)homology for an introduction to the topic. Zigzag persistence is a generalization of the latter. While standard persistence only allows to grow the filtered complex by adding cells, zigzag persistence also allows removals. Hence the name "zigzag", as the module diagram will have arrows alternating between forward and backward.

The module consists of the Zigzag_persistence class and two wrappers Filtered_zigzag_persistence and Filtered_zigzag_persistence_with_storage:

- Zigzag_persistence computes the persistence of a sequence of insertions and removals. A cell can be inserted or removed one at a time and the returned persistence pairs / bars are indexed on the operation numbers. For example, if a cycle is born at operation number 6 and dies at operation number 7, it will output a bar starting at 6 and ending at 7.
- Filtered_zigzag_persistence and Filtered_zigzag_persistence_with_storage are adding the notion of "filtration value" to Zigzag_persistence. At each call, an operation can be associated to a filtration value, which will be used to index the returned bars instead (bars with new length 0 are then ignored). The two classes also have more flexible inputs (the boundaries do not have to be ordered, nor identified continuously from 0). The difference between both classes is on the way they manage the memory: Filtered_zigzag_persistence removes systematically all unnecessary information and outputs a pair as soon it is closed, while Filtered_zigzag_persistence_with_storage will store all information about filtration values and bars until the end and output the pairs only when asked. Depending on the use and the length of the filtration, one will be more efficient than the other and vice versa.

The implementation is based on the algorithm introduced in [zigzag].

## Stream-like interface

As removals are possible in zigzag filtration, the maximal size of the complex does not depend on the length of the filtration anymore. This makes it possible to build very long fine tuned filtrations with relatively small complexes which can be processed without overreaching memory space. For this purpose, it is possible to feed the module with information about the filtration "on the fly" to avoid loading the whole filtration at once. Information about the current barcode can be retrieved between any steps via callback methods.

# Examples

## Minimalistic examples

- Zigzag_persistence/example_usage_zigzag_persistence.cpp - A simple example to showcase how to use the Zigzag_persistence class to compute a barcode.
  Details
  #include <iostream>
  #include <gudhi/zigzag_persistence.h>
  using Zigzag_persistence = Gudhi::zigzag_persistence::Zigzag_persistence<>;
  using Dimension = Zigzag_persistence::Dimension;
  using Index = Zigzag_persistence::Index;
  int main() {
  std::clog << "************* Minimalistic example of usage of the Zigzag_persistence class *************" << std::endl;
  // Zigzag_persistence(callback) with for example callback method as a anonymous lambda
  Zigzag_persistence zp([](Dimension dim, Index birth, Index death) {
  std::cout << "[" << dim << "] " << birth << " - " << death << std::endl;
  });
  // It is important that the operations of insertions and removals are made **in the same order** as in the zigzag
  // filtration ones wants to compute the barcode from.
  // A cell has to be identified in the boundaries by the operation number the cell was inserted with in the sequence.
  // inserts vertex 0 -> birth at 0 of 0-cycle
  zp.insert_cell({}, 0);
  // inserts vertex 1 -> birth at 1 of 0-cycle
  zp.insert_cell({}, 0);
  // inserts edge 2 = (0,1) -> death at 2 -> outputs (0, 1, 2)
  zp.insert_cell({0, 1}, 1);
  // inserts vertex 3 -> birth at 3 of 0-cycle
  zp.insert_cell({}, 0);
  // inserts edge 4 = (0,3) -> death at 4 -> outputs (0, 3, 4)
  zp.insert_cell({0, 3}, 1);
  // inserts edge 5 = (1,3) -> birth at 5 of 1-cycle
  zp.insert_cell({1, 3}, 1);
  // removes edge 4 -> death at 6 -> outputs (1, 5, 6)
  zp.remove_cell(4);
  // removes edge 2 -> birth at 7 of 0-cycle
  zp.remove_cell(2);
  // Only the closed bars were output so far, so the open/infinite bars still need to be retrieved.
  // in this example, computes (0, 0) and (0, 7)
  zp.get_current_infinite_intervals(
  [](Dimension dim, Index birth) { std::cout << "[" << dim << "] " << birth << " - inf" << std::endl; });
  return 0;
  Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Dimension
  typename Options::Dimension Dimension
  Definition filtered_zigzag_persistence.h:448
  Gudhi::zigzag_persistence::Zigzag_persistence
  Class computing the zigzag persistent homology of a zigzag sequence. Algorithm based on zigzag.
  Definition zigzag_persistence.h:150
  zigzag_persistence.h
  Contains the implementation of the Gudhi::zigzag_persistence::Zigzag_persistence class.
  }
- Zigzag_persistence/example_usage_filtered_zigzag_persistence.cpp - A simple example to showcase how to use the Filtered_zigzag_persistence class to compute a barcode.
  Details
  #include <iostream>
  #include <gudhi/filtered_zigzag_persistence.h>
  using Zigzag_persistence = Gudhi::zigzag_persistence::Filtered_zigzag_persistence<>;
  using Dimension = Zigzag_persistence::Dimension;
  using Filtration_value = Zigzag_persistence::Filtration_value;
  int main() {
  std::clog << "********* Minimalistic example of usage of the Filtered_zigzag_persistence class ********" << std::endl;
  // Filtered_zigzag_persistence(callback) with for example callback method as a anonymous lambda
  Zigzag_persistence zp([](Dimension dim, Filtration_value birth, Filtration_value death) {
  std::cout << "[" << dim << "] " << birth << " - " << death << std::endl;
  });
  // It is important that the operations of insertions and removals are made **in the same order** as in the zigzag
  // filtration ones wants to compute the barcode from.
  // A cell can be identified in the boundaries by any given numerical label, it is just important that the given
  // filtration values are monotonous (ie., either only increasing or only decreasing).
  // inserts vertex 2 at filtration value 0.1 -> birth at 0.1 of 0-cycle
  zp.insert_cell(2, {}, 0, 0.1);
  // inserts vertex 4 at filtration value 0.1 -> birth at 0.1 of 0-cycle
  zp.insert_cell(4, {}, 0, 0.1);
  // inserts edge 5 = (2,4) at filtration value 0.3 -> death at 0.3 -> outputs (0, 0.1, 0.3)
  zp.insert_cell(5, {2, 4}, 1, 0.3);
  // inserts vertex 3 at filtration value 0.4 -> birth at 0.4 of 0-cycle
  zp.insert_cell(3, {}, 0, 0.4);
  // inserts edge 6 = (2,3) at filtration value 0.4 -> death at 0.4 of the cycle born at 0.4 -> outputs nothing
  zp.insert_cell(6, {2, 3}, 1, 0.4);
  // inserts edge 9 = (3,4) at filtration value 1.2 -> birth at 1.2 of 1-cycle
  zp.insert_cell(9, {4, 3}, 1, 1.2);
  // removes edge 6 at filtration value 1.5 -> death at 1.5 -> outputs (1, 1.2, 1.5)
  zp.remove_cell(6, 1.5);
  // removes edge 5 at filtration value 2.0 -> birth at 2.0 of 0-cycle
  zp.remove_cell(5, 2.0);
  // Only the closed bars where output so far, so the open/infinite bars still need to be retrieved.
  // in this example, computes (0, 0.1) and (0, 2.0)
  zp.get_current_infinite_intervals([](Dimension dim, Filtration_value birth) {
  std::cout << "[" << dim << "] " << birth << " - inf" << std::endl;
  });
  return 0;
  Gudhi::zigzag_persistence::Filtered_zigzag_persistence
  Class computing the zigzag persistent homology of a zigzag filtration. Algorithm based on zigzag.
  Definition filtered_zigzag_persistence.h:442
  Gudhi::zigzag_persistence::Filtered_zigzag_persistence::Filtration_value
  typename Options::Filtration_value Filtration_value
  Definition filtered_zigzag_persistence.h:447
  filtered_zigzag_persistence.h
  Contains the implementation of the Gudhi::zigzag_persistence::Default_filtered_zigzag_options structu...
  }
- Zigzag_persistence/example_usage_filtered_zigzag_persistence_with_storage.cpp - A simple example to showcase how to use the Filtered_zigzag_persistence_with_storage class to compute a barcode.
  Details
  #include <iostream>
  #include <gudhi/filtered_zigzag_persistence.h>
  using Zigzag_persistence = Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage<>;
  int main() {
  std::clog << "** Minimalistic example of usage of the Filtered_zigzag_persistence_with_storage class **" << std::endl;
  Zigzag_persistence zp;
  // It is important that the operations of insertions and removals are made **in the same order** as in the zigzag
  // filtration ones wants to compute the barcode from.
  // A cell can be identified in the boundaries by any given numerical label, it is just important that the given
  // filtration values are monotonous (ie., either only increasing or only decreasing).
  // inserts vertex 2 at filtration value 0.1 -> birth at 0.1 of 0-cycle
  zp.insert_cell(2, {}, 0, 0.1);
  // inserts vertex 4 at filtration value 0.1 -> birth at 0.1 of 0-cycle
  zp.insert_cell(4, {}, 0, 0.1);
  // inserts edge 5 = (2,4) at filtration value 0.3 -> death at 0.3 -> stores (0, 0.1, 0.3)
  zp.insert_cell(5, {2, 4}, 1, 0.3);
  // inserts vertex 3 at filtration value 0.4 -> birth at 0.4 of 0-cycle
  zp.insert_cell(3, {}, 0, 0.4);
  // inserts edge 6 = (2,3) at filtration value 0.4 -> death at 0.4 of the cycle born at 0.4 -> stores nothing
  zp.insert_cell(6, {2, 3}, 1, 0.4);
  // inserts edge 9 = (3,4) at filtration value 1.2 -> birth at 1.2 of 1-cycle
  zp.insert_cell(9, {4, 3}, 1, 1.2);
  // removes edge 6 at filtration value 1.5 -> death at 1.5 -> stores (1, 1.2, 1.5)
  zp.remove_cell(6, 1.5);
  // removes edge 5 at filtration value 2.0 -> birth at 2.0 of 0-cycle
  zp.remove_cell(5, 2.0);
  // The bars are stored within the class and where not output at all for now.
  // get all bars in a vector
  auto barcode = zp.get_persistence_diagram();
  // do something with the vector, e.g., stream out content:
  for (auto& bar : barcode) {
  std::cout << bar << std::endl;
  }
  return 0;
  Gudhi::zigzag_persistence::Filtered_zigzag_persistence_with_storage
  Class computing the zigzag persistent homology of a zigzag filtration. Algorithm based on zigzag....
  Definition filtered_zigzag_persistence.h:121
  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::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
  }

## More elaborate examples

- Zigzag_persistence/example_zigzag_filtration_as_input_loop.cpp - A simple example to showcase how to use the Filtered_zigzag_persistence_with_storage class within an input loop.
- Zigzag_persistence/example_zzfiltration_from_file.cpp - An example of a "stream-like" usage with Filtered_zigzag_persistence by reading off the filtration from a file.