CMR  1.3.0
separation.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <utility>
4 #include <cstddef>
5 #include <vector>
7 #include "matroid.hpp"
9 
10 namespace tu
11 {
12 
17  class separation
18  {
19  public:
20  typedef std::pair <std::size_t, std::size_t> split_type;
21  typedef std::pair <std::size_t, std::size_t> witness_type;
22 
27  separation();
28 
36 
45 
55 
62  separation(const separation& other);
63 
71  separation& operator=(const separation& other);
72 
77  ~separation();
78 
84 
89  int upper_right_rank() const
90  {
91  return upper_right_rank_;
92  }
93 
98  int lower_left_rank() const
99  {
100  return lower_left_rank_;
101  }
102 
107  int rank() const
108  {
109  return lower_left_rank() + upper_right_rank();
110  }
111 
116  const std::pair <size_t, size_t>& split() const
117  {
118  return split_;
119  }
120 
125  bool is_valid() const
126  {
127  return split_.first > 0 || split_.second > 0;
128  }
129 
137  const witness_type& witness(size_t index = 0) const
138  {
139  return witnesses_[index];
140  }
141 
149  void set_special_swap(char type, size_t index)
150  {
151  special_swap_ = std::make_pair(type, index);
152  }
153 
158  bool has_special_swap() const
159  {
160  return special_swap_.first != 0;
161  }
162 
167  bool has_special_row_swap() const
168  {
169  return special_swap_.first == 'r';
170  }
171 
176  size_t get_special_swap_index() const
177  {
178  return special_swap_.second;
179  }
180 
192  template <typename MatroidType, typename MatrixType>
193  void create_components(const MatroidType& matroid, const MatrixType& matrix, integer_matroid& upper_left_matroid,
194  integer_matrix& upper_left_matrix, integer_matroid& lower_right_matroid, integer_matrix& lower_right_matrix) const
195  {
196  assert (is_valid());
197  assert (matroid.size1() == matrix.size1());
198  assert (matroid.size2() == matrix.size2());
199 
201  if (rank() == 0)
202  {
203  upper_left_matroid.resize(split_.first, split_.second);
204  for (size_t row = 0; row < upper_left_matroid.size1(); ++row)
205  upper_left_matroid.name1(row) = matroid.name1(row);
206  for (size_t column = 0; column < upper_left_matroid.size2(); ++column)
207  upper_left_matroid.name2(column) = matroid.name2(column);
208  upper_left_matrix.resize(split_.first, split_.second, false);
209  for (size_t row = 0; row < upper_left_matrix.size1(); ++row)
210  {
211  for (size_t column = 0; column < upper_left_matrix.size2(); ++column)
212  upper_left_matrix(row, column) = matrix(row, column);
213  }
214 
215  lower_right_matroid.resize(matroid.size1() - split_.first, matroid.size2() - split_.second);
216  for (size_t row = 0; row < lower_right_matroid.size1(); ++row)
217  lower_right_matroid.name1(row) = matroid.name1(split_.first + row);
218  for (size_t column = 0; column < lower_right_matroid.size2(); ++column)
219  lower_right_matroid.name2(column) = matroid.name2(split_.second + column);
220  lower_right_matrix.resize(matrix.size1() - split_.first, matrix.size2() - split_.second, false);
221  for (size_t row = 0; row < lower_right_matrix.size1(); ++row)
222  {
223  for (size_t column = 0; column < lower_right_matrix.size2(); ++column)
224  lower_right_matrix(row, column) = matrix(split_.first + row, split_.second + column);
225  }
226  }
227  else if (rank() == 1 && witness().first >= split_.first)
228  {
230 
231  upper_left_matroid.resize(split_.first + 1, split_.second);
232  for (size_t row = 0; row < split_.first; ++row)
233  upper_left_matroid.name1(row) = matroid.name1(row);
234  upper_left_matroid.name1(split_.first) = matroid.name1(witness().first);
235  for (size_t column = 0; column < upper_left_matroid.size2(); ++column)
236  upper_left_matroid.name2(column) = matroid.name2(column);
237 
238  upper_left_matrix.resize(split_.first + 1, split_.second, false);
239  for (size_t column = 0; column < upper_left_matrix.size2(); ++column)
240  {
241  for (size_t row = 0; row < split_.first; ++row)
242  upper_left_matrix(row, column) = matrix(row, column);
243  upper_left_matrix(split_.first, column) = matrix(witness().first, column);
244  }
245 
246  lower_right_matroid.resize(matroid.size1() - split_.first, matroid.size2() - split_.second + 1);
247  for (size_t row = 0; row < lower_right_matroid.size1(); ++row)
248  lower_right_matroid.name1(row) = matroid.name1(split_.first + row);
249  for (size_t column = 1; column < lower_right_matroid.size2(); ++column)
250  lower_right_matroid.name2(column) = matroid.name2(split_.second + column - 1);
251  lower_right_matroid.name2(0) = matroid.name2(witness().second);
252 
253  lower_right_matrix.resize(matrix.size1() - split_.first, matrix.size2() - split_.second + 1, false);
254  for (size_t row = 0; row < lower_right_matrix.size1(); ++row)
255  {
256  for (size_t column = 1; column < lower_right_matrix.size2(); ++column)
257  lower_right_matrix(row, column) = matrix(split_.first + row, split_.second + column - 1);
258  lower_right_matrix(row, 0) = matrix(split_.first + row, witness().second);
259  }
260  }
261  else if (rank() == 1 && witness().second >= split_.second)
262  {
264 
265  upper_left_matroid.resize(split_.first, split_.second + 1);
266  for (size_t row = 0; row < split_.first; ++row)
267  upper_left_matroid.name1(row) = matroid.name1(row);
268  for (size_t column = 0; column < split_.second; ++column)
269  upper_left_matroid.name2(column) = matroid.name2(column);
270  upper_left_matroid.name2(split_.second) = matroid.name2(witness().second);
271 
272  upper_left_matrix.resize(split_.first, split_.second + 1, false);
273  for (size_t row = 0; row < split_.first; ++row)
274  {
275  for (size_t column = 0; column < split_.second; ++column)
276  upper_left_matrix(row, column) = matrix(row, column);
277  upper_left_matrix(row, split_.second) = matrix(row, witness().second);
278  }
279 
280  lower_right_matroid.resize(matroid.size1() - split_.first + 1, matroid.size2() - split_.second);
281  for (size_t row = 1; row < lower_right_matroid.size1(); ++row)
282  lower_right_matroid.name1(row) = matroid.name1(split_.first + row - 1);
283  for (size_t column = 0; column < lower_right_matroid.size2(); ++column)
284  lower_right_matroid.name2(column) = matroid.name2(split_.second + column);
285  lower_right_matroid.name1(0) = matroid.name1(witness().first);
286 
287  lower_right_matrix.resize(matrix.size1() - split_.first + 1, matrix.size2() - split_.second, false);
288  for (size_t column = 0; column < lower_right_matrix.size2(); ++column)
289  {
290  for (size_t row = 1; row < lower_right_matrix.size1(); ++row)
291  lower_right_matrix(row, column) = matrix(split_.first + row - 1, split_.second + column);
292  lower_right_matrix(0, column) = matrix(witness().first, split_.second + column);
293  }
294  }
295  else
296  {
298 
299  upper_left_matroid.resize(split_.first + 2, split_.second + 1);
300  for (size_t row = 0; row < split_.first + 2; ++row)
301  upper_left_matroid.name1(row) = matroid.name1(row);
302  for (size_t column = 0; column < split_.second + 1; ++column)
303  upper_left_matroid.name2(column) = matroid.name2(column);
304 
305  upper_left_matrix.resize(split_.first + 2, split_.second + 1, false);
306  for (size_t row = 0; row < split_.first + 2; ++row)
307  {
308  for (size_t column = 0; column < split_.second + 1; ++column)
309  upper_left_matrix(row, column) = matrix(row, column);
310  }
311 
312  lower_right_matroid.resize(matroid.size1() - split_.first + 1, matroid.size2() - split_.second + 2);
313  for (size_t row = 0; row < lower_right_matroid.size1(); ++row)
314  lower_right_matroid.name1(row) = matroid.name1(split_.first + row - 1);
315  for (size_t column = 0; column < lower_right_matroid.size2(); ++column)
316  lower_right_matroid.name2(column) = matroid.name2(split_.second + column - 2);
317 
318  lower_right_matrix.resize(matrix.size1() - split_.first + 1, matrix.size2() - split_.second + 2, false);
319  for (size_t column = 0; column < lower_right_matrix.size2(); ++column)
320  {
321  for (size_t row = 0; row < lower_right_matrix.size1(); ++row)
322  lower_right_matrix(row, column) = matrix(split_.first + row - 1, split_.second + column - 2);
323  }
324  }
325  }
326 
327  private:
328  std::pair <size_t, size_t> split_;
329  std::vector <std::pair <size_t, size_t> > witnesses_;
330  int upper_right_rank_;
331  int lower_left_rank_;
332  std::pair <char, size_t> special_swap_;
333  };
334 
335 } /* namespace tu */
Definition: matroid.hpp:22
void resize(size_t size1, size_t size2)
Definition: matroid.hpp:63
size_t size1() const
Definition: matroid.hpp:77
size_t size2() const
Definition: matroid.hpp:86
name_type & name2(size_t index)
Definition: matroid.hpp:116
name_type & name1(size_t index)
Definition: matroid.hpp:96
Definition: separation.hpp:18
const witness_type & witness(size_t index=0) const
Definition: separation.hpp:137
void create_components(const MatroidType &matroid, const MatrixType &matrix, integer_matroid &upper_left_matroid, integer_matrix &upper_left_matrix, integer_matroid &lower_right_matroid, integer_matrix &lower_right_matrix) const
Definition: separation.hpp:193
size_t get_special_swap_index() const
Definition: separation.hpp:176
bool has_special_swap() const
Definition: separation.hpp:158
separation transposed()
Definition: separation.cpp:161
int rank() const
Definition: separation.hpp:107
separation()
Definition: separation.cpp:15
std::pair< std::size_t, std::size_t > split_type
Definition: separation.hpp:20
separation & operator=(const separation &other)
Definition: separation.cpp:137
int upper_right_rank() const
Definition: separation.hpp:89
~separation()
Definition: separation.cpp:152
bool has_special_row_swap() const
Definition: separation.hpp:167
bool is_valid() const
Definition: separation.hpp:125
void set_special_swap(char type, size_t index)
Definition: separation.hpp:149
int lower_left_rank() const
Definition: separation.hpp:98
const std::pair< size_t, size_t > & split() const
Definition: separation.hpp:116
std::pair< std::size_t, std::size_t > witness_type
Definition: separation.hpp:21
Definition: algorithm.hpp:14
boost::numeric::ublas::matrix< long long > integer_matrix
Definition: common.hpp:27