Columns in the only_rows case, rows in the only_cols case.
This assertion is checked only in the DIMENSION_CHECKS compilation mode.
The concrete matrix type hidden behind the GenericIncidenceMatrix.
A row of an incidence matrix appears as a set of column indices of true matrix elements belonging to this row. It is always a representative of the GenericSet family.
A column of an incidence matrix appears as a set of row indices of true matrix elements belonging to this column. It is always a representative of the GenericSet family.
The real result type is a masquerade reference Transposed&, pointing to the originator matrix. It inherits the const-ness from the latter.
Either a functor class satisfying the extended requirements for binary operations, or an untyped template of such a class wrapped into BuildBinary or BuildBinaryIt (preferably expressed via the convenience typedef from namespace polymake::operations.
Rows in the only_rows case, columns in the only_cols case.
Random-column-access incidence matrix: IncidenceMatrix, block matrix built of random-column-access incidence matrices, or a minor of a random-column-access incidence matrix with a random-access column index set (sequence or series).
Any combination of GenericSet<...,int>, Complement<...,int>, and a special identifier All (choosing all rows/columns) is allowed here.
The real result type is a temporary alias object of type pm::MatrixMinor. It inherits the const-ness from the originator incidence matrix.
Random-row-access incidence matrix: IncidenceMatrix, block matrix built of random-row-access incidence matrices, or a minor of a random-row-access incidence matrix with a random-access row index set (sequence or series).
IncidenceMatrix or an alias object referring to a mutable (non-const) martix.
This assertion is checked only in the INDEX_CHECKS compilation mode.
Either a functor class satisfying the extended requirements for unary operations, or an untyped template of such a class wrapped into BuildUnary or BuildUnaryIt (preferably expressed via the convenience typedef from namespace polymake::operations.
A GenericSet<...,int> or a Complement<...,int>.
The real result type is a temporary alias object of type pm::RowChain or pm::ColChain.
The real return type is a temporary proxy object, forwarding the read/write access operations to the incidence matrix. Prior to the destruction, which happens after the completion of the expression envolving the random access, it checks whether the element became false; if so, it is removed from the matrix.

Prerequisits

#include <IncidenceMatrix.h>
using namespace polymake; 

Introduction

template <bool symmetric=false> class IncidenceMatrix;

The only persistent class from the incidence matrix family. The implementation is based on a two-dimensional grid of balanced binary search (AVL) trees, the same as for SparseMatrix. The whole internal data structure is attached to a smart pointer with REFCOUNT.

A symmetric incidence matrix is a square matrix whose elements (i,j) and (j,i) are always equal. Internally it is stored in a triangular form, avoiding redundant elements, but appears as a full square.

Generic type

template <typename _Matrix, typename _sym_discr=typename _Matrix::sym_discr> class GenericIncidenceMatrix;

The GenericClass for all matrix classes. Defines the following types and constants:

element_type bool, for the sake of compatibility with matrix classes
top_type _Matrix, the concrete matrix object behind the generic reference
generic_type GenericIncidenceMatrix<_Matrix> itself
persistent_type IncidenceMatrix
row_type
col_type
Masquerade classes representing single matrix rows and columns respectively. They always belong to the GenericSet family.
bool is_symmetric true if the matrix is symmetric
sym_discr bool2type<is_symmetric>; is introduced mainly as a workaround of compiler bugs concerning non-type template parameters. It may disappear in the future.

Methods and friend functions applicable to GenericIncidenceMatrix directly are scattered over the entire page. They are discernible on the prefix GenericIncidenceMatrix:: or parameters of type GenericIncidenceMatrix&. To use other methods via a generic reference (or pointer), you must first move to the concrete object using the top() method.

Construction

IncidenceMatrix();
Create a matrix with 0 rows and 0 columns.
IncidenceMatrix (int m, int n);
Create a matrix with m rows and n columns, all elements are implicitly false.
template <typename Iterator> IncidenceMatrix (int m, int n, Iterator src);
Create a matrix with m rows and n columns, initialize it from a data sequence. src should iterate either over m×n boolean values, corresponding to the elements in the row order (the column index changes first,) or over m sets with integer elements (or convertible to integer), which are assigned to the matrix rows.
In the symmetric case the redundant elements must be present in the input sequence; their values are ignored.
template <typename OtherMatrix> IncidenceMatrix (const GenericIncidenceMatrix<OtherMatrix>&);
Create a matrix as a copy of another matrix. A symmetric matrix cannot be created as a copy of a non-symmetric one.

Modification

template <typename OtherMatrix> GenericIncidenceMatrix::operator= (const GenericIncidenceMatrix<OtherMatrix>&);
Persistent matrix objects (IncidenceMatrix) have after the assignment the same dimensions as the right hand side operand.
Alias objects, such as matrix minor or block matrix, cannot be resized, thus must have the same dimensions as on the right hand side.
void std::swap(GenericIncidenceMatrix&, GenericIncidenceMatrix&);
Swap the contents of two matrices in a most efficient way. If at least one non-persistent object is involved, the operands must have equal dimensions.
void IncidenceMatrix::resize(int m, int n);
Extend or truncate to new dimensions (m rows, n columns.) Surviving elements keep their values, new elements are implicitly false.
IncidenceMatrix deploys an adaptive reallocation strategy similar to std::vector, reserving additional stock memory by every reallocation. If you repeatedly increase the matrix dimensions by one, the amortized reallocation costs will be proportional to the logarithm of the final dimension.
A special case, looking at the first glance like a "no operation": M.resize(M.rows(), M.cols()) , gets rid of this extra allocated storage.
void IncidenceMatrix::clear();
Truncate to 0x0 matrix.
void IncidenceMatrix::squeeze(); template <typename RowIndexConsumer> void IncidenceMatrix::squeeze(RowIndexConsumer row_index_consumer); template <typename RowIndexConsumer, typename ColIndexConsumer> void IncidenceMatrix::squeeze(RowIndexConsumer row_index_consumer, ColIndexConsumer col_index_consumer);
Remove all empty (i.e., consisting entirely of implicit false values) rows and columns, renumber the rest, and reduce the dimensions. If you want to get the mapping of the old row (column) indices to the new ones, you can supply output iterators (e.g., back_inserter of a std::list) as row_index_consumer (col_index_consumer).
template <typename Iterator> void IncidenceMatrix::permute_rows(Iterator perm); template <typename Iterator> void IncidenceMatrix::permute_cols(Iterator perm); template <typename Iterator> void IncidenceMatrix::permute_inv_rows(Iterator inv_perm); template <typename Iterator> void IncidenceMatrix::permute_inv_cols(Iterator inv_perm);
Permute the rows(columns) without copying the elements. These operations are nevetherless expensive, as they need to visit each element and adjust its indices.
An iterator argument should run over a sequence of integer indices. In the straight variant (perm), it has the same meaning as in the select function. In the inverted variant (inv_perm), it is an inverse permutation: the first element specifies the new position of the 0-th row (column) etc.
If the index sequence does not build a proper permutation, the results are undefined. It is the responsibility of the application context to assure this condition.

Element access

int GenericIncidenceMatrix::rows() const; int GenericIncidenceMatrix::cols() const;
Tell the current matrix dimensions.

Sequential access

An incidence matrix as such is not a container in the STL sense. It can be, however, disguised as a sequence of rows or columns, both being STL-conforming containers:

masquerade class producing function description
Rows<_Matrix>
const Rows<_Matrix>
rows(GenericIncidenceMatrix&)
rows(const GenericIncidenceMatrix&)
A sequence of rows of the matrix.
Cols<_Matrix>
const Cols<_Matrix>
cols(GenericIncidenceMatrix&)
cols(const GenericIncidenceMatrix&)
A sequence of columns of the matrix.

Note the difference to SparseMatrix, where the rows and columns are sparse vectors of the same element type as the matrix itself.

If the originator matrix is mutable, you can assign each kind of GenericSet<...,int> or Complement<...,int>, or apply an assignment version of a set-theoretic operation, to a row (column). Then the matrix elements with the column (row) indices contained in the resulting set become true, and the rest become false (by Complement vice versa.)

int Rows<IncidenceMatrix>::iterator::index(); int Cols<IncidenceMatrix>::iterator::index();
Tell the current row (column) number. The numbers start, as usual, with 0.
IncidenceMatrix::col_type::iterator cross_direction(const IncidenceMatrix::row_type::iterator&); IncidenceMatrix::row_type::iterator cross_direction(const IncidenceMatrix::col_type::iterator&);
For an element of a incidence matrix pointed to by the given iterator over the row, create an iterator over the column pointing to the same element (and vice versa.)

Random access

bool& IncidenceMatrix::operator() (int i, int j); bool IncidenceMatrix::operator() (int i, int j) const;
Get the element in i-th row, j-th column. The indices must lie in the valid ranges.
GenericSet IncidenceMatrix::row(int i); GenericSet IncidenceMatrix::operator[] (int i); GenericSet IncidenceMatrix::col(int i);
Get the i-th row or column respectively. The const variants of these methods create immutable set objects. The indices must lie in the valid ranges.
Rows and columns of an IncidenceMatrix offer the binary tree data access methods additionally to the GenericSet interface.
operator[] is a mere synonym for row(int).

Operations

_Matrix& GenericIncidenceMatrix::transitive_closure();
Build the transitive closure of the binary relation in place. The matrix must be square.
IncidenceMatrix convolute (const GenericIncidenceMatrix& M1, const GenericIncidenceMatrix& M2);
Compute a convolution of two binary relations.
bool operator== (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&); bool operator!= (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&); bool operator< (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&); bool operator> (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&); bool operator<= (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&); bool operator>= (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&);
Compare two incidence matrices lexicographically, row for row.

Other constructions

GenericIncidenceMatrix::minor (const RowIndexSet& row_indices, const ColIndexSet& column_indices);
Select an incidence matrix minor lying on the intersection of the given row and column subsets. Be aware that indices of the minor elements (and, automatically, elements of its rows and columns,) appear renumbered, with 0 corresponding to the first selected row (column), 1 to the second one, etc.
The const variant of this method creates an immutable minor object. The indices must lie in the valid ranges.
T(GenericIncidenceMatrix&);
Transpose the incidence matrix. The roles of Rows and Cols get swapped. From the binary relation point of view, this means inversion.
operator/ (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&); operator/ (const &, const GenericIncidenceMatrix&); operator/ (const GenericIncidenceMatrix&, const &);
Create a block incidence matrix, virtually appending the rows of the second matrix after the last row of the first matrix. A set argument is treated as an incidence matrix with one row, having true (false in the Complement case) elements in the columns enumerated in the set. Column dimensions of the operands must be equal.
Sorry for a rather weird mnemonics...
operator| (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&); operator| (const &, const GenericIncidenceMatrix&); operator| (const GenericIncidenceMatrix&, const &);
Create a block matrix, virtually appending the columns of the second matrix after the last column of the first matrix. A set argument is treated as desribed above. Row dimensions of the operands must be equal.
IncidenceMatrix& IncidenceMatrix::operator/= (const GenericIncidenceMatrix&); IncidenceMatrix& IncidenceMatrix::operator/= (const &); IncidenceMatrix& IncidenceMatrix::operator|= (const GenericIncidenceMatrix&); IncidenceMatrix& IncidenceMatrix::operator|= (const &);
Append rows or columns to the matrix.
diag (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&);
Create a block-diagonal incidence matrix.
diag_1 (const GenericIncidenceMatrix&, const GenericIncidenceMatrix&);
Create a block-diagonal incidence matrix, filling the upper right and lower left corner blocks with true elements.

Restricted incidence matrix

enum sparse2d::restriction_kind { only_rows, only_cols }; template <sparse2d::restriction_kind restriction=only_rows> class RestrictedIncidenceMatrix;

A special class allowing for efficient incremental building of incidence matrices.

If you have to fill an incidence matrix element for element, but do not know one of its dimensions in advance, you would have to resize it repeatedly, which would severely impact the performance. This special class maintains the internal data only for one direction, and thus can be filled cheaper than IncidenceMatrix.

On the other hand, almost all matrix operations described above need information about both directions (rows and columns.) Therefore, RestrictedIncidenceMatrix is deliberately not included in the GenericIncidenceMatrix class family. Its only puspose is to gather elements and finally hand them over to a IncidenceMatrix object (without copying!)

RestrictedIncidenceMatrix();
Create a matrix with 0 rows and 0 columns.
explicit RestrictedIncidenceMatrix(int n);
Create a matrix with n rows and 0 columns (or vice versa in only_cols case), all elements are implicit false.
template <typename Iterator> RestrictedIncidenceMatrix(int n, Iterator src);
Create a matrix with n rows and 0 columns (or vice versa in only_cols case), initialize the rows (columns) from the input sequence. Each item supplied by src should be a GenericSet, whose elements are interpreted as column (row) indices of true elements.
void RestrictedIncidenceMatrix::clear();
Truncate to a 0x0 matrix.
void std::swap(RestrictedIncidenceMatrix&, RestrictedIncidenceMatrix&);
Swap the contents of two matrices in a most efficient way.
int RestrictedIncidenceMatrix::rows() const; int RestrictedIncidenceMatrix::cols() const;
Tell the current matrix dimensions. For the unsupported direction, the value returned is the highest column (row) index ever seen in an element access or modification operation.
bool& RestrictedIncidenceMatrix::operator() (int i, int j); bool RestrictedIncidenceMatrix() (int i, int j) const;
Random access to an element. The index for the must lie in the valid range, the opposite index can cause the matrix to grow dynamically.
Rows< RestrictedIncidenceMatrix >& rows(RestrictedIncidenceMatrix&); const Rows< RestrictedIncidenceMatrix >& rows(const RestrictedIncidenceMatrix&); Cols< RestrictedIncidenceMatrix >& cols(RestrictedIncidenceMatrix&); const Cols< RestrictedIncidenceMatrix >& cols(const RestrictedIncidenceMatrix&);
Sequential access to the rows and columns. Defined only for the .
GenericSet RestrictedIncidenceMatrix::row (int i); GenericSet RestrictedIncidenceMatrix::col (int i);
Random access to a row (column). Defined only for the .
RestrictedIncidenceMatrix& RestrictedIncidenceMatrix::operator/= (const GenericIncidenceMatrix&); RestrictedIncidenceMatrix& RestrictedIncidenceMatrix::operator/= (const GenericSet&);
Append rows to the matrix. Allowed in both only_rows and only_cols cases. Unlike in the similar operator for IncidenceMatrix, set complements are not allowed here.
RestrictedIncidenceMatrix& RestrictedIncidenceMatrix::operator|= (const GenericIncidenceMatrix&); RestrictedIncidenceMatrix& RestrictedIncidenceMatrix::operator|= (const GenericSet&);
Append columns to the matrix. Allowed in both only_rows and only_cols cases. Unlike in the similar operator for IncidenceMatrix, set complements are not allowed here.
explicit IncidenceMatrix(RestrictedIncidenceMatrix&);
The final and alone destination of a RestrictedIncidenceMatrix object is to hand over its internal data to a new created IncidenceMatrix. Any further action on the RestrictedIncidenceMatrix object (except destruction, obviously) is prohibited: it would lead to the immediate program crash.