|
CGAL 6.3-dev - Homological Discrete Vector Fields
|
The concept HDVF describes the requirements for Homological Discrete Vector Fields (HDVF for short) , a theory of computational homology unifying discrete Morse theory and effective homology. HDVFs were introduced by Aldo Gonzalez-Lorenzo in his PhD (see [AGL,2017], [AGL,2016]).
A HDVF is a combinatorial tool computing the homology of a chain complex (described by the AbstractChainComplex concept) including "geometric" information such as homology and cohomology generators.
In order to build a perfect HDVF, a pairing operation called A() associates (under conditions) two critical cells (becoming PRIMARY and SECONDARY) and updates the reduction in time \(\mathscr O(n^2)\). Intuitively, this operation bears some similitudes with discrete Morse theory's DGVF arrows (see introduction to discrete Morse theory in user manual). Actually, an HDVF can always be represented by a vector field - possibly with cycles. The validity condition for A is tested by various find_pair_A() and find_pairs_A() methods, which search for such valid pairs.
Starting from this operation, HDVF provides two methods to generate perfect HDVFs (and hence compute homology):
For efficiency, the HDVF reduction can be computed partially and we define constants to define the HDVF computation option required:
[AGL, 2017] Aldo Gonzalez-Lorenzo, Alexandra Bac, Jean-Luc Mari, Pedro Real. Allowing cycles in discrete Morse theory, Topology and its Applications, Volume 228, 2017, Pages 1-35.
[AGL, 2016] Aldo Gonzalez-Lorenzo. Computational Homology Applied to Discrete Objects. Discrete Mathematics [cs.DM]. Aix-Marseille Université; Universidad de Sevilla, 2016.
Concepts | |
| struct | Cell_pair |
| Structure to represent data for HDVF operations (between pairs of cells). More... | |
Constants | |
| enum | PSC_flag |
| HDVF Enum for the label of cells. More... | |
| const int | OPT_BND = 0b0001 |
| HDVF computation option: compute only the reduced boundary. | |
| const int | OPT_F = 0b0010 |
| HDVF computation option: compute only the reduced boundary and \(f\). | |
| const int | OPT_G = 0b0100 |
| HDVF computation option: compute only the reduced boundary and \(g\). | |
| const int | OPT_FULL = 0b1000 |
| HDVF computation option: compute the full reduction. | |
Types | |
| typedef unspecified_type | Complex |
| Type of underlying chain complex (a model of AbstractChainComplex). | |
| typedef Complex::Coefficient_ring | Coefficient_ring |
| Type of coefficients used to compute homology (a model of IntegralDomainWithoutDivision). | |
| typedef unspecified_type | Sparse_chain |
| Type of sparse chains (a model of SparseChain). | |
| typedef unspecified_type | Sparse_matrix |
| Type of sparse matrices (a model of SparseMatrix). | |
| typedef Sparse_chain< CoefficientType, CGAL::OSM::COLUMN > | Column_chain |
| Type of column-major chains. | |
| typedef Sparse_chain< CoefficientType, CGAL::OSM::ROW > | Row_chain |
| Type of row-major chains. | |
| typedef Sparse_matrix< CoefficientType, CGAL::OSM::COLUMN, Sparse_chain > | Column_matrix |
| Type of column-major sparse matrices. | |
| typedef Sparse_matrix< CoefficientType, CGAL::OSM::ROW, Sparse_chain > | Row_matrix |
| Type of row-major sparse matrices. | |
Functions to find valid pairs for A() operations | |
| 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, size_t gamma, bool &found) 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, size_t gamma, bool &found) const |
| Finds all valid Cell_pair for A containing gamma (a cell of dimension q). | |
| bool | is_valid_pair_for_A (size_t gamma, size_t gamma_prime, int q) |
| Checks if the pair of cells \((\gamma, \gamma')\), of dimensions q / q+1, is valid for A. | |
HDVF functions and operations | |
| void | A (size_t gamma1, size_t gamma2, int q) |
| A operation: pairs critical cells. | |
| void | A (const Cell_pair &p) |
| 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. | |
| bool | operator== (const Hdvf_core &other) |
| Comparison operator (with a HDVF over the same underlying complex). | |
| bool | compare (const Hdvf_core &other, bool full_compare=false) const |
| Compares the HDVF with another HDVF over the same underlying complex. | |
Getters | |
| std::vector< std::vector< size_t > > | psc_flag (PSC_flag flag) const |
| Gets cells with a given PSC_flag in any dimension. | |
| std::vector< size_t > | psc_flag (PSC_flag flag, int q) const |
| Gets cells with a given PSC_flag in dimension q. | |
| PSC_flag | psc_flag (size_t tau, int q) const |
| Gets the PSC_flag of the cell tau in dimension q. | |
| virtual const std::vector< PSC_flag > & | psc_flags (int q) const |
| Gets thePSC_flag of all cells in dimension q. | |
| virtual const std::vector< std::vector< PSC_flag > > & | psc_flags () const |
| Gets thePSC_flag of all cells. | |
| size_t | number_of_cells_by_flag (PSC_flag flag, int q) |
| Returns the number of cells with a given flag in dimension q. | |
| int | hdvf_opts () |
| Gets HDVF 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). | |
| const Chain_complex & | complex () const |
| Gets a constant reference over the underlying chain complex. | |
| Column_chain | homology_chain (size_t cell_index, int q) const |
| Returns a chain containing the homology generator associated to cell_index (critical cell) of dimension q. | |
| virtual Column_chain | cohomology_chain (size_t cell_index, int dim, bool co_faces=false) const |
| Returns a chain containing the cohomology generators associated to cell_index (critical cell) of dimension q. | |
Dimension restriction functions | |
| int | dimension_restriction () const |
| Returns the dimension of the Hdvf computation. | |
| void | dimension_restriction (int dimension) |
| Changes the dimension of Hdvf computation. | |
Input, output | |
| std::ostream & | write_matrices (std::ostream &out=std::cout, int dimension_restriction=-2) const |
| Writes the matrices of the reduction. | |
| std::ostream & | write_reduction (std::ostream &out=std::cout, int dimension_restriction=-2) const |
| Writes the homology and cohomology reduction information. | |
| std::ostream & | write_flags (std::ostream &out=std::cout, int dimension_restriction=-2) const |
| Writes the PSC flags of cells along computed dimensions. | |
| std::ostream & | write_hdvf_reduction (std::ostream &out) const |
| Writes a HDVF together with the associated reduction (f, g, h, d matrices). | |
| void | write_hdvf_reduction (std::string filename) const |
| 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) |
| Reads a HDVF together with the associated reduction (f, g, h, d matrices). | |
| void | read_hdvf_reduction (std::string filename) |
| Reads a HDVF together with the associated reduction from a file (f, g, h, d matrices). | |
| std::vector< std::vector< int > > | psc_labels () const |
| Exports an integer code for cells labels (in particular for vtk export). | |
| enum HDVF::PSC_flag |
HDVF Enum for the label of cells.
Values can be PRIMARY, SECONDARY, CRITICAL or NONE (for discarded cells in persistent homology or duality).
| void HDVF::A | ( | const Cell_pair & | p | ) |
A operation (pairs critical cells).
A pair of critical cells \((\gamma_1, \gamma_2)\) of respective dimension q and q+1 is valid for A if \(\langle \partial_{q+1}(\gamma_2), \gamma_1 \rangle\) is invertible. After the A() operation, \(\gamma_1\) becomes PRIMARY, \(\gamma_2\) becomes SECONDARY. The A method updates the reduction accordingly (in time \(\mathcal O(n^2)\)).
| p | Argument Cell_pair containing \(\gamma_1\), \(\gamma_2\) and the dimension of the pair. |
| void HDVF::A | ( | size_t | gamma1, |
| size_t | gamma2, | ||
| int | q ) |
A operation: pairs critical cells.
A pair of critical cells \((\gamma_1, \gamma_2)\) of respective dimension q and q+1 is valid for A if \(\langle \partial_{q+1}(\gamma_2), \gamma_1 \rangle\) is invertible. After the A() operation, \(\gamma_1\) becomes PRIMARY, \(\gamma_2\) becomes SECONDARY. The A method updates the reduction accordingly (in time \(\mathcal O(n^2)\)).
| gamma1 | First cell of the pair (dimension q) |
| gamma2 | Second cell of the pair (dimension q+1) |
| q | Dimension of the pair |
|
virtual |
Returns a chain containing the cohomology generators associated to cell_index (critical cell) of dimension q.
The method exports:
The complexity is in the number of (non zero) coefficients of the generator.
Below, a sample mesh with, (left) homology generators, (right) two examples of cohomology generators (corresponding generators/co-generators bear similar colours):

