OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
Go to the documentation of this file.
1
32#pragma once
33
34
36
37namespace ogdf {
38namespace fast_multipole_embedder {
39
42public:
45 : firstInner(0)
46 , firstLeaf(0)
47 , lastInner(0)
48 , lastLeaf(0)
49 , numInnerNodes(0)
50 , numLeaves(0)
51 , tree(treeRef)
54 }
55
57 void build();
58
61
64
67
70
73
76
81 } else {
83 }
86 }
87
104
105 inline void restoreChain() {
107 numInnerNodes = 0;
108 if (!tree.isLeaf(tree.root())) {
110 }
113 }
114 }
115
118 // 64 bit version
119#if 0
120 // FIXME: a < 0 is always true (PointID is unsigned int)
121 if (a < 0) return 64;
122#endif
123 if (b >= tree.numberOfPoints()) {
124 return 64;
125 }
126 uint32_t res = (32 - ((mostSignificantBit(tree.mortonNr(a) ^ tree.mortonNr(b))) / 2));
127 return res;
128 }
129
132
137
141};
142
143}
144}
Definition of utility functions for FME layout.
returns the level of the first common ancestor of a and b
merges the node curr with curr's next node by appending the next nodes children to curr except the fi...
used by restore chain
constructor
prepares the node and leaf layer from position begin until end (excluding end)
void prepareTree()
prepares the node and leaf layer for the complete tree from 0 to n (excluding n)
prepares the node and leaf layer at position leafPos where nextLeafPos is the next position
void buildHierarchy()
the main function for the new link-only recursive builder
void setFirstPoint(NodeID nodeID, PointID firstPoint)
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 ...
NodeID child(NodeID nodeID, uint32_t i) const
returns the i th child index of node nodeID
void setNumberOfPoints(NodeID nodeID, uint32_t numPoints)
sets the number of nodes containted in node nodeID
NodeID root() const
returns the index of the root
bool isLeaf(NodeID nodeID) const
returns true if the given node index is a leaf
void setNextNode(NodeID nodeID, NodeID next)
uint32_t numberOfPoints(NodeID nodeID) const
returns the number of points contained in the subtree of node nodeID