Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
DTreeMultilevelEmbedder.h
Go to the documentation of this file.
1
29#pragma once
30
35
36namespace ogdf {
37
38template<int Dim>
40public:
41 struct NodeCoords {
42 double coords[Dim];
43 };
44
70
72 void call(const Graph& graph, NodeArray<NodeCoords>& coords);
73
74private:
84
87};
88
90public:
91 void call(GraphAttributes& GA) override {
92 // the graph
93 const Graph& G = GA.constGraph();
94
95 // the input for the general d dim class
97
98 // call it
99 DTreeMultilevelEmbedder<2>::call(GA.constGraph(), coords);
100
101 // copy the coords back to graph attributes
102 for (node v = G.firstNode(); v; v = v->succ()) {
103 GA.x(v) = coords[v].coords[0];
104 GA.y(v) = coords[v].coords[1];
105 }
106 }
107};
108
110public:
111 void call(GraphAttributes& GA) override {
112 // assert 3d
114
115 // the graph
116 const Graph& G = GA.constGraph();
117
118 // the input for the general d dim class
120
121 // call it
122 DTreeMultilevelEmbedder<3>::call(GA.constGraph(), coords);
123
124 // copy the coords back to graph attributes
125 for (node v = G.firstNode(); v; v = v->succ()) {
126 GA.x(v) = coords[v].coords[0];
127 GA.y(v) = coords[v].coords[1];
128 GA.z(v) = coords[v].coords[2];
129 }
130 }
131};
132
133template<int Dim>
135 using namespace energybased::dtree;
137
138 // we call this just in case
139 resultCoords.init(graph);
140
141 // make sure the graph is connected
142 OGDF_ASSERT(isConnected(graph));
143
144 // setup the multilevel step
145 GalaxyLevel levelBegin(graph);
146
147 // this is the coarsest level with at most m_levelMaxNumNodes
148 GalaxyLevel* pLevelEnd = levelBegin.buildLevelsUntil(m_levelMaxNumNodes);
149
150 // this array will hold the layout information of the parent node in the coarser level.
151 // furthermore this will keep the final result.
153
154 double currNumIterations = m_numIterationsFinestLevel;
155 double currThreshold = m_thresholdFinestLevel;
156
157 // loop from the coarsest to the finest level
158 for (GalaxyLevel* pCurrLevel = &levelBegin; pCurrLevel != nullptr;
159 pCurrLevel = pCurrLevel->nextCoarser()) {
160 currNumIterations *= m_numIterationsFactorPerLevel;
161 currThreshold *= m_thresholdFactorPerLevel;
162 }
163
164 // now we loop from the coarsest to the finest level
165 for (GalaxyLevel* pCurrLevel = pLevelEnd; pCurrLevel; pCurrLevel = pCurrLevel->nextFiner()) {
166 currNumIterations /= m_numIterationsFactorPerLevel;
167 currThreshold /= m_thresholdFactorPerLevel;
168
169 // new embedder instance for the current level
170 Embedder embedder(pCurrLevel->graph());
171
172 // if this is coarsest one
173 if (pCurrLevel->isCoarsestLevel()) {
174 // we cannot init from the parent level, do it random
175 for (node v = pCurrLevel->graph().firstNode(); v; v = v->succ()) {
176 // for all dims
177 for (int d = 0; d < Dim; d++) {
178 // set the position to some random value
179 embedder.setPosition(v, d, randomDouble(-1.0, 1.0));
180 }
181 }
182 } else { // if we have a parent level
183 // iterate over all nodes
184 for (node v = pCurrLevel->graph().firstNode(); v; v = v->succ()) {
185 // this is a node on the coarser level we already processed
186 node v_parent = pCurrLevel->parent(v);
187
188 // now init the position from the parent.
189 for (int d = 0; d < Dim; d++) {
190 // get the position of the parent
191 double offset = parentPosition[v_parent].coords[d] * m_scaleFactorPerLevel;
192
193 // set v's position to the parents pos with some random
194 embedder.setPosition(v, d, offset + randomDouble(-1.0, 1.0));
195 }
196 }
197 }
198 // we have some proper initial coordinates for the nodes
199
200 if (m_useMultilevelWeights) {
201 // we cannot init from the parent level, do it random
202 for (node v = pCurrLevel->graph().firstNode(); v; v = v->succ()) {
203 embedder.setMass(v, pCurrLevel->weight(v));
204 }
205
206 for (edge e = pCurrLevel->graph().firstEdge(); e; e = e->succ()) {
207 embedder.setEdgeWeight(e, pCurrLevel->edgeWeight(e));
208 }
209 }
210
211 const int numIterationsMaybe =
212 pCurrLevel->isCoarsestLevel() ? m_numIterationsCoarsestLevel : currNumIterations;
213 const int numIterations = std::min(std::max(m_minIterationsPerLevel, numIterationsMaybe),
214 m_maxIterationsPerLevel);
215
216 embedder.scaleNodes(3.0);
217 embedder.doIterationsNewton(numIterations, currThreshold, RepForceFunctionNewton<Dim, 1>,
219 embedder.scaleNodes(1.0 / 3.0);
220 embedder.doIterationsNewton(numIterations, currThreshold, RepForceFunctionNewton<Dim, 2>,
222 // run the layout
223
224 // we now have to backup the positions before getting rid of the embedder
225 parentPosition.init(pCurrLevel->graph());
226
227 // iterate over all nodes
228 for (node v = pCurrLevel->graph().firstNode(); v; v = v->succ()) {
229 // for all coords
230 for (int d = 0; d < Dim; d++) {
231 parentPosition[v].coords[d] = embedder.position(v, d);
232 }
233 }
234 }
235
236 // we are done with the layout. It is saved now in the parentposition nodearray.
237 // which is a reference to the result array
238}
239
240}
Declaration of interface for layout algorithms (class LayoutModule)
void call(GraphAttributes &GA) override
Computes a layout of graph GA.
void call(GraphAttributes &GA) override
Computes a layout of graph GA.
DTreeMultilevelEmbedder()
constructor with a given graph, allocates memory and does initialization
void call(const Graph &graph, NodeArray< NodeCoords > &coords)
call the multilevel embedder layout for graph, the result is stored in coords
Class for the representation of edges.
Definition Graph_d.h:300
Stores additional attributes of a graph (like layout information).
static const long threeD
Corresponds to node attribute z(node). Note that all methods work on 2D coordinates only.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Interface of general layout algorithms.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
bool isConnected(const Graph &G)
Returns true iff G is connected.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
double randomDouble(double low, double high)
Returns a random double value from the interval [low, high).
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Declaration of simple graph algorithms.