CGAL 6.3-dev - Homological Discrete Vector Fields
Loading...
Searching...
No Matches

Definition

The concept SparseChain describes the requirements for sparse vectors (called sparse chains in homology) optimized for topological computations. More precisely, SparseChain provides all the operations on chains required by the SparseMatrix concept.

SparseChain encodes non zero coefficients of a sparse vector.

SparseChain can be either row or column vectors. The following integer constants, called Storage_format, encode the direction of sparse chains (and sparse matrices).

  • CGAL::OSM::COLUMN for column-major chains and matrices (which is the default),
  • CGAL::OSM::ROW for row-major chains and matrices.
Has models
CGAL::OSM::Sparse_chain<CoefficientRing, StorageFormat>
See also
IntegralDomainWithoutDivision
SparseMatrix

Types

typedef unspecified_type Coefficient_ring
 Type of coefficients stored in the matrix (a model of IntegralDomainWithoutDivision).
template<typename CR, int SF>
using Sparse_matrix_derived = OSM::Sparse_matrix_structure<OSM::Sparse_chain>::Sparse_matrix_type<CR, SF>
 Type of derived sparse matrices.
typedef unspecified_type iterator
 Sparse chain iterator type.
typedef unspecified_type const_iterator
 Sparse chain constant iterator type.

Member data

int Storage_format
 Chain storage format (either CGAL::OSM::ROW or CGAL::OSM::COLUMN).

Creation, filling

 SparseChain ()
 Creates new empty sparse chain.
 SparseChain (size_t chainSize)
 Creates new empty sparse chain (ie. zero-chain) of given size.
Sparse_chain & operator= (const Sparse_chain &other)
 Assignment.

Matrix informations and iterators

size_t dimension () const
 Size of 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.

Linear algebra operators

Sparse_chain operator+ (const Sparse_chain &other)
 Adds two chains.
Sparse_chain operator- (const Sparse_chain &other)
 Subtracts a chain from current chain.
Sparse_chain operator* (const Coefficient_ring &lambda)
 Multiplies each coefficient of chain by lambda.
SparseChain & operator+= (const SparseChain &other)
 Adds a chain to this.
SparseChain & operator-= (const SparseChain &other)
 Sustracts a chain to this.
SparseChain & operator*= (const Coefficient_ring &lambda)
 Multiplies each coefficient of this by lambda.
SparseChain transpose ()
 Transposes a sparse chain.
SparseChain operator* (const Coefficient_ring &lambda, const SparseChain &chain)
 Multiplies each coefficient of chain by lambda.
Sparse_matrix_derived< Coefficient_ring, COLUMN > operator* (const SparseChain &column, const SparseChain &row)
 Performs matrix multiplication between two chains (COLUMN x ROW) and return a COLUMN matrix.
SparseMatrix operator% (const Sparse_chain &column, const Sparse_chain &row)
 Performs matrix multiplication between two chains (COLUMN x ROW) and return a ROW matrix.
Coefficient_ring operator* (const Sparse_chain &row, const Sparse_chain &column)
 Performs dot product between two chains (ROW x COLUMN).

Test, access and modifications

bool is_column () const
 Checks if chain is a column.
bool is_row () const
 Checks if chain is a row.
bool is_null (size_t index) const
 Checks if a coefficient is null (that is, not store in the sparse chain).
bool is_null () const
 Checks if the chain is null.
Coefficient_ring get_coefficient (size_t index) const
 Gets the value of a coefficient index of the chain.
void set_coefficient (size_t index, Coefficient_ring d)
 Sets coefficient index of the chain to value d.
SparseChain & operator/= (const std::vector< size_t > &indices)
 Restricts the chain to a sub-chain by removing indices.
SparseChain & operator/= (size_t index)
 Restricts the chain to a sub-chain by removing a given index.
void nullify ()
 Removes all coefficients from the chain.
bool operator== (const Sparse_chain &chain, const Sparse_chain &other)
 Tests if two chains are equal.
SparseChain operator/ (const SparseChain &chain, const std::vector< size_t > &indices)
 Gets a subchain from the chain.
SparseChain operator/ (const SparseChain &chain, size_t index)
 Gets a subchain from the chain.

Output

std::ostream & operator<< (std::ostream &stream, const SparseChain &chain)
 Inserts chain in the output stream with a compact "user friendly" format.
template<typename _CT, int _SF>
std::ostream & write_chain (const Sparse_chain< _CT, _SF > &chain, std::ostream &out)
 Write a sparse chain to an output stream using the .osm file format.
