CGAL::OSM Namespace Reference

Classes
class	Bitboard
	The class Bitboard implements an accelerating structure, derived from the chess community. More...
class	Full_lu
	The class Full_lu implements LU decomposition via full pivoting for an OSM::Sparse_matrix. More...
class	Sparse_chain
	The class Sparse_chain implements the concept SparseChain, that is, sparse vectors (encoding homological chains) optimized for topological computations. More...
struct	Sparse_matrix
	The structure Sparse_matrix provides a more friendly interface for sparse matrices built over a given SparseChainmodel (actually a Curryfication of the Sparse_matrix_core template). More...
class	Sparse_matrix_core
	The class Sparse_matrix_core implements the concept SparseMatrix, that is, sparse matrices optimized for topological computations. More...
struct	Sub_sparse_matrix
	The structure Sub_sparse_matrix provides a more friendly interface for sparse matrices built over a given SparseChainmodel (actually a Curryfication of the Sparse_matrix_core template). More...
class	Sub_sparse_matrix_core
	The class Sub_sparse_matrix_core is a technical class implementing the concept SparseMatrix together with a system of masks to partially screen matrices (and restrict computations to a subset of indices along their major direction). More...

Typedefs
typedef int	ZCoefficient
	The default type for signed integers.

Functions
template<typename CoefficientRing , int StorageFormat, typename SparseMatrix >
std::ostream &	operator<< (std::ostream &out, const Full_lu< CoefficientRing, StorageFormat, SparseMatrix > &lu)
template<typename _CT >
Sparse_matrix< OSM::Sparse_chain >::Sparse_matrix_type< _CT, COLUMN >	operator* (const Sparse_chain< _CT, COLUMN > &column, const Sparse_chain< _CT, ROW > &row)
template<typename _CT >
Sparse_matrix< OSM::Sparse_chain >::Sparse_matrix_type< _CT, ROW >	operator% (const Sparse_chain< _CT, COLUMN > &column, const Sparse_chain< _CT, ROW > &row)
template<typename CoefficientRing >
CoefficientRing	operator* (const Sparse_chain< CoefficientRing, ROW > &row, const Sparse_chain< CoefficientRing, COLUMN > &column)
template<typename _CT >
bool	operator== (const Sparse_chain< _CT, OSM::COLUMN > &chain, const Sparse_chain< _CT, OSM::COLUMN > &other)
template<typename _CT >
bool	operator== (const Sparse_chain< _CT, OSM::ROW > &chain, const Sparse_chain< _CT, OSM::ROW > &other)
template<typename _CT >
bool	operator== (const Sparse_chain< _CT, OSM::COLUMN > &, const Sparse_chain< _CT, OSM::ROW > &)
template<typename _CT >
bool	operator== (const Sparse_chain< _CT, OSM::ROW > &, const Sparse_chain< _CT, OSM::COLUMN > &)
template<typename _CT , int _CTF>
Sparse_chain< _CT, _CTF >	operator* (const Sparse_chain< _CT, _CTF > &chain, const _CT &lambda)
template<typename _CT , int _SF>
std::ostream &	write_chain (const Sparse_chain< _CT, _SF > &chain, std::ostream &out)
template<typename _CT , int _SF>
void	write_chain (Sparse_chain< _CT, _SF > chain, std::string filename)
template<typename _CT , int _SF>
std::istream &	read_chain (Sparse_chain< _CT, _SF > &chain, std::istream &in)
template<typename _CT , int _SF>
void	read_chain (Sparse_chain< _CT, _SF > &chain, std::string filename)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
Sparse_matrix_core< _CT, _CTF, SCT >	operator* (const Sparse_matrix_core< _CT, _CTF, SCT > &matrix, const _CT &lambda)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT >	operator* (const Sparse_matrix_core< _CT, COLUMN, SCT > &first, const Sparse_matrix_core< _CT, COLUMN, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT >	operator* (const Sparse_matrix_core< _CT, ROW, SCT > &first, const Sparse_matrix_core< _CT, COLUMN, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT >	operator* (const Sparse_matrix_core< _CT, COLUMN, SCT > &first, const Sparse_matrix_core< _CT, ROW, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT >	operator* (const Sparse_matrix_core< _CT, ROW, SCT > &first, const Sparse_matrix_core< _CT, ROW, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, COLUMN >	operator* (const Sparse_matrix_core< _CT, COLUMN, SCT > &first, const SCT< _CT, COLUMN > &second)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, COLUMN >	operator* (const Sparse_matrix_core< _CT, ROW, SCT > &first, const SCT< _CT, COLUMN > &second)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, ROW >	operator* (const SCT< _CT, ROW > &first, const Sparse_matrix_core< _CT, ROW, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, ROW >	operator* (const SCT< _CT, ROW > &first, const Sparse_matrix_core< _CT, COLUMN, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT >	operator% (const Sparse_matrix_core< _CT, COLUMN, SCT > &first, const Sparse_matrix_core< _CT, COLUMN, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT >	operator% (const Sparse_matrix_core< _CT, ROW, SCT > &first, const Sparse_matrix_core< _CT, COLUMN, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT >	operator% (const Sparse_matrix_core< _CT, COLUMN, SCT > &first, const Sparse_matrix_core< _CT, ROW, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT >	operator% (const Sparse_matrix_core< _CT, ROW, SCT > &first, const Sparse_matrix_core< _CT, ROW, SCT > &second)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT > &	operator+= (Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, const Sparse_matrix_core< _CT, ROW, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT > &	operator+= (Sparse_matrix_core< _CT, ROW, SCT > &matrix, const Sparse_matrix_core< _CT, COLUMN, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT > &	operator-= (Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, const Sparse_matrix_core< _CT, ROW, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT > &	operator-= (Sparse_matrix_core< _CT, ROW, SCT > &matrix, const Sparse_matrix_core< _CT, COLUMN, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT > &	operator*= (Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, const Sparse_matrix_core< _CT, COLUMN, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT > &	operator*= (Sparse_matrix_core< _CT, ROW, SCT > &matrix, const Sparse_matrix_core< _CT, ROW, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, COLUMN, SCT > &	operator*= (Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, const Sparse_matrix_core< _CT, ROW, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
Sparse_matrix_core< _CT, ROW, SCT > &	operator*= (Sparse_matrix_core< _CT, ROW, SCT > &matrix, const Sparse_matrix_core< _CT, COLUMN, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, COLUMN >	get_column (const Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, size_t index)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, COLUMN >	get_column (const Sparse_matrix_core< _CT, ROW, SCT > &matrix, size_t index)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, ROW >	get_row (const Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, size_t index)
template<typename _CT , template< typename, int > typename SCT>
SCT< _CT, ROW >	get_row (const Sparse_matrix_core< _CT, ROW, SCT > &matrix, size_t index)
template<typename _CT , template< typename, int > typename SCT>
const SCT< _CT, COLUMN > &	cget_column (const Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, size_t index)
template<typename _CT , template< typename, int > typename SCT>
const SCT< _CT, ROW > &	cget_row (const Sparse_matrix_core< _CT, ROW, SCT > &matrix, const size_t index)
template<typename _CT , template< typename, int > typename SCT>
void	set_column (Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, size_t index, const SCT< _CT, COLUMN > &chain)
template<typename _CT , template< typename, int > typename SCT>
void	set_column (Sparse_matrix_core< _CT, ROW, SCT > &matrix, size_t index, const SCT< _CT, COLUMN > &chain)
template<typename _CT , template< typename, int > typename SCT>
void	set_row (Sparse_matrix_core< _CT, COLUMN, SCT > &matrix, size_t index, const SCT< _CT, ROW > &chain)
template<typename _CT , template< typename, int > typename SCT>
void	set_row (Sparse_matrix_core< _CT, ROW, SCT > &matrix, size_t index, const SCT< _CT, ROW > &chain)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
void	set_coefficient (Sparse_matrix_core< _CT, _CTF, SCT > &matrix, size_t i, size_t j, const _CT d)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
_CT	get_coefficient (const Sparse_matrix_core< _CT, _CTF, SCT > &matrix, size_t i, size_t j)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
Sparse_matrix_core< _CT, _CTF, SCT > &	remove_column (Sparse_matrix_core< _CT, _CTF, SCT > &matrix, size_t index)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
Sparse_matrix_core< _CT, _CTF, SCT > &	remove_row (Sparse_matrix_core< _CT, _CTF, SCT > &matrix, size_t index)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
Sparse_matrix_core< _CT, _CTF, SCT > &	remove_coefficient (Sparse_matrix_core< _CT, _CTF, SCT > &matrix, size_t i, size_t j)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
Sparse_matrix_core< _CT, _CTF, SCT > &	swap_rows (Sparse_matrix_core< _CT, _CTF, SCT > &matrix, size_t i, size_t j)
template<typename _CT , int _CTF, template< typename, int > typename SCT>
Sparse_matrix_core< _CT, _CTF, SCT > &	swap_columns (Sparse_matrix_core< _CT, _CTF, SCT > &matrix, size_t i, size_t j)
template<typename _CT , template< typename, int > typename SCT>
std::ostream &	write_matrix (const Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &M, std::ostream &out)
template<typename _CT , template< typename, int > typename SCT>
std::ostream &	write_matrix (const Sparse_matrix_core< _CT, OSM::ROW, SCT > &M, std::ostream &out)
template<typename _CT , template< typename, int > typename SCT>
void	write_matrix (const Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &M, std::string filename)
template<typename _CT , template< typename, int > typename SCT>
void	write_matrix (const Sparse_matrix_core< _CT, OSM::ROW, SCT > &M, std::string filename)
template<typename _CT , template< typename, int > typename SCT>
std::istream &	read_matrix (Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &M, std::istream &in)
template<typename _CT , template< typename, int > typename SCT>
std::istream &	read_matrix (Sparse_matrix_core< _CT, OSM::ROW, SCT > &M, std::istream &in)
template<typename _CT , template< typename, int > typename SCT>
void	read_matrix (Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &M, std::string filename)
template<typename _CT , template< typename, int > typename SCT>
void	read_matrix (Sparse_matrix_core< _CT, OSM::ROW, SCT > &M, std::string filename)
template<typename _CT , template< typename, int > typename SCT>
bool	operator== (const Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &matrix, const Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
bool	operator== (const Sparse_matrix_core< _CT, OSM::ROW, SCT > &matrix, const Sparse_matrix_core< _CT, OSM::ROW, SCT > &other)
template<typename _CT , template< typename, int > typename SCT>
bool	operator== (const Sparse_matrix_core< _CT, OSM::ROW, SCT > &, const Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &)
template<typename _CT , template< typename, int > typename SCT>
bool	operator== (const Sparse_matrix_core< _CT, OSM::COLUMN, SCT > &, const Sparse_matrix_core< _CT, OSM::ROW, SCT > &)

Variables
const int	COLUMN = 0b01
	StorageFormat for column chain.
const int	ROW = 0b10
	StorageFormat flag for row chain.
const size_t	size_t_maxvalue = std::numeric_limits<size_t>::max()
const int	tab64 [64]
const int	index64 [64]

Function Documentation

cget_column()

template<typename _CT , template< typename, int > typename SCT>

const SCT< _CT, COLUMN > & CGAL::OSM::cget_column ( const Sparse_matrix_core< _CT, COLUMN, SCT > &  matrix, size_t  index  )

related

Constant time get.

Warning

The matrix will perform boundary check.

Parameters

matrix	The matrix considered.
index	The column index.

Returns

A constant reference over the column stored at given index.

Examples

HDVF/matrix_chain.cpp.

cget_row()

template<typename _CT , template< typename, int > typename SCT>

const SCT< _CT, ROW > & CGAL::OSM::cget_row ( const Sparse_matrix_core< _CT, ROW, SCT > &  matrix, const size_t  index  )

related

Constant time get.

Warning

The matrix will perform boundary check.

Parameters

matrix	The matrix considered.
index	The row index.

Returns

A const reference over the row stored at given index.

get_coefficient()

template<typename _CT , int _CTF, template< typename, int > typename SCT>

_CT CGAL::OSM::get_coefficient ( const Sparse_matrix_core< _CT, _CTF, SCT > &  matrix, size_t  i, size_t  j  )

related

Returns the coefficient on row i and column j of the matrix.

Warning

The matrix will perform boundary check.

Parameters

matrix	Constant reference on the matrix.
i	The row index.
j	The column index.

Returns

The value of the given coefficient.

operator%()

template<typename _CT >

Sparse_matrix< OSM::Sparse_chain >::Sparse_matrix_type< _CT, ROW > CGAL::OSM::operator% ( const Sparse_chain< _CT, COLUMN > &  column, const Sparse_chain< _CT, ROW > &  row  )

related

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*()

template<typename _CT >

Sparse_matrix< OSM::Sparse_chain >::Sparse_matrix_type< _CT, COLUMN > CGAL::OSM::operator* ( const Sparse_chain< _CT, COLUMN > &  column, const Sparse_chain< _CT, ROW > &  row  )

related

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.

remove_coefficient()

template<typename _CT , int _CTF, template< typename, int > typename SCT>

Sparse_matrix_core< _CT, _CTF, SCT > & CGAL::OSM::remove_coefficient ( Sparse_matrix_core< _CT, _CTF, SCT > &  matrix, size_t  i, size_t  j  )

related

Removes coefficient at row i and column j.

Parameters

matrix	Reference on the matrix to modify.
i	Index of the row
j	Index of the column

Returns

The modified matrix representing the result.

remove_column()

template<typename _CT , int _CTF, template< typename, int > typename SCT>

Sparse_matrix_core< _CT, _CTF, SCT > & CGAL::OSM::remove_column ( Sparse_matrix_core< _CT, _CTF, SCT > &  matrix, size_t  index  )

related

Removes column of index index whatever the StorageFormat of the matrix. For column matrices, it just comes to the \= operator and for row matrices, it entails a traversal of the matrix.

Parameters

matrix	Reference on the matrix to modify.
index	The index to remove.

Returns

A reference over the modified matrix.

remove_row()

template<typename _CT , int _CTF, template< typename, int > typename SCT>

Sparse_matrix_core< _CT, _CTF, SCT > & CGAL::OSM::remove_row ( Sparse_matrix_core< _CT, _CTF, SCT > &  matrix, size_t  index  )

related

Removes row of index index whatever the StorageFormat of the matrix. For row matrices, it just comes to the \= operator and for column matrices, it entails a traversal of the matrix.

Parameters

matrix	Reference on the matrix to modify.
index	The index to remove.

Returns

A reference over the modified matrix.

set_coefficient()

template<typename _CT , int _CTF, template< typename, int > typename SCT>

void CGAL::OSM::set_coefficient ( Sparse_matrix_core< _CT, _CTF, SCT > &  matrix, size_t  i, size_t  j, const _CT  d  )

related

Assign the scalar d to the coefficient on row i and column j.

Warning

The matrix will perform boundary check.

Parameters

matrix	Reference on the matrix to modify.
i	The row index.
j	The column index.
d	The value.

Examples

HDVF/matrix_chain.cpp.

swap_columns()

template<typename _CT , int _CTF, template< typename, int > typename SCT>

Sparse_matrix_core< _CT, _CTF, SCT > & CGAL::OSM::swap_columns ( Sparse_matrix_core< _CT, _CTF, SCT > &  matrix, size_t  i, size_t  j  )

related

Swaps columns at indices i and j whatever the StorageFormat of the matrix. For column matrices, the operation runs in constant time, while it entails a traversal of the matrix for row matrices.

Parameters

matrix	Reference on the matrix to modify.
i	Index of the first column.
j	Index of the second column.

Returns

A reference over the modified matrix.

swap_rows()

template<typename _CT , int _CTF, template< typename, int > typename SCT>

Sparse_matrix_core< _CT, _CTF, SCT > & CGAL::OSM::swap_rows ( Sparse_matrix_core< _CT, _CTF, SCT > &  matrix, size_t  i, size_t  j  )

related

Swaps rows at indices i and j whatever the StorageFormat of the matrix. For row matrices, the operation runs in constant time, while it entails a traversal of the matrix for column matrices.

Parameters

matrix	Reference on the matrix to modify.
i	Index of the first row.
j	Index of the second row.

Returns

A reference over the modified matrix.

Variable Documentation

index64

const int CGAL::OSM::index64[64]

Initial value:

= {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
}

tab64

const int CGAL::OSM::tab64[64]

Initial value:

= {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5
}