lti::sparseMatrix< T > Class Template Reference
[Aggregate Data Types, Linear Algebra]

SparseMatrix container class. More...

#include <ltiSparseMatrix.h>

Inheritance diagram for lti::sparseMatrix< T >:

[legend]

Collaboration diagram for lti::sparseMatrix< T >:

[legend]

List of all members.

Public Types
typedef T	value_type
typedef std::vector< T >::iterator	iterator
typedef std::vector< T > ::const_iterator	const_iterator
Public Member Functions
	sparseMatrix ()
	sparseMatrix (const int theRows, const int theCols, const T &sparseVal=T())
	sparseMatrix (const point &size, const T &sparseVal=T())
	sparseMatrix (const sparseMatrix< T > &other)
virtual	~sparseMatrix ()
bool	resize (const int rows, const int cols, const T &sparseVal)
bool	resize (const point &size, const T &sparseVal)
sparseMatrix< T > &	castFrom (const matrix< T > &srcMatrix, const T &sValue)
sparseMatrix< T > &	castFrom (const matrix< T > &srcMatrix)
template<class U >
sparseMatrix< T > &	castFrom (const sparseMatrix< U > &other)
bool	castTo (matrix< T > &destMatrix)
sparseMatrix< T > &	copy (const sparseMatrix< T > &other)
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
const T &	at (const int row, const int col) const
const T &	getAt (const int row, const int col) const
T &	forceAt (const int row, const int col)
T &	forceAt (const point &p)
bool	setAt (const int row, const int col, const T newValue)
bool	setAt (const point &position, const T newValue)
void	fill (const T &iniValue, const int &fromRow=0, const int &fromCol=0, const int &toRow=MaxInt32, const int &toCol=MaxInt32)
void	clear ()
bool	empty () const
point	getPosition (const iterator &iter)
point	getPosition (const const_iterator &iter)
lti::vector< T >	getRowCopy (const int &row) const
lti::vector< T >	getColumnCopy (const int &col) const
virtual const char *	getTypeName () const
virtual mathObject *	clone () const
sparseMatrix< T > &	operator= (const sparseMatrix< T > &other)
bool	operator== (const sparseMatrix< T > other) const
const point &	size () const
int	getNumNonSparseValues () const
T	getSparseValue () const
const int &	columns () const
const int &	rows () const
Arithmetical Operations

sparseMatrix< T > &	operator+= (const T value)
sparseMatrix< T >	operator+ (const T value) const
sparseMatrix< T > &	operator*= (const T value)
sparseMatrix< T > &	add (const T value)
sparseMatrix< T > &	divide (const T value)
sparseMatrix< T > &	multiply (const T value)
void	multiply (const vector< T > &srcVec, vector< T > &destVec) const
sparseMatrix< T >	transpose ()
T	maximum () const
point	getIndexOfMaximum () const
T	minimum () const
point	getIndexOfMinimum () const
Input and Output

virtual bool	write (ioHandler &handler, const bool complete=true) const
virtual bool	read (ioHandler &handler, const bool complete=true)


const std::vector< T > &	getValues () const
const std::vector< int > &	getColIndex () const
const lti::vector< int > &	getRowPtr () const

Detailed Description

template<class T>
class lti::sparseMatrix< T >

SparseMatrix container class.

The lti::sparseMatrix class allows the representation of n x m matrices as sparse matrices (SM).

The SM class is a container class implemented as template.

All types defined in ltiTypes.h except bool can be contained.

A matrix is normaly defined as sparse if it contains a lot of zeros, in this class you can use an arbitrary value denoted with sparseValue.

Only the non-sparse values of the matrix are saved in the container using the Compressed Row Storage format.

Due to the characteristics of the storage, the method at() is here a read-only one. To write values into the matrix use the setAt() or forceAt() methods.

The Compressed Row Storage (CRS) format puts the subsequent nonsparse values of the matrix rows in contiguous memory locations.

