|
CGAL 6.3-dev - Homological Discrete Vector Fields
|
#include <CGAL/HDVF/Hdvf_duality.h>
CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
The class Hdvf_duality is the implementation of homological discrete vector fields (HDVF for short) for Alexander duality computation.
In dimension \(n\), given a complex \(L\) homeomorphic to \(\mathscr S^n\) and a sub-complex \(K\subseteq L\), Alexander duality states that for all \(q\leqslant n\):
\[\overset{\thicksim}{H}_q(K) \simeq \overset{\thicksim}{H}^{n-q-1}(L-K)\]
where \(\overset{\thicksim}{H}_q\) and \(\overset{\thicksim}{H}^q\) denote reduced homology and cohomology groups.
Combinatorial Alexander duality (see user manual and [Gonzalez and al. 2025]) is actually based on the following isomorphism for the co-complex \(L-K\), for all \(q\leqslant n\):
\[\overset{\thicksim}{H}_q(K) \simeq \overset{\thicksim}{H}^{q+1}(L-K)\]
HDVFs provide a fast and convenient mean to compute this isomorphism. In this context, the complex \(L\) must be homeomorphic to a ball of dimension \(n\) (thus \(\mathscr S^n\) is actually homeomorphic to \(L\) plus an infinite \(n\)-cell closing its boundary).
Perfect HDVFs are first computed over \(K\) and \(L-K\) (providing corresponding relative homology) respectively and Alexander isomorphism gives rise to a pairing between critical cells in \(K\) and \(L-K\), that is a pairing between homology/cohomology generators in \(K\) and \(L-K\).
In order to compute relative homology, a sub chain complex mask is used to partially screen the complex L and thus restrict HDVF computation. This mask is called "current mask" (and can be set over K or L-K) and the corresponding sub chain complex is called the "current sub chain complex".
The class provides HDVF constuction operations: compute_perfect_hdvf() and compute_rand_perfect_hdvf(), which build perfect HDVFs over \(K\) and \(L-K\) respectively (actually, the package computes relative homology). Then, compute_alexander_pairing() computes Alexander isomorphism (and provides a pairing between homology/cohomology generators in \(K\) and \(L-K\)).
HDVF | ChainComplex | a model of the AbstractChainComplex concept, providing the type of abstract chain complex used. The sparse matrix structure provided by ChainComplex must be an instance of the Sub_sparse_matrix_structure template. |
[Gonzalez and al. 2025] Gonzalez-Lorenzo, A., Bac, A. & Gazull, YS. A constructive approach of Alexander duality. J Appl. and Comput. Topology 9, 2 (2025).
Public Types | |
| typedef ChainComplex | Chain_complex |
| Chain complex type. | |
| typedef Chain_complex::Coefficient_ring | Coefficient_ring |
| Type of coefficients used to compute homology. | |
| typedef Hdvf_core< ChainComplex > | Base |
| Type of parent Hdvf_core class. | |
| Public Types inherited from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex > | |
| typedef ChainComplex | Chain_complex |
| Type of the underlying chain complex. | |
| typedef ChainComplex::Coefficient_ring | Coefficient_ring |
| Type of coefficients used to compute homology. | |
| typedef ChainComplex::Sparse_matrix_structure | Sparse_matrix_structure |
| Type of sparse matrix structure used to compute homology. | |
| template<typename CR, int SF> | |
| using | Sparse_chain_base = typename Sparse_matrix_structure::template Sparse_chain_type<CR, SF> |
| Template type of underlying sparse chains. | |
| template<typename CR, int SF> | |
| using | Sparse_matrix_base = typename Sparse_matrix_structure::template Sparse_matrix_type<CR, SF> |
| Template type of underlying sparse matrices. | |
| typedef Sparse_chain_base< Coefficient_ring, CGAL::OSM::COLUMN > | Column_chain |
| Type of column-major chains. | |
| typedef Sparse_chain_base< Coefficient_ring, CGAL::OSM::ROW > | Row_chain |
| Type of row-major chains. | |
| typedef Sparse_matrix_base< Coefficient_ring, CGAL::OSM::COLUMN > | Column_matrix |
| Type of column-major sparse matrices. | |
| typedef Sparse_matrix_base< Coefficient_ring, CGAL::OSM::ROW > | Row_matrix |
| Type of row-major sparse matrices. | |
Public Member Functions | |
| Hdvf_duality (const Chain_complex &L, Sub_chain_complex_mask< Chain_complex > &K, int hdvf_opt=OPT_FULL) | |
| Hdvf_duality constructor ( from a complex L and a sub-complex K). | |
| Cell_pair | find_pair_A (int q, bool &found) const |
| Finds a valid cell pair of dimension q / q+1 for A in the current sub chain complex. | |
| Cell_pair | find_pair_A (int q, size_t gamma, bool &found) const |
| Finds a valid cell pair for A containing gamma in the current sub chain complex (a cell of dimension q). | |
| std::vector< Cell_pair > | find_pairs_A (int q, bool &found) const |
| Finds all valid cell pairs of dimension q / q+1 in the current sub chain complex for A. | |
| std::vector< Cell_pair > | find_pairs_A (int q, size_t gamma, bool &found) const |
| Finds all valid cell pairs for Acontaining gamma in the current sub chain complex (a cell of dimension q). | |
| void | set_mask_K () |
| Sets the current sub chain complex masks over K. | |
| void | set_mask_L_K () |
| Sets the current sub chain complex masks over L-K. | |
| Sub_chain_complex_mask< ChainComplex > | get_current_mask () const |
| Returns the value of the current sub chain complex mask. | |
| std::vector< Cell_pair > | compute_perfect_hdvf (bool verbose=false) |
| Computes a perfect HDVF over the current sub chain complex. | |
| std::vector< Cell_pair > | compute_rand_perfect_hdvf (bool verbose=false) |
| Computes a random perfect HDVF over the current sub chain complex. | |
| bool | is_perfect_hdvf (int dimension_restriction=-2) |
| Tests if HDVFs over K and L-K are perfect. | |
| std::vector< Cell_pair > | compute_pairing_hdvf () |
| Computes a "pairing" HDVF between K and L-K. | |
| std::vector< Cell_pair > | compute_rand_pairing_hdvf () |
| Computes a random "pairing" HDVF between K and L-K. | |
| std::vector< std::vector< size_t > > | psc_flag (PSC_flag flag) const |
| Gets cells with a given PSC_flag in any dimension in the current sub chain complex. | |
| std::vector< size_t > | psc_flag (PSC_flag flag, int q) const |
| Gets cells with a given PSC_flag in dimension q in the current sub chain complex. | |
| std::ostream & | write_reduction (std::ostream &out=std::cout) |
| Prints the homology and cohomology reduction information for K and L-K. | |
| std::ostream & | write_reduction_sub (std::ostream &out=std::cout) |
| Prints the homology and cohomology reduction information for the current sub chain complex. | |
| std::ostream & | print_bnd_pairing (std::ostream &out=std::cout) |
| Prints the reduced boundary over critical cells of K and L-K. | |
| std::vector< std::vector< int > > | psc_labels () const |
| Exports primary/secondary/critical labels of the current sub chain complex for vtk export. | |
| Column_chain | homology_chain (size_t cell_index, int dim) const |
| Exports the homology generator of the current sub chain complex associated to cell_index (critical cell) of dimension q. | |
| Column_chain | cohomology_chain (size_t cell_index, int dim) const |
| Exports the cohomology generator of the current sub chain complex associated to cell_index (critical cell) of dimension q. | |
| Public Member Functions inherited from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex > | |
| Hdvf_core (const ChainComplex &K, int hdvf_opt=OPT_FULL, int dimension_restriction=-1) | |
| Constructor from a chain complex. | |
| Hdvf_core (const Hdvf_core &hdvf) | |
| Copy constructor. | |
| Hdvf_core & | operator= (const Hdvf_core &hdvf) |
| Affectation operator. | |
| Hdvf_core (const ChainComplex &K, const std::vector< std::vector< PSC_flag > > &flags, bool with_build_reduction=false, int hdvf_opt=OPT_FULL, int dimension_restriction=-1) | |
| Constructor from the PRIMARY/SECONDARY/CRITICAL labels. | |
| PSC_flag | psc_flag (size_t tau, int q) const |
| Gets the PSC_flag of the cell tau in dimension q. | |
| CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::Hdvf_duality | ( | const Chain_complex & | L, |
| Sub_chain_complex_mask< Chain_complex > & | K, | ||
| int | hdvf_opt = OPT_FULL ) |
Hdvf_duality constructor ( from a complex L and a sub-complex K).
L is a complex of a given dimension \(n\) homeomorphic to \(\mathcal B^n\) and K is a sub-complex of L described by a bitboard (cells of K have a bit set to 1, cells of K have a bit set to 0).
Initially, the sub chain complex mask is set to K.
| L | A complex of a given dimension \(n\) homeomorphic to \(\mathcal B^n\). |
| K | A sub complex of L encoded through a bitboard. |
| hdvf_opt | Option for HDVF computation (OPT_BND, OPT_F, OPT_G or OPT_FULL). |
| Empty_complex | If the complex `L` is empty, raises a `std::runtime_error`. |
|
virtual |
Exports the cohomology generator of the current sub chain complex associated to cell_index (critical cell) of dimension q.
The method exports the chain \(f^\star(\sigma)\) for \(\sigma\) the cell of index cell_index and dimension q.
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
| std::vector< Cell_pair > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::compute_pairing_hdvf | ( | ) |
Computes a "pairing" HDVF between K and L-K.
The function computes a perfect HDVF over remaining critical cells. Each pair of cells inserted with the A() operation maps corresponding homology/cohomology generators in the Alexander isomorphism.
| Non_perfect_hdvfs | If the HDVFs over `K` and `L-K` are not perfect, raises a `std::runtime_error`. |
| std::vector< Cell_pair > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::compute_perfect_hdvf | ( | bool | verbose = false | ) |
Computes a perfect HDVF over the current sub chain complex.
As long as valid pairs for A exist in the current sub chain complex, the function selects the first available pair (returned by find_pair_A()) and applies the corresponding A() operation. If the coefficient ring 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 > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::compute_rand_pairing_hdvf | ( | ) |
Computes a random "pairing" HDVF between K and L-K.
The function computes a random perfect HDVF over remaining critical cells. Each pair of cells inserted with the A() operation maps corresponding homology/cohomology generators in the Alexander isomorphism.
| Non_perfect_hdvfs | If the HDVFs over `K` and `L-K` are not perfect, raises a `std::runtime_error`. |
| std::vector< Cell_pair > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::compute_rand_perfect_hdvf | ( | bool | verbose = false | ) |
Computes a random perfect HDVF over the current sub chain complex.
As long as valid pairs for A exist in the current sub chain complex, the function selects a random pair (among pairs returned by find_pairs_A()) and applies the corresponding A() operation. If the coefficient ring 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. |
|
virtual |
Finds a valid cell pair of dimension q / q+1 for A in the current sub chain complex.
The function searches a pair of critical cells, in the current sub chain complex, \((\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.
| 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. |
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
|
virtual |
Finds a valid cell pair for A containing gamma in the current sub chain complex (a cell of dimension q).
The function searches a cell \(\gamma'\) in the current sub chain complex such that one of the following conditions holds:
| 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. |
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
|
virtual |
Finds all valid cell pairs of dimension q / q+1 in the current sub chain complex for A.
The function searches all pairs of critical cells \((\gamma_1, \gamma2)\) in the current sub chain complex 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.
| q | Lower dimension of the pairs. |
| found | Reference to a Boolean variable. The method sets found to true if a valid pair is found, false otherwise. |
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
|
virtual |
Finds all valid cell pairs for Acontaining gamma in the current sub chain complex (a cell of dimension q).
The function searches all CRITICAL cells \(\gamma'\) in the current sub chain complex such that one of the following conditions holds:
| 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. |
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
|
virtual |
Exports the homology generator of the current sub chain complex 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.
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
| bool CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::is_perfect_hdvf | ( | int | dimension_restriction = -2 | ) |
Tests if HDVFs over K and L-K are perfect.
The function returns true if the HDVFs over K and L-Kare perfect, that is, if the reduced boundary matrix is null and false otherwise. The functions tests all dimensions if dimension_restriction is -1 (default value) and tests only dimension dimension_restriction otherwise.
| dimension_restriction | If positive, restricts the test to a single dimension , if -1 is provided, all dimensions are tested, if -2 is provided (default) test is carried out according to the HDVF dimension restriction value. |
| std::ostream & CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::print_bnd_pairing | ( | std::ostream & | out = std::cout | ) |
Prints the reduced boundary over critical cells of K and L-K.
The method prints out the reduced boundary matrix in each dimension, restricted to critical cells of K and L-K (ie. the matrix used to compute Alexander pairing).
By default, outputs the complex to std::cout.
|
virtual |
Gets cells with a given PSC_flag in any dimension in the current sub chain complex.
The function returns a vector containing, for each dimension, the vector of cells of the current sub chain complex with a given PSC_flag.
| flag | PSC_flag to select. |
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
|
virtual |
Gets cells with a given PSC_flag in dimension q in the current sub chain complex.
The function returns the vector of cells of dimension q of the current sub chain complex with a given PSC_flag.
| flag | PSC_flag to select. |
| q | Dimension visited. |
Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.
| std::vector< std::vector< int > > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::psc_labels | ( | ) | const |
Exports primary/secondary/critical labels of the current sub chain complex for vtk export.
The method exports the labels of every cells in each dimension. Exports the label 2 (ie. NONE) for cells out of the current sub chain complex.
| void CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::set_mask_K | ( | ) |
Sets the current sub chain complex masks over K.
Further HDVF computations will be restricted to K (ie. computation of reduced homology).
| void CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::set_mask_L_K | ( | ) |
Sets the current sub chain complex masks over L-K.
Further HDVF computations will be restricted to L-K (ie. computation of reduced homology).
| std::ostream & CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::write_reduction | ( | std::ostream & | out = std::cout | ) |
Prints the homology and cohomology reduction information for K and L-K.
Prints \(f^*\), \(g\) \(\partial'\) the reduced boundary over each critical cell.
By default, outputs the complex to std::cout.
| std::ostream & CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::write_reduction_sub | ( | std::ostream & | out = std::cout | ) |
Prints the homology and cohomology reduction information for the current sub chain complex.
Writes \(f^*\), \(g\) \(\partial'\) the reduced boundary over each critical cell.
By default, outputs the complex to std::cout.