# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
Go to the documentation of this file.
1
32#pragma once
33
35
36
37#define OGDF_LQ_M2L_MIN_BOUND 8
38#define OGDF_LQ_WSPD_BRANCH_BOUND 16
39#define OGDF_LQ_WSPD_BOUND 25
40
41namespace ogdf {
42namespace fast_multipole_embedder {
43
45class WSPD;
46
50
51public:
52 using NodeID = unsigned int;
53 using PointID = unsigned int;
54
55 struct LQPoint // 16 byte
56 {
57 MortonNR mortonNr; // 8 byte
58 uint32_t node; // 4 byte
59 uint32_t ref; // 4 byte
60 };
61
62 struct LQNode // 27 byte
63 {
64 uint32_t level; // 4 byte
65 NodeID next; // 4 byte
66 NodeID child[4]; // 4 byte *4 = 16 byte
70 bool fence; // 1 byte
71 };
72
73 struct LQWSPair {
74 LQWSPair(NodeID c, NodeID d) : a(c), b(d) {};
77 };
78
81
83
84 inline bool operator()(NodeID u) { return tree.isFence(u); }
85 };
86
91
94
96
97 inline bool operator()(NodeID u) { return tree.isLeaf(u); }
98 };
99
104
106 template<typename F>
112
115
116 inline void operator()() {
117 NodeID it = begin;
118 for (uint32_t i = 0; i < numNodes; i++) {
119 func(it);
120 it = tree.nextNode(it);
121 }
122 }
123 };
124
126 template<typename F>
128 return forall_tree_nodes_functor<F>(*this, f, begin, num);
129 }
130
132 template<typename F>
136
138
139 inline void operator()(NodeID u) {
140 if (tree.isLeaf(u)) {
141 return;
142 }
143 for (uint32_t i = 0; i < tree.numberOfChilds(u); i++) {
144 func(tree.child(u, i));
145 }
146 }
147 };
148
150 template<typename F>
154
156 template<typename Func>
160
162
163 inline void operator()(NodeID u) {
166 for (PointID i = firstPoint; i < end; i++) {
167 func(i);
168 }
169 }
170 };
171
173 template<typename Func>
175 return forall_points_functor<Func>(*this, func);
176 }
177
179 template<typename F>
183
185 : tree(t), func(f) { }
186
187 inline void operator()(NodeID u) {
188 if (tree.isLeaf(u)) {
189 return;
190 }
191 for (uint32_t i = 0; i < tree.numberOfChilds(u); i++) {
192 for (uint32_t j = i + 1; j < tree.numberOfChilds(u); j++) {
193 func(tree.child(u, i), tree.child(u, j));
194 }
195 }
196 }
197 };
198
200 template<typename F>
204
206 template<typename F, typename CondType = true_condition>
211
213
215 : tree(t), func(f), cond(c) { }
216
217 inline void operator()(NodeID u) {
218 if (cond(u)) {
219 func(u);
220 tree.forall_children (*this)(u);
221 };
222 }
223 };
224
226 template<typename F>
230
232 template<typename F, typename Cond>
236
238 template<typename F, typename CondType = true_condition>
243
245
247 : tree(t), func(f), cond(c) { }
248
249 inline void operator()(NodeID u) {
250 if (cond(u)) {
251 tree.forall_children (*this)(u);
252 func(u);
253 };
254 }
255 };
256
258 template<typename F>
262
264 template<typename F, typename Cond>
268
269 template<typename WSPairFuncType, typename DPairFuncType, typename DNodeFuncType,
277
281
284 : tree(t)
285 , WSFunction(wsf)
289
290 inline void operator()(NodeID u) {
291 if (BranchCondFunction(u)) {
293 if (tree.numberOfPoints(u) > 1) {
294 DNodeFunction(u);
295 }
296 } else {
297 tree.forall_children (*this)(u);
299 }
300 }
301 }
302
303 inline void operator()(NodeID u, NodeID v) {
304 if (tree.isWS(u, v)) {
307 DPairFunction(u, v);
308 } else {
309 WSFunction(u, v);
310 }
311 } else {
314 || tree.isLeaf(u) || tree.isLeaf(v)) {
315 DPairFunction(u, v);
316 } else {
317 if (tree.level(u) >= tree.level(v)) {
318 tree.forall_children(pair_call(*this, v))(u);
319 } else {
320 tree.forall_children(pair_call(*this, u))(v);
321 }
322 }
323 }
324 }
325 };
326
327 template<typename A, typename B, typename C, typename ConditionType>
329 ConditionType cond) {
330 return wspd_functor<A, B, C, ConditionType>(*this, a, b, c, cond);
331 }
332
333 template<typename A, typename B, typename C>
335 return wspd_functor<A, B, C>(*this, a, b, c);
336 }
337
340
342
343 inline void operator()(NodeID a, NodeID b) { tree.addWSPD(a, b); }
344 };
345
347
350
352
353 inline void operator()(NodeID a, NodeID b) { tree.addDirectPair(a, b); }
354 };
355
357 return StoreDirectPairFunctor(*this);
358 }
359
362
364
365 inline void operator()(NodeID a) { tree.addDirect(a); }
366 };
367
369 return StoreDirectNodeFunctor(*this);
370 }
371
372 inline NodeID level(NodeID nodeID) const { return m_tree[nodeID].level; }
373
374 inline NodeID nextNode(NodeID nodeID) const { return m_tree[nodeID].next; }
375
376 inline void setNextNode(NodeID nodeID, NodeID next) { m_tree[nodeID].next = next; }
377
378 inline void setLevel(NodeID nodeID, uint32_t level) { m_tree[nodeID].level = level; }
379
380 inline PointID firstPoint(NodeID nodeID) const { return m_tree[nodeID].firstPoint; }
381
382 inline void setFirstPoint(NodeID nodeID, PointID firstPoint) {
383 m_tree[nodeID].firstPoint = firstPoint;
384 }
385
387
388 inline const LQPoint& point(PointID pointID) const { return m_points[pointID]; }
389
391
395 inline uint32_t numberOfChilds(NodeID nodeID) const { return m_tree[nodeID].numChilds; }
396
398 inline void setNumberOfChilds(NodeID nodeID, uint32_t numChilds) {
399 m_tree[nodeID].numChilds = numChilds;
400 }
401
403 inline NodeID child(NodeID nodeID, uint32_t i) const { return m_tree[nodeID].child[i]; }
404
406 inline void setChild(NodeID nodeID, uint32_t i, NodeID c) { m_tree[nodeID].child[i] = c; }
407
409 inline bool isLeaf(NodeID nodeID) const { return !m_tree[nodeID].numChilds; }
410
412 inline bool isFence(NodeID nodeID) const { return m_tree[nodeID].fence; }
413
415 inline uint32_t numberOfPoints(NodeID nodeID) const { return m_tree[nodeID].numPoints; }
416
418 inline void setNumberOfPoints(NodeID nodeID, uint32_t numPoints) {
419 m_tree[nodeID].numPoints = numPoints;
420 }
421
423 inline NodeID root() const { return m_root; }
424
426 inline uint32_t numberOfPoints() const { return m_numPoints; }
427
430
432 inline uint32_t maxNumberOfNodes() const { return m_maxNumNodes; }
433
435 void clear();
436
439
442
444
445 inline NodeID pointLeaf(PointID point) const { return m_points[point].node; }
446
448
449 inline float pointX(PointID point) const { return m_pointXPos[point]; }
450
451 inline float pointY(PointID point) const { return m_pointYPos[point]; }
452
453 inline float pointSize(PointID point) const { return m_pointSize[point]; }
454
455 inline float* pointX() const { return m_pointXPos; }
456
457 inline float* pointY() const { return m_pointYPos; }
458
459 inline float* pointSize() const { return m_pointSize; }
460
461 inline float nodeX(NodeID nodeID) const { return m_nodeXPos[nodeID]; }
462
463 inline void setNodeX(NodeID nodeID, float x) { m_nodeXPos[nodeID] = x; }
464
465 inline float nodeY(NodeID nodeID) const { return m_nodeYPos[nodeID]; }
466
467 inline void setNodeY(NodeID nodeID, float y) { m_nodeYPos[nodeID] = y; }
468
469 inline float nodeSize(NodeID nodeID) const { return m_nodeSize[nodeID]; }
470
471 inline void setNodeSize(NodeID nodeID, float size) { m_nodeSize[nodeID] = size; }
472
473 void setPoint(PointID id, float x, float y, uint32_t ref) {
474 m_pointXPos[id] = x;
475 m_pointYPos[id] = y;
476 m_points[id].ref = ref;
477 }
478
480 uint32_t ref = m_points[id].ref;
481 m_pointXPos[id] = m_origXPos[ref];
482 m_pointYPos[id] = m_origYPos[ref];
483 m_pointSize[id] = m_origSize[ref];
484 }
485
486 void setPoint(PointID id, float x, float y, float r, uint32_t ref) {
487 m_pointXPos[id] = x;
488 m_pointYPos[id] = y;
489 m_pointSize[id] = r;
490 m_points[id].ref = ref;
491 }
492
493 void setPoint(PointID id, float x, float y, float r) {
494 m_pointXPos[id] = x;
495 m_pointYPos[id] = y;
496 m_pointSize[id] = r;
497 }
498
499 inline uint32_t refOfPoint(PointID id) const { return m_points[id].ref; }
500
501 inline NodeID nodeOfPoint(PointID id) const { return m_points[id].node; }
502
503 inline void nodeFence(NodeID nodeID) { m_tree[nodeID].fence = true; }
504
505 inline bool isWS(NodeID a, NodeID b) const {
506 float s = 0.00000001f;
507 float dx = nodeX(a) - nodeX(b);
508 float dy = nodeY(a) - nodeY(b);
509 float d_sq = dx * dx + dy * dy;
510 float size = max(nodeSize(a), nodeSize(b));
511 return d_sq > (s * 0.5 + 1) * (s * 0.5 + 1) * 2 * size * size;
512 }
513
515
517
518 inline NodeID firstInnerNode() const { return m_firstInner; }
519
520 inline uint32_t numberOfInnerNodes() const { return m_numInnerNodes; }
521
522 inline NodeID firstLeaf() const { return m_firstLeaf; }
523
524 inline uint32_t numberOfLeaves() const { return m_numLeaves; }
525
526 uint32_t numberOfWSP() const { return m_numWSP; }
527
529
531
532 inline NodeID directNode(uint32_t i) const { return m_directNodes[i]; }
533
534 inline NodeID directNodeA(uint32_t i) const { return m_notWspd[i].a; }
535
536 inline NodeID directNodeB(uint32_t i) const { return m_notWspd[i].b; }
537
538 WSPD* wspd() const { return m_WSPD; };
539
540 void init(float min_x, float min_y, float max_x, float max_y);
541
542 inline float minX() const { return m_min_x; }
543
544 inline float minY() const { return m_min_y; }
545
546 inline float maxX() const { return m_max_x; }
547
548 inline float maxY() const { return m_max_y; }
549
550 inline double scaleInv() const { return m_scaleInv; }
551
553 uint32_t ix, iy;
554 uint32_t level = this->level(nodeIndex);
555 float s = (float)(m_cellSize * (1 << level));
556 this->setNodeSize(nodeIndex, s);
557 MortonNR mnr = this->mortonNr(this->firstPoint(nodeIndex));
558 mnr = mnr >> (level * 2);
559 mnr = mnr << (level * 2);
561 this->setNodeX(nodeIndex,
562 (float)((m_sideLengthPoints * ((float)ix) - 0.5) / m_sideLengthGrid + (float)m_min_x
563 + (float)s * 0.5f));
564 this->setNodeY(nodeIndex,
565 (float)((m_sideLengthPoints * ((float)iy) - 0.5) / m_sideLengthGrid + (float)m_min_y
566 + (float)s * 0.5f));
567 }
568
570
572
573private:
576
579
580 inline void initLeaf(NodeID leaf, PointID firstPoint, uint32_t numPoints, NodeID next) {
581 m_tree[leaf].numChilds = 0;
582 m_tree[leaf].next = next;
583 m_tree[leaf].fence = 0;
584 m_tree[leaf].level = 0;
586 m_tree[leaf].numPoints = numPoints;
587 }
588
590 NodeID next) {
591 m_tree[nodeID].numChilds = 2;
592 m_tree[nodeID].child[0] = leftChild;
593 m_tree[nodeID].child[1] = rightChild;
594 m_tree[nodeID].next = next;
595 m_tree[nodeID].fence = 0;
596 m_tree[nodeID].level = level;
597 m_tree[nodeID].firstPoint = leftChild;
599 }
600
602 inline void nodeAppendChild(NodeID nodeID, NodeID child) {
603 m_tree[nodeID].child[m_tree[nodeID].numChilds++] = child;
605 }
606
612
615
618
621
623 float m_min_x;
624
626 float m_min_y;
627
629 float m_max_x;
630
632 float m_max_y;
633
636
639
642
645
648
651
654
657
660
663
666
667
670
673
676
679
682
685
687
690
693
696
699
702
705
708
711};
712
714 return a.mortonNr < b.mortonNr;
715}
716
717}
718}
Definitions of functors used in FME layout.
Definition of utility functions for FME layout.
#define OGDF_LQ_WSPD_BOUND
#define OGDF_LQ_WSPD_BRANCH_BOUND
#define OGDF_LQ_M2L_MIN_BOUND
float * m_origSize
point size in graph order
uint32_t m_numInnerNodes
number of inner nodes in the chain
uint32_t m_numPoints
number of points this quadtree is based on
void setFirstPoint(NodeID nodeID, PointID firstPoint)
add a direct pair to the array list of direct pairs
LQPoint * m_points
the point order in tree order
void setPoint(PointID id, float x, float y, float r, uint32_t ref)
void init(float min_x, float min_y, float max_x, float max_y)
float * m_pointSize
point size in tree order
bottom_up_traversal_functor< F > bottom_up_traversal(F f) const
creator
uint32_t numberOfPoints() const
returns the number of points in this tree
double m_sideLengthPoints
the maximum of height and width
void setChild(NodeID nodeID, uint32_t i, NodeID c)
sets the i th child index of node nodeID
void setNodeSize(NodeID nodeID, float size)
LinearQuadtree(uint32_t n, float *origXPos, float *origYPos, float *origSize)
constructor. required tree mem will be allocated
float m_max_y
the y coordinate of the top most point
NodeID m_firstLeaf
first leaf in the leaf chain
void deallocate()
helper function for releasing memory
bool isFence(NodeID nodeID) const
sets the fence flag for node nodeID
WSPD * m_WSPD
void setNumberOfChilds(NodeID nodeID, uint32_t numChilds)
sets the number of children of a node
const LQPoint & point(PointID pointID) const
uint32_t maxNumberOfNodes() const
the upper bound for a compressed quadtree (2*numPoints)
void leafAppendPoint(NodeID leaf, PointID point)
appends an successing point by simply increasing childcount of a leaf. Assumes isLeaf
void nodeAppendChild(NodeID nodeID, NodeID child)
appends one child index. Assumes childCount < 4 and not leaf
wspd_functor< A, B, C, ConditionType > forall_well_separated_pairs(A a, B b, C c, ConditionType cond)
uint32_t numberOfChilds(NodeID nodeID) const
returns the number of children of node nodeID. for an inner node this is 1..4 and can be accessed by ...
forall_ordered_pairs_of_children_functor< F > forall_ordered_pairs_of_children(F f) const
creator
void allocate(uint32_t n)
helper function for allocating the array's
LQNode * m_tree
the main tree array containing all nodes (including leaves)
uint32_t m_numLeaves
number of leaves in the chain
wspd_functor< A, B, C > forall_well_separated_pairs(A a, B b, C c)
void setLevel(NodeID nodeID, uint32_t level)
adds a well-separated pair to the wspd
forall_children_functor< F > forall_children(F f) const
creator
PointID findFirstPointInCell(PointID somePointInCell) const
float m_max_x
the x coordinate of the right most point
is_leaf_condition_functor is_leaf_condition() const
creator
destructor. tree mem will be released
void setPoint(PointID id, float x, float y, uint32_t ref)
is_fence_condition_functor is_fence_condition() const
creator
float m_min_x
the x coordinate of the left most point
add a direct node to the array list of direct nodes
NodeID child(NodeID nodeID, uint32_t i) const
returns the i th child index of node nodeID
void initLeaf(NodeID leaf, PointID firstPoint, uint32_t numPoints, NodeID next)
void setNumberOfPoints(NodeID nodeID, uint32_t numPoints)
sets the number of nodes containted in node nodeID
float m_min_y
the y coordinate of the bottom most point
bottom_up_traversal_functor< F, Cond > bottom_up_traversal(F f, Cond cond) const
creator
NodeID m_firstInner
first inner node in the inner node chain
void initInnerNode(NodeID nodeID, NodeID leftChild, NodeID rightChild, uint32_t level, NodeID next)
NodeID root() const
returns the index of the root
top_down_traversal_functor< F > top_down_traversal(F f) const
creator
uint32_t m_maxNumNodes
the maximum number of nodes (2*n here instead of 2*n-1)
double m_scaleInv
the inverse scale to transform
float * m_pointYPos
point y coord in tree order
forall_points_functor< Func > forall_points(const Func &func) const
creator
double m_cellSize
the height and width of a grid cell
bool isLeaf(NodeID nodeID) const
returns true if the given node index is a leaf
double m_sideLengthGrid
the resulting side length of the grid (constant)
float * m_pointXPos
point x coord in tree order
top_down_traversal_functor< F, Cond > top_down_traversal(F f, Cond cond) const
creator
void setNextNode(NodeID nodeID, NodeID next)
forall_tree_nodes_functor< F > forall_tree_nodes(F f, NodeID begin, uint32_t num) const
creator
float * m_origXPos
point x coord in graph order
float * m_origYPos
point y coord in graph order
void setPointLeaf(PointID point, NodeID leaf)
uint32_t numberOfPoints(NodeID nodeID) const
returns the number of points contained in the subtree of node nodeID
void setPoint(PointID id, float x, float y, float r)
uint32_t numberOfNodes() const
returns the number of nodes in this tree
Class for the Well-Separated-Pairs-Decomposition (WSPD)
Definition WSPD.h:41
int r[]