Time and space efficient representation of sparse {0,1}-matrices. More...

#include <zo.h>

Inheritance diagram for ZeroOne< _Field >:

Data Structures
class	IndexIterator
	IndexIterator. More...

class	Iterator
	Raw iterator. More...

struct	rebind

Public Types
enum	howToSort { sortedByRow , sortedByCol }

typedef ZeroOne< _Field >	Self_t

typedef _Field	Field

typedef _Field::Element	Element

typedef size_t	Index

typedef ZeroOne< _Field >	Self_t

typedef _Field	Field

typedef _Field::Element	Element

typedef std::vector< Index >	IndexVector

typedef std::vector< IndexVector::iterator >	PointerVector

typedef MatrixCategories::BlackboxTag	MatrixCategory

Public Member Functions
	ZeroOne (const Field &F)

	ZeroOne (Field &F, Index rowP, Index colP, Index rows, Index cols, Index NNz, bool rowSort=false, bool colSort=false)

	~ZeroOne ()

template<class OutVector, class InVector>
OutVector &	apply (OutVector &y, const InVector &x) const
	apply.

template<class OutVector, class InVector>
OutVector &	applyTranspose (OutVector &y, const InVector &x) const
	applyTranspose.

size_t	rowdim () const

size_t	coldim () const

template<typename _Tp1>
	ZeroOne (const ZeroOne< _Tp1 > &Z, const Field &F)

Iterator	Begin ()

Iterator	End ()

const Iterator	Begin () const

const Iterator	End () const

IndexIterator	indexBegin ()

const IndexIterator	indexBegin () const

IndexIterator	indexEnd ()

const IndexIterator	indexEnd () const

std::istream &	read (std::istream &is)
	Read the matrix from a stream in the JGD's SMS format.

std::ostream &	write (std::ostream &out=std::cout)

const Field &	field () const

bool	isRowSorted () const

bool	isColSorted () const

size_t	nnz () const

	ZeroOne ()

	ZeroOne (const Field &F)

	ZeroOne (const Field &F, IndexVector &index, PointerVector &indexP, Index Rowdim, Index Coldim, bool sortedBy)

	ZeroOne (Field &F, Index rowP, Index colP, Index rows, Index cols, Index NNz)
	The real constructor /todo give docs here assuming entries are sorted in lexicographic order by (row,col) pair.

	ZeroOne (const ZeroOne< Field > &A)

void	switch_sort () const

	~ZeroOne ()

template<class OutVector, class InVector>
OutVector &	apply (OutVector &y, const InVector &x) const
	Uses one of the three private utility functions.

template<class OutVector, class InVector>
OutVector &	applyTranspose (OutVector &y, const InVector &x) const
	Uses one of the three private utility functions, in the manner described above.

size_t	rowdim () const

size_t	coldim () const

std::istream &	read (std::istream &is)
	Read the matrix from a stream in the JGD's SMS format.

std::ostream &	write (std::ostream &out=std::cout) const

const Field &	field () const

size_t	nnz () const

template<typename _Tp1>
	ZeroOne (const ZeroOne< _Tp1 > &A, const GF2 F2)

Data Fields
IndexVector	_index

PointerVector	_indexP

Index	_rowdim

Index	_coldim

bool	sorted

Protected Types
typedef size_t	Index

Protected Member Functions
void	rowSort () const
	Tells the number of nonzero entries.

void	colSort () const

void	_qsort (size_t start, size_t endp1, int &mode) const

size_t	_part (size_t start, size_t endp1, int &mode) const

void	init (std::vector< std::pair< Index, Index > > &ip)

Protected Attributes
const Field *	_field

Element	_tmp

Index	_rows

Index	_cols

Index	_nnz

Index *	_rowP

Index *	_colP

bool	_rowSort

bool	_colSort

bool	dynamic

Detailed Description

template<class _Field>
class LinBox::ZeroOne< _Field >

Time and space efficient representation of sparse {0,1}-matrices.

A 0-1 matrix is a matrix with all 0's and 1's as entries. We're using a NAG-sparse format. Applies can be performed fast, using only additions. When initalizing this class, you only need to build 2 arrays of equal length: an array of the row indices for the non-zero (1's) entries, and an array of the column indices for the non-zero (1's) entries.

A {0, 1,-1} matrix can be effecively represented as the Dif of two ZeroOne's.

A 0-1 matrix is a matrix with all 0's and 1's as entries. We're using a comp-col or comp-row format. That is we have an array of col indices and an array of pointers indicating where the col indices for each row begins within the col index array. (or vice versa if we have sorted by columns.

Applies can be performed fast, using only additions. When initalizing this class, you only need to build 2 arrays of equal length: an array of the row indices for the non-zero (1's) entries, and an array of the column indices for the non-zero (1's) entries.

A {0, 1,-1} matrix can be effecively represented as the Dif of two ZeroOne's.

Examples: examples/graph-charpoly.C.

Member Typedef Documentation

◆ Index [1/2]

template<class _Field>

typedef size_t Index

protected

◆ Self_t [1/2]

template<class _Field>

typedef ZeroOne<_Field> Self_t

◆ Field [1/2]

template<class _Field>

typedef _Field Field

◆ Element [1/2]

template<class _Field>

typedef _Field::Element Element

◆ Index [2/2]

template<class _Field>

typedef size_t Index

◆ Self_t [2/2]

template<class _Field>

typedef ZeroOne<_Field> Self_t

◆ Field [2/2]

template<class _Field>

typedef _Field Field

◆ Element [2/2]

template<class _Field>

typedef _Field::Element Element

◆ IndexVector

template<class _Field>

typedef std::vector<Index> IndexVector

◆ PointerVector

template<class _Field>

typedef std::vector<IndexVector::iterator> PointerVector

◆ MatrixCategory

template<class _Field>

typedef MatrixCategories::BlackboxTag MatrixCategory

Member Enumeration Documentation

◆ howToSort

template<class _Field>

enum howToSort

Enumerator
sortedByRow
sortedByCol

Constructor & Destructor Documentation

◆ ZeroOne() [1/9]

template<class Field>

ZeroOne ( const Field & F )

◆ ZeroOne() [2/9]

template<class Field>

ZeroOne	(	Field &	F,
		Index *	rowP,
		Index *	colP,
		Index	rows,
		Index	cols,
		Index	NNz,
		bool	rowSort = false,
		bool	colSort = false )

◆ ~ZeroOne() [1/2]

template<class Field>

~ZeroOne ( )

◆ ZeroOne() [3/9]

template<class _Field>

template<typename _Tp1>

ZeroOne	(	const ZeroOne< _Tp1 > &	Z,
		const Field &	F )

inline

◆ ZeroOne() [4/9]

template<class _Field>

ZeroOne ( )

inline

◆ ZeroOne() [5/9]

template<class _Field>

ZeroOne ( const Field & F )

inline

◆ ZeroOne() [6/9]

template<class _Field>

ZeroOne	(	const Field &	F,
		IndexVector &	index,
		PointerVector &	indexP,
		Index	Rowdim,
		Index	Coldim,
		bool	sortedBy )

inline

◆ ZeroOne() [7/9]

template<class _Field>

ZeroOne	(	Field &	F,
		Index *	rowP,
		Index *	colP,
		Index	rows,
		Index	cols,
		Index	NNz )

inline

The real constructor /todo give docs here assuming entries are sorted in lexicographic order by (row,col) pair.

◆ ZeroOne() [8/9]

template<class _Field>

ZeroOne ( const ZeroOne< Field > & A )

inline

◆ ~ZeroOne() [2/2]

template<class _Field>

~ZeroOne ( )

inline

◆ ZeroOne() [9/9]

template<class _Field>

template<typename _Tp1>

ZeroOne	(	const ZeroOne< _Tp1 > &	A,
		const GF2	F2 )

Member Function Documentation

◆ apply() [1/2]

template<class Field>

template<class OutVector, class InVector>

OutVector & apply	(	OutVector &	y,
		const InVector &	x ) const

inline

apply.

Uses one of the three private utility functions. It calls the generalized utility function _apply if there is no special ordering, _fyapply if there is C_ordering or _fxapply if there is fortran_ordering

◆ applyTranspose() [1/2]

template<class Field>

template<class OutVector, class InVector>

OutVector & applyTranspose	(	OutVector &	y,
		const InVector &	x ) const

inline

applyTranspose.

Uses one of the three private utility functions, in the manner described above. Worthy of note is the fact that applyTranspose works by passing the column positions to the _apply functions as if they were rows, and row positions as if they were columns, as if the matrix had been transposed.

◆ rowdim() [1/2]

template<class _Field>

size_t rowdim ( ) const

inline

◆ coldim() [1/2]

template<class _Field>

size_t coldim ( ) const

inline

◆ Begin() [1/2]

template<class Field>

ZeroOne< GF2 >::Iterator Begin ( )

inline

◆ End() [1/2]

template<class Field>

ZeroOne< GF2 >::Iterator End ( )

inline

◆ Begin() [2/2]

template<class Field>

const ZeroOne< GF2 >::Iterator Begin ( ) const

inline

◆ End() [2/2]

template<class Field>

const ZeroOne< GF2 >::Iterator End ( ) const

inline

◆ indexBegin() [1/2]

template<class Field>

ZeroOne< GF2 >::IndexedIterator indexBegin ( )

inline

◆ indexBegin() [2/2]

template<class Field>

const ZeroOne< GF2 >::IndexedIterator indexBegin ( ) const

inline

◆ indexEnd() [1/2]

template<class Field>

ZeroOne< GF2 >::IndexedIterator indexEnd ( )

inline

◆ indexEnd() [2/2]

template<class Field>

const ZeroOne< GF2 >::IndexedIterator indexEnd ( ) const

inline

◆ read() [1/2]

template<class _Field>

std::istream & read ( std::istream & is )

inline

Read the matrix from a stream in the JGD's SMS format.

Parameters

is	Input stream from which to read the matrix

Returns: Reference to input stream

◆ write() [1/2]

template<class _Field>

std::ostream & write ( std::ostream & out = std::cout )

inline

◆ field() [1/2]

template<class _Field>

const Field & field ( ) const

inline

◆ isRowSorted()

template<class _Field>

bool isRowSorted ( ) const

inline

◆ isColSorted()

template<class _Field>

bool isColSorted ( ) const

inline

◆ nnz() [1/2]

template<class _Field>

size_t nnz ( ) const

inline

◆ rowSort()

template<class Field>

void rowSort ( ) const

protected

Tells the number of nonzero entries.

Non blackbox function.

◆ colSort()

template<class Field>

void colSort ( ) const

protected

◆ _qsort()

template<class Field>

void _qsort	(	size_t	start,
		size_t	endp1,
		int &	mode ) const

protected

QuickSort function for when there is no sorting

◆ _part()

template<class Field>

size_t _part	(	size_t	start,
		size_t	endp1,
		int &	mode ) const

protected

Partition for quicksort

◆ switch_sort()

template<class _Field>

void switch_sort ( ) const

inline

◆ init()

template<class _Field>

void init ( std::vector< std::pair< Index, Index > > & ip )

inlineprotected

◆ apply() [2/2]

template<class _Field>

template<class OutVector, class InVector>

OutVector & apply	(	OutVector &	y,
		const InVector &	x ) const

Uses one of the three private utility functions.

It calls the generalized utility function _apply if there is no special ordering, _fyapply if there is C_ordering or _fxapply if there is fortran_ordering

◆ applyTranspose() [2/2]

template<class _Field>

template<class OutVector, class InVector>

OutVector & applyTranspose	(	OutVector &	y,
		const InVector &	x ) const

Uses one of the three private utility functions, in the manner described above.

Worthy of note is the fact that applyTranspose works by passing the column positions to the _apply functions as if they were rows, and row positions as if they were columns, as if the matrix had been transposed.

◆ rowdim() [2/2]

template<class _Field>

size_t rowdim ( ) const

inline

◆ coldim() [2/2]

template<class _Field>

size_t coldim ( ) const

inline

◆ read() [2/2]

template<class _Field>

std::istream & read ( std::istream & is )

inline

Read the matrix from a stream in the JGD's SMS format.

Parameters

is	Input stream from which to read the matrix

Returns: Reference to input stream

◆ write() [2/2]

template<class _Field>

std::ostream & write ( std::ostream & out = std::cout ) const

inline

◆ field() [2/2]

template<class _Field>

const Field & field ( ) const

inline

◆ nnz() [2/2]

template<class _Field>

size_t nnz ( ) const

inline

Field Documentation

◆ _field

template<class _Field>

const Field * _field

protected

The field used by this class

◆ _tmp

template<class _Field>

Element _tmp

protected

A temporary element used for initalization for the Begin() and End() methods of the ZeroOne class. Is used to initalize a 1 so that the Iterator returned stores a 1

◆ _rows

template<class _Field>

Index _rows

protected

number of rows of the Matrix

◆ _cols

template<class _Field>

Index _cols

protected

number of columns

◆ _nnz

template<class _Field>

Index _nnz

protected

Number of Non-Zero elements in the Matrix. It also happens to be the length of the three NAGSparse arrays.

◆ _rowP

template<class _Field>

Index* _rowP

mutableprotected

pointer to an array of row indexes.

◆ _colP

template<class _Field>

Index* _colP

mutableprotected

pointer to an array of column indexes. (_rowP and _colP are the other arrays of a NAGSparse format Matrix.)

◆ _rowSort

template<class _Field>

bool _rowSort

mutableprotected

◆ _colSort

template<class _Field>

bool _colSort

mutableprotected

status flags for sorting state

◆ dynamic

template<class _Field>

bool dynamic

protected

◆ _index

template<class _Field>

IndexVector _index

mutable

◆ _indexP

template<class _Field>

PointerVector _indexP

mutable

◆ _rowdim

template<class _Field>

Index _rowdim

◆ _coldim

template<class _Field>

Index _coldim

◆ sorted

template<class _Field>

bool sorted

mutable

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

Data Structures

Public Types

Public Member Functions

Data Fields

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Index [1/2]

◆ Self_t [1/2]

◆ Field [1/2]

◆ Element [1/2]

◆ Index [2/2]

◆ Self_t [2/2]

◆ Field [2/2]

◆ Element [2/2]

◆ IndexVector

◆ PointerVector

◆ MatrixCategory

Member Enumeration Documentation

◆ howToSort

Constructor & Destructor Documentation

◆ ZeroOne() [1/9]

◆ ZeroOne() [2/9]

◆ ~ZeroOne() [1/2]

◆ ZeroOne() [3/9]

◆ ZeroOne() [4/9]

◆ ZeroOne() [5/9]

◆ ZeroOne() [6/9]

◆ ZeroOne() [7/9]

◆ ZeroOne() [8/9]

◆ ~ZeroOne() [2/2]

◆ ZeroOne() [9/9]

Member Function Documentation

◆ apply() [1/2]

◆ applyTranspose() [1/2]

◆ rowdim() [1/2]

◆ coldim() [1/2]

◆ Begin() [1/2]

◆ End() [1/2]

◆ Begin() [2/2]

◆ End() [2/2]

◆ indexBegin() [1/2]

◆ indexBegin() [2/2]

◆ indexEnd() [1/2]

◆ indexEnd() [2/2]

◆ read() [1/2]

◆ write() [1/2]

◆ field() [1/2]

◆ isRowSorted()

◆ isColSorted()

◆ nnz() [1/2]

◆ rowSort()

◆ colSort()

◆ _qsort()

◆ _part()

◆ switch_sort()

◆ init()

◆ apply() [2/2]

◆ applyTranspose() [2/2]

◆ rowdim() [2/2]

◆ coldim() [2/2]

◆ read() [2/2]

◆ write() [2/2]

◆ field() [2/2]

◆ nnz() [2/2]

Field Documentation

◆ _field

◆ _tmp

◆ _rows

◆ _cols

◆ _nnz

◆ _rowP

◆ _colP

◆ _rowSort

◆ _colSort

◆ dynamic

◆ _index

◆ _indexP