#include <CGAL/HDVF/Hdvf_persistence.h>

Inherits from

CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >.

Definition

template<typename ChainComplex, typename Degree, typename Filtration_>
class CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >

The class Hdvf_persistence computes persistent homology using HDVFs (over a ring of coefficients which should actually be a field).

Hence, unlike other persistence algorithms, beside standard persistent intervals informations (birth/death indices, degrees, associated cells), Hdvf_persistence also provides homology and cohomology generators for persistent pairs. Intuitively, holes die when they are "filled" by a cell: associated homology and cohomology generators provide a representation of the hole and of the cells filling the hole.

Given a Filtration, the Hdvf_persistence constructor basically builds a HDVF where indices of cells in the bases follow the filtration order (permutations between initial indices of cells in the chain complex and new indices given by the filtration are stored). Besides, Hdvf_persistence derives from Hdvf_core with the SparseMatrix parameter type set to OSM::Sub_sparse_matrix. Hence, Hdvf_persistence computes homology over a larger and larger sub-complex of K (encoded through a Bitboard mask of OSM::Sub_sparse_matrix) following the filtration f. At each step of the filtration, the new cell is paired (A operation) with the youngest cell valid for A.

A few words about persistent generators. At a given time \(t_2\) along the filtration, let us denote by \(\tau\) the \(q+1\)-cell inserted and let us assume that persistent homology computation pairs \(A(\sigma, \tau)\) (let \(t_1\) be the index of \(\sigma\) along the filtration). A new persistent interval \((t_1, t_2)\)is created, generated by \(\sigma\) and filled by \(\tau\). Reduction at time \(t_2-1\) (just before the insertion of \(\tau\)) provides persistent generators: \(g(\sigma)\) is a cycle and \(g(\tau)\) is a chain "filling" this cycle (before the pairing \(A(\sigma, \tau)\), the HDVF over \(K_{t_2}\) is not perfect, thus \(g(\tau)\) is not a cycle but a chain bounded by \(q\)-cycles).

Next figures illustrate such informations for a filtration of a dented double torus.

Filtration Filtration_lower_star along the z axis of a dented double torus.

The first persistent hole is a dimension 1 hole with a duration of 0.359 along z.

(Left) the complex at time 622 along the filtration (in blue, the 2-cell \(\tau\) added at time 623). This 1-homology of this complex contains two cycles depicted in white and yellow respectively. Yellow curve: a 1-cycle born at time 319 (with cell \(\sigma\)) along the filtration. White curve: the second 1-cycle of this complex (born at time 156 along the filtration).
(Middle) the filtration adds the (blue) 2-cell \(\tau\) at time 623: this cell fills one the 1-cycles (actually the "youngest" cycle, thus the yellow one). Middle image illustrates as a yellow patch the "filling 2-chain", a chain a 2-cells filling the hole when the cell \(\tau\) is added. As stated earlier, this filling chain is not a cycle and it equals \(g(\tau)\) in the (non perfect) reduction before the pairing A(319, 623) between \(\sigma\) and \(\tau\). Middle figure illustrates that in the (non perfect) HDVF before A operation, \(g(\tau)\) is not a cycle but a chain bounded by \(q\)-cycles.
(Right) the complex after insertion of \(\tau\) and the pairing A(319, 623) between \(\sigma\) and \(\tau\). Only the white 1-cycle remains (actually its persistent lifetime is infinite).

The figure above illustrates next persistent hole (dimension 0 hole) which duration is 0.684 along z. The cell \(\tau\) is added at time 1237 and fills the 0-hole (connected component) introduced at time 756 by the cell \(\sigma\). The persistent generator associated to \(\sigma\) is simply the cell itself identifying its connected component. The persistent generator associated to \(\tau\) is a 1-chain (depicted in yellow) connecting \(\sigma\) to the critical cell identifying the second connected component.

Figures above illustrate next finite persistent intervals and (right) infinite dimension 1 persistent intervals.

Is model of: HDVF

Template Parameters

ChainComplex	a model of the `AbstractChainComplex` concept, providing the type of abstract chain complex used (the underlying ring of coefficients must be a model of `Field`).
Degree	a scalar data type used for the degrees of the filtration (a model of `RealEmbeddable` concept).
Filtration_	a model of the `Filtration` concept, providing the filtration used to compute persistence.

Classes
struct	iterator
	Iterator over (finite) persistent intervals. More...

struct	Persistence_interval
	Structure storing (full) persistent interval data: More...

struct	Persistent_hole
	Hole information returned by the persistent diagram iterator. More...

Public Types
typedef ChainComplex	Chain_complex
	Chain complex type.

typedef Chain_complex::Coefficient_ring	Coefficient_ring
	Type of coefficients used to compute homology.

typedef CGAL::OSM::Sparse_chain< Coefficient_ring, CGAL::OSM::COLUMN >	Column_chain
	Type of column-major chains.

typedef CGAL::OSM::Sparse_chain< Coefficient_ring, CGAL::OSM::ROW >	Row_chain
	Type of row-major chains.

typedef CGAL::OSM::Sub_sparse_matrix< Coefficient_ring, CGAL::OSM::COLUMN >	Column_matrix
	Type of column-major sparse matrices.

typedef CGAL::OSM::Sub_sparse_matrix< Coefficient_ring, CGAL::OSM::ROW >	Row_matrix
	Type of row-major sparse matrices.

typedef Hdvf_core< ChainComplex, CGAL::OSM::Sparse_chain, CGAL::OSM::Sub_sparse_matrix >	Base
	Type of parent HDVF class (`Hdvf_core` with appropriate template parameters) The `SparseMatrix` model is set to `Sub_sparse_matrix` to activate (co)homology computation over a subcomplex.

typedef Filtration_	Filtration
	Type of filtrations used to compute persistence.

Public Types inherited from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >
typedef ChainComplex::Coefficient_ring	Coefficient_ring
	Type of coefficients used to compute homology.

typedef OSM::Sparse_chain< Coefficient_ring, CGAL::OSM::COLUMN >	Column_chain
	Type of column-major chains.

typedef OSM::Sparse_chain< Coefficient_ring, CGAL::OSM::ROW >	Row_chain
	Type of row-major chains.

typedef OSM::Sub_sparse_matrix< Coefficient_ring, CGAL::OSM::COLUMN >	Column_matrix
	Type of column-major sparse matrices.

typedef OSM::Sub_sparse_matrix< Coefficient_ring, CGAL::OSM::ROW >	Row_matrix
	Type of row-major sparse matrices.

Public Member Functions
	Hdvf_persistence (const Chain_complex &K, const Filtration &f, int hdvf_opt=OPT_BND, bool with_export=false)
	Hdvf_persistence default constructor.

std::vector< Cell_pair >	compute_perfect_hdvf (bool verbose=false)
	Computes a perfect persistent HDVF.

bool	with_export ()
	Gets the "with_export" Boolean flag.

const Filtration &	filtration ()
	Get a constant reference on the filtration.

std::ostream &	print_hdvf_persistence_info (std::ostream &out)
	Prints informations related to the filtration.

std::vector< std::vector< int > >	psc_labels () const
	Exports primary/secondary/critical labels (e.g. for vtk export).

Column_chain	homology_chain (size_t cell_index, int q) const
	Exports homology generators associated to `cell_index` (critical cell) of dimension `q` (e.g. for vtk export).

Column_chain	cohomology_chain (size_t cell_index, int q) const
	Exports cohomology generators associated to `cell` (critical cell) of dimension `q` (used by vtk export).

iterator	begin (bool discard_small=true)
	Iterator to the beginning of persistent intervals.

iterator	end ()
	Iterator past-the-end of the chain indices.

Public Member Functions inherited from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >
	Hdvf_core (const ChainComplex &K, int hdvf_opt=OPT_FULL)
	Default constructor.

	Hdvf_core (const Hdvf_core &hdvf)

	~Hdvf_core ()

virtual Cell_pair	find_pair_A (int q, bool &found) const
	Finds a valid Cell_pair of dimension q / q+1 for A.

virtual Cell_pair	find_pair_A (int q, bool &found, size_t gamma) const
	Finds a valid Cell_pair for A containing `gamma` (a cell of dimension `q`)

virtual std::vector< Cell_pair >	find_pairs_A (int q, bool &found) const
	Finds all valid Cell_pair of dimension q / q+1 for A.

virtual std::vector< Cell_pair >	find_pairs_A (int q, bool &found, size_t gamma) const
	Finds all valid Cell_pair for A containing `gamma` (a cell of dimension `q`)

void	A (size_t gamma1, size_t gamma2, int q)
	A operation: pairs critical cells.

std::vector< Cell_pair >	compute_perfect_hdvf (bool verbose=false)
	Computes a perfect HDVF.

std::vector< Cell_pair >	compute_rand_perfect_hdvf (bool verbose=false)
	Computes a random perfect HDVF.

bool	is_perfect_hdvf ()
	Tests if a HDVF is perfect.

virtual std::vector< std::vector< size_t > >	psc_flags (PSC_flag flag) const
	Gets cells with a given `PSC_flag` in any dimension.