template<typename _CT, int _SF>
void write_chain (const Sparse_chain< _CT, _SF > &chain, std::string filename)
 Write a sparse chain to a file using the .osm file format.
template<typename _CT, int _SF>
std::istream & read_chain (Sparse_chain< _CT, _SF > &chain, std::istream &in)
 Reads a sparse chain from an input stream using the .osm file format.
template<typename _CT, int _SF>
void read_chain (Sparse_chain< _CT, _SF > &chain, std::string filename)
 Reads a sparse chain from a file using the .osm file format.

Constructor & Destructor Documentation

◆ SparseChain() [1/2]

SparseChain::SparseChain ( )

Creates new empty sparse chain.

Creates a sparse chain encoding an empty linear combination of cells.

◆ SparseChain() [2/2]

SparseChain::SparseChain ( size_t chainSize)

Creates new empty sparse chain (ie. zero-chain) of given size.

Constructor with size, initializes an empty sparse chain encoding a linear combination of cells with all coefficients null.

Member Function Documentation

◆ begin() [1/2]

const_iterator SparseChain::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]

iterator SparseChain::begin ( )
noexcept

Iterator to the beginning of the chain.

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

◆ cbegin()

const_iterator SparseChain::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()

const_iterator SparseChain::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()

size_t SparseChain::dimension ( ) const

Size of the chain.

Returns
Dimension of the basis (that is, the size of the chain).

◆ end() [1/2]

const_iterator SparseChain::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 past-the end of the chain.

◆ end() [2/2]

iterator SparseChain::end ( )
noexcept

Iterator to the end of the chain.

Warning
The chain is stored unordered for speed reason.
Returns
The function returns an iterator past-the-end of the chain.

◆ get_coefficient()

Coefficient_ring SparseChain::get_coefficient ( size_t index) const

Gets the value of a coefficient index of the chain.

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

◆ is_null() [1/2]

bool SparseChain::is_null ( ) const

Checks if the chain is null.

Returns
true if the chain is null (that is, contains no non zero coefficients), false otherwise.

◆ is_null() [2/2]

bool SparseChain::is_null ( size_t index) const

Checks if a coefficient is null (that is, not store in the sparse chain).

Parameters
indexThe index to check.
Returns
true if the data at given index is null, false.

◆ nullify()

void SparseChain::nullify ( )

Removes all coefficients from the chain.

The function comes to set all coefficients to zero.

◆ operator*()

Sparse_chain SparseChain::operator* ( const Coefficient_ring & lambda)

Multiplies each coefficient of chain by lambda.

Parameters
lambdaThe factor to apply.
Returns
A new chain representing the result.

◆ operator*=()

SparseChain & SparseChain::operator*= ( const Coefficient_ring & lambda)

Multiplies each coefficient of this by lambda.

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

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

◆ operator+()

Sparse_chain SparseChain::operator+ ( const Sparse_chain & other)

Adds two chains.

Adds other chain to current chain and returns the result in a new matrix.

Precondition
Chains must have the same Coefficient_ring and the same Storage_format.
Warning
Will raise an error if the two chains are not the same Coefficient_ring.
Will raise a compilation error if the two chains don't have the same Storage_format.
Parameters
otherThe other chain.
Returns
A new chain representing the result.

◆ operator+=()

SparseChain & SparseChain::operator+= ( const SparseChain & other)

Adds a chain to this.

Add a chain to this.

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

◆ operator-()

Sparse_chain SparseChain::operator- ( const Sparse_chain & other)

Subtracts a chain from current chain.

Subtracts other chain from current chain and returns the result in a new matrix.

Precondition
Chains must have the same Coefficient_ring and the same Storage_format.
Warning
Will raise an error if the two chains are not the same Coefficient_ring.
Will raise a compilation error if the two chains don't have the same Storage_format.
Parameters
otherThe other chain.
Returns
A new chain representing the result.

◆ operator-=()

SparseChain & SparseChain::operator-= ( const SparseChain & other)

Sustracts a chain to this.

Subtract a chain to this.

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

◆ operator/=() [1/2]

SparseChain & SparseChain::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. Returns a reference to the modified chain.

Note
Will not alter the chain if indices is empty.
Parameters
indicesThe indices to remove.
Returns
A reference to the modified chain.

◆ operator/=() [2/2]

SparseChain & SparseChain::operator/= ( size_t index)

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

