CGAL 6.1 - Homological Discrete Vector Fields
Loading...
Searching...
No Matches
CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag > Class Template Reference

#include <CGAL/OSM/Sparse_chain.h>

Definition

template<typename CoefficientType, int ChainTypeFlag>
class CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >

The class Sparse_chain implements the concept SparseChain, that is, sparse vectors (encoding homological chains) optimized for topological computations.

Given a complex (for instance a simplicial, cubical or cellular complex) which cells in a given dimension \(q\) are numbered \(\{\sigma_i\,;\, i=1\ldots n_q\}\), homology with coefficients in a given ring \(\mathbb K\) defines \(q\)-chains as formal linear combinations:

\[\gamma = \sum_{i=1}^{n_q}\lambda_i\cdot \sigma_i\]

with coefficients \(\lambda_i\in\mathbb K\). In the basis \(\{\sigma_i\,;\, i=1\ldots n_q\}\), the coordinates of \(\gamma\) are given by the vector: \([\lambda_1,\ldots \lambda_{n_q}]\).

Now, as chains considered in homology are boundaries of cells, most \(\lambda_i\) coefficients are null. Hence Sparse_chain encodes such vectors in a "sparse" way, that is, storing only non zero coefficients through a map:

\[i\mapsto \lambda_i\ \ \ \forall i=1\ldots n_q\text{ such that }\lambda_i\neq 0\]

Moreover, as per any linear algebra vector, a Sparse_chain is either a column or row vector (the ChainTypeFlag parameter determines the type).

The class Sparse_chain provides standard linear algebra operators and fast iterators and block operations (set, get and nullify) which are required to implement efficiently HDVFs.

Is model of
SparseChain
Template Parameters
CoefficientTypea model of the Ring concept, providing the ring used to compute homology.
ChainTypeFlagan integer constant encoding the type of matrices (OSM::COLUMN or OSM::ROW).
Examples
HDVF/example_matrix_chain.cpp, and HDVF/main_hdvf.cpp.

Public Types

typedef std::unordered_map< size_t, CoefficientType >::iterator iterator
 Type of chains iterators.
 
typedef std::unordered_map< size_t, CoefficientType >::const_iterator const_iterator
 Type of chains constant iterators.
 

Public Member Functions

 Sparse_chain ()
 Creates new empty Sparse_chain.
 
 Sparse_chain (const size_t chainSize)
 Creates new empty SparseChain of given size.
 
 Sparse_chain (const Sparse_chain &otherToCopy)
 Creates new SparseChain by copy.
 
Sparse_chainoperator= (const Sparse_chain &otherToCopy)
 Assigns to other chain.
 
size_t dimension () const
 Size of the chain.
 
Sparse_chainoperator+= (const Sparse_chain &other)
 Adds a chain to this.
 
Sparse_chainoperator-= (const Sparse_chain &other)
 Sustracts a chain to this.
 
Sparse_chainoperator*= (const CoefficientType &lambda)
 Applies factor on each coefficients of this.
 
CoefficientType operator[] (size_t index) const
 Gets the value of a coefficient of the chain.
 
CoefficientType get_coef (size_t index) const
 Gets the value of a coefficient of the chain.
 
void set_coef (size_t index, CoefficientType d)
 Sets a given coefficient of the chain.
 
const bool is_null (size_t index) const
 Checks if a coefficient is null.
 
const bool is_null () const
 Checks if the chain is null.
 
Sparse_chainoperator/= (const std::vector< size_t > &indices)
 Restricts the chain to a sub-chain by removing indices.
 
Sparse_chainoperator/= (const size_t index)
 Restricts the chain to a sub-chain by removing a given index.
 
void nullify ()
 Removes all coefficients from the chain.
 
iterator begin () noexcept
 Iterator to the beginning of the chain.
 
const_iterator begin () const noexcept
 Constant iterator to the beginning of the chain.
 