The same generators displayed through their co-faces:

All homology / cohomology generators:

| bool HDVF::compare | ( | const Hdvf_core & | other, |
| bool | full_compare = false ) const |
| std::vector< Cell_pair > HDVF::compute_perfect_hdvf | ( | bool | verbose = false | ) |
Computes a perfect HDVF.
As long as valid pairs for A exist, the function selects the first available pair (returned by find_pair_A()) and applies the corresponding A() operation. If the IntegralDomainWithoutDivision of coefficients is a field, this operation always produces a perfect HDVF (ie. the reduced boundary is null and the reduction provides homology and cohomology information). Otherwise the operation produces a maximal HDVF with a residual boundary matrix over critical cells.
If the HDVF is initially not trivial (some cells have already been paired), the function completes it into a perfect HDVF.
| verbose | If this parameter is true, all intermediate reductions are printed out. |
| std::vector< Cell_pair > HDVF::compute_rand_perfect_hdvf | ( | bool | verbose = false | ) |
Computes a random perfect HDVF.
As long as valid pairs for A exist, the function selects a random pair (among pairs returned by find_pairs_A()) and applies the corresponding A() operation. If the IntegralDomainWithoutDivision of coefficients is a field, this operation always produces a perfect HDVF (that is the reduced boundary is null and the reduction provides homology and cohomology information).
If the HDVF is initially not trivial (some cells have already been paired), the function randomly completes it into a perfect HDVF.
| verbose | If this parameter is true, all intermediate reductions are printed out. |
| int HDVF::dimension_restriction | ( | ) | const |
| void HDVF::dimension_restriction | ( | int | dimension | ) |
Changes the dimension of Hdvf computation.
| dimension | Dimension along which the computation is restricted. Set -1 for full computation (computation of homology in any dimension), and a positive value lower than the complex dimension for a computation restricted to dimension dimension. |
|
virtual |
Finds a valid Cell_pair of dimension q / q+1 for A.
The function searches a pair of critical cells \((\gamma_1, \gamma2)\) of dimension q / q+1, valid for A (ie. such that \(\langle \partial_{q+1}(\gamma_2), \gamma_1 \rangle\) invertible). It returns the first valid pair found by iterators.
If the dimension is incorrect (negative or larger than the dimension of the underlying complex), found is set to false.
| q | Lower dimension of the pair. |
| found | Reference to a Boolean variable. The method sets found to true if a valid pair is found, false otherwise. |
|
virtual |
Finds a valid Cell_pair for A containing gamma (a cell of dimension q).
The function searches a cell \(\gamma'\) such that one of the following conditions holds:
If the dimension is incorrect (negative or larger than the dimension of the underlying complex), found is set to false. If the cell index is incorrect (larger than the number of cells in the dimension), found is set to false.
| q | Dimension of the cell gamma. |
| gamma | Index of a cell to pair. |
| found | Reference to a Boolean variable. The method sets found to true if a valid pair is found, false otherwise. |
|
virtual |
Finds all valid Cell_pair of dimension q / q+1 for A.
The function searches all pairs of critical cells \((\gamma_1, \gamma2)\) of dimension q / q+1, valid for A (ie. such that \(\langle \partial_{q+1}(\gamma_2), \gamma_1 \rangle\) invertible). It returns a vector of such pairs.
If the dimension is incorrect (negative or larger than the dimension of the underlying complex), found is set to false and the function returns an empty vector.
| q | Lower dimension of the pair. |
| found | Reference to a Boolean variable. The method sets found to true if a valid pair is found, false otherwise. |
|
virtual |
Finds all valid Cell_pair for A containing gamma (a cell of dimension q).
The function searches all CRITICAL cells \(\gamma'\) such that one of the following conditions holds:
If the dimension is incorrect (negative or larger than the dimension of the underlying complex), found is set to false. If the cell index is incorrect (larger than the number of cells in the dimension), found is set to false. In both cases, the function returns an empty vector.
| q | Dimension of the cell gamma. |
| gamma | Index of a cell to pair. |
| found | Reference to a Boolean variable. The method sets found to true if a valid pair is found, false otherwise. |
| Column_chain HDVF::homology_chain | ( | size_t | cell_index, |
| int | q ) const |
Returns a chain containing the homology generator associated to cell_index (critical cell) of dimension q.
The method exports the chain \(g(\sigma)\) for \(\sigma\) the cell of index cell_index and dimension q.
The complexity is in the number of (non zero) coefficients of the generator.
| bool HDVF::is_perfect_hdvf | ( | ) |
Tests if a HDVF is perfect.
The function returns true if the reduced boundary matrix is null and false otherwise.
| bool HDVF::is_valid_pair_for_A | ( | size_t | gamma, |
| size_t | gamma_prime, | ||
| int | q ) |
Checks if the pair of cells \((\gamma, \gamma')\), of dimensions q / q+1, is valid for A.
The pair is valid if \(\langle \mathrm d(\gamma),\gamma' \rangle\) is invertible.
| size_t HDVF::number_of_cells_by_flag | ( | PSC_flag | flag, |
| int | q ) |
Returns the number of cells with a given flag in dimension q.
| flag | PSC_flag tested. |
| q | Dimension along which the number of cells is returned. |
| bool HDVF::operator== | ( | const Hdvf_core & | other | ) |
| std::vector< std::vector< size_t > > HDVF::psc_flag | ( | PSC_flag | flag | ) | const |
| std::vector< size_t > HDVF::psc_flag | ( | PSC_flag | flag, |
| int | q ) const |
| PSC_flag HDVF::psc_flag | ( | size_t | tau, |
| int | q ) const |
|
virtual |
|
virtual |
| std::vector< std::vector< int > > HDVF::psc_labels | ( | ) | const |
Exports an integer code for cells labels (in particular for vtk export).
The method exports integers encoding cells labels for every cell in each dimension. Labels are encoded as follows:
| std::istream & HDVF::read_hdvf_reduction | ( | std::istream & | in_stream | ) |
Reads a HDVF together with the associated reduction (f, g, h, d matrices).
Loads a HDVF and its reduction from a stream in hdvf file format, a simple text file format (see HDVF_file_format "user manual" for a specification).
| in_stream | Input stream. |
| Incompatible_prefix | If the prefix of the stored HDVF is not 'HDVF_core' raises a `std::runtime_error`. |
| Incompatible_type | If the type of the stored HDVF is not 0 (HDVF and reduction storage) raises a `std::runtime_error`. |
| Incompatible_dimension | If the dimension of the HDVF stored does not match the dimension of the underlying complex, raises a `std::runtime_error`. |
| Incoherent_number_of_cells | If the number of cells loaded in a given dimension does not match that of the underlying complex, raises a `std::runtime_error`. |
| void HDVF::read_hdvf_reduction | ( | std::string | filename | ) |
Reads a HDVF together with the associated reduction from a file (f, g, h, d matrices).
Loads a HDVF and its reduction from a file in hdvf file format, a simple text file format (see HDVF_file_format "user manual" for a specification).
| filename | Input file name. |
| File_not_found | If the file `filename` cannot be opened, raises a `std::runtime_error`. |
| std::ostream & HDVF::write_flags | ( | std::ostream & | out = std::cout, |
| int | dimension_restriction = -2 ) const |
Writes the PSC flags of cells along computed dimensions.
If dimension_restriction is -1, writes flags in any dimensions. If dimension_restriction is positive, restricts output to dimension_restriction. If dimension_restriction is -2 (default value), uses the HDVF dimension restriction value.
| out | Output stream (by default, writes the complex to std::cout). |
| dimension_restriction | If positive, restricts the output to a single dimension, if -1, outputs reductions in any dimensions, if -2 (default value) uses the HDVF dimension restriction value. |
| std::ostream & HDVF::write_hdvf_reduction | ( | std::ostream & | out | ) | const |
| void HDVF::write_hdvf_reduction | ( | std::string | filename | ) | const |
Writes a HDVF together with the associated reduction to a file (f, g, h, d matrices).
Exports a HDVF to a file in hdvf file format (a simple text file format, see HDVF_file_format "user manual" for a specification).
| filename | Output file name. |
| File_not_found | If the file `filename` cannot be opened, raises a `std::runtime_error`. |
| std::ostream & HDVF::write_matrices | ( | std::ostream & | out = std::cout, |
| int | dimension_restriction = -2 ) const |
Writes the matrices of the reduction.
Writes the matrices of the reduction (that is \(f\), \(g\), \(h\), \(\partial'\) the reduced boundary).
If dimension_restriction is -1, writes matrices in any dimensions. If dimension_restriction is positive, restricts output to dimension_restriction. If dimension_restriction is -2 (default value), uses the HDVF dimension restriction value.
| out | Output stream (by default, writes the complex to std::cout). |
| dimension_restriction | If positive, restricts the output to a single dimension, if -1, outputs matrices in any dimensions, if -2 (default value) uses the HDVF dimension restriction value. |
| std::ostream & HDVF::write_reduction | ( | std::ostream & | out = std::cout, |
| int | dimension_restriction = -2 ) const |
Writes the homology and cohomology reduction information.
Writes \(f^*\), \(g\) \(\partial'\) the reduced boundary over each critical cell.
If dimension_restriction is -1, writes the reduction in any dimensions. If dimension_restriction is positive, restricts output to dimension_restriction. If dimension_restriction is -2 (default value), uses the HDVF dimension restriction value.
| out | Output stream (by default, writes the complex to std::cout). |
| dimension_restriction | If positive, restricts the output to a single dimension, if -1, outputs reductions in any dimensions, if -2 (default value) uses the HDVF dimension restriction value. |