#include <CGAL/OSM/Sparse_chain.h>

Definition

template<typename CoefficientRing, int StorageFormat>
class CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >

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 StorageFormat parameter determines this storage format).

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

CoefficientRing	a model of the `IntegralDomainWithoutDivision` concept, providing the ring used to compute homology.
StorageFormat	an integer constant encoding the storage format of matrices (`CGAL::OSM::COLUMN` or `CGAL::OSM::ROW`).

Examples: HDVF/main_hdvf.cpp, and HDVF/matrix_chain.cpp.

Public Types
typedef CoefficientRing	Coefficient_ring
	Type of the coefficient ring.

typedef std::unordered_map< size_t, CoefficientRing >::iterator	iterator
	Type of chains iterators.

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

Public Member Functions
	Sparse_chain ()
	Creates new empty sparse chain.

	Sparse_chain (const size_t chain_size)
	Creates new empty sparse chain (ie.

	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 two chains.

Sparse_chain	operator- (const Sparse_chain &other)
	Subtracts a chain from current chain.

Sparse_chain	operator* (const CoefficientRing &lambda)
	Applies multiplication on each coefficient.

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 CoefficientRing &lambda)
	Applies multiplication on each coefficient of `this`.

Coefficient_ring	operator[] (size_t index) const
	Gets the value of a coefficient of the chain.

Coefficient_ring	get_coefficient (size_t index) const
	Gets the value of a coefficient of the chain.

void	set_coefficient (size_t index, Coefficient_ring 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)
	Gets a subchain from the chain.

Sparse_chain	operator/ (size_t index)
	Gets a subchain from the chain.

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< CoefficientRing, COLUMN+ROW - StorageFormat >	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, CoefficientRing >	pair

Protected Attributes
std::unordered_map< size_t, CoefficientRing >	_chainData

size_t	_upperBound

Friends
template<typename _CT , int _CTF>
class	Sparse_chain

template<typename _CT , int _CTF>
class	Sparse_matrix

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.

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &stream, const Sparse_chain &chain)
	writes a sparse chain in the output stream.

template<int _CTF>
Sparse_chain	operator* (const CoefficientRing &lambda, const Sparse_chain< CoefficientRing, _CTF > &chain)
	Applies multiplication on each coefficient.

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

Constructor & Destructor Documentation

◆ Sparse_chain() [1/3]

template<typename CoefficientRing , int StorageFormat>

CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::Sparse_chain ( )

Creates new empty sparse chain.

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

◆ Sparse_chain() [2/3]

template<typename CoefficientRing , int StorageFormat>

CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::Sparse_chain ( const size_t chain_size )

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.

Parameters

chain_size The size of the sparse chain.

◆ Sparse_chain() [3/3]

template<typename CoefficientRing , int StorageFormat>

CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::Sparse_chain ( const Sparse_chain< CoefficientRing, StorageFormat > & otherToCopy )

Creates new SparseChain by copy.

Copy constructor, initialize a sparse chain from an existing sparse chain.

Precondition: The chains have the same CoefficientRing and StorageFormat.

Parameters

otherToCopy The chain to copy.

Member Function Documentation

◆ begin() [1/2]

template<typename CoefficientRing , int StorageFormat>

const_iterator CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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 CoefficientRing , int StorageFormat>

iterator CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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()

template<typename CoefficientRing , int StorageFormat>

const_iterator CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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 CoefficientRing , int StorageFormat>

const_iterator CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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 CoefficientRing , int StorageFormat>

size_t CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::dimension ( ) const

Size of the chain.

Returns: Size allocated for the chain.

◆ end() [1/2]

template<typename CoefficientRing , int StorageFormat>

const_iterator CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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]

template<typename CoefficientRing , int StorageFormat>

iterator CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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()

template<typename CoefficientRing , int StorageFormat>

Coefficient_ring CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::get_coefficient ( size_t index ) const

Gets the value of a coefficient of the chain.

Warning: The chain will perform boundary check.

Parameters

index The coefficient index.

Returns: The value of the coefficient.

◆ is_column()

template<typename CoefficientRing , int StorageFormat>

bool CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::is_column ( ) const

Checks if chain is a column.

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

◆ is_null() [1/2]

template<typename CoefficientRing , int StorageFormat>

const bool CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::is_null ( ) const

Checks if the chain is null.

Returns: True if the chain is null.

◆ is_null() [2/2]

template<typename CoefficientRing , int StorageFormat>

const bool CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::is_null ( size_t index ) const

Checks if a coefficient is null.

Parameters

index The index to check.

Returns: True if the data is null at given index.

◆ is_row()

template<typename CoefficientRing , int StorageFormat>

bool CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::is_row ( ) const

Checks if chain is a row.

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

◆ nullify()

template<typename CoefficientRing , int StorageFormat>

void CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::nullify ( )

Removes all coefficients from the chain.

The function comes to set all coefficients to zero.

◆ operator*()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator* ( const CoefficientRing & lambda )

Applies multiplication on each coefficient.

Parameters

lambda The factor to apply.

Returns: A new chain representing the result.

◆ operator*=()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator*= ( const CoefficientRing & lambda )

Applies multiplication on each coefficient of this.

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

Parameters

lambda The factor to apply.

Returns: The modified chain representing the result.

◆ operator+()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator+ ( const Sparse_chain< CoefficientRing, StorageFormat > & other )

Adds two chains.

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

Precondition: Chains must have the same CoefficientRing and the same StorageFormat.

Warning: Will raise an error if the two chains are not the same CoefficientRing.; Will raise a compilation error if the two chains don't have the same StorageFormat.

Parameters

other The other chain.

Returns: A new chain representing the result.

◆ operator+=()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator+= ( const Sparse_chain< CoefficientRing, StorageFormat > & other )

Adds a chain to this.

Add a chain to this.

Precondition: Chains must have the same CoefficientRing and the same StorageFormat.

Warning: Will raise an error if the two chains are not the same CoefficientRing.; Will raise an error if the two chains don't have the same StorageFormat.

Parameters

other The other chain.

Returns: The modified chain representing the result.

◆ operator-()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator- ( const Sparse_chain< CoefficientRing, StorageFormat > & other )

Subtracts a chain from current chain.

Subtract other chain from current chain and return the result in a new matrix.

Precondition: Chains must have the same CoefficientRing and the same StorageFormat.

Warning: Will raise an error if the two chains are not the same CoefficientRing.; Will raise a compilation error if the two chains don't have the same StorageFormat.

Parameters

other The other chain.

Returns: A new chain representing the result.

◆ operator-=()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator-= ( const Sparse_chain< CoefficientRing, StorageFormat > & other )

Sustracts a chain to this.

Subtract a chain to this.

Precondition: Chains must have the same CoefficientRing and the same StorageFormat.

Warning: Will raise an error if the two chains are not the same CoefficientRing.; Will raise an error if the two chains don't have the same StorageFormat.

Parameters

other The other chain.

Returns: The modified chain representing the result.

◆ operator/() [1/2]

template<typename CoefficientRing , int StorageFormat>

Sparse_chain CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator/ ( const std::vector< size_t > & indices )

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

indices The indices to remove.

Returns: A new chain representing the result.

◆ operator/() [2/2]

template<typename CoefficientRing , int StorageFormat>

Sparse_chain CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator/ ( size_t index )

Gets a subchain from the chain.

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

Parameters

index The index to remove.

◆ operator/=() [1/2]

template<typename CoefficientRing , int StorageFormat>

Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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

index The index to remove.

Returns: Return a reference to the modified chain.

◆ operator/=() [2/2]

template<typename CoefficientRing , int StorageFormat>

Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::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

indices The indices to remove.

Returns: Return a reference to the modified chain.

◆ operator=()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain & CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator= ( const Sparse_chain< CoefficientRing, StorageFormat > & 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 CoefficientRing.

Parameters

otherToCopy The chain we want to copy.

◆ operator[]()

template<typename CoefficientRing , int StorageFormat>

Coefficient_ring CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::operator[] ( size_t index ) const

Gets the value of a coefficient of the chain.

Warning: The chain will perform boundary check.

Parameters

index The coefficient index.

Returns: The value of the coefficient.

◆ set_coefficient()

template<typename CoefficientRing , int StorageFormat>

void CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::set_coefficient	(	size_t	index,
		Coefficient_ring	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

index	The coefficient index.
d	Value of the coefficient

◆ transpose()

template<typename CoefficientRing , int StorageFormat>

Sparse_chain< CoefficientRing, COLUMN+ROW - StorageFormat > CGAL::OSM::Sparse_chain< CoefficientRing, StorageFormat >::transpose ( )

Transposes a sparse chain.

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

Returns: A new chain where the StorageFormat is changed.

Friends And Related Function Documentation

◆ operator%

template<typename CoefficientRing , int StorageFormat>

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 CoefficientRing.

Warning: Will raise an error if chains do not have the same CoefficientRing.

Parameters

column	The column chain.
row	The row chain.

Returns: The result of the matrix multiplication, row-based.

◆ operator* [1/3]

template<typename CoefficientRing , int StorageFormat>

template<int _CTF>

Sparse_chain operator*	(	const CoefficientRing &	lambda,
		const Sparse_chain< CoefficientRing, _CTF > &	chain
	)

friend

Applies multiplication on each coefficient.

Parameters

lambda	The factor to apply.
chain	The chain.

Returns: A new chain representing the result.

◆ operator* [2/3]

template<typename CoefficientRing , int StorageFormat>

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 CoefficientRing.

Warning: Will raise an error if chains do not have the same CoefficientRing.

Parameters

column	The column chain.
row	The row chain.

Returns: The result of the matrix multiplication, column-based.

◆ operator* [3/3]

template<typename CoefficientRing , int StorageFormat>

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 CoefficientRing.

Warning: Will raise an error if the chains do not have the same CoefficientRing.

Parameters

row	The row chain.
column	The column chain.

Returns: The result of type CoefficientRing.

◆ operator<<

template<typename CoefficientRing , int StorageFormat>

std::ostream & operator<<	(	std::ostream &	stream,
		const Sparse_chain< CoefficientRing, StorageFormat > &	chain
	)

friend

writes a sparse chain in the output stream.

Parameters

stream	The output stream.
chain	The chain to display.

Returns: A reference to the modified stream.

Definition

Public Types

Public Member Functions

Protected Types

Protected Attributes

Friends

Related Functions

Constructor & Destructor Documentation

◆ Sparse_chain() [1/3]

◆ Sparse_chain() [2/3]

◆ Sparse_chain() [3/3]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ dimension()

◆ end() [1/2]

◆ end() [2/2]

◆ get_coefficient()

◆ is_column()

◆ is_null() [1/2]

◆ is_null() [2/2]

◆ is_row()

◆ nullify()

◆ operator*()

◆ operator*=()

◆ operator+()

◆ operator+=()

◆ operator-()

◆ operator-=()

◆ operator/() [1/2]

◆ operator/() [2/2]

◆ operator/=() [1/2]

◆ operator/=() [2/2]

◆ operator=()

◆ operator[]()

◆ set_coefficient()

◆ transpose()

Friends And Related Function Documentation

◆ operator%

◆ operator* [1/3]

◆ operator* [2/3]

◆ operator* [3/3]

◆ operator<<