Removes the index provided from the chain.

Parameters
indexThe index to remove.
Returns
A reference to the modified chain.

◆ operator=()

Sparse_chain & SparseChain::operator= ( const Sparse_chain & other)

Assignment.

The assignment operator converts the storage format if needed (complexity \(\mathscr O(k)\) with \(k\) the number of non zero coefficients of other).

Precondition
Chains must have the same Coefficient_ring.
Parameters
otherChain to copy into this.

◆ set_coefficient()

void SparseChain::set_coefficient ( size_t index,
Coefficient_ring d )

Sets coefficient index of the chain to value d.

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

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

◆ transpose()

SparseChain SparseChain::transpose ( )

Transposes a sparse chain.

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

Returns
A new chain where the Storage_format is changed.

◆ operator%

SparseMatrix operator% ( const Sparse_chain & column,
const Sparse_chain & 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 Coefficient_ring.
column.is_column() and row.is_row() must be true
Warning
Will raise an error if chains do not have the same Coefficient_ring.
Parameters
columnThe column chain.
rowThe row chain.
Returns
The result of the matrix multiplication, row-based.

◆ operator* [1/3]

SparseChain operator* ( const Coefficient_ring & lambda,
const SparseChain & chain )
friend

Multiplies each coefficient of chain by lambda.

Parameters
lambdaThe factor to apply.
chainThe chain.
Returns
A new chain representing the result.

◆ operator* [2/3]

Coefficient_ring operator* ( const Sparse_chain & row,
const Sparse_chain & column )
friend

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

Precondition
Chains must have the same Coefficient_ring.
row.is_row() and column.is_column() must be true
Warning
Will raise an error if the chains do not have the same Coefficient_ring.
Parameters
rowThe row chain.
columnThe column chain.
Returns
The result of type Coefficient_ring.

◆ operator* [3/3]

Sparse_matrix_derived< Coefficient_ring, COLUMN > operator* ( const SparseChain & column,
const SparseChain & 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 Coefficient_ring.
column.is_column() and row.is_row() must be true
Warning
Will raise an error if chains do not have the same Coefficient_ring.
Parameters
columnThe column chain.
rowThe row chain.
Returns
The result of the matrix multiplication, column-based.

◆ operator/ [1/2]

SparseChain operator/ ( const SparseChain & chain,
const std::vector< size_t > & indices )
friend

Gets a subchain from the chain.

Returns a copy of 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
indicesThe indices to remove.
Returns
A new chain representing the result.

◆ operator/ [2/2]

SparseChain operator/ ( const SparseChain & chain,
size_t index )
friend

Gets a subchain from the chain.

Returns a copy of chain where the coefficient at a given index is removed.

Parameters
indexThe index to remove.

◆ operator<<

std::ostream & operator<< ( std::ostream & stream,
const SparseChain & chain )
friend

Inserts chain in the output stream with a compact "user friendly" format.

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

◆ operator==

bool operator== ( const Sparse_chain & chain,
const Sparse_chain & other )
friend

Tests if two chains are equal.

If the storage formats of chains differ, return false, otherwise, tests if all coefficients are equal.

Parameters
chainFirst chain to compare.
otherSecond chain to compare.

◆ read_chain [1/2]

template<typename _CT, int _SF>
std::istream & read_chain ( Sparse_chain< _CT, _SF > & chain,
std::istream & in )
friend

Reads a sparse chain from an input stream using the .osm file format.

Loads a sparse chain (the chain can be exported using write_chain), see OSM file format documentation.

◆ read_chain [2/2]

template<typename _CT, int _SF>
void read_chain ( Sparse_chain< _CT, _SF > & chain,
std::string filename )
friend

Reads a sparse chain from a file using the .osm file format.

Loads a sparse chain (the chain can be exported using write_chain), see OSM file format documentation.

◆ write_chain [1/2]

template<typename _CT, int _SF>
std::ostream & write_chain ( const Sparse_chain< _CT, _SF > & chain,
std::ostream & out )
friend

Write a sparse chain to an output stream using the .osm file format.

Outputs a sparse chain (the chain can be reloaded using read_chain), see OSM file format documentation.

◆ write_chain [2/2]

template<typename _CT, int _SF>
void write_chain ( const Sparse_chain< _CT, _SF > & chain,
std::string filename )
friend

Write a sparse chain to a file using the .osm file format.

Outputs a sparse chain (the chain can be reloaded using read_chain), see OSM file format documentation.