include/libstick-0.1/matrixreduction.h

   1 #ifndef matrixreduction_h_aPeinoXeiFeethuz
   2 #define matrixreduction_h_aPeinoXeiFeethuz
   3
   4 #include <iostream>
   5
   6 #include "booleanmatrix.h"
   7
   8
   9 namespace libstick {
  10
  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
  15  * matrix times v. */
  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());
  19
  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);
  23         if (col.size() == 0)
  24             continue;
  25
  26         // The column is not a zero-column, take the lowest 1, and reduce the other columns at the row
  27         IT r = col.back();
  28         assert(b.get(r, c));
  29
  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);
  34
  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) {
  38             if (*it <= c)
  39                 continue;
  40
  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));
  45         }
  46     }
  47 }
  48
  49 }
  50
  51 #endif