1 #ifndef matrixreduction_h_aPeinoXeiFeethuz
2 #define matrixreduction_h_aPeinoXeiFeethuz
6 #include "booleanmatrix.h"
11 /** Takes the boundary matrix b and transforms it inplace into a reduced matrix
12 * b. The matrix v is required to be a unit matrix having the same dimensions
13 * as b. It is maintained in order to leave the product b*inverse(v) as an
14 * invariant. Hence, the resulting b is equal to the product of the boundary
16 template<class IT
, class D
>
17 void reduce_boundary_matrix(boolean_colrowmatrix
<IT
> &b
, boolean_colmatrix_base
<IT
, D
> &v
) {
18 assert(b
.size() == v
.width());
20 // Make every column reduced, i.e., it is a zero-column or contains only one 1.
21 for (unsigned c
=0; c
< b
.size(); ++c
) {
22 const typename boolean_colrowmatrix
<IT
>::colbase::column_type
&col
= b
.get_column(c
);
26 // The column is not a zero-column, take the lowest 1, and reduce the other columns at the row
30 // Get a copy of the r-th row
31 typename boolean_colrowmatrix
<IT
>::rowbase::row_type
row(b
.get_row(r
).size());
32 copy(b
.get_row(r
).begin(), b
.get_row(r
).end(), row
.begin());
33 assert(row
.size() >= 1);
35 // Get rid of 1s at that row right of column c.
36 typename boolean_colrowmatrix
<IT
>::row_type::const_iterator it
= lower_bound(row
.begin(), row
.end(), c
);
37 for(; it
!= row
.end(); ++it
) {
41 assert(b
.get(r
, *it
));
42 b
.add_column(*it
, col
);
43 v
.add_column(*it
, v
.get_column(c
));
44 assert(!b
.get(r
, *it
));