Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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...
 
SparVecoperator= (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...
 
AbacusGlobalglob_
 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
globA pointer to the corresponding global object.
sizeThe maximal number of nonzeros of the sparse vector (without reallocation).
reallocFacThe 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
globA pointer to the corresponding global object.
sizeThe maximal number of nonzeros (without reallocation).
sAn array storing the support of the sparse vector, i.e., the elements for which a (normally nonzero) coefficient is given in c.
cAn 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().
reallocFacThe 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
globA pointer to the corresponding global object.
sizeThe maximal number of nonzeros (without reallocation).
sAn array storing the support of the sparse vector, i.e., the elements for which a (normally nonzero) coefficient is given in c.
cAn 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().
reallocFacThe 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
rhsThe 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
iThe 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
vecThe 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
sThe new support.
cThe 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
delThe 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
rhsThe right hand side of the assignment.
Returns
A reference to the left hand side.

◆ origCoeff()

double abacus::SparVec::origCoeff ( int  i) const
Parameters
iThe 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
iAn 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
newSizeThe 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
newNameThe 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
iThe 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
outThe output stream.
rhsThe 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: