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 [41]. 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 [41]. 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 [41]. 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 [41].

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.

  #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;
  }

• 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.

  #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;
  }

• 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.

  #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;
  }

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.