abacus::SparVec Class Reference

Sparse vectors. More...

#include <ogdf/lib/abacus/sparvec.h>

Inheritance diagram for abacus::SparVec:

Public Member Functions
	SparVec (AbacusGlobal *glob, int size, const Array< int > &s, const Array< double > &c, double reallocFac=10.0)
	Creates a sparse vector and initializes support and coefficients. More...
	SparVec (AbacusGlobal *glob, int size, double reallocFac=10.0)
	Creates an empty sparse vector. More...
	SparVec (AbacusGlobal *glob, int size, int *s, double *c, double reallocFac=10.0)
	Creates a sparse vector and initializes support and coefficients. More...
	SparVec (const SparVec &rhs)
	Copy constructor. More...
	~SparVec ()
	The destructor. More...
void	clear ()
	Removes all nonzeros from the sparse vector. More...
double	coeff (int i) const
void	copy (const SparVec &vec)
	Copies vector vec. More...
void	insert (int s, double c)
	Adds a new support/coefficient pair to the vector. More...
void	leftShift (ArrayBuffer< int > &del)
	Deletes the elements listed in a buffer from the sparse vector. More...
int	nnz () const
	Returns the number of nonzero elements. More...
double	norm ()
	Returns the Euclidean norm of the sparse vector. More...
SparVec &	operator= (const SparVec &rhs)
	The assignment operator. More...
double	origCoeff (int i) const
void	realloc ()
	Increases the size of the sparse vector by reallocFac_ percent of the original size. More...
void	realloc (int newSize)
	Reallocates the sparse vector to a given length. More...
void	rename (Array< int > &newName)
	Replaces the index of the support by new names. More...
int	size () const
	Returns the maximal length of the sparse vector. More...
int	support (int i) const
Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor. More...

Protected Member Functions
void	rangeCheck (int i) const
	Checks whether i is a valid index. More...

Protected Attributes
double *	coeff_
	The array storing the corresponding nonzero coefficients. More...
AbacusGlobal *	glob_
	A pointer to the corresponding global object. More...
int	nnz_
	The number of stored elements ("nonzeros"). More...
double	reallocFac_
	If a new element is inserted but the sparse vector is full, then its size is increased by reallocFac_ percent. More...
int	size_
	The maximal number of nonzero coefficients which can be stored without reallocation. More...
int *	support_
	The array storing the nonzero variables. More...

Friends
std::ostream &	operator<< (std::ostream &out, const SparVec &rhs)
	The output operator. More...

Additional Inherited Members
Static Public Member Functions inherited from abacus::AbacusRoot
static bool	ascii2bool (const string &str)
	Converts the string str to a boolean value. More...
static bool	endsWith (const string &str, const string &end)
	Returns true if str ends with end, false otherwise. More...
static double	fracPart (double x)
	Returns the absolute value of the fractional part of x. More...
static const char *	onOff (bool value)
	Converts a boolean variable to the strings "on" and "off". More...

Detailed Description

Sparse vectors.

If the number of components of a vector having nonzero coefficients is small (sparse), then it is more adequate to store only the number of these components together with the nonzero coefficients.

Since other classes, e.g., the class Row are derived from this class, all data members are protected in order to provide efficient access also in these derived classes.

Definition at line 47 of file sparvec.h.

Constructor & Destructor Documentation

SparVec() [1/4]

abacus::SparVec::SparVec	(	AbacusGlobal *	glob,
		int	size,
		double	reallocFac = 10.0
	)

Creates an empty sparse vector.

If no memory for support_ and coeff_ is allocated then an automatic allocation will be performed when the function insert() is called the first time.

Parameters

glob	A pointer to the corresponding global object.
size	The maximal number of nonzeros of the sparse vector (without reallocation).
reallocFac	The reallocation factor (in percent of the original size), which is used in a default reallocation if a variable is inserted when the sparse vector is already full. Its default value is 10.

SparVec() [2/4]

abacus::SparVec::SparVec	(	AbacusGlobal *	glob,
		int	size,
		const Array< int > &	s,
		const Array< double > &	c,
		double	reallocFac = 10.0
	)

Creates a sparse vector and initializes support and coefficients.

The minimum value of size and s.size is the number of nonzeros of the sparse vector.

If size is 0, then also no elements are copied in the for-loop since nnz_ will be also 0.

Parameters

glob	A pointer to the corresponding global object.
size	The maximal number of nonzeros (without reallocation).
s	An array storing the support of the sparse vector, i.e., the elements for which a (normally nonzero) coefficient is given in c.
c	An array storing the coefficients of the support elements given in s. This array must have at least the length of the minimum of size and s.size().
reallocFac	The reallocation factor (in percent of the original size), which is used in a default reallocation if a variable is inserted when the sparse vector is already full. Its default value is 10.

SparVec() [3/4]

abacus::SparVec::SparVec	(	AbacusGlobal *	glob,
		int	size,
		int *	s,
		double *	c,
		double	reallocFac = 10.0
	)

Creates a sparse vector and initializes support and coefficients.

This constructor is equivalent to the previous one except that it is using C-style arrays for the initialization of the sparse vector.

Parameters

glob	A pointer to the corresponding global object.
size	The maximal number of nonzeros (without reallocation).
s	An array storing the support of the sparse vector, i.e., the elements for which a (normally nonzero) coefficient is given in c.
c	An array storing the coefficients of the support elements given in s. This array must have at least the length of the minimum of size and s.size().
reallocFac	The reallocation factor (in percent of the original size), which is used in a default reallocation if a variable is inserted when the sparse vector is already full. Its default value is 10.

