Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

PipeOrder.h
Go to the documentation of this file.
1 
31 #pragma once
32 
33 #include <ogdf/basic/List.h>
35 #include <ogdf/basic/basic.h>
37 
38 #include <algorithm>
39 #include <memory>
40 #include <random>
41 
42 namespace ogdf::sync_plan {
43 // using PipeCmp = std::function<bool(const Pipe *, const Pipe *)>;
44 
46 template<typename PipeCmp>
47 struct PipeCmpPtr {
48  const PipeCmp* cmp;
49 
50  PipeCmpPtr() = delete;
51 
52  PipeCmpPtr(const PipeCmp* queue) : cmp(queue) {};
53 
54  bool operator()(const Pipe* x, const Pipe* y) const {
55  if (x == nullptr) {
56  return y != nullptr; // true
57  } else if (y == nullptr) {
58  return false;
59  } else if (x->pipe_priority != y->pipe_priority) {
60  return x->pipe_priority > y->pipe_priority;
61  } else {
62  return cmp->comparePipes(x, y);
63  }
64  }
65 
66  bool checkOrder(const Pipe* first, const Pipe* second) const {
67  return first == second || !(*this)(second, first);
68  }
69 };
70 
72 template<typename PipeCmp>
73 class SimplePipeQueue : public PipeQueue {
74 public:
77 
78 protected:
79  std::unique_ptr<PipesHeap> pipes_heap;
80 
81 public:
82  SimplePipeQueue() = default;
83 
84  SimplePipeQueue(const SimplePipeQueue& copy) = delete;
85 
87 
89 
91 
92  bool empty() override { return pipes_heap->empty(); }
93 
94  int size() override { return pipes_heap->size(); }
95 
96  Pipe* getTop() override { return pipes_heap->top(); }
97 
98  void addPipe(Pipe* p) override {
99 #ifdef OGDF_DEBUG
100  OGDF_ASSERT(p->node1->degree() == p->node2->degree());
101  p->dbg_degree = p->node1->degree();
102 #endif
103  p->heap_entry = pipes_heap->push(p);
104  }
105 
106  void removePipe(Pipe* pipe) override {
107  OGDF_ASSERT(pipes_heap->value((PipesHeapHandle)pipe->heap_entry) == pipe);
108  pipes_heap->decrease((PipesHeapHandle)pipe->heap_entry, nullptr);
109  OGDF_ASSERT(pipes_heap->top() == nullptr);
110  pipes_heap->pop();
111  OGDF_ASSERT(pipes_heap->empty() || pipes_heap->top() != nullptr);
112  }
113 
114  void rebuild(List<Pipe>& pipes_list) override {
115  clear();
116  for (Pipe& p : pipes_list) {
117  addPipe(&p);
118  }
119  }
120 
121  void clear() override {
122 #if 0
123  Pipe* top = nullptr;
124  while (!pipes_heap->empty()) {
125  OGDF_ASSERT(checkOrder(top, pipes_heap->top()));
126  top = pipes_heap->top();
127  pipes_heap->pop();
128  }
129 #else
130  pipes_heap->clear();
131 #endif
132  }
133 };
134 
136 struct OGDF_EXPORT PipeQueueByDegree : public SimplePipeQueue<PipeQueueByDegree> {
138 
142  explicit PipeQueueByDegree(bool invert = false) : invert_degree(invert) {
143  pipes_heap = std::make_unique<PipesHeap>(this);
144  };
145 
146  bool comparePipes(const Pipe* x, const Pipe* y) const {
147  if (invert_degree) {
148  return x->degree() < y->degree();
149  } else {
150  return x->degree() > y->degree();
151  }
152  }
153 };
154 
156 struct OGDF_EXPORT PipeQueueRandom : public SimplePipeQueue<PipeQueueRandom> {
157  using engine = std::minstd_rand;
158  mutable engine gen;
159 
160  explicit PipeQueueRandom() { pipes_heap = std::make_unique<PipesHeap>(this); };
161 
162  engine::result_type hash(const Pipe* p) const {
163  gen.seed(max(p->node1->index(), p->node2->index()));
164  gen.discard(5 + p->degree() % 20);
165  return gen();
166  }
167 
168  bool comparePipes(const Pipe* x, const Pipe* y) const {
169  if (x == nullptr) {
170  return true;
171  } else if (y == nullptr) {
172  return false;
173  }
174  return hash(x) > hash(y);
175  }
176 };
177 
179 template<typename PipeCmp1, typename PipeCmp2>
180 class DoublePipeQueue : public SimplePipeQueue<PipeCmp1> {
181 public:
185 
186 protected:
187  using Base::pipes_heap;
188  std::unique_ptr<PipesHeap2> pipes_heap2;
189 
190  virtual bool isQueue1(Pipe* p) const = 0;
191 
192 public:
193  bool empty() override { return Base::empty() && pipes_heap2->empty(); }
194 
195  int size() override { return Base::size() + pipes_heap2->size(); }
196 
197  Pipe* getTop() override {
198  while (!Base::empty()) {
199  Pipe* p = Base::getTop();
200  if (isQueue1(p)) {
201  return p;
202  } else {
203  removePipe(p);
204  addPipe(p);
205  }
206  }
207  OGDF_ASSERT(!pipes_heap2->empty());
208  return pipes_heap2->top();
209  }
210 
211  void addPipe(Pipe* p) override {
212 #ifdef OGDF_DEBUG
213  OGDF_ASSERT(p->node1->degree() == p->node2->degree());
214  p->dbg_degree = p->node1->degree();
215 #endif
216  if (isQueue1(p)) {
217  p->heap_data = 1;
218  p->heap_entry = pipes_heap->push(p);
219  } else {
220  p->heap_data = 2;
221  p->heap_entry = pipes_heap2->push(p);
222  }
223  }
224 
225  void removePipe(Pipe* pipe) override {
226  if (pipe->heap_data == 2) {
227  OGDF_ASSERT(pipes_heap2->value((PipesHeapHandle2)pipe->heap_entry) == pipe);
228  pipes_heap2->decrease((PipesHeapHandle2)pipe->heap_entry, nullptr);
229  OGDF_ASSERT(pipes_heap2->top() == nullptr);
230  pipes_heap2->pop();
231  OGDF_ASSERT(pipes_heap2->empty() || pipes_heap2->top() != nullptr);
232  } else {
233  Base::removePipe(pipe);
234  }
235  }
236 
237  void clear() override {
238 #if 0
239  Pipe* top = nullptr;
240  while (!pipes_heap->empty()) {
241  OGDF_ASSERT(checkOrder(top, pipes_heap->top()));
242  top = pipes_heap->top();
243  pipes_heap->pop();
244  }
245  while (!pipes_heap2->empty()) {
246  OGDF_ASSERT(checkOrder(top, pipes_heap2->top()));
247  top = pipes_heap2->top();
248  pipes_heap2->pop();
249  }
250 #else
251  pipes_heap->clear();
252  pipes_heap2->clear();
253 #endif
254  }
255 };
256 
257 class SyncPlan;
258 
261  : public DoublePipeQueue<PipeQueueByDegreePreferContract, PipeQueueByDegreePreferContract> {
263  bool invert_degree, invert_contract;
264 
270  explicit PipeQueueByDegreePreferContract(SyncPlan* pq, bool invertDegree = false,
271  bool invertContract = false)
272  : PQ(pq), invert_degree(invertDegree), invert_contract(invertContract) {
273  pipes_heap = std::make_unique<PipesHeap>(this);
274  pipes_heap2 = std::make_unique<PipesHeap2>(this);
275  }
276 
277  bool comparePipes(const Pipe* x, const Pipe* y) const;
278 
279  bool isQueue1(Pipe* p) const override;
280 };
281 }
ogdf::sync_plan::PipeQueue
A queue of all pipes, ordered by an arbitrary comparator function.
Definition: PMatching.h:67
ogdf::sync_plan::DoublePipeQueue::addPipe
void addPipe(Pipe *p) override
Definition: PipeOrder.h:211
PMatching.h
Manages the matching of P-nodes via pipes in an instance of SyncPlan.
ogdf::sync_plan::PipeQueueRandom::engine
std::minstd_rand engine
Definition: PipeOrder.h:157
ogdf::sync_plan::PipeQueueByDegree::invert_degree
bool invert_degree
Definition: PipeOrder.h:137
ogdf::sync_plan::PipeQueueRandom
PipeQueue yielding pipes in some random (but stable and deterministic) order.
Definition: PipeOrder.h:156
ogdf::sync_plan::PipeCmpPtr
A null-safe and priority aware comparator (wrapper) for pipes.
Definition: PipeOrder.h:47
ogdf::sync_plan::DoublePipeQueue::pipes_heap2
std::unique_ptr< PipesHeap2 > pipes_heap2
Definition: PipeOrder.h:188
ogdf::sync_plan::PipeQueueByDegree::comparePipes
bool comparePipes(const Pipe *x, const Pipe *y) const
Definition: PipeOrder.h:146
ogdf::sync_plan
Definition: clustering.h:44
ogdf::sync_plan::Pipe::node2
node node2
Definition: PMatching.h:48
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:66
PriorityQueue.h
Priority queue interface wrapping various heaps.
ogdf::sync_plan::PipeQueueByDegreePreferContract::invert_degree
bool invert_degree
Definition: PipeOrder.h:263
ogdf::sync_plan::Pipe::heap_data
int heap_data
Definition: PMatching.h:52
ogdf::NodeElement::index
int index() const
Returns the (unique) node index.
Definition: Graph_d.h:274
ogdf::sync_plan::DoublePipeQueue::removePipe
void removePipe(Pipe *pipe) override
Definition: PipeOrder.h:225
ogdf::sync_plan::DoublePipeQueue< PipeQueueByDegreePreferContract, PipeQueueByDegreePreferContract >::PipesHeapHandle2
typename PipesHeap2::handle PipesHeapHandle2
Definition: PipeOrder.h:183
ogdf::sync_plan::PipeCmpPtr::PipeCmpPtr
PipeCmpPtr()=delete
ogdf::sync_plan::PipeQueueRandom::gen
engine gen
Definition: PipeOrder.h:158
ogdf::sync_plan::PipeQueueRandom::hash
engine::result_type hash(const Pipe *p) const
Definition: PipeOrder.h:162
ogdf::sync_plan::DoublePipeQueue::isQueue1
virtual bool isQueue1(Pipe *p) const =0
ogdf::sync_plan::DoublePipeQueue::size
int size() override
Definition: PipeOrder.h:195
ogdf::sync_plan::SimplePipeQueue::removePipe
void removePipe(Pipe *pipe) override
Definition: PipeOrder.h:106
ogdf::sync_plan::Pipe::dbg_degree
int dbg_degree
Definition: PMatching.h:54
ogdf::sync_plan::SimplePipeQueue::addPipe
void addPipe(Pipe *p) override
Definition: PipeOrder.h:98
ogdf::sync_plan::PipeQueueByDegreePreferContract::PipeQueueByDegreePreferContract
PipeQueueByDegreePreferContract(SyncPlan *pq, bool invertDegree=false, bool invertContract=false)
Definition: PipeOrder.h:270
ogdf::sync_plan::PipeQueueRandom::PipeQueueRandom
PipeQueueRandom()
Definition: PipeOrder.h:160
ogdf::sync_plan::SimplePipeQueue::operator=
SimplePipeQueue & operator=(const SimplePipeQueue &copy)=delete
ogdf::sync_plan::SyncPlan
A class for modelling and solving Synchronized Planarity instances.
Definition: SyncPlan.h:124
ogdf::sync_plan::PipeCmpPtr::cmp
const PipeCmp * cmp
Definition: PipeOrder.h:48
ogdf::sync_plan::Pipe
A pair of matched vertices of the same degree, whose rotation shall be synchronized.
Definition: PMatching.h:47
ogdf::sync_plan::Pipe::heap_entry
void * heap_entry
Definition: PMatching.h:51
ogdf::sync_plan::SimplePipeQueue< PipeQueueByDegreePreferContract >::PipesHeapHandle
typename PipesHeap::handle PipesHeapHandle
Definition: PipeOrder.h:76
ogdf::sync_plan::SimplePipeQueue::clear
void clear() override
Definition: PipeOrder.h:121
Minisat::Internal::copy
static void copy(const T &from, T &to)
Definition: Alg.h:61
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:283
ogdf::sync_plan::SimplePipeQueue::size
int size() override
Definition: PipeOrder.h:94
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243
ogdf::sync_plan::SimplePipeQueue::empty
bool empty() override
Definition: PipeOrder.h:92
ogdf::sync_plan::PipeQueueByDegree
PipeQueue yielding pipes in order of descending or ascending degree.
Definition: PipeOrder.h:136
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: DfsMakeBiconnected.h:40
ogdf::sync_plan::SimplePipeQueue::getTop
Pipe * getTop() override
Definition: PipeOrder.h:96
ogdf::sync_plan::PipeQueueByDegreePreferContract::PQ
SyncPlan * PQ
Definition: PipeOrder.h:262
ogdf::sync_plan::Pipe::node1
node node1
Definition: PMatching.h:48
ogdf::sync_plan::SimplePipeQueue::SimplePipeQueue
SimplePipeQueue()=default
basic.h
Basic declarations, included by all source files.
ogdf::sync_plan::PipeCmpPtr::checkOrder
bool checkOrder(const Pipe *first, const Pipe *second) const
Definition: PipeOrder.h:66
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:101
ogdf::sync_plan::PipeQueueByDegreePreferContract
PipeQueue yielding contractable pipes first (or last), in order of descending (or ascending) degree.
Definition: PipeOrder.h:260
ogdf::sync_plan::SimplePipeQueue
PipeQueue CRTP base class for ordering pipes by some simple comparator function.
Definition: PipeOrder.h:73
ogdf::sync_plan::PipeCmpPtr::operator()
bool operator()(const Pipe *x, const Pipe *y) const
Definition: PipeOrder.h:54
ogdf::sync_plan::Pipe::degree
int degree() const
ogdf::sync_plan::DoublePipeQueue::empty
bool empty() override
Definition: PipeOrder.h:193
List.h
Declaration of doubly linked lists and iterators.
ogdf::sync_plan::PipeCmpPtr::PipeCmpPtr
PipeCmpPtr(const PipeCmp *queue)
Definition: PipeOrder.h:52
ogdf::sync_plan::SimplePipeQueue::rebuild
void rebuild(List< Pipe > &pipes_list) override
Definition: PipeOrder.h:114
ogdf::sync_plan::SimplePipeQueue::pipes_heap
std::unique_ptr< PipesHeap > pipes_heap
Definition: PipeOrder.h:79
ogdf::PriorityQueue::handle
typename SpecImpl::Handle handle
Definition: PriorityQueue.h:73
ogdf::sync_plan::DoublePipeQueue::getTop
Pipe * getTop() override
Definition: PipeOrder.h:197
ogdf::sync_plan::PipeQueueRandom::comparePipes
bool comparePipes(const Pipe *x, const Pipe *y) const
Definition: PipeOrder.h:168
ogdf::sync_plan::Pipe::pipe_priority
int pipe_priority
Definition: PMatching.h:49
ogdf::sync_plan::DoublePipeQueue::clear
void clear() override
Definition: PipeOrder.h:237
ogdf::sync_plan::DoublePipeQueue
Base class for PipeQueues providing a "priority lane" for some pipes and sorting with different funct...
Definition: PipeOrder.h:180
ogdf::sync_plan::PipeQueueByDegree::PipeQueueByDegree
PipeQueueByDegree(bool invert=false)
Definition: PipeOrder.h:142
ogdf::PriorityQueue
Priority queue interface wrapper for heaps.
Definition: PriorityQueue.h:62
Minisat::Internal::hash
static uint32_t hash(uint32_t x)
Definition: Map.h:38