const_iterator cbegin () const noexcept
 Constant iterator to the beginning of the chain.
 
iterator end () noexcept
 Iterator to the end of the chain.
 
const_iterator end () const noexcept
 Constant iterator to the end of the chain.
 
const_iterator cend () const noexcept
 Constant iterator to the end of the chain.
 
Sparse_chain< CoefficientType, COLUMN+ROW - ChainTypeFlag > transpose ()
 Transposes a Sparse_chain.
 
bool is_column () const
 Checks if chain is a column.
 
bool is_row () const
 Checks if chain is a row.
 

Protected Types

typedef std::pair< size_t, CoefficientType > pair
 

Protected Attributes

std::unordered_map< size_t, CoefficientType > _chainData
 
size_t _upperBound
 

Friends

template<typename _CT , int _CTF>
class Sparse_chain
 
template<typename _CT , int _CTF>
class Sparse_matrix
 
template<typename _CT >
Sparse_chain< _CT, COLUMNoperator* (const Sparse_matrix< _CT, COLUMN > &_first, const Sparse_chain< _CT, COLUMN > &_second)
 
template<typename _CT >
Sparse_chain< _CT, COLUMNoperator* (const Sparse_matrix< _CT, COLUMN > &_first, const Sparse_chain< _CT, ROW > &_second)
 
template<typename _CT >
Sparse_chain< _CT, COLUMNoperator* (const Sparse_matrix< _CT, ROW > &_first, const Sparse_chain< _CT, COLUMN > &_second)
 
template<typename _CT >
Sparse_chain< _CT, COLUMNoperator* (const Sparse_matrix< _CT, ROW > &_first, const Sparse_chain< _CT, ROW > &_second)
 
template<typename _CT >
Sparse_chain< _CT, ROWoperator* (const Sparse_chain< _CT, ROW > &_first, const Sparse_matrix< _CT, COLUMN > &_second)
 
template<typename _CT >
Sparse_chain< _CT, COLUMNget_column (const Sparse_matrix< _CT, COLUMN > &_matrix, size_t _index)
 
template<typename _CT >
Sparse_chain< _CT, COLUMNget_column (const Sparse_matrix< _CT, ROW > &_matrix, size_t _index)
 
template<typename _CT >
Sparse_chain< _CT, ROWget_row (const Sparse_matrix< _CT, COLUMN > &_matrix, size_t _index)
 
template<typename _CT >
Sparse_chain< _CT, ROWget_row (const Sparse_matrix< _CT, ROW > &_matrix, size_t _index)
 
template<typename _CT >
void set_column (Sparse_matrix< _CT, COLUMN > &matrix, size_t index, const Sparse_chain< _CT, COLUMN > &chain)
 
template<typename _CT >
void set_column (Sparse_matrix< _CT, ROW > &matrix, size_t index, const Sparse_chain< _CT, COLUMN > &chain)
 
template<typename _CT >
void set_row (Sparse_matrix< _CT, COLUMN > &_matrix, size_t _index, const Sparse_chain< _CT, ROW > &_chain)
 
template<typename _CT >
void set_row (Sparse_matrix< _CT, ROW > &_matrix, size_t _index, const Sparse_chain< _CT, ROW > &_chain)
 
std::ostream & operator<< (std::ostream &stream, const Sparse_chain &chain)
 Displays a Sparse_chain in the output stream.
 
template<int _CTF>
Sparse_chain operator+ (const Sparse_chain &first, const Sparse_chain< CoefficientType, _CTF > &second)
 Adds two chains together.
 
template<int _CTF>
Sparse_chain operator- (const Sparse_chain &first, const Sparse_chain< CoefficientType, _CTF > &second)
 Subtracts two chains together.
 
template<int _CTF>
Sparse_chain operator* (const CoefficientType &lambda, const Sparse_chain< CoefficientType, _CTF > &chain)
 Applies factor on each coefficients.
 