virtual std::vector< size_t >	psc_flags (PSC_flag flag, int q) const
	Gets cells with a given `PSC_flag` in dimension `q`.

PSC_flag	psc_flag (int q, size_t tau) const
	Gets the PSC_flag of the cell `tau` in dimension `q`.

int	hdvf_opts () const
	Gets HDVF computation option.

const Row_matrix &	matrix_f (int q) const
	Gets the row-major matrix of \(f\) (from the reduction associated to the HDVF).

const Column_matrix &	matrix_g (int q) const
	Gets the column-major matrix of \(g\) (from the reduction associated to the HDVF).

const Column_matrix &	matrix_h (int q) const
	Gets the column-major matrix of \(h\) (from the reduction associated to the HDVF).

const Column_matrix &	matrix_dd (int q) const
	Gets the column-major matrix of \(\partial'\), reduced boundary operator (from the reduction associated to the HDVF).

std::ostream &	write_matrices (std::ostream &out=std::cout) const
	Prints the matrices of the reduction.

std::ostream &	write_reduction (std::ostream &out=std::cout) const
	Writes the homology and cohomology reduction information.

virtual std::vector< std::vector< int > >	psc_labels () const
	Exports primary/secondary/critical labels (in particular for vtk export)

virtual Column_chain	homology_chain (size_t cell_index, int q) const
	Gets homology generators associated to `cell` (critical cell) of dimension `q` (used by vtk export).

virtual Column_chain	cohomology_chain (size_t cell_index, int dim) const
	Gets cohomology generators associated to `cell_index` (critical cell) of dimension `q` (used by vtk export).

std::ostream &	write_hdvf_reduction (std::ostream &out)
	Writes a HDVF together with the associated reduction (f, g, h, d matrices)

void	write_hdvf_reduction (std::string filename)
	Writes a HDVF together with the associated reduction to a file (f, g, h, d matrices).

std::istream &	read_hdvf_reduction (std::istream &in_stream)
	Loads a HDVF together with the associated reduction (f, g, h, d matrices)

void	read_hdvf_reduction (std::string filename)
	Loads a HDVF together with the associated reduction from a file (f, g, h, d matrices)

bool	compare (const Hdvf_core &other, bool full_compare=false)
	Compares the HDVF with another HDVF over the same underlying complex.

bool	operator== (const Hdvf_core &other)
	Comparison operator.

Protected Attributes
const Filtration &	_f

std::vector< std::vector< size_t > >	_K_to_per

std::vector< std::vector< size_t > >	_per_to_K

std::vector< Persistence_interval >	_persist

bool	_with_export

std::vector< std::vector< std::vector< int > > >	_export_labels

std::vector< std::pair< Column_chain, Column_chain > >	_export_g

std::vector< std::pair< Column_chain, Column_chain > >	_export_fstar

size_t	_t

std::vector< size_t >	_t_dim

std::vector< OSM::Bitboard >	_masks

Protected Attributes inherited from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >
std::vector< std::vector< PSC_flag > >	_flag

std::vector< size_t >	_nb_P

std::vector< size_t >	_nb_S

std::vector< size_t >	_nb_C

std::vector< Row_matrix >	_F_row

std::vector< Column_matrix >	_G_col

std::vector< Column_matrix >	_H_col

std::vector< Column_matrix >	_DD_col

const ChainComplex &	_K

int	_hdvf_opt

Friends
std::ostream &	operator<< (std::ostream &out_stream, const Hdvf_persistence &per_hdvf)
	Overload of `operator<<()` for `Hdvf_persistence`.

Additional Inherited Members
Protected Member Functions inherited from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >
OSM::Sparse_chain< Coefficient_ring, StorageFormat >	projection (const OSM::Sparse_chain< Coefficient_ring, StorageFormat > &chain, PSC_flag flag, int q) const

void	progress_bar (size_t i, size_t n)

Constructor & Destructor Documentation

◆ Hdvf_persistence()

template<typename ChainComplex , typename Degree , typename Filtration_ >

CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::Hdvf_persistence	(	const Chain_complex &	K,
		const Filtration &	f,
		int	hdvf_opt = `OPT_BND`,
		bool	with_export = `false`
	)

Hdvf_persistence default constructor.

Builds an "empty" HDVF_persistence (with all cells critical) associated to the chain complex K and the filtration f. By default, the HDVF option is set to OPT_FULL (full reduction computed)

Parameters

K	A chain complex (a model of `AbstractChainComplex`).
f	A filtration (a model of `Filtration`).
hdvf_opt	Option for HDVF computation (`OPT_BND`, `OPT_F`, `OPT_G` or `OPT_FULL`)
with_export	Boolean option to activate or not the export of PSC labels and homology/cohomology generators for of persistent intervals of positive duration. This information is used by vtk exporters.

Member Function Documentation

◆ begin()

template<typename ChainComplex , typename Degree , typename Filtration_ >

iterator CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::begin ( bool discard_small = true )

Iterator to the beginning of persistent intervals.

Parameters

discard_small If true, the iterator visits only persistent intervals of (strictly) positive degree duration. Otherwise, visit all persistent intervals.

Returns: The iterator to the beginning of the chain indices.

◆ cohomology_chain()

template<typename ChainComplex , typename Degree , typename Filtration_ >

Column_chain CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::cohomology_chain	(	size_t	cell_index,
		int	q
	)		const

virtual

Exports cohomology generators associated to cell (critical cell) of dimension q (used by vtk export).

The method exports the chain \(f^\star(\sigma)\) for \(\sigma\) the cell of index cell and dimension q.

Returns: A column-major chain.

Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >.

◆ compute_perfect_hdvf()

template<typename ChainComplex , typename Degree , typename Filtration_ >

std::vector< Cell_pair > CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::compute_perfect_hdvf ( bool verbose = false )

Computes a perfect persistent HDVF.

This method follows the filtration and considers cells one by one. For each of them, it searches the youngest possible cell valid for A (returned by find_pair_A()), and applies the corresponding A() operation. By definition of persistent homology, the IntegralDomainWithoutDivision of coefficients must be a field.

Parameters

verbose If this parameter is true, all intermediate reductions are printed out.

Returns: The vector of all Cell_pair paired with A.

◆ end()

template<typename ChainComplex , typename Degree , typename Filtration_ >

iterator CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::end ( )

Iterator past-the-end of the chain indices.

Returns: The past-the-end iterator of the chain indices.

◆ homology_chain()

template<typename ChainComplex , typename Degree , typename Filtration_ >

Column_chain CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::homology_chain	(	size_t	cell_index,
		int	q
	)		const

virtual

Exports homology generators associated to cell_index (critical cell) of dimension q (e.g. for vtk export).

The method exports the chain \(g(\sigma)\) for \(\sigma\) the cell of index cell_index and dimension q.

Returns: A column-major chain.

Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >.

◆ print_hdvf_persistence_info()

template<typename ChainComplex , typename Degree , typename Filtration_ >

std::ostream & CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::print_hdvf_persistence_info ( std::ostream & out )

Prints informations related to the filtration.

Prints out the filtration and associated permutations (_K_to_per and _per_to_K) between indices of cells in each dimension in the basis of K and indices along the filtration.

Parameters

out	Reference to an output stream.

◆ psc_labels()

template<typename ChainComplex , typename Degree , typename Filtration_ >

std::vector< std::vector< int > > CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::psc_labels ( ) const

virtual

Exports primary/secondary/critical labels (e.g. for vtk export).

The method exports the labels of every cell in each dimension. Encoding used:

PRIMARY: -1
SECONDARY: +1
CRITICAL: 0

Returns: A vector containing, for each dimension, the vector of labels by cell index.

Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex, OSM::Sparse_chain, OSM::Sub_sparse_matrix >.

◆ with_export()

template<typename ChainComplex , typename Degree , typename Filtration_ >

bool CGAL::Homological_discrete_vector_field::Hdvf_persistence< ChainComplex, Degree, Filtration_ >::with_export ( )

Gets the "with_export" Boolean flag.

If the flag is true, homology/cohomology generators and corresponding PSC labels are exported for each persistent interval of positive duration.

Friends And Related Function Documentation

◆ operator<<

template<typename ChainComplex , typename Degree , typename Filtration_ >

std::ostream & operator<<	(	std::ostream &	out_stream,
		const Hdvf_persistence< ChainComplex, Degree, Filtration_ > &	per_hdvf
	)

friend

Overload of operator<<() for Hdvf_persistence.

Prints out finite and infinite persistence intervals.

Parameters

out_stream	Reference to an output stream.
per_hdvf	Constant reference on the `Hdvf_persistence` to print.

Inherits from

Definition

Classes

Public Types

Public Member Functions

Protected Attributes

Friends

Additional Inherited Members

Constructor & Destructor Documentation

◆ Hdvf_persistence()

Member Function Documentation

◆ begin()

◆ cohomology_chain()

◆ compute_perfect_hdvf()

◆ end()

◆ homology_chain()

◆ print_hdvf_persistence_info()

◆ psc_labels()

◆ with_export()

Friends And Related Function Documentation

◆ operator<<