The CRS format uses three vectors to store the non sparse values:

values, type of T
colIndex, type of int
rowPtr, type of int

In the values vector are saved the values of the non sparse elements of the matrix, as they are traversed in a row-wise fashion.

The colIndex vector stores the column indices of the elements in the values vector.

The rowPtr vector stores the position in the values vector that start a new row. The vector size is equal number of rows plus one. The last value in the rowPtr vector is needed to calculate the number of elements in the last row of the matrix.

Example:

 matrix A = ( 0  2  5  0
              1  0  0  0
              0  4  0  6 )

The CRS format for the matrix A is specified by the vectors given below:

 values   = ( 2  5  1  4  6 )
 colIndex = ( 1  2  0  1  3 )

 rowPtr   = ( 0  2  3  5 )

The iterators of the sparse matrices visit only the non sparse values, as this is usually the required task.

You can use the getPosition() methods to gain the index of the element pointed by an iterator. If for each non-sparse element you need to compute its index, it is more efficient to avoid iterators and using the data structures of the CRS directly:

 // assume you are in a template class/method of type T, or that type
 // T is somehow defined (for example typedef float T)

 lti::point p; // the coordinates
 lti::sparseMatrix<T> smat; 

 // ... fill the sparse matrix with data here

 const lti::ivector& rows     = smat.getRowPtr();
 const std::vector<int>& cols = smat.getColIndex();
 const std::vector<T>& vals   = smat.getValues();

 int i,f,l;
 T val; 

 // for each row
 for (p.y=0;p.y<rows.lastIdx();++p.y) {
   f=rows.at(p.y);       // first row element
   l=rows.at(p.y+1);     // last row element
   for (i=f;i<l;++i) { // for each element in row
     p.x=cols[i];
     val=vals[i];
     // the matrix element at \c p contains value \c val
     // here you can do whatever you need to...
   }
 }

Member Typedef Documentation

template<class T>

typedef std::vector<T>::const_iterator lti::sparseMatrix< T >::const_iterator

const_iterator the const_iterator points to one element of the values vector you only have access to these values, not to the sparseValues

template<class T>

typedef std::vector<T>::iterator lti::sparseMatrix< T >::iterator

iterator the iterator points to one element of the values vector you only have access to these values, not to the sparseValues

template<class T>

typedef T lti::sparseMatrix< T >::value_type

type of the contained data

Constructor & Destructor Documentation

template<class T>

lti::sparseMatrix< T >::sparseMatrix ( )

default constructor creates an empty sparseMatrix

template<class T>

lti::sparseMatrix< T >::sparseMatrix	(	const int	theRows,
		const int	theCols,
		const T &	sparseVal = `T()`
	)

construct a sparse matrix of the given size and fill it with the given value (i.e.

use the given value as sparse value).

template<class T>

lti::sparseMatrix< T >::sparseMatrix	(	const point &	size,
		const T &	sparseVal = `T()`
	)

construct a sparse matrix of the given size and fill it with the given value (i.e.

use the given value as sparse value).

template<class T>

lti::sparseMatrix< T >::sparseMatrix ( const sparseMatrix< T > & other )

copy constructor.

create this sparseMatrix as a connected copy of another sparseMatrix for this const version, the data will be always copied!

Parameters:

other

the sparseMatrix to be copied.

template<class T>

virtual lti::sparseMatrix< T >::~sparseMatrix ( ) [virtual]

destructor

Member Function Documentation

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::add ( const T value )

add a constant value to all elements of the matrix and leave the result here

Parameters:

value

the constant value

Returns:: return a reference to the actual matrix

template<class T>

const T& lti::sparseMatrix< T >::at	(	const int	row,
		const int	col
	)			const `[inline]`

access element at the given row and column

Parameters:

	row	the row of the element
	col	the column of the element

Returns:: a reference to the matrix element

References lti::sparseMatrix< T >::getAt().

template<class T>

const_iterator lti::sparseMatrix< T >::begin ( ) const

const_iterator begin

template<class T>

iterator lti::sparseMatrix< T >::begin ( )

iterator begin

template<class T>

template<class U >

sparseMatrix<T>& lti::sparseMatrix< T >::castFrom ( const sparseMatrix< U > & other ) [inline]

convert the other sparse matrix of type U to this sparse matrix of type T

References lti::sparseMatrix< T >::getColIndex(), lti::sparseMatrix< T >::getNumNonSparseValues(), lti::sparseMatrix< T >::getRowPtr(), lti::sparseMatrix< T >::getValues(), and lti::sparseMatrix< T >::size().

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::castFrom ( const matrix< T > & srcMatrix )

convert matrix to SparseMatrix

The value of the srcMatrix used as sparseValue is chosen by statistical evaluation (the most used one), which of course cost some time.

Parameters:

srcMatrix

the matrix to be converted into a sparseMatrix

Returns:: a reference to this object.

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::castFrom	(	const matrix< T > &	srcMatrix,
		const T &	sValue
	)

convert matrix to SparseMatrix

Parameters:

	srcMatrix	the matrix converted to sparseMatrix
	sValue	the value of srcMatrix used as sparseValue in the sparseMatrix

Returns:: a reference to this object.

template<class T>

bool lti::sparseMatrix< T >::castTo ( matrix< T > & destMatrix )

convert SparseMatrix to matrix

Parameters:

destMatrix

the lti::matrix where this sparseMatrix will be copied into.

template<class T>

void lti::sparseMatrix< T >::clear ( )

clear sparseMatrix to get a empty sparseMatrix sparseValue is set to zero

template<class T>

virtual mathObject* lti::sparseMatrix< T >::clone ( ) const [virtual]

create a clone of this matrix

Returns:: a pointer to a copy of this matrix

Implements lti::mathObject.

template<class T>

const int& lti::sparseMatrix< T >::columns ( ) const [inline]

return the number of columns of the matrix

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::copy ( const sparseMatrix< T > & other )

copy the contents of other to this object

Parameters:

other

the matrix to be copied

Reimplemented from lti::ioObject.

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::divide ( const T value )

devide the elements of the matrix by a constant value and leave the result here

Parameters:

value

the constant value (divisor)

Returns:: return a reference to the actual matrix

template<class T>

bool lti::sparseMatrix< T >::empty ( ) const

returns true if there are only "sparse values" on the matrix.

template<class T>

const_iterator lti::sparseMatrix< T >::end ( ) const

const_iterator end

template<class T>

iterator lti::sparseMatrix< T >::end ( )

iterator end

template<class T>

void lti::sparseMatrix< T >::fill	(	const T &	iniValue,
		const int &	fromRow = `0`,
		const int &	fromCol = `0`,
		const int &	toRow = `MaxInt32`,
		const int &	toCol = `MaxInt32`
	)

insert element at the given row and column

Parameters:

	iniValue	the value to fill the (sub-)matrix with
	fromRow	the row to begin fill
	fromCol	the column to begin fill
	toRow	the last row to fill
	toCol	the last col to fill

template<class T>

T& lti::sparseMatrix< T >::forceAt ( const point & p ) [inline]

get a read-write reference to the given element, and in case the element was a "sparse" one, insert it first.

References lti::sparseMatrix< T >::forceAt(), lti::tpoint< T >::x, and lti::tpoint< T >::y.

template<class T>

T& lti::sparseMatrix< T >::forceAt	(	const int	row,
		const int	col
	)

get a read-write reference to the given element, and in case the element was a "sparse" one, insert it first (with the sparse value.

You can for example use this method, when you want to increment the elements in a sparse matrix:

 sparseMatrix<int> sparseMat(1000,1000,0);
 sparseMat.setAt(row,col,getAt(row,col)+1);

is very inefficient, because the element at (row,col) must be search twice. On the other hand

 sparseMat.forceAt(row,col)++;

makes just one access to the point and returns a reference.

Note that if you just call forceAt without explicitelly changing the value thereafter, you will have sparseElement as normal elements in your matrix. So, please use with care. The normal way to reset a value with the sparseValue is using setAt(row,col,sparseValue).

Referenced by lti::sparseMatrix< T >::forceAt().

template<class T>

const T& lti::sparseMatrix< T >::getAt	(	const int	row,
		const int	col
	)			const

access element at the given row and column

Parameters:

	row	the row of the element
	col	the column of the element

Returns:: the value of the matrix element

Referenced by lti::sparseMatrix< T >::at().

template<class T>

const std::vector<int>& lti::sparseMatrix< T >::getColIndex ( ) const

returns colIndex vector vector of int

Referenced by lti::sparseMatrix< T >::castFrom().

template<class T>

lti::vector<T> lti::sparseMatrix< T >::getColumnCopy ( const int & col ) const

get a copy of the column of the matrix

Parameters:

col

the column to be accessed

Returns:: a vector with the contents of the column of the matrix

template<class T>

point lti::sparseMatrix< T >::getIndexOfMaximum ( ) const

get index of maximum value of the matrix

Returns:: return a copy of the index as a point

template<class T>

point lti::sparseMatrix< T >::getIndexOfMinimum ( ) const

get index of minimum value of the matrix

Returns:: return a copy of the index as a point

template<class T>

int lti::sparseMatrix< T >::getNumNonSparseValues ( ) const

returns the number of non-sparse valued elements in the sparseMatrix

Referenced by lti::sparseMatrix< T >::castFrom().

template<class T>

point lti::sparseMatrix< T >::getPosition ( const const_iterator & iter )

get the position in the matrix of the const_iterator

Parameters:

iter

const_iterator that points to a non-sparse element

Returns:: point with index of the pointed element

template<class T>

point lti::sparseMatrix< T >::getPosition ( const iterator & iter )

get the position in the matrix of the iterator

Parameters:

iter

iterator that points to a non-sparse element

Returns:: point with index of the pointed element

template<class T>

lti::vector<T> lti::sparseMatrix< T >::getRowCopy ( const int & row ) const

get a copy of the row of the matrix

Parameters:

row

the row to be accessed

Returns:: a vector with the contents of the row of the matrix

template<class T>

const lti::vector<int>& lti::sparseMatrix< T >::getRowPtr ( ) const

returns rowPtr vector vector of int

Referenced by lti::sparseMatrix< T >::castFrom().

template<class T>

T lti::sparseMatrix< T >::getSparseValue ( ) const

return the used sparse value

template<class T>

virtual const char* lti::sparseMatrix< T >::getTypeName ( ) const [virtual]

Returns:: the name of this class: "sparseMatrix"

Reimplemented from lti::mathObject.

template<class T>

const std::vector<T>& lti::sparseMatrix< T >::getValues ( ) const

Following methods allow the access to the internal data structures, which can be used to access very efficiently the non-sparse elements in the rows of the matrix.

returns values vector

Referenced by lti::sparseMatrix< T >::castFrom().

template<class T>

T lti::sparseMatrix< T >::maximum ( ) const

get maximum value of the matrix

Returns:: return a copy of this value

template<class T>

T lti::sparseMatrix< T >::minimum ( ) const

get minimum value of the matrix

Returns:: return a copy of this value

template<class T>

void lti::sparseMatrix< T >::multiply	(	const vector< T > &	srcVec,
		vector< T > &	destVec
	)			const

multiply sparseMatrix with vector, write result to a new vector

Parameters:

	srcVec	vector to be multiplied with, Its dimension must be equal to the number of columns of the matrix.
	destVec	vector to write result to Its dimension will be equal to the number of rows of the matrix.

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::multiply ( const T value )

multiply the elements of the matrix by a constant value and leave the result there

Parameters:

value

the constant value

Returns:: a reference to the actual matrix

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::operator*= ( const T value )

alias for multiply(const T value)

Parameters:

value

the constant value

Returns:: a reference to the actual matrix

template<class T>

sparseMatrix<T> lti::sparseMatrix< T >::operator+ ( const T value ) const

add a constant value to this matrix and leave result in new matrix

Parameters:

value

the value added to each element of the matrix

Returns:: a new matrix with the result

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::operator+= ( const T value )

alias for add(const T value)

Parameters:

value

the value added to each element of the matrix

Returns:: a reference to the actual matrix

template<class T>

sparseMatrix<T>& lti::sparseMatrix< T >::operator= ( const sparseMatrix< T > & other )

assignment operator (alias for copy(other))

Parameters:

other

the matrix to be copied

Returns:: a reference to the actual matrix

Reimplemented from lti::ioObject.

template<class T>

bool lti::sparseMatrix< T >::operator== ( const sparseMatrix< T > other ) const

compare this sparseMatrix with other

Parameters:

other

the sparseMatrix to be compared with

Returns:: true if both sparseMatrices have the same SparseValue the same values-, colIndex- and rowPtr-vector

template<class T>

virtual bool lti::sparseMatrix< T >::read	(	ioHandler &	handler,
		const bool	complete = `true`
	)			`[virtual]`

read the object from the given ioHandler

Reimplemented from lti::mathObject.

template<class T>

bool lti::sparseMatrix< T >::resize	(	const point &	size,
		const T &	sparseVal
	)

resize the given sparse matrix and fill it with the given value.

It is not possible to keep the old data when resizing the matrix.

template<class T>

bool lti::sparseMatrix< T >::resize	(	const int	rows,
		const int	cols,
		const T &	sparseVal
	)

resize the given sparse matrix and fill it with the given value.

It is not possible to keep the old data when resizing the matrix.

template<class T>

const int& lti::sparseMatrix< T >::rows ( ) const [inline]

return the number of columns of the matrix

template<class T>

bool lti::sparseMatrix< T >::setAt	(	const point &	position,
		const T	newValue
	)			`[inline]`

modify element at point

Parameters:

	position	index of the element in sparseMatrix to be set
	newValue	new value for a matrix element

Returns:: true if existing value is changed or false if sparseValue is replaced by element

References lti::sparseMatrix< T >::setAt(), lti::tpoint< T >::x, and lti::tpoint< T >::y.

template<class T>

bool lti::sparseMatrix< T >::setAt	(	const int	row,
		const int	col,
		const T	newValue
	)

modify element at the given row and column

Parameters:

	row	the row of the element
	col	the column of the element
	newValue	new value for a matrix element

Returns:: true if existing value is changed or false if sparseValue is replaced by element

Referenced by lti::sparseMatrix< T >::setAt().

template<class T>

const point& lti::sparseMatrix< T >::size ( ) const

returns size of the sparseMatrix

Referenced by lti::sparseMatrix< T >::castFrom().

template<class T>

sparseMatrix<T> lti::sparseMatrix< T >::transpose ( )

transpose sparseMatrix

Returns:: return a reference to the sparseMatrix

template<class T>

virtual bool lti::sparseMatrix< T >::write	(	ioHandler &	handler,
		const bool	complete = `true`
	)			const `[virtual]`

write the object in the given ioHandler

Reimplemented from lti::mathObject.

The documentation for this class was generated from the following file:

ltiSparseMatrix.h

lti::sparseMatrix< T > Class Template Reference [Aggregate Data Types, Linear Algebra]

Public Types

Public Member Functions

Detailed Description

template<class T> class lti::sparseMatrix< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

lti::sparseMatrix< T > Class Template Reference
[Aggregate Data Types, Linear Algebra]

template<class T>
class lti::sparseMatrix< T >