Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

GF2Solver.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/basic/List.h>
36 #include <iomanip>
37 
38 
39 namespace ogdf {
40 
41 class GF2Solver {
42 
43  static constexpr int chunkSize = 13;
44  static constexpr int chunkSize2 = 9;
45 
46  template<int Dim, typename Next>
47  struct ChunkBase {
48  int m_x[Dim];
49  int m_max;
50  Next* m_next;
51 
52  bool full() const {
53  return m_max == Dim - 1;
54  }
55 
57  m_max = -1;
58  m_next = nullptr;
59  for (int i = 0; i < Dim; i++) {
60  m_x[i] = 0;
61  }
62  }
63 
65  };
66 
67  struct Chunk : public ChunkBase<chunkSize, Chunk> {
69 
70  void add(int x) {
71  m_x[++m_max] = x;
72  }
73 
75  };
76 
77  struct Chunk2 : public ChunkBase<chunkSize2, Chunk2> {
79 
81 
82  void add(int x, ListIterator<int> it) {
83  ++m_max;
84  m_x [m_max] = x;
85  m_it[m_max] = it;
86  }
87 
89  };
90 
91 #if 0
92  struct Row {
93  Chunk *m_pHead;
94  Chunk *m_pTail;
95 
96  Row() {
97  m_pHead = m_pTail = nullptr;
98  }
99 
100  void addChunk(Chunk *p) {
101  if(m_pHead == nullptr)
102  m_pHead = m_pTail = p;
103  else {
104  m_pTail->m_next = p;
105  m_pTail = p;
106  }
107  }
108  };
109 #endif
110 
111  struct Row2 {
114 
115  Row2() {
116  m_pHead = m_pTail = nullptr;
117  }
118 
119  void addChunk(Chunk2 *p) {
120  if(m_pHead == nullptr)
121  m_pHead = m_pTail = p;
122  else {
123  m_pTail->m_next = p;
124  m_pTail = p;
125  }
126  }
127  };
128 
131 
132 #if 0
133  Chunk *getChunk() {
134  if(m_freelist != nullptr) {
135  Chunk *p = m_freelist;
136  m_freelist = p->m_next;
137  p->m_next = nullptr;
138  p->m_max = -1;
139  return p;
140  }
141  return new Chunk;
142  }
143 #endif
144 
146  if(m_freelist2 != nullptr) {
147  Chunk2 *p = m_freelist2;
148  m_freelist2 = p->m_next;
149  p->m_next = nullptr;
150  p->m_max = -1;
151  return p;
152  }
153  return new Chunk2;
154  }
155 
156 #if 0
157  void freeChunk(Chunk *p) {
158  p->m_next = m_freelist;
159  m_freelist = p;
160  }
161 #endif
162 
163  void freeChunk2(Chunk2 *p) {
164  p->m_next = m_freelist2;
165  m_freelist2 = p;
166  }
167 
168 #if 0
169  void freeChunks(Chunk *pHead, Chunk *pTail) {
170  pTail->m_next = m_freelist;
171  m_freelist = pHead;
172  }
173 #endif
174 
175  void freeChunks2(Chunk2 *pHead, Chunk2 *pTail) {
176  pTail->m_next = m_freelist2;
177  m_freelist2 = pHead;
178  }
179 
180 #if 0
181  bool contains(const Row &r, int x) const;
182 
183  void symDiff(Row &r, const Row &other);
184 #endif
185  void symDiff2(int r1, int r2, Array<Row2> &rows, Array<List<int>> &cols);
186 
187 public:
188 
189  class Equation {
190 
192 
193  public:
194  Equation() { }
195 
196  void print() {
197  std::cout << m_objects << std::endl;
198  }
199 
200  ListConstIterator<int> begin() const { return m_objects.begin(); }
201  ListConstIterator<int> end() const { return m_objects.end(); }
202 
203 #if 0
204  bool contains(OBJ obj) const {
205  for(OBJ x : m_objects) {
206  if(x == obj)
207  return true;
208  else if(x > obj)
209  return false;
210  }
211  return false;
212  }
213 #endif
214 
215  int size() const {
216  return m_objects.size();
217  }
218 
219  Equation &operator|=(int obj) {
220  ListIterator<int> it = m_objects.begin();
221  while(it.valid() && *it < obj)
222  ++it;
223  if(it.valid()) {
224  if(*it != obj)
225  m_objects.insertBefore(obj,it);
226  } else
227  m_objects.pushBack(obj);
228 
229  return *this;
230  }
231 
232 #if 0
233  Equation &operator^=(const Equation &other) {
234  ListConstIterator<OBJ> itOther = other.m_objects.begin();
235  ListIterator<OBJ> it = m_objects.begin();
236 
237  while(itOther.valid())
238  {
239  if(!it.valid()) {
240  m_objects.pushBack(*itOther);
241  ++itOther;
242 
243  } else if(*it == *itOther) {
244  ListIterator<OBJ> itDel = it;
245  ++it; ++itOther;
246  m_objects.del(itDel);
247 
248  } else if(*itOther < *it) {
249  m_objects.insertBefore(*itOther, it);
250  ++itOther;
251 
252  } else {
253  ++it;
254  }
255  }
256 
257  return *this;
258  }
259 #endif
260 
262  };
263 
264  class Matrix {
265 
269 
270  public:
271  Matrix() : m_equations(0, 255, nullptr), m_numRows(0), m_numCols(0) { }
272 
274  for(int i = 0; i < m_numRows; ++i)
275  delete m_equations[i];
276  }
277 
279  OGDF_ASSERT(i >= 0);
280  OGDF_ASSERT(i < m_numRows);
281  return *m_equations[i];
282  }
283 
284  const Equation &operator[](int i) const {
285  OGDF_ASSERT(i >= 0);
286  OGDF_ASSERT(i < m_numRows);
287  return *m_equations[i];
288  }
289 
290  int numRows() const { return m_numRows; }
291  int numColumns() const { return m_numCols; }
292 
293  int addRow() {
294  int i = m_numRows++;
295  if(i == m_equations.size())
296  m_equations.grow(m_equations.size(), nullptr);
297  m_equations[i] = new Equation;
298 
299  return i;
300  }
301 
302  int addColumn() {
303  return m_numCols++;
304  }
305 
306  void clear() {
307  for(int i = 0; i < m_numRows; ++i)
308  delete m_equations[i];
309 
310  m_equations.init(0, 255, nullptr);
311  m_numRows = m_numCols = 0;
312  }
313 
314  void print() const {
315  for(int i = 0; i < m_numRows; ++i) {
316  std::cout << std::setw(4) << i << ": ";
317  m_equations[i]->print();
318  }
319  }
320  };
321 
322 
324  : m_freelist(nullptr)
325  , m_freelist2(nullptr)
326  , m_matrix(Mx)
327  {
328  }
329 
330  ~GF2Solver();
331 
332  bool solve();
333  bool solve2();
334 
335 
336 private:
338 };
339 
340 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::GF2Solver::Equation::size
int size() const
Definition: GF2Solver.h:215
ogdf::GF2Solver::Chunk2::add
void add(int x, ListIterator< int > it)
Definition: GF2Solver.h:82
ogdf::GF2Solver::Matrix::numRows
int numRows() const
Definition: GF2Solver.h:290
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::GF2Solver::freeChunk2
void freeChunk2(Chunk2 *p)
Definition: GF2Solver.h:163
ogdf::GF2Solver::Matrix::addColumn
int addColumn()
Definition: GF2Solver.h:302
ogdf::GF2Solver::Row2::Row2
Row2()
Definition: GF2Solver.h:115
ogdf::GF2Solver::Matrix::m_equations
Array< Equation * > m_equations
Definition: GF2Solver.h:266
ogdf::GF2Solver::ChunkBase::full
bool full() const
Definition: GF2Solver.h:52
ogdf::GF2Solver::Equation
Definition: GF2Solver.h:189
ogdf::ListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: List.h:124
ogdf::GF2Solver
Definition: GF2Solver.h:41
ogdf::GF2Solver::Row2::m_pTail
Chunk2 * m_pTail
Definition: GF2Solver.h:113
ogdf::GF2Solver::Equation::print
void print()
Definition: GF2Solver.h:196
ogdf::GF2Solver::solve2
bool solve2()
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::GF2Solver::Chunk2::Chunk2
Chunk2()
Definition: GF2Solver.h:80
ogdf::GF2Solver::ChunkBase
Definition: GF2Solver.h:47
ogdf::GF2Solver::Matrix::clear
void clear()
Definition: GF2Solver.h:306
ogdf::GF2Solver::Row2::addChunk
void addChunk(Chunk2 *p)
Definition: GF2Solver.h:119
ogdf::GF2Solver::m_freelist2
Chunk2 * m_freelist2
Definition: GF2Solver.h:130
ogdf::GF2Solver::m_freelist
Chunk * m_freelist
Definition: GF2Solver.h:129
ogdf::GF2Solver::Equation::begin
ListConstIterator< int > begin() const
Definition: GF2Solver.h:200
ogdf::GF2Solver::Equation::Equation
Equation()
Definition: GF2Solver.h:194
ogdf::GF2Solver::Matrix::operator[]
const Equation & operator[](int i) const
Definition: GF2Solver.h:284
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::GF2Solver::Matrix::~Matrix
~Matrix()
Definition: GF2Solver.h:273
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::GF2Solver::Equation::m_objects
List< int > m_objects
Definition: GF2Solver.h:191
ogdf::GF2Solver::~GF2Solver
~GF2Solver()
ogdf::GF2Solver::Matrix::Matrix
Matrix()
Definition: GF2Solver.h:271
ogdf::GF2Solver::getChunk2
Chunk2 * getChunk2()
Definition: GF2Solver.h:145
ogdf::List< int >
ogdf::GF2Solver::Matrix::m_numCols
int m_numCols
Definition: GF2Solver.h:268
ogdf::GF2Solver::Matrix::print
void print() const
Definition: GF2Solver.h:314
ogdf::GF2Solver::ChunkBase::ChunkBase
ChunkBase()
Definition: GF2Solver.h:56
ogdf::GF2Solver::Chunk2::m_it
ListIterator< int > m_it[chunkSize2]
Definition: GF2Solver.h:78
ogdf::GF2Solver::Row2
Definition: GF2Solver.h:111
ogdf::GF2Solver::symDiff2
void symDiff2(int r1, int r2, Array< Row2 > &rows, Array< List< int >> &cols)
ogdf::GF2Solver::Chunk::Chunk
Chunk()
Definition: GF2Solver.h:68
ogdf::GF2Solver::Row2::m_pHead
Chunk2 * m_pHead
Definition: GF2Solver.h:112
ogdf::GF2Solver::ChunkBase::m_x
int m_x[Dim]
Definition: GF2Solver.h:48
ogdf::List::del
void del(iterator it)
Removes it from the list.
Definition: List.h:1438
ogdf::GF2Solver::Chunk2
Definition: GF2Solver.h:77
ogdf::GF2Solver::Matrix
Definition: GF2Solver.h:264
ogdf::GF2Solver::Chunk
Definition: GF2Solver.h:67
ogdf::GF2Solver::GF2Solver
GF2Solver(GF2Solver::Matrix &Mx)
Definition: GF2Solver.h:323
ogdf::GF2Solver::chunkSize
static constexpr int chunkSize
Definition: GF2Solver.h:43
ogdf::GF2Solver::Matrix::addRow
int addRow()
Definition: GF2Solver.h:293
List.h
Declaration of doubly linked lists and iterators.
ogdf::GF2Solver::freeChunks2
void freeChunks2(Chunk2 *pHead, Chunk2 *pTail)
Definition: GF2Solver.h:175
ogdf::GF2Solver::Matrix::m_numRows
int m_numRows
Definition: GF2Solver.h:267
ogdf::GF2Solver::Chunk::add
void add(int x)
Definition: GF2Solver.h:70
ogdf::List::size
int size() const
Returns the number of elements in the list.
Definition: List.h:1313
ogdf::GF2Solver::Matrix::numColumns
int numColumns() const
Definition: GF2Solver.h:291
ogdf::GF2Solver::Equation::end
ListConstIterator< int > end() const
Definition: GF2Solver.h:201
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::GF2Solver::solve
bool solve()
ogdf::GF2Solver::chunkSize2
static constexpr int chunkSize2
Definition: GF2Solver.h:44
ogdf::GF2Solver::Matrix::operator[]
Equation & operator[](int i)
Definition: GF2Solver.h:278
ogdf::GF2Solver::ChunkBase::m_max
int m_max
Definition: GF2Solver.h:49
ogdf::GF2Solver::Equation::operator|=
Equation & operator|=(int obj)
Definition: GF2Solver.h:219
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1374
ogdf::GF2Solver::m_matrix
Matrix & m_matrix
Definition: GF2Solver.h:337
ogdf::List::insertBefore
iterator insertBefore(const E &x, iterator it)
Inserts element x before it.
Definition: List.h:1393
ogdf::GF2Solver::ChunkBase::m_next
Next * m_next
Definition: GF2Solver.h:50