Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
LinearQuadtree.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/basic.h>
37
38#include <algorithm>
39#include <cstdint>
40
41#define OGDF_LQ_M2L_MIN_BOUND 8
42#define OGDF_LQ_WSPD_BRANCH_BOUND 16
43#define OGDF_LQ_WSPD_BOUND 25
44
45namespace ogdf {
46namespace fast_multipole_embedder {
47
48class WSPD;
49
53
54public:
55 using NodeID = unsigned int;
56 using PointID = unsigned int;
57
58 struct LQPoint // 16 byte
59 {
60 MortonNR mortonNr; // 8 byte
61 uint32_t node; // 4 byte
62 uint32_t ref; // 4 byte
63 };
64
65 struct LQNode // 27 byte
66 {
67 uint32_t level; // 4 byte
68 NodeID next; // 4 byte
69 NodeID child[4]; // 4 byte *4 = 16 byte
70 uint32_t numChilds; // 4 byte
72 uint32_t numPoints; // 4 byte
73 bool fence; // 1 byte
74 };
75
76 struct LQWSPair {
77 LQWSPair(NodeID c, NodeID d) : a(c), b(d) {};
80 };
81
84
86
87 inline bool operator()(NodeID u) { return tree.isFence(u); }
88 };
89
94
97
99
100 inline bool operator()(NodeID u) { return tree.isLeaf(u); }
101 };
102
107
109 template<typename F>
114 uint32_t numNodes;
115
116 forall_tree_nodes_functor(const LinearQuadtree& t, F f, NodeID b, uint32_t num)
117 : tree(t), func(f), begin(b), numNodes(num) { }
118
119 inline void operator()() {
120 NodeID it = begin;
121 for (uint32_t i = 0; i < numNodes; i++) {
122 func(it);
123 it = tree.nextNode(it);
124 }
125 }
126 };
127
129 template<typename F>
131 return forall_tree_nodes_functor<F>(*this, f, begin, num);
132 }
133
135 template<typename F>
139
141
142 inline void operator()(NodeID u) {
143 if (tree.isLeaf(u)) {
144 return;
145 }
146 for (uint32_t i = 0; i < tree.numberOfChilds(u); i++) {
147 func(tree.child(u, i));
148 }
149 }
150 };
151
153 template<typename F>
155 return forall_children_functor<F>(*this, f);
156 }
157
159 template<typename Func>
162 Func func;
163
164 forall_points_functor(const LinearQuadtree& t, const Func& f) : tree(t), func(f) { }
165
166 inline void operator()(NodeID u) {
169 for (PointID i = firstPoint; i < end; i++) {
170 func(i);
171 }
172 }
173 };
174
176 template<typename Func>
177 inline forall_points_functor<Func> forall_points(const Func& func) const {
178 return forall_points_functor<Func>(*this, func);
179 }
180
182 template<typename F>
186
189
190 inline void operator()(NodeID u) {
191 if (tree.isLeaf(u)) {
192 return;
193 }
194 for (uint32_t i = 0; i < tree.numberOfChilds(u); i++) {
195 for (uint32_t j = i + 1; j < tree.numberOfChilds(u); j++) {
196 func(tree.child(u, i), tree.child(u, j));
197 }
198 }
199 }
200 };
201
203 template<typename F>
207
209 template<typename F, typename CondType = true_condition>
213 CondType cond;
214
216
218 : tree(t), func(f), cond(c) { }
219
220 inline void operator()(NodeID u) {
221 if (cond(u)) {
222 func(u);
223 tree.forall_children (*this)(u);
224 };
225 }
226 };
227
229 template<typename F>
233
235 template<typename F, typename Cond>
237 return top_down_traversal_functor<F, Cond>(*this, f, cond);
238 }
239
241 template<typename F, typename CondType = true_condition>
245 CondType cond;
246
248
250 : tree(t), func(f), cond(c) { }
251
252 inline void operator()(NodeID u) {
253 if (cond(u)) {
254 tree.forall_children (*this)(u);
255 func(u);
256 };
257 }
258 };
259
261 template<typename F>
265
267 template<typename F, typename Cond>
269 return bottom_up_traversal_functor<F, Cond>(*this, f, cond);
270 }
271
272 template<typename WSPairFuncType, typename DPairFuncType, typename DNodeFuncType,
273 typename BranchCondType = true_condition>
276 WSPairFuncType WSFunction;
277 DPairFuncType DPairFunction;
278 DNodeFuncType DNodeFunction;
279 BranchCondType BranchCondFunction;
280
281 wspd_functor(const LinearQuadtree& t, WSPairFuncType& wsf, DPairFuncType& dpf,
282 DNodeFuncType& dnf)
283 : tree(t), WSFunction(wsf), DPairFunction(dpf), DNodeFunction(dnf) { }
284
285 wspd_functor(const LinearQuadtree& t, WSPairFuncType& wsf, DPairFuncType& dpf,
286 DNodeFuncType& dnf, BranchCondType& bc)
287 : tree(t)
288 , WSFunction(wsf)
289 , DPairFunction(dpf)
290 , DNodeFunction(dnf)
291 , BranchCondFunction(bc) { }
292
293 inline void operator()(NodeID u) {
294 if (BranchCondFunction(u)) {
296 if (tree.numberOfPoints(u) > 1) {
297 DNodeFunction(u);
298 }
299 } else {
300 tree.forall_children (*this)(u);
302 }
303 }
304 }
305
306 inline void operator()(NodeID u, NodeID v) {
307 if (tree.isWS(u, v)) {
310 DPairFunction(u, v);
311 } else {
312 WSFunction(u, v);
313 }
314 } else {
317 || tree.isLeaf(u) || tree.isLeaf(v)) {
318 DPairFunction(u, v);
319 } else {
320 if (tree.level(u) >= tree.level(v)) {
321 tree.forall_children(pair_call(*this, v))(u);
322 } else {
323 tree.forall_children(pair_call(*this, u))(v);
324 }
325 }
326 }
327 }
328 };
329
330 template<typename A, typename B, typename C, typename ConditionType>
332 ConditionType cond) {
333 return wspd_functor<A, B, C, ConditionType>(*this, a, b, c, cond);
334 }
335
336 template<typename A, typename B, typename C>
338 return wspd_functor<A, B, C>(*this, a, b, c);
339 }
340
348
350
358
362
370
374
375 inline NodeID level(NodeID nodeID) const { return m_tree[nodeID].level; }
376
377 inline NodeID nextNode(NodeID nodeID) const { return m_tree[nodeID].next; }
378
379 inline void setNextNode(NodeID nodeID, NodeID next) { m_tree[nodeID].next = next; }
380
381 inline void setLevel(NodeID nodeID, uint32_t level) { m_tree[nodeID].level = level; }
382
383 inline PointID firstPoint(NodeID nodeID) const { return m_tree[nodeID].firstPoint; }
384
385 inline void setFirstPoint(NodeID nodeID, PointID firstPoint) {
386 m_tree[nodeID].firstPoint = firstPoint;
387 }
388
389 inline LQPoint& point(PointID pointID) { return m_points[pointID]; }
390
391 inline const LQPoint& point(PointID pointID) const { return m_points[pointID]; }
392
394
398 inline uint32_t numberOfChilds(NodeID nodeID) const { return m_tree[nodeID].numChilds; }
399
401 inline void setNumberOfChilds(NodeID nodeID, uint32_t numChilds) {
402 m_tree[nodeID].numChilds = numChilds;
403 }
404
406 inline NodeID child(NodeID nodeID, uint32_t i) const { return m_tree[nodeID].child[i]; }
407
409 inline void setChild(NodeID nodeID, uint32_t i, NodeID c) { m_tree[nodeID].child[i] = c; }
410
412 inline bool isLeaf(NodeID nodeID) const { return !m_tree[nodeID].numChilds; }
413
415 inline bool isFence(NodeID nodeID) const { return m_tree[nodeID].fence; }
416
418 inline uint32_t numberOfPoints(NodeID nodeID) const { return m_tree[nodeID].numPoints; }
419
421 inline void setNumberOfPoints(NodeID nodeID, uint32_t numPoints) {
422 m_tree[nodeID].numPoints = numPoints;
423 }
424
426 inline NodeID root() const { return m_root; }
427
429 inline uint32_t numberOfPoints() const { return m_numPoints; }
430
432 inline uint32_t numberOfNodes() const { return m_numInnerNodes + m_numLeaves; }
433
435 inline uint32_t maxNumberOfNodes() const { return m_maxNumNodes; }
436
438 void clear();
439
441 LinearQuadtree(uint32_t n, float* origXPos, float* origYPos, float* origSize);
442
445
446 uint64_t sizeInBytes() const;
447
448 inline NodeID pointLeaf(PointID point) const { return m_points[point].node; }
449
450 inline void setPointLeaf(PointID point, NodeID leaf) { m_points[point].node = leaf; }
451
452 inline float pointX(PointID point) const { return m_pointXPos[point]; }
453
454 inline float pointY(PointID point) const { return m_pointYPos[point]; }
455
456 inline float pointSize(PointID point) const { return m_pointSize[point]; }
457
458 inline float* pointX() const { return m_pointXPos; }
459
460 inline float* pointY() const { return m_pointYPos; }
461
462 inline float* pointSize() const { return m_pointSize; }
463
464 inline float nodeX(NodeID nodeID) const { return m_nodeXPos[nodeID]; }
465
466 inline void setNodeX(NodeID nodeID, float x) { m_nodeXPos[nodeID] = x; }
467
468 inline float nodeY(NodeID nodeID) const { return m_nodeYPos[nodeID]; }
469
470 inline void setNodeY(NodeID nodeID, float y) { m_nodeYPos[nodeID] = y; }
471
472 inline float nodeSize(NodeID nodeID) const { return m_nodeSize[nodeID]; }
473
474 inline void setNodeSize(NodeID nodeID, float size) { m_nodeSize[nodeID] = size; }
475
476 void setPoint(PointID id, float x, float y, uint32_t ref) {
477 m_pointXPos[id] = x;
478 m_pointYPos[id] = y;
479 m_points[id].ref = ref;
480 }
481
483 uint32_t ref = m_points[id].ref;
484 m_pointXPos[id] = m_origXPos[ref];
485 m_pointYPos[id] = m_origYPos[ref];
486 m_pointSize[id] = m_origSize[ref];
487 }
488
489 void setPoint(PointID id, float x, float y, float r, uint32_t ref) {
490 m_pointXPos[id] = x;
491 m_pointYPos[id] = y;
492 m_pointSize[id] = r;
493 m_points[id].ref = ref;
494 }
495
496 void setPoint(PointID id, float x, float y, float r) {
497 m_pointXPos[id] = x;
498 m_pointYPos[id] = y;
499 m_pointSize[id] = r;
500 }
501
502 inline uint32_t refOfPoint(PointID id) const { return m_points[id].ref; }
503
504 inline NodeID nodeOfPoint(PointID id) const { return m_points[id].node; }
505
506 inline void nodeFence(NodeID nodeID) { m_tree[nodeID].fence = true; }
507
508 inline bool isWS(NodeID a, NodeID b) const {
509 float s = 0.00000001f;
510 float dx = nodeX(a) - nodeX(b);
511 float dy = nodeY(a) - nodeY(b);
512 float d_sq = dx * dx + dy * dy;
513 float size = max(nodeSize(a), nodeSize(b));
514 return d_sq > (s * 0.5 + 1) * (s * 0.5 + 1) * 2 * size * size;
515 }
516
518
520
521 inline NodeID firstInnerNode() const { return m_firstInner; }
522
523 inline uint32_t numberOfInnerNodes() const { return m_numInnerNodes; }
524
525 inline NodeID firstLeaf() const { return m_firstLeaf; }
526
527 inline uint32_t numberOfLeaves() const { return m_numLeaves; }
528
529 uint32_t numberOfWSP() const { return m_numWSP; }
530
531 uint32_t numberOfDirectPairs() const { return m_numNotWSP; }
532
533 uint32_t numberOfDirectNodes() const { return m_numDirectNodes; }
534
535 inline NodeID directNode(uint32_t i) const { return m_directNodes[i]; }
536
537 inline NodeID directNodeA(uint32_t i) const { return m_notWspd[i].a; }
538
539 inline NodeID directNodeB(uint32_t i) const { return m_notWspd[i].b; }
540
541 WSPD* wspd() const { return m_WSPD; };
542
543 void init(float min_x, float min_y, float max_x, float max_y);
544
545 inline float minX() const { return m_min_x; }
546
547 inline float minY() const { return m_min_y; }
548
549 inline float maxX() const { return m_max_x; }
550
551 inline float maxY() const { return m_max_y; }
552
553 inline double scaleInv() const { return m_scaleInv; }
554
555 inline void computeCoords(NodeID nodeIndex) {
556 uint32_t ix, iy;
557 uint32_t level = this->level(nodeIndex);
558 float s = (float)(m_cellSize * (1 << level));
559 this->setNodeSize(nodeIndex, s);
560 MortonNR mnr = this->mortonNr(this->firstPoint(nodeIndex));
561 mnr = mnr >> (level * 2);
562 mnr = mnr << (level * 2);
563 mortonNumberInv<uint64_t, uint32_t>(mnr, ix, iy);
564 this->setNodeX(nodeIndex,
565 (float)((m_sideLengthPoints * ((float)ix) - 0.5) / m_sideLengthGrid + (float)m_min_x
566 + (float)s * 0.5f));
567 this->setNodeY(nodeIndex,
568 (float)((m_sideLengthPoints * ((float)iy) - 0.5) / m_sideLengthGrid + (float)m_min_y
569 + (float)s * 0.5f));
570 }
571
573
574 PointID findFirstPointInCell(PointID somePointInCell) const;
575
576private:
578 void allocate(uint32_t n);
579
582
583 inline void initLeaf(NodeID leaf, PointID firstPoint, uint32_t numPoints, NodeID next) {
584 m_tree[leaf].numChilds = 0;
585 m_tree[leaf].next = next;
586 m_tree[leaf].fence = 0;
587 m_tree[leaf].level = 0;
589 m_tree[leaf].numPoints = numPoints;
590 }
591
592 inline void initInnerNode(NodeID nodeID, NodeID leftChild, NodeID rightChild, uint32_t level,
593 NodeID next) {
594 m_tree[nodeID].numChilds = 2;
595 m_tree[nodeID].child[0] = leftChild;
596 m_tree[nodeID].child[1] = rightChild;
597 m_tree[nodeID].next = next;
598 m_tree[nodeID].fence = 0;
599 m_tree[nodeID].level = level;
600 m_tree[nodeID].firstPoint = leftChild;
601 m_tree[nodeID].numPoints = rightChild - leftChild;
602 }
603
605 inline void nodeAppendChild(NodeID nodeID, NodeID child) {
606 m_tree[nodeID].child[m_tree[nodeID].numChilds++] = child;
608 }
609
611 inline void leafAppendPoint(NodeID leaf, PointID point) {
612 m_points[point].node = leaf;
613 m_tree[leaf].numPoints++;
614 }
615
618
621
624
626 float m_min_x;
627
629 float m_min_y;
630
632 float m_max_x;
633
635 float m_max_y;
636
639
642
645
648
651
654
657
660
663
666
669
670
673
676
679
682
685
687 uint32_t m_numPoints;
688
689 uint32_t m_numWSP;
690
692 uint32_t m_numNotWSP;
693
696
699
702
705
707 uint32_t m_numLeaves;
708
711
714};
715
717 return a.mortonNr < b.mortonNr;
718}
719
720}
721}
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
Basic declarations, included by all source files.
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)
void addDirectPair(NodeID s, NodeID t)
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
the wspd of this quadtree
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)
void addWSPD(NodeID s, NodeID t)
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
~LinearQuadtree(void)
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
void addDirect(NodeID s)
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:43
static pair_call_functor< F, A > pair_call(F f, A a)
creates a pair call resulting in a call f(a, *)
bool LQPointComparer(const LinearQuadtree::LQPoint &a, const LinearQuadtree::LQPoint &b)
The namespace for all OGDF objects.
HypergraphRegistry< HypernodeElement >::iterator begin(const HypergraphRegistry< HypernodeElement > &self)
HypergraphRegistry< HypernodeElement >::iterator end(const HypergraphRegistry< HypernodeElement > &self)
simple functor for iterating over all children of a node
functor for iterating over all ordered pairs of children of a node
simple functor for iterating over all points of a node
forall_tree_nodes_functor(const LinearQuadtree &t, F f, NodeID b, uint32_t num)
wspd_functor(const LinearQuadtree &t, WSPairFuncType &wsf, DPairFuncType &dpf, DNodeFuncType &dnf, BranchCondType &bc)
wspd_functor(const LinearQuadtree &t, WSPairFuncType &wsf, DPairFuncType &dpf, DNodeFuncType &dnf)
condition functor for returning a constant boolean value