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 Top, typename _sym_discr=typename Top::sym_discr> class GenericIncidenceMatrix;
The generic class for all matrix classes.
Defines the following types and constants:
Top, the concrete matrix object behind the generic reference
generic_type
GenericIncidenceMatrix<Top> 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.
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.
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.
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.
Remove all empty (i.e., consisting entirely of implicit false values) rows and columns, renumber the rest,
and reduce the dimensions. If you need to know the original numbers of non-empty rows and columns,
you can supply output iterators (e.g., back_inserter of a std::list.)
They will get the numbers assigned in the ascending order.
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.
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.
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:
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 or Complement,
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.
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
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).
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).
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.
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 index range check can be activated.
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 index range check can be activated.
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.
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.
Read a property from polymake server. The input data is expected to look like a sequence of sets.
Parse errors are reported by raising the std::iostream::failure exception in the constructor,
or via std::iostream::fail() flag in the input operator.
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.
Read a property from the polymake server. The input data is expected to look
like a sequence of sets, otherwise an exception of type std::iostream::failure is raised.
Currently this constructor is defined only for only_rows case.
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;
Append rows to the matrix. Allowed in both only_rows and only_cols modi.
Unlike in the similar operator for IncidenceMatrix, set complements are not allowed here.
Append columns to the matrix. Allowed in both only_rows and only_cols modi.
Unlike in the similar operator for IncidenceMatrix, set complements are not allowed here.
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.