1 #ifndef booleanmatrix_h_AechohNgakoghahV
2 #define booleanmatrix_h_AechohNgakoghahV
18 /** The base class of boolean_colmatrix and boolean_colrowmatrix which implements
19 * the common logic of both. */
20 template<class IT
, class D
>
21 class boolean_colmatrix_base
{
24 typedef IT index_type
;
25 typedef std::vector
<index_type
> column_type
;
28 /** Create a matrix with 'width' columns, initalized with zero entries. */
29 boolean_colmatrix_base(size_t width
) :
33 /** Get height resp. width of the matrix. */
34 size_t width() const {
38 /** Get the matrix entry at row 'r' and column 'c'. */
39 bool get(index_type r
, index_type c
) const {
41 const column_type
&col
= get_column(c
);
42 return binary_search(col
.begin(), col
.end(), r
);
45 /** Set the matrix entry at row 'r' and column 'c'. */
46 void set(index_type r
, index_type c
, bool value
) {
47 get_derived()->_set(r
, c
, value
);
50 /** Get the c-th column. */
51 const column_type
& get_column(index_type c
) const {
56 /** Add the column-vector 'col' to the c-th column. Note that 'col'
57 * actually contains the list of row-indices that are 1. */
58 void add_column(index_type c
, const column_type
&col
) {
61 // Flip all entries that are set in 'col'.
62 for (typename
column_type::const_iterator it
= col
.begin(); it
!= col
.end(); ++it
)
63 set(*it
, c
, !get(*it
, c
));
66 /** Two matrices are equal iff they have the same entries */
67 bool operator==(const boolean_colmatrix_base
<IT
, D
> &m
) const {
68 return cols
== m
.cols
;
71 /** Two matrices are equal iff they have the same entries */
72 bool operator!=(const boolean_colmatrix_base
<IT
, D
> &m
) const {
77 /** Set the matrix entry at row 'r' and column 'c'. */
78 void _set(index_type r
, index_type c
, bool value
) {
81 column_type
&col
= cols
.at(c
);
82 // Let us see where to insert the new element
83 typename
column_type::iterator it
= lower_bound(col
.begin(), col
.end(), r
);
84 bool exists
= (it
!= col
.end() && *it
== r
);
85 assert(get(r
,c
) == exists
);
87 // Add 'r' to c-th column
89 // r is new, insert it
102 // C++11 would have is_sorted
103 for (unsigned i
=1; i
< col
.size(); i
++)
104 assert(col
[i
-1] < col
[i
]);
109 /** The matrix is the set of columns. */
110 std::vector
<column_type
> cols
;
112 /** A cast to the derived type */
113 derived
* get_derived() {
114 return static_cast<derived
*>(this);
119 /** This is boolean matrix that is a std::vector of column-vectors and in each
120 * column-vector we save the row-indices of the 1s. It is designed to handle a
121 * few 1s and column-wise operations well. */
122 template<class IT
=uint32_t>
123 class boolean_colmatrix
: public boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > {
126 typedef IT index_type
;
127 typedef boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > base
;
129 /** Create a matrix with 'width' columns, initalized with zero entries. */
130 boolean_colmatrix(size_t columns
) :
134 /** Set the matrix entry at row 'r' and column 'c'. */
135 void _set(index_type r
, index_type c
, bool value
) {
136 base::_set(r
, c
, value
);
141 /** The base class of boolean_rowmatrix and boolean_colrowmatrix which implements
142 * the common logic of both. */
143 template<class IT
, class D
>
144 class boolean_rowmatrix_base
{
147 typedef IT index_type
;
148 typedef std::vector
<index_type
> row_type
;
151 /** Create a matrix with 'height' rows, initalized with zero entries.
153 boolean_rowmatrix_base(size_t height
) :
157 /** Get height resp. width of the matrix. */
158 size_t height() const {
162 /** Get the matrix entry at row 'r' and column 'c'. */
163 bool get(index_type r
, index_type c
) const {
164 assert(r
< height());
165 const row_type
&row
= get_row(r
);
166 return binary_search(row
.begin(), row
.end(), c
);
169 /** Set the matrix entry at row 'r' and column 'c'. */
170 void set(index_type r
, index_type c
, bool value
) {
171 get_derived()->_set(r
, c
, value
);
174 /** Get the r-th row. */
175 const row_type
& get_row(index_type r
) const {
176 assert(r
< height());
180 /** Add the row-vector 'row' to the r-th row. Note that 'row'
181 * actually contains the list of column-indices that are 1. */
182 void add_row(index_type r
, const row_type
&row
) {
183 assert(r
< height());
185 // Flip all entries that are set in 'row'.
186 for (typename
row_type::const_iterator it
= row
.begin(); it
!= row
.end(); ++it
)
187 set(r
, *it
, !get(r
, *it
));
190 /** Two matrices are equal iff they have the same entries */
191 bool operator==(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
192 return rows
== m
.rows
;
195 /** Two matrices are equal iff they have the same entries */
196 bool operator!=(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
197 return !(*this == m
);
201 /** Set the matrix entry at row 'r' and column 'c'. */
202 void _set(index_type r
, index_type c
, bool value
) {
203 assert(r
< height());
205 row_type
&row
= rows
.at(r
);
206 // Let us see where to insert/remove the new element
207 typename
row_type::iterator it
= lower_bound(row
.begin(), row
.end(), c
);
208 bool exists
= (it
!= row
.end() && *it
== c
);
209 assert(get(r
,c
) == exists
);
211 // Add 'r' to c-th column
213 // r is new, insert it
218 // Remove the element
226 // C++11 would have is_sorted
227 for (unsigned i
=1; i
< row
.size(); i
++)
228 assert(row
[i
-1] < row
[i
]);
233 derived
* get_derived() {
234 return static_cast<derived
*>(this);
237 /** The matrix is the set of columns. */
238 std::vector
<row_type
> rows
;
242 /** This is boolean matrix that is a std::vector of row-vectors and in each
243 * row-vector we save the column-indices of the 1s. It is designed to handle a
244 * few 1s and row-wise operations well. */
245 template<class IT
=uint32_t>
246 class boolean_rowmatrix
: public boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > {
249 typedef IT index_type
;
250 typedef boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > base
;
252 /** Create a matrix with 'height' rows, initalized with zero entries. */
253 boolean_rowmatrix(size_t height
) :
257 /** Set the matrix entry at row 'r' and column 'c'. */
258 void _set(index_type r
, index_type c
, bool value
) {
259 base::_set(r
, c
, value
);
264 /** This is a boolean matrix that supports. It is designed to handle a
265 * few 1s and row- and column-wise operations well. */
266 template<class IT
=uint32_t>
267 class boolean_colrowmatrix
: public boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> >,
268 public boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > {
271 typedef boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > colbase
;
272 typedef boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > rowbase
;
275 typedef IT index_type
;
277 /** Create a size x size matrix, initialized with zeros. */
278 boolean_colrowmatrix(size_t size
) :
283 /** Override implementation. */
284 void _set(index_type r
, index_type c
, bool value
) {
285 colbase::_set(r
, c
, value
);
286 rowbase::_set(r
, c
, value
);
290 /** Get height resp. width of the matrix. */
291 size_t size() const {
292 assert(colbase::width() == rowbase::height());
293 return colbase::width();
296 /** Set the matrix entry at row 'r' and column 'c'. */
297 void set(index_type r
, index_type c
, bool value
) {
298 //Calling set() for one base suffices, static polymorphism
299 //calls _set() anyhow.
300 //rowbase::set(r, c, value);
301 colbase::set(r
, c
, value
);
304 /** Get the matrix entry at row 'r' and column 'c'. */
305 bool get(index_type r
, index_type c
) const {
306 assert(colbase::get(r
, c
) == rowbase::get(r
, c
));
307 return colbase::get(r
, c
);
310 /** Two matrices are equal iff they have the same entries */
311 bool operator==(const boolean_colrowmatrix
<IT
> &m
) const {
312 assert(rowbase::operator==(m
) == colbase::operator==(m
));
313 return colbase::operator==(m
);
316 /** Two matrices are equal iff they have the same entries */
317 bool operator!=(const boolean_colrowmatrix
<IT
> &m
) const {
318 return !(*this == m
);
321 /** Multiply with matrix b from the right */
323 boolean_colrowmatrix
<IT
> operator*(const boolean_colmatrix_base
<IT
, D
> &b
) {
324 boolean_colrowmatrix
<IT
> c(size());
325 multiply_matrix(c
, *this, b
);
331 /** Counts the number of common elements in two sorted vectors. Equal to
332 * counting the number of elements given by std::set_intersection. */
333 template <class InputIterator1
, class InputIterator2
>
334 size_t count_set_intersection (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
)
338 // As long as we did not either end, look for common elements
339 while (first1
!=last1
&& first2
!=last2
)
341 if (*first1
< *first2
)
343 else if (*first2
< *first1
)
345 // Element is common to both
355 /** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */
356 template<class IT
, class D
, class RT
>
357 void multiply_matrix(RT
&result
, const boolean_rowmatrix_base
<IT
, D
> &a
, const boolean_colmatrix_base
<IT
, D
> &b
) {
358 assert(a
.height() == b
.width());
360 for (unsigned r
=0; r
< a
.height(); ++r
) {
361 const typename boolean_rowmatrix_base
<IT
, D
>::row_type
&row
= a
.get_row(r
);
362 for (unsigned c
=0; c
< b
.width(); ++c
) {
363 const typename boolean_colmatrix_base
<IT
, D
>::column_type
&col
= b
.get_column(c
);
364 if (count_set_intersection(row
.begin(), row
.end(), col
.begin(), col
.end()) % 2 == 1)
365 result
.set(r
, c
, true);
371 MT
create_unit_matrix(size_t size
) {
373 for (unsigned i
=0; i
< size
; ++i
)
379 std::ostream
& operator<<(std::ostream
&os
, const boolean_colrowmatrix
<IT
> &mat
) {
380 for (unsigned r
=0; r
< mat
.size(); ++r
) {
381 for (unsigned c
=0; c
< mat
.size(); ++c
)
382 os
<< (mat
.get(r
,c
) ? "X" : ".");
384 if (r
< mat
.size() - 1)
391 std::ostream
& operator<<(std::ostream
&os
, boolean_colrowmatrix
<IT
> &mat
) {
392 const boolean_colrowmatrix
<IT
> &m
= mat
;
396 template<class IT
, class D
>
397 std::ostream
& operator<<(std::ostream
&os
, const boolean_rowmatrix_base
<IT
, D
> &mat
) {
398 for (unsigned r
=0; r
< mat
.height(); ++r
) {
399 // Get the sorted r-th row
400 std::list
<IT
> row(mat
.get_row(r
).size());
401 copy(mat
.get_row(r
).begin(), mat
.get_row(r
).end(), row
.begin());
404 // Print the elements, and remove them
405 for (unsigned c
=0; row
.size() > 0; ++c
) {
406 if (row
.front() == c
) {
413 if (r
< mat
.height() - 1)
419 template<class IT
, class D
>
420 std::ostream
& operator<<(std::ostream
&os
, boolean_rowmatrix_base
<IT
, D
> &mat
) {
421 const boolean_rowmatrix_base
<IT
, D
> &m
= mat
;
425 template<class IT
, class D
>
426 std::ostream
& operator<<(std::ostream
&os
, const boolean_colmatrix_base
<IT
, D
> &mat
) {
427 // The sorted columns
428 std::vector
<std::list
<IT
> > cols
;
429 // The max height (max. value) of all columns
432 for (unsigned c
=0; c
< mat
.width(); ++c
) {
433 // Get the sorted c-th column
434 std::list
<IT
> col(mat
.get_column(c
).size());
435 copy(mat
.get_column(c
).begin(), mat
.get_column(c
).end(), col
.begin());
441 height
= std::max(height
, col
.back());
446 for (unsigned r
=0; r
<= height
; ++r
) {
447 // Print the elements, and remove them
448 for (unsigned c
=0; c
< mat
.width(); ++c
) {
449 std::list
<IT
> &col
= cols
.at(c
);
450 // This column is already empty
453 else if (col
.front() == r
) {
465 template<class IT
, class D
>
466 std::ostream
& operator<<(std::ostream
&os
, boolean_colmatrix_base
<IT
, D
> &mat
) {
467 const boolean_colmatrix_base
<IT
, D
> &m
= mat
;