template<int _CTF>
Sparse_chain operator* (const Sparse_chain< CoefficientType, _CTF > &chain, const CoefficientType &lambda)
 Applies factor on each coefficients.
 
template<typename _CT >
Sparse_matrix< _CT, COLUMNoperator* (const Sparse_chain< _CT, COLUMN > &column, const Sparse_chain< _CT, ROW > &row)
 Performs matrix multiplication between two chains (COLUMN x ROW) and return a COLUMN matrix.
 
template<typename _CT >
Sparse_matrix< _CT, ROWoperator% (const Sparse_chain< _CT, COLUMN > &column, const Sparse_chain< _CT, ROW > &row)
 Performs matrix multiplication between two chains (COLUMN x ROW) and return a ROW matrix.
 
template<typename _CT >
_CT operator* (const Sparse_chain< _CT, ROW > &row, const Sparse_chain< _CT, COLUMN > &column)
 Performs dot product between two chains (ROW x COLUMN).
 
template<typename _CT >
bool operator== (const Sparse_chain< _CT, OSM::COLUMN > &chain, const Sparse_chain< _CT, OSM::COLUMN > &other)
 Comparison of two COLUMN chains.
 
template<typename _CT >
bool operator== (const Sparse_chain< _CT, OSM::COLUMN > &chain, const Sparse_chain< _CT, OSM::ROW > &other)
 Comparison of a COLUMN and a ROW chain.
 
template<typename _CT >
bool operator== (const Sparse_chain< _CT, OSM::ROW > &chain, const Sparse_chain< _CT, OSM::COLUMN > &other)
 Comparison of a ROW and a COLUMN chain.
 
template<typename _CT >
bool operator== (const Sparse_chain< _CT, OSM::ROW > &chain, const Sparse_chain< _CT, OSM::ROW > &other)
 Comparison of two ROW chains.
 
template<typename _CT , int _CTF>
Sparse_chain< _CT, _CTF > operator/ (const Sparse_chain< _CT, _CTF > &chain, const std::vector< size_t > &indices)
 Gets a subchain from the chain.
 
template<typename _CT , int _CTF>
Sparse_chain< _CT, _CTF > operator/ (const Sparse_chain< _CT, _CTF > &chain, size_t index)
 Gets a subchain from the chain.
 

Constructor & Destructor Documentation

◆ Sparse_chain() [1/3]

template<typename CoefficientType , int ChainTypeFlag>
CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::Sparse_chain ( )

Creates new empty Sparse_chain.

Default constructor, initialize an empty Sparse_chain. The default chain size is 0.

◆ Sparse_chain() [2/3]

template<typename CoefficientType , int ChainTypeFlag>
CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::Sparse_chain ( const size_t  chainSize)

Creates new empty SparseChain of given size.

Constructor with size, initialize an empty Sparse_chain.

Parameters
[in]chainSizeThe size of the Sparse_chain.

◆ Sparse_chain() [3/3]

template<typename CoefficientType , int ChainTypeFlag>
CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::Sparse_chain ( const Sparse_chain< CoefficientType, ChainTypeFlag > &  otherToCopy)

Creates new SparseChain by copy.

Copy constructor, initialize a SparseChain from an existing SparseChain.

Precondition
The chains have the same CoefficientType and ChainTypeFlag.
Parameters
[in]otherToCopyThe chain to copy.

Member Function Documentation

◆ begin() [1/2]

template<typename CoefficientType , int ChainTypeFlag>
const_iterator CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::begin ( ) const
noexcept

Constant iterator to the beginning of the chain.

Warning
The chain is stored unordered for speed reason.
Returns
The function returns a constant iterator to the first non zero index.

◆ begin() [2/2]

template<typename CoefficientType , int ChainTypeFlag>
iterator CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::begin ( )
noexcept

Iterator to the beginning of the chain.

Warning
The chain is stored unordered for speed reason.
Returns
The function returns an iterator to the first non zero index.

◆ cbegin()

template<typename CoefficientType , int ChainTypeFlag>
const_iterator CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::cbegin ( ) const
noexcept

Constant iterator to the beginning of the chain.

Warning
The chain is stored unordered for speed reason.
Returns
The function returns a constant iterator to the first non zero index.

◆ cend()

template<typename CoefficientType , int ChainTypeFlag>
const_iterator CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::cend ( ) const
noexcept

Constant iterator to the end of the chain.

Warning
The chain is stored unordered for speed reason.
Returns
The function returns a constant iterator to the ending of the chain.

◆ dimension()

template<typename CoefficientType , int ChainTypeFlag>
size_t CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::dimension ( ) const

Size of the chain.

Returns
Size allocated for the chain.

◆ end() [1/2]

template<typename CoefficientType , int ChainTypeFlag>
const_iterator CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::end ( ) const
noexcept

Constant iterator to the end of the chain.

Warning
The chain is stored unordered for speed reason.
Returns
The function returns a constant iterator to the ending of the chain.

◆ end() [2/2]

template<typename CoefficientType , int ChainTypeFlag>
iterator CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::end ( )
noexcept

Iterator to the end of the chain.

Warning
The chain is stored unordered for speed reason.
Returns
The function returns an iterator to the ending of the chain.

◆ get_coef()

template<typename CoefficientType , int ChainTypeFlag>
CoefficientType CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::get_coef ( size_t  index) const

Gets the value of a coefficient of the chain.

Warning
The chain will perform boundary check.
Parameters
[in]indexThe coefficient index.
Returns
The value of the coefficient.

◆ is_column()

template<typename CoefficientType , int ChainTypeFlag>
bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_column ( ) const

Checks if chain is a column.

Returns
true if chain is column-major, false otherwise.

◆ is_null() [1/2]

template<typename CoefficientType , int ChainTypeFlag>
const bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_null ( ) const

Checks if the chain is null.

Returns
True if the chain is null.

◆ is_null() [2/2]

template<typename CoefficientType , int ChainTypeFlag>
const bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_null ( size_t  index) const

Checks if a coefficient is null.

Parameters
[in]indexThe index to check.
Returns
True if the data is null at given index.

◆ is_row()

template<typename CoefficientType , int ChainTypeFlag>
bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_row ( ) const

Checks if chain is a row.

Returns
true if chain is row-major, false otherwise.

◆ nullify()

template<typename CoefficientType , int ChainTypeFlag>
void CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::nullify ( )

Removes all coefficients from the chain.

The function comes to set all coefficients to zero.

◆ operator*=()

template<typename CoefficientType , int ChainTypeFlag>
Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator*= ( const CoefficientType &  lambda)

Applies factor on each coefficients of this.

If lambda is null, this function comes to nullify the chain.

Parameters
[in]lambdaThe factor to apply.
Returns
The modified chain representing the result.

◆ operator+=()

template<typename CoefficientType , int ChainTypeFlag>
Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator+= ( const Sparse_chain< CoefficientType, ChainTypeFlag > &  other)

Adds a chain to this.

Add a chain to this.

Precondition
Chains must have the same CoefficientType and the same ChainTypeFlag.
Warning
Will raise an error if the two chains are not the same CoefficientType.
Will raise an error if the two chains don't have the same ChainTypeFlag.
Parameters
[in]otherThe other chain.
Returns
The modified chain representing the result.

◆ operator-=()

template<typename CoefficientType , int ChainTypeFlag>
Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator-= ( const Sparse_chain< CoefficientType, ChainTypeFlag > &  other)

Sustracts a chain to this.

Subtract a chain to this.

Precondition
Chains must have the same CoefficientType and the same ChainTypeFlag.
Warning
Will raise an error if the two chains are not the same CoefficientType.
Will raise an error if the two chains don't have the same ChainTypeFlag.
Parameters
[in]otherThe other chain.
Returns
The modified chain representing the result.

◆ operator/=() [1/2]

template<typename CoefficientType , int ChainTypeFlag>
Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator/= ( const size_t  index)

Restricts the chain to a sub-chain by removing a given index.

Removes the index provided from the chain.

Note
Will not alter the chain if given vector is empty.
Parameters
[in]indexThe index to remove.
Returns
Return a reference to the modified chain.

◆ operator/=() [2/2]

template<typename CoefficientType , int ChainTypeFlag>
Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator/= ( const std::vector< size_t > &  indices)

Restricts the chain to a sub-chain by removing indices.

Removes all indices provided in the vector from the chain. Return a reference to the modified chain.

Note
Will not alter the chain if indices is empty.
Parameters
[in]indicesThe indices to remove.
Returns
Return a reference to the modified chain.

◆ operator=()

template<typename CoefficientType , int ChainTypeFlag>
Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator= ( const Sparse_chain< CoefficientType, ChainTypeFlag > &  otherToCopy)

Assigns to other chain.

Assign to other chain coefficient-wise, equivalent to copying it.

Precondition
The chains have the same coefficent type.
Warning
Chains must have the same CoefficientType.
Parameters
[in]otherToCopyThe chain we want to copy.

◆ operator[]()

template<typename CoefficientType , int ChainTypeFlag>
CoefficientType CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator[] ( size_t  index) const

Gets the value of a coefficient of the chain.

Warning
The chain will perform boundary check.
Parameters
[in]indexThe coefficient index.
Returns
The value of the coefficient.

◆ set_coef()

template<typename CoefficientType , int ChainTypeFlag>
void CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::set_coef ( size_t  index,
CoefficientType  d 
)

Sets a given coefficient of the chain.

Set the value of the coefficient in the chain at index.

Warning
The chain will perform boundary check.
Parameters
[in]indexThe coefficient index.
[in]dValue of the coefficient

◆ transpose()

template<typename CoefficientType , int ChainTypeFlag>
Sparse_chain< CoefficientType, COLUMN+ROW - ChainTypeFlag > CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::transpose ( )

Transposes a Sparse_chain.

The result is a chain with ChainTypeFlag switched between COLUMN and ROW.

Returns
A new chain where the chain type flag is changed.

Friends And Related Function Documentation

◆ operator%

template<typename CoefficientType , int ChainTypeFlag>
template<typename _CT >
Sparse_matrix< _CT, ROW > operator% ( const Sparse_chain< _CT, COLUMN > &  column,
const Sparse_chain< _CT, ROW > &  row 
)
friend

Performs matrix multiplication between two chains (COLUMN x ROW) and return a ROW matrix.

Generate a row-based matrix from the matrix multiplication and return it.

Precondition
Chains must have the same CoefficientType.
Warning
Will raise an error if chains do not have the same CoefficientType.
Parameters
[in]columnThe column chain.
[in]rowThe row chain.
Returns
The result of the matrix multiplication, row-based.

◆ operator* [1/4]

template<typename CoefficientType , int ChainTypeFlag>
template<int _CTF>
Sparse_chain operator* ( const CoefficientType &  lambda,
const Sparse_chain< CoefficientType, _CTF > &  chain 
)
friend

Applies factor on each coefficients.

Parameters
[in]lambdaThe factor to apply.
[in]chainThe second chain.
Returns
A new chain representing the result.

◆ operator* [2/4]

template<typename CoefficientType , int ChainTypeFlag>
template<typename _CT >
Sparse_matrix< _CT, COLUMN > operator* ( const Sparse_chain< _CT, COLUMN > &  column,
const Sparse_chain< _CT, ROW > &  row 
)
friend

Performs matrix multiplication between two chains (COLUMN x ROW) and return a COLUMN matrix.

Generate a column-based matrix from the matrix multiplication and return it.

Precondition
Chains must have the same CoefficientType.
Warning
Will raise an error if chains do not have the same CoefficientType.
Parameters
[in]columnThe column chain.
[in]rowThe row chain.
Returns
The result of the matrix multiplication, column-based.

◆ operator* [3/4]

template<typename CoefficientType , int ChainTypeFlag>
template<typename _CT >
_CT operator* ( const Sparse_chain< _CT, ROW > &  row,
const Sparse_chain< _CT, COLUMN > &  column 
)
friend

Performs dot product between two chains (ROW x COLUMN).

Precondition
Chains must have the same CoefficientType.
Warning
Will raise an error if the chains do not have the same CoefficientType.
Parameters
[in]rowThe row chain.
[in]columnThe column chain.
Returns
The result of type CoefficientType.

◆ operator* [4/4]

template<typename CoefficientType , int ChainTypeFlag>
template<int _CTF>
Sparse_chain operator* ( const Sparse_chain< CoefficientType, _CTF > &  chain,
const CoefficientType &  lambda 
)
friend

Applies factor on each coefficients.

Parameters
[in]chainThe second chain.
[in]lambdaThe factor to apply.
Returns
A new chain representing the result.

◆ operator+

template<typename CoefficientType , int ChainTypeFlag>
template<int _CTF>
Sparse_chain operator+ ( const Sparse_chain< CoefficientType, ChainTypeFlag > &  first,
const Sparse_chain< CoefficientType, _CTF > &  second 
)
friend

Adds two chains together.

Adds two chains together and return the result in a new matrix.

Precondition
Chains must have the same CoefficientType and the same ChainTypeFlag.
Warning
Will raise an error if the two chains are not the same CoefficientType.
Will raise an error if the two chains don't have the same ChainTypeFlag.
Parameters
[in]firstThe first chain.
[in]secondThe second chain.
Returns
A new chain representing the result.

◆ operator-

template<typename CoefficientType , int ChainTypeFlag>
template<int _CTF>
Sparse_chain operator- ( const Sparse_chain< CoefficientType, ChainTypeFlag > &  first,
const Sparse_chain< CoefficientType, _CTF > &  second 
)
friend

Subtracts two chains together.

Subtract two chains together and return the result in a new matrix.

Precondition
Chains must have the same CoefficientType and the same ChainTypeFlag.
Warning
Will raise an error if the two chains are not the same CoefficientType.
Will raise an error if the two chains don't have the same ChainTypeFlag.
Parameters
[in]firstThe first chain.
[in]secondThe second chain.
Returns
A new chain representing the result.

◆ operator/ [1/2]

template<typename CoefficientType , int ChainTypeFlag>
template<typename _CT , int _CTF>
Sparse_chain< _CT, _CTF > operator/ ( const Sparse_chain< _CT, _CTF > &  chain,
const std::vector< size_t > &  indices 
)
friend

Gets a subchain from the chain.

Return a new chain where all coefficients of indices provided in the vector are removed.

Note
Will return a copy of the chain if indices is empty.
Parameters
[in]chainThe chain to process.
[in]indicesThe indexes to remove.
Returns
A new chain representing the result.

◆ operator/ [2/2]

template<typename CoefficientType , int ChainTypeFlag>
template<typename _CT , int _CTF>
Sparse_chain< _CT, _CTF > operator/ ( const Sparse_chain< _CT, _CTF > &  chain,
size_t  index 
)
friend

Gets a subchain from the chain.

Return a new chain where the coefficients at a given index is removed.

Parameters
[in]chainThe chain to process.
[in]indexThe index to remove.

◆ operator<<

template<typename CoefficientType , int ChainTypeFlag>
std::ostream & operator<< ( std::ostream &  stream,
const Sparse_chain< CoefficientType, ChainTypeFlag > &  chain 
)
friend

Displays a Sparse_chain in the output stream.

Parameters
[in]streamThe output stream.
[in]chainThe chain to display.
Returns
A reference to the modified stream.