Jive reference manual
|
Represents the structure of a sparse matrix. More...
Public Types | |
typedef Tuple< int, 2 > | Shape |
A type representing the shape of a sparse structure. More... | |
Public Member Functions | |
SparseStructure () | |
Constructs an empty sparse structure. More... | |
SparseStructure (const Shape &sh, const Array< int > &rowOffsets, const Array< int > &columnIndices) | |
Constructs a sparse structure given an index array and an offset array. More... | |
SparseStructure (const SparseStructure &rhs) | |
Creates a shallow copy of another sparse structure. More... | |
SparseStructure & | operator= (const SparseStructure &rhs) |
Makes a shallow copy of another sparse structure. More... | |
void | swap (SparseStructure &rhs) |
Interchanges the contents of two sparse structures. More... | |
SparseStructure | clone () const |
Returns a deep copy of this sparse structure. More... | |
SparseStructure | transpose () const |
Returns the transpose of this sparse structure. More... | |
int | nonZeroCount () const |
Tests whether this sparse structure is valid. More... | |
Shape | shape () const |
Returns the shape of this sparse structure. More... | |
int | size (int dim) const |
Returns the size of this sparse structure in a given dimension. More... | |
const Array< int > & | getRowOffsets () const |
Returns a reference to the row offset array. More... | |
const Array< int > & | getColumnIndices () const |
Returns a reference to the column index array. More... | |
Array< int > | getColumnIndices (int i) const |
Returns the column indices of the non-zero elements on a particular row. More... | |
Protected Attributes | |
Shape | shape_ |
The shape of this sparse structure. More... | |
Array< int > | offsets_ |
The row offset array. More... | |
Array< int > | indices_ |
The column index array. More... | |
Related Functions | |
(Note that these are not member functions.) | |
io::DataInput & | operator>> (io::DataInput &in, SparseStructure &s) |
Sparse structure de-serialization operator. More... | |
io::DataOutput & | operator<< (io::DataOutput &out, const SparseStructure &s) |
Sparse structure serialization operator. More... | |
io::TextOutput & | operator<< (io::TextOutput &out, const SparseStructure &s) |
Sparse structure print operator. More... | |
void | swap (SparseStructure &lhs, SparseStructure &rhs) |
Interchanges the internals states of two sparse structures. More... | |
#include <jem/numeric/sparse/SparseStructure.h>
The SparseStructure
class represents the non-zero pattern of a sparse matrix. Although it is typically used as a helper class of the SparseMatrix
class, it can also be used by itself to represent sparse matrices containing ones and zeroes, and other entities that can be represented by such matrices. For instance, one can use the SparseStructure
class to represent the connectivity graph of a computer network.
A SparseStructure
instance encapsulates two integer arrays that encode the row and column indices of the non-zero elements in a sparse matrix. One array, called the column index array, contains the column indices of the non-zero elements. The indices are stored row by row: first the column indices of the non-zero elements on the first row; then the column indices of the non-zero elements on the second row; etc. It should be clear that the length of the column index array is equal to the number of non-zero elements in the sparse matrix.
The other integer array, called the row offset array, stores the starting position of each row in the column index array. The first entry in this array is always zero; the second entry equals the number of non-zero matrix elements on the first row; the third entry equals the number of non-zero elements on the first and second rows; and so on. The last entry equals the total number of non-zero matrix elements. The length of the row offset array is equal to the number of rows plus one.
The encoding scheme outlined above implies that if offsets
denotes the row offset array, then number of non-zero elements on the i-th row is equal to:
(offsets[i+1] - offsets[i])
.
The encoding scheme also implies that the column indices of the non-zero elements on the i-th row are given by the sequence:
indices[offsets[i]], indices[offsets[i]+1], ..., indices[offsets[i+1]-1]
where indices
denotes the column index array.
As an example, consider the following (5x5) sparse matrix (each `X' marks a non-zero element):
The colummn index and offset arrays corresponding to this matrix are given by:
Note the column indices do not necessarily have to be stored in ascending order. Thus, the column indices in the example above may also be stored as follows:
In addition to the index and offset arrays, a SparseStructure
also encapsulates a shape that specifies the dimensions of the sparse matrix. The shape is represented by an integer Tuple
of length two. The first element in this tuple equals the number of rows, while the second element equals the number of columns.
SparseMatrix
typedef Tuple<int,2> jem::numeric::SparseStructure::Shape |
The Shape
type represents the shape of a SparseStructure
instance. It is an alias for Tuple<int,2>
.
jem::numeric::SparseStructure::SparseStructure | ( | ) |
Constructs an empty SparseStructure
that represents a (0x0) sparse matrix.
this->size(0) == 0 &&
this->size(1) == 0
jem::numeric::SparseStructure::SparseStructure | ( | const Shape & | sh, |
const Array< int > & | rowOffsets, | ||
const Array< int > & | columnIndices | ||
) |
Constructs a SparseStructure
given the shape sh, the row offset array rowOffsets, and the column index array columnIndices. The last two arrays are copied by reference and not by value. This means that this sparse structure object points to the same data blocks as the array objects rowOffsets and columnIndices. As a consequence, any modifications to these arrays will be visible in this sparse structure object. If you do not want this behavior, you should invoke the member function Array::clone()
on each array.
sh | - a Tuple specifying the shape of this SparseStructure . |
rowOffsets | - an integer array containing the starting positions of each row in the column index array. |
columnIndices | - an integer array containing the column indices of the non-zero matrix elements. |
sh[0] >= 0 && sh[1] >= 0 &&
rowOffsets.size() == sh[0] + 1 &&
rowOffsets.back() == columnIndices.size()
equal( this->shape(), sh ) &&
equal( this->getRowOffsets(), rowOffsets ) &&
equal( this->getColumnIndices(), columnIndices )
jem::numeric::SparseStructure::SparseStructure | ( | const SparseStructure & | rhs | ) |
Creates a shallow copy of the rhs sparse structure. This means that this sparse structure points to the same data as the rhs sparse structure. Any modifications to this sparse structure will therefore be visible in the rhs sparse structure, and the other way around.
The data shared between two or more sparse structure objects is deallocated when the last sparse structure pointing to that data is destroyed.
Because of the shallow copy semantics, returning a sparse structure from a function is a relatively cheap operation.
rhs | - the SparseStructure to be copied. |
equal( this->shape(), rhs.shape() ) &&
equal( this->getRowOffsets(), rhs.getRowOffsets() ) &&
equal( this->getColumnIndices(), rhs.getColumnIndices() )
SparseStructure& jem::numeric::SparseStructure::operator= | ( | const SparseStructure & | rhs | ) |
Like the copy constructor, the assignment operator has shallow copy semantics. Thus, after invoking the assignment operator, this sparse structure points to the same data as the rhs sparse structure. The current contents of this sparse structure are deleted if no other sparse structures point to the same data.
rhs | - the SparseStructure to be copied. |
equal( this->shape(), rhs.shape() ) &&
equal( this->getRowOffsets(), rhs.getRowOffsets() ) &&
equal( this->getColumnIndices(), rhs.getColumnIndices() )
*this
void jem::numeric::SparseStructure::swap | ( | SparseStructure & | rhs | ) |
Swaps the internal state of this sparse structure with that of the rhs sparse structure.
rhs | - a SparseStructure object. |
SparseStructure jem::numeric::SparseStructure::clone | ( | ) | const |
Returns a deep copy of this sparse structure.
SparseStructure (
this->shape(),
this->getRowOffsets().clone(),
this->getColumnIndices().clone()
)
SparseStructure jem::numeric::SparseStructure::transpose | ( | ) | const |
Returns a SparseStructure
instance that represents the structure of the transpose of the sparse matrix represented by this SparseStructure
. For instance, if this sparse structure represents the matrix
then this function returns a sparse structure representing the matrix
The returned sparse structure does not share its data with this sparse structure.
SparseStructure
object. int jem::numeric::SparseStructure::nonZeroCount | ( | ) | const |
Tests whether the row offset and column index arrays encapsulated by this sparse structure contain valid data.
true
if this sparse structure contains valid data, and false
otherwise.Returns the number of non-zero elements.
Returns the number of non-zero elements in the matrix represented by this sparse structure.
this->getColumnIndices.size()
Shape jem::numeric::SparseStructure::shape | ( | ) | const |
Returns a Tuple
specifying the shape of this sparse structure. The first element in the tuple equals the number of rows, and the second element equals the number of columns.
int jem::numeric::SparseStructure::size | ( | int | dim | ) | const |
Returns the size of this sparse structure in the dimension dim. Thus, size(0)
returns the number of rows, while size(1)
returns the number of columns.
dim | - the dimension index. |
dim >= 0 && dim < 2
this->shape()[dim]
const Array<int>& jem::numeric::SparseStructure::getRowOffsets | ( | ) | const |
Returns a const reference to the row offset array. The reference is valid until the destructor of this sparse structure is invoked.
const Array<int>& jem::numeric::SparseStructure::getColumnIndices | ( | ) | const |
Returns a const reference to the column index array of this sparse structure. The reference is valid until the destructor of this sparse structure is invoked.
Array<int> jem::numeric::SparseStructure::getColumnIndices | ( | int | i | ) | const |
Returns an integer array containing the column indices of the non-zero matrix elements on row i. The returned array shares its data with the column index array of this sparse structure.
This function is equivalent with:
i | - a valid row index. |
i >= 0 && i < this->size(0)
|
related |
Reads the sparse structure s from the data input stream in. The current contents of s are deleted if no other sparse structures point to the same data.
in | - a data input stream. |
s | - the SparseStructure to be read. |
io::IOException | - if an I/O error occurs. |
io::SerializationException | - if the input data are inconsistent. |
|
related |
Writes the sparse structure s to the data output stream out. The de-serialization operator can be used to restore the SparseStructure
object at a later time.
out | - a data output stream. |
s | - the SparseStructure to be written. |
io::IOException | - if an I/O error occurs. |
|
related |
Writes the sparse structure s in a human-readable format to the text output stream out.
out | - a text output stream. |
s | - the SparseStructure to be written. |
io::IOException | - if an I/O error occurs. |
|
related |
Interchanges the internal states of two SparseStructure
objects. This function is equivalent with:
lhs | - a SparseStructure object. |
rhs | - another SparseStructure object. |
|
protected |
A Tuple
specifying the shape of this sparse structure: shape_[0]
equals the number of rows and shape_[1]
equals the number of columns.
|
protected |
An integer array containing the starting position of each row in the column index array.
|
protected |
An integer array containing the column indices of the non-zero elements in the sparse matrix.