|
CGAL 6.1 - Homological Discrete Vector Fields
|
#include <CGAL/OSM/Sparse_chain.h>
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.
SparseChain | CoefficientType | a model of the Ring concept, providing the ring used to compute homology. |
| ChainTypeFlag | an integer constant encoding the type of matrices (OSM::COLUMN or OSM::ROW). |
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_chain & | operator= (const Sparse_chain &otherToCopy) |
| Assigns to other chain. | |
| size_t | dimension () const |
| Size of the chain. | |
| Sparse_chain & | operator+= (const Sparse_chain &other) |
Adds a chain to this. | |
| Sparse_chain & | operator-= (const Sparse_chain &other) |
Sustracts a chain to this. | |
| Sparse_chain & | operator*= (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_chain & | operator/= (const std::vector< size_t > &indices) |
| Restricts the chain to a sub-chain by removing indices. | |
| Sparse_chain & | operator/= (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, COLUMN > | operator* (const Sparse_matrix< _CT, COLUMN > &_first, const Sparse_chain< _CT, COLUMN > &_second) |
| template<typename _CT > | |
| Sparse_chain< _CT, COLUMN > | operator* (const Sparse_matrix< _CT, COLUMN > &_first, const Sparse_chain< _CT, ROW > &_second) |
| template<typename _CT > | |
| Sparse_chain< _CT, COLUMN > | operator* (const Sparse_matrix< _CT, ROW > &_first, const Sparse_chain< _CT, COLUMN > &_second) |
| template<typename _CT > | |
| Sparse_chain< _CT, COLUMN > | operator* (const Sparse_matrix< _CT, ROW > &_first, const Sparse_chain< _CT, ROW > &_second) |
| template<typename _CT > | |
| Sparse_chain< _CT, ROW > | operator* (const Sparse_chain< _CT, ROW > &_first, const Sparse_matrix< _CT, COLUMN > &_second) |
| template<typename _CT > | |
| Sparse_chain< _CT, COLUMN > | get_column (const Sparse_matrix< _CT, COLUMN > &_matrix, size_t _index) |
| template<typename _CT > | |
| Sparse_chain< _CT, COLUMN > | get_column (const Sparse_matrix< _CT, ROW > &_matrix, size_t _index) |
| template<typename _CT > | |
| Sparse_chain< _CT, ROW > | get_row (const Sparse_matrix< _CT, COLUMN > &_matrix, size_t _index) |
| template<typename _CT > | |
| Sparse_chain< _CT, ROW > | get_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, COLUMN > | operator* (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, ROW > | operator% (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. | |
| 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.
| 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.
| [in] | chainSize | The size of the Sparse_chain. |
| 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.
CoefficientType and ChainTypeFlag.| [in] | otherToCopy | The chain to copy. |
|
noexcept |
Constant iterator to the beginning of the chain.
|
noexcept |
Iterator to the beginning of the chain.
|
noexcept |
Constant iterator to the beginning of the chain.
|
noexcept |
Constant iterator to the end of the chain.
| size_t CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::dimension | ( | ) | const |
Size of the chain.
|
noexcept |
Constant iterator to the end of the chain.
|
noexcept |
Iterator to the end of the chain.
| CoefficientType CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::get_coef | ( | size_t | index | ) | const |
Gets the value of a coefficient of the chain.
| [in] | index | The coefficient index. |
| bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_column | ( | ) | const |
Checks if chain is a column.
| const bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_null | ( | ) | const |
Checks if the chain is null.
| const bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_null | ( | size_t | index | ) | const |
Checks if a coefficient is null.
| [in] | index | The index to check. |
| bool CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::is_row | ( | ) | const |
Checks if chain is a row.
| void CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::nullify | ( | ) |
Removes all coefficients from the chain.
The function comes to set all coefficients to zero.
| 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.
| [in] | lambda | The factor to apply. |
| 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.
CoefficientType and the same ChainTypeFlag.CoefficientType. ChainTypeFlag.| [in] | other | The other chain. |
| 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.
CoefficientType and the same ChainTypeFlag.CoefficientType. ChainTypeFlag.| [in] | other | The other chain. |
| 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.
| [in] | index | The index to remove. |
| 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.
indices is empty.| [in] | indices | The indices to remove. |
| 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.
CoefficientType.| [in] | otherToCopy | The chain we want to copy. |
| CoefficientType CGAL::OSM::Sparse_chain< CoefficientType, ChainTypeFlag >::operator[] | ( | size_t | index | ) | const |
Gets the value of a coefficient of the chain.
| [in] | index | The coefficient index. |
| 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.
| [in] | index | The coefficient index. |
| [in] | d | Value of the coefficient |
| 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.
|
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.
CoefficientType.CoefficientType.| [in] | column | The column chain. |
| [in] | row | The row chain. |
|
friend |
Applies factor on each coefficients.
| [in] | lambda | The factor to apply. |
| [in] | chain | The second chain. |
|
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.
CoefficientType.CoefficientType.| [in] | column | The column chain. |
| [in] | row | The row chain. |
|
friend |
Performs dot product between two chains (ROW x COLUMN).
CoefficientType.CoefficientType.| [in] | row | The row chain. |
| [in] | column | The column chain. |
|
friend |
Applies factor on each coefficients.
| [in] | chain | The second chain. |
| [in] | lambda | The factor to apply. |
|
friend |
Adds two chains together.
Adds two chains together and return the result in a new matrix.
CoefficientType and the same ChainTypeFlag.CoefficientType. ChainTypeFlag.| [in] | first | The first chain. |
| [in] | second | The second chain. |
|
friend |
Subtracts two chains together.
Subtract two chains together and return the result in a new matrix.
CoefficientType and the same ChainTypeFlag.CoefficientType. ChainTypeFlag.| [in] | first | The first chain. |
| [in] | second | The second chain. |
|
friend |
Gets a subchain from the chain.
Return a new chain where all coefficients of indices provided in the vector are removed.
indices is empty.| [in] | chain | The chain to process. |
| [in] | indices | The indexes to remove. |
|
friend |
Gets a subchain from the chain.
Return a new chain where the coefficients at a given index is removed.
| [in] | chain | The chain to process. |
| [in] | index | The index to remove. |
|
friend |
Displays a Sparse_chain in the output stream.
| [in] | stream | The output stream. |
| [in] | chain | The chain to display. |