SparVec() [4/4]

abacus::SparVec::SparVec

(

const SparVec &

rhs

)

Copy constructor.

Parameters

rhs	The sparse vector that is copied.

~SparVec()

abacus::SparVec::~SparVec

(

)

The destructor.

Member Function Documentation

clear()

void abacus::SparVec::clear ( )

inline

Removes all nonzeros from the sparse vector.

Definition at line 213 of file sparvec.h.

coeff()

double abacus::SparVec::coeff ( int  i ) const

inline

Parameters

i	The number of the nonzero element.

Returns

The coefficient of the i-th nonzero element.

Definition at line 163 of file sparvec.h.

copy()

void abacus::SparVec::copy

(

const SparVec &

vec

)

Copies vector vec.

Is very similar to the assignment operator, yet the size of the two vectors need not be equal and only the support, the coefficients, and the number of nonzeros is copied. A reallocation is performed if required.

Parameters

vec	The sparse vector that is copied.

insert()

void abacus::SparVec::insert ( int  s, double  c  )

inline

Adds a new support/coefficient pair to the vector.

If necessary a reallocation of the member data is performed automatically.

Parameters

s	The new support.
c	The new coefficient.

Definition at line 184 of file sparvec.h.

leftShift()

void abacus::SparVec::leftShift

(

ArrayBuffer< int > &

del

)

Deletes the elements listed in a buffer from the sparse vector.

The numbers of indices in this buffer must be upward sorted. The elements before the first element in the buffer are unchanged. Then the elements which are not deleted are shifted left in the arrays.

Parameters

del	The numbers of the elements removed from the sparse vector.

nnz()

int abacus::SparVec::nnz ( ) const

inline

Returns the number of nonzero elements.

This is not necessarily the correct number of nonzeros, yet the number of coefficient/support pairs, which are stored. Some of these pairs may have a zero coefficient.

Definition at line 232 of file sparvec.h.

norm()

double abacus::SparVec::norm

(

)

Returns the Euclidean norm of the sparse vector.

operator=()

SparVec& abacus::SparVec::operator=

(

const SparVec &

rhs

)

The assignment operator.

Requires that the left hand and the right hand side have the same length (otherwise use the function copy()).

Parameters

rhs	The right hand side of the assignment.

Returns

A reference to the left hand side.

origCoeff()

double abacus::SparVec::origCoeff

(

int

i

)

const

Parameters

i	The number of the original coefficient.

Returns

The coefficient having support i.

rangeCheck()

void abacus::SparVec::rangeCheck ( int  i ) const

protected

Checks whether i is a valid index.

Throws an exception if i is negative or greater or equal than the number of nonzero elements.

If the class SparVec is compiled with the flag OGDF_DEBUG, then before each access operation on element i of the sparse vector the function rangeCheck() is called.

Parameters

i	An integer that should be checked if it is in the range of the sparse vector.

realloc() [1/2]

void abacus::SparVec::realloc

(

)

Increases the size of the sparse vector by reallocFac_ percent of the original size.

realloc() [2/2]

void abacus::SparVec::realloc

(

int

newSize

)

Reallocates the sparse vector to a given length.

It is an error to decrease size below the current number of nonzeros.

Parameters

newSize

The new maximal number of nonzeroes that can be stored in the sparse vector.

rename()

void abacus::SparVec::rename

(

Array< int > &

newName

)

Replaces the index of the support by new names.

Parameters

newName

The new names (support) of the elements of the sparse vector. The array newName must have at least a length equal to the maximal element in the support of the sparse vector.

size()

int abacus::SparVec::size ( ) const

inline

Returns the maximal length of the sparse vector.

Definition at line 224 of file sparvec.h.

support()

int abacus::SparVec::support ( int  i ) const

inline

Parameters

i	The number of the nonzero element.

Returns

The support of the i-th nonzero element.

Definition at line 151 of file sparvec.h.

Friends And Related Function Documentation

operator<<

std::ostream& operator<< ( std::ostream &  out, const SparVec &  rhs  )

friend

The output operator.

Writes the elements of the support and their coefficients line by line on an output stream.

Parameters

out	The output stream.
rhs	The sparse vector being output.

Returns

A reference to the output stream.

Member Data Documentation

coeff_

double* abacus::SparVec::coeff_

protected

The array storing the corresponding nonzero coefficients.

Definition at line 283 of file sparvec.h.

glob_

AbacusGlobal* abacus::SparVec::glob_

protected

A pointer to the corresponding global object.

Definition at line 267 of file sparvec.h.

nnz_

int abacus::SparVec::nnz_

protected

The number of stored elements ("nonzeros").

Definition at line 273 of file sparvec.h.

reallocFac_

double abacus::SparVec::reallocFac_

protected

If a new element is inserted but the sparse vector is full, then its size is increased by reallocFac_ percent.

Definition at line 277 of file sparvec.h.

size_

int abacus::SparVec::size_

protected

The maximal number of nonzero coefficients which can be stored without reallocation.

Definition at line 270 of file sparvec.h.

support_

int* abacus::SparVec::support_

protected

The array storing the nonzero variables.

Definition at line 280 of file sparvec.h.

---

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

• include/ogdf/lib/abacus/sparvec.h