CGAL 6.3-dev - Homological Discrete Vector Fields
Loading...
Searching...
No Matches
CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex > Class Template Reference

#include <CGAL/HDVF/Hdvf_duality.h>

Inherits from

CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.

Definition

template<typename ChainComplex>
class CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >

The class Hdvf_duality is the implementation of homological discrete vector fields (HDVF for short) for Alexander duality computation.

Warning
The ring of coefficients provided should be a field.

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\)).

Is model of
HDVF
Template Parameters
ChainComplexa 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.
Warning
The sparse matrix 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.

Constructor & Destructor Documentation

◆ Hdvf_duality()

template<typename ChainComplex>
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.

Parameters
LA complex of a given dimension \(n\) homeomorphic to \(\mathcal B^n\).
KA sub complex of L encoded through a bitboard.
hdvf_optOption for HDVF computation (OPT_BND, OPT_F, OPT_G or OPT_FULL).
Exceptions
Empty_complexIf the complex `L` is empty, raises a `std::runtime_error`.

Member Function Documentation

◆ cohomology_chain()

template<typename ChainComplex>
Column_chain CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::cohomology_chain ( size_t cell_index,
int dim ) const
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.

Returns
A column-major chain.

Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.

◆ compute_pairing_hdvf()

template<typename 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.

Warning
Run compute_perfect_hdvf() first (to build perfect HDVFs over K and L-K respectively).

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.

Returns
The vector of paired critical cells (encoding Alexander isomorphism).
Exceptions
Non_perfect_hdvfsIf the HDVFs over `K` and `L-K` are not perfect, raises a `std::runtime_error`.

◆ compute_perfect_hdvf()

template<typename ChainComplex>
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.

Parameters
verboseIf this parameter is true, all intermediate reductions are printed out.
Returns
The vector of all Cell_pair paired with A.

◆ compute_rand_pairing_hdvf()

template<typename ChainComplex>
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.

Warning
Run compute_perfect_hdvf() first (to build perfect HDVFs over K and L-K respectively).

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.

Returns
The vector of paired critical cells (encoding Alexander isomorphism).
Exceptions
Non_perfect_hdvfsIf the HDVFs over `K` and `L-K` are not perfect, raises a `std::runtime_error`.

◆ compute_rand_perfect_hdvf()

template<typename ChainComplex>
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.

Warning
This method is slower that compute_perfect_hdvf() (finding out all possible valid pairs requires additional time).
Parameters
verboseIf this parameter is true, all intermediate reductions are printed out.
Returns
The vector of all pairs of cells used for apply A.

◆ find_pair_A() [1/2]

template<typename ChainComplex>
Cell_pair CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::find_pair_A ( int q,
bool & found ) const
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.

Parameters
qLower dimension of the pair.
foundReference 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 >.

◆ find_pair_A() [2/2]

template<typename ChainComplex>
Cell_pair CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::find_pair_A ( int q,
size_t gamma,
bool & found ) const
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:

  • \(\gamma'\) has dimension q+1 and \((\gamma, \gamma')\) is valid for A (ie. such that \(\langle \partial_{q+1}(\gamma'), \gamma \rangle\) invertible),
  • \(\gamma'\) has dimension q-1 and \((\gamma', \gamma)\) is valid for A (ie. such that \(\langle \partial_{q}(\gamma), \gamma' \rangle\) invertible).
Parameters
qDimension of the cell gamma.
gammaIndex of a cell to pair.
foundReference 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 >.

◆ find_pairs_A() [1/2]

template<typename ChainComplex>
std::vector< Cell_pair > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::find_pairs_A ( int q,
bool & found ) const
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.

Parameters
qLower dimension of the pairs.
foundReference 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 >.

◆ find_pairs_A() [2/2]

template<typename ChainComplex>
std::vector< Cell_pair > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::find_pairs_A ( int q,
size_t gamma,
bool & found ) const
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:

  • \(\gamma'\) has dimension q+1 and \((\gamma, \gamma')\) is valid for A (ie. such that \(\langle \partial_{q+1}(\gamma'), \gamma \rangle\) invertible),
  • \(\gamma'\) has dimension q-1 and \((\gamma', \gamma)\) is valid for A (ie. such that \(\langle \partial_{q}(\gamma), \gamma' \rangle\) invertible). It returns a vector of such pairs.
Parameters
qDimension of the cell gamma.
gammaIndex of a cell to pair.
foundReference 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 >.

◆ homology_chain()

template<typename ChainComplex>
Column_chain CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::homology_chain ( size_t cell_index,
int dim ) const
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.

Returns
A column-major chain.

Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.

◆ is_perfect_hdvf()

template<typename 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.

Parameters
dimension_restrictionIf 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.

◆ print_bnd_pairing()

template<typename ChainComplex>
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).

Warning
Call this method after compute_perfect_hdvf().

By default, outputs the complex to std::cout.

◆ psc_flag() [1/2]

template<typename ChainComplex>
std::vector< std::vector< size_t > > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::psc_flag ( PSC_flag flag) const
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.

Parameters
flagPSC_flag to select.

Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.

◆ psc_flag() [2/2]

template<typename ChainComplex>
std::vector< size_t > CGAL::Homological_discrete_vector_field::Hdvf_duality< ChainComplex >::psc_flag ( PSC_flag flag,
int q ) const
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.

Parameters
flagPSC_flag to select.
qDimension visited.

Reimplemented from CGAL::Homological_discrete_vector_field::Hdvf_core< ChainComplex >.

◆ psc_labels()

template<typename 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.

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

◆ set_mask_K()

template<typename ChainComplex>
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).

◆ set_mask_L_K()

template<typename ChainComplex>
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).

◆ write_reduction()

template<typename ChainComplex>
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.

◆ write_reduction_sub()

template<typename ChainComplex>
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.