1 /** \file
2 * \brief Implementation of class FastMultipoleEmbedder.
3 *
4 * \author Martin Gronemann
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32 #include <ogdf/energybased/FastMultipoleEmbedder.h>
33 #include <ogdf/energybased/fast_multipole_embedder/FMEMultipoleKernel.h>
34 #include <ogdf/fileformats/GraphIO.h>
35
36 namespace ogdf {
37
38 using namespace fast_multipole_embedder;
39
FastMultipoleEmbedder()40 FastMultipoleEmbedder::FastMultipoleEmbedder()
41 {
42 m_precisionParameter = 5;
43 m_defaultEdgeLength = 1.0;
44 m_defaultNodeSize = 1.0;
45 m_numIterations = 100;
46 m_randomize = true;
47 m_numberOfThreads = 0;
48 m_maxNumberOfThreads = 1; //the only save value
49 }
50
~FastMultipoleEmbedder(void)51 FastMultipoleEmbedder::~FastMultipoleEmbedder(void)
52 {
53 // nothing
54 }
55
initOptions()56 void FastMultipoleEmbedder::initOptions()
57 {
58 m_pOptions->preProcTimeStep = 0.5;
59 m_pOptions->preProcMaxNumIterations = 20;
60 m_pOptions->preProcEdgeForceFactor = 0.5;
61 m_pOptions->timeStep = 0.25;
62 m_pOptions->edgeForceFactor = 1.0;
63 m_pOptions->repForceFactor = 2.0;
64 m_pOptions->stopCritConstSq = 2000400;
65 m_pOptions->stopCritAvgForce = 0.1f;
66 m_pOptions->minNumIterations = 4;
67 m_pOptions->multipolePrecision = m_precisionParameter;
68 }
69
70 #if 0
71 void FastMultipoleEmbedder::call(MultilevelGraph &MLG)
72 {
73 Graph &G = MLG.getGraph();
74 call(G, MLG.getXArray(), MLG.getYArray(), MLG.getWArray(), MLG.getRArray());
75 }
76 #endif
77
call(const Graph & G,NodeArray<float> & nodeXPosition,NodeArray<float> & nodeYPosition,const EdgeArray<float> & edgeLength,const NodeArray<float> & nodeSize)78 void FastMultipoleEmbedder::call(const Graph& G,
79 NodeArray<float>& nodeXPosition, NodeArray<float>& nodeYPosition,
80 const EdgeArray<float>& edgeLength, const NodeArray<float>& nodeSize)
81 {
82 allocate(G.numberOfNodes(), G.numberOfEdges());
83 m_pGraph->readFrom(G, nodeXPosition, nodeYPosition, edgeLength, nodeSize);
84 run(m_numIterations);
85 m_pGraph->writeTo(G, nodeXPosition, nodeYPosition);
86 deallocate();
87 }
88
call(GraphAttributes & GA)89 void FastMultipoleEmbedder::call(GraphAttributes &GA)
90 {
91 EdgeArray<float> edgeLength(GA.constGraph());
92 NodeArray<float> nodeSize(GA.constGraph());
93
94 for(node v : GA.constGraph().nodes)
95 {
96 nodeSize[v] = (float)sqrt(GA.width(v)*GA.width(v) + GA.height(v)*GA.height(v)) * 0.5f;
97 }
98
99 for(edge e : GA.constGraph().edges)
100 {
101 edgeLength[e] = nodeSize[e->source()] + nodeSize[e->target()];
102 }
103 call(GA, edgeLength, nodeSize);
104 }
105
call(GraphAttributes & GA,const EdgeArray<float> & edgeLength,const NodeArray<float> & nodeSize)106 void FastMultipoleEmbedder::call(GraphAttributes &GA, const EdgeArray<float>& edgeLength, const NodeArray<float>& nodeSize)
107 {
108 allocate(GA.constGraph().numberOfNodes(), GA.constGraph().numberOfEdges());
109 m_pGraph->readFrom(GA, edgeLength, nodeSize);
110 run(m_numIterations);
111 m_pGraph->writeTo(GA);
112 deallocate();
113
114 for(edge e : GA.constGraph().edges)
115 {
116 GA.bends(e).clear();
117 }
118 }
119
run(uint32_t numIterations)120 void FastMultipoleEmbedder::run(uint32_t numIterations)
121 {
122 if (m_pGraph->numNodes() == 0) return;
123 if (m_pGraph->numNodes() == 1)
124 {
125 m_pGraph->nodeXPos()[0] = 0.0f;
126 m_pGraph->nodeYPos()[0] = 0.0f;
127 return;
128 }
129
130 if (m_randomize)
131 {
132 double avgNodeSize = 0.0;
133 for (uint32_t i = 0; i < m_pGraph->numNodes(); i++)
134 {
135 avgNodeSize += m_pGraph->nodeSize()[i];
136 }
137
138 avgNodeSize = (avgNodeSize / (double)m_pGraph->numNodes());
139 for (uint32_t i = 0; i < m_pGraph->numNodes(); i++)
140 {
141 m_pGraph->nodeXPos()[i] = (float)(randomDouble(-(double)m_pGraph->numNodes(), (double)m_pGraph->numNodes())*avgNodeSize*2);
142 m_pGraph->nodeYPos()[i] = (float)(randomDouble(-(double)m_pGraph->numNodes(), (double)m_pGraph->numNodes())*avgNodeSize*2);
143 }
144 }
145
146 m_pOptions->maxNumIterations = numIterations;
147 m_pOptions->stopCritForce = (((float)m_pGraph->numNodes())*((float)m_pGraph->numNodes())*m_pGraph->avgNodeSize()) / m_pOptions->stopCritConstSq;
148 if (m_pGraph->numNodes() < 100)
149 runSingle();
150 else
151 runMultipole();
152 }
153
154
runMultipole()155 void FastMultipoleEmbedder::runMultipole()
156 {
157 FMEGlobalContext* pGlobalContext = FMEMultipoleKernel::allocateContext(m_pGraph, m_pOptions, m_threadPool->numThreads());
158 m_threadPool->runKernel<FMEMultipoleKernel>(pGlobalContext);
159 FMEMultipoleKernel::deallocateContext(pGlobalContext);
160 }
161
162
runSingle()163 void FastMultipoleEmbedder::runSingle()
164 {
165 FMESingleKernel kernel;
166 kernel(*m_pGraph, m_pOptions->timeStep, m_pOptions->minNumIterations, m_pOptions->maxNumIterations, m_pOptions->stopCritForce);
167 }
168
169
allocate(uint32_t numNodes,uint32_t numEdges)170 void FastMultipoleEmbedder::allocate(uint32_t numNodes, uint32_t numEdges)
171 {
172 m_pOptions = new FMEGlobalOptions();
173 m_pGraph = new ArrayGraph(numNodes, numEdges);
174 initOptions();
175 if (!m_maxNumberOfThreads)
176 {
177 uint32_t availableThreads = System::numberOfProcessors();
178 uint32_t minNodesPerThread = 100;
179 m_numberOfThreads = numNodes / minNodesPerThread;
180 m_numberOfThreads = max<uint32_t>(1, m_numberOfThreads);
181 m_numberOfThreads = prevPowerOfTwo(min<uint32_t>(m_numberOfThreads, availableThreads));
182 } else
183 {
184 uint32_t availableThreads = min<uint32_t>(m_maxNumberOfThreads, System::numberOfProcessors());
185 uint32_t minNodesPerThread = 100;
186 m_numberOfThreads = numNodes / minNodesPerThread;
187 m_numberOfThreads = max<uint32_t>(1, m_numberOfThreads);
188 m_numberOfThreads = prevPowerOfTwo(min<uint32_t>(m_numberOfThreads, availableThreads));
189 }
190 m_threadPool = new FMEThreadPool(m_numberOfThreads);
191 }
192
193
deallocate()194 void FastMultipoleEmbedder::deallocate()
195 {
196 delete m_threadPool;
197 delete m_pGraph;
198 delete m_pOptions;
199 }
200
201
202
dumpCurrentLevel(const char * filename)203 void FastMultipoleMultilevelEmbedder::dumpCurrentLevel(const char *filename)
204 {
205 const Graph& G = *(m_pCurrentLevel->m_pGraph);
206 GraphAttributes GA(G);
207
208 for(node v : G.nodes)
209 {
210 GalaxyMultilevel::LevelNodeInfo& nodeInfo = (*(m_pCurrentLevel->m_pNodeInfo))[v];
211 GA.x(v) = (*m_pCurrentNodeXPos)[v];
212 GA.y(v) = (*m_pCurrentNodeYPos)[v];
213 GA.width(v) = GA.height(v)= nodeInfo.radius / sqrt(2.0);
214 }
215 GraphIO::write(GA, filename, GraphIO::writeGML);
216 }
217
call(GraphAttributes & GA)218 void FastMultipoleMultilevelEmbedder::call(GraphAttributes &GA)
219 {
220 EdgeArray<float> edgeLengthAuto(GA.constGraph());
221 computeAutoEdgeLength(GA, edgeLengthAuto);
222 const Graph& t = GA.constGraph();
223 if (t.numberOfNodes() <= 25)
224 {
225 FastMultipoleEmbedder fme;
226 fme.setNumberOfThreads(this->m_iMaxNumThreads);
227 fme.setRandomize(true);
228 fme.setNumIterations(500);
229 fme.call(GA);
230 return;
231 }
232
233 run(GA, edgeLengthAuto);
234
235 for(edge e : GA.constGraph().edges)
236 {
237 GA.bends(e).clear();
238 }
239 }
240
computeAutoEdgeLength(const GraphAttributes & GA,EdgeArray<float> & edgeLength,float factor)241 void FastMultipoleMultilevelEmbedder::computeAutoEdgeLength(const GraphAttributes& GA, EdgeArray<float>& edgeLength, float factor)
242 {
243 for(edge e : GA.constGraph().edges)
244 {
245 node v = e->source();
246 node w = e->target();
247 float radius_v = (float)sqrt(GA.width(v)*GA.width(v) + GA.height(v)*GA.height(v)) * 0.5f;
248 float radius_w = (float)sqrt(GA.width(w)*GA.width(w) + GA.height(w)*GA.height(w)) * 0.5f;
249 float sum = radius_v + radius_w;
250 if (OGDF_GEOM_ET.equal(sum, (float) 0))
251 sum = 1.0;
252 edgeLength[e] = factor*(sum);
253 }
254 }
255
run(GraphAttributes & GA,const EdgeArray<float> & edgeLength)256 void FastMultipoleMultilevelEmbedder::run(GraphAttributes& GA, const EdgeArray<float>& edgeLength)
257 {
258 // too lazy for new, delete
259 NodeArray<float> nodeXPos1;
260 NodeArray<float> nodeYPos1;
261 NodeArray<float> nodeXPos2;
262 NodeArray<float> nodeYPos2;
263 EdgeArray<float> edgeLength1;
264 NodeArray<float> nodeSize1;
265
266 m_pCurrentNodeXPos = &nodeXPos1;
267 m_pCurrentNodeYPos = &nodeYPos1;
268 m_pLastNodeXPos = &nodeXPos2;
269 m_pLastNodeYPos = &nodeYPos2;
270 m_pCurrentEdgeLength= &edgeLength1;
271 m_pCurrentNodeSize = &nodeSize1;
272 Graph* pGraph = const_cast<Graph*>(&(GA.constGraph()));
273
274 // create all multilevels
275 this->createMultiLevelGraphs(pGraph, GA, edgeLength);
276 // init the coarsest level
277 initCurrentLevel();
278
279 // layout the current level
280 layoutCurrentLevel();
281
282 //proceed with remaining levels
283 while (m_iCurrentLevelNr > 0)
284 {
285 // move to finer level
286 nextLevel();
287 // init the arrays for current level
288 initCurrentLevel();
289 // assign positions from last to current
290 assignPositionsFromPrevLevel();
291 // layout the current level
292 layoutCurrentLevel();
293 }
294 // the finest level is processed
295 // assumes m_pCurrentGraph == GA.constGraph
296 writeCurrentToGraphAttributes(GA);
297 // clean up multilevels
298 deleteMultiLevelGraphs();
299 }
300
createMultiLevelGraphs(Graph * pGraph,GraphAttributes & GA,const EdgeArray<float> & finestLevelEdgeLength)301 void FastMultipoleMultilevelEmbedder::createMultiLevelGraphs(Graph* pGraph, GraphAttributes& GA, const EdgeArray<float>& finestLevelEdgeLength)
302 {
303 m_pCurrentLevel = new GalaxyMultilevel(pGraph);
304 m_pFinestLevel = m_pCurrentLevel;
305 initFinestLevel(GA, finestLevelEdgeLength);
306 m_iNumLevels = 1;
307 m_iCurrentLevelNr = 0;
308
309 GalaxyMultilevelBuilder builder;
310 while (m_pCurrentLevel->m_pGraph->numberOfNodes() > m_multiLevelNumNodesBound)
311 {
312 GalaxyMultilevel* newLevel = builder.build(m_pCurrentLevel);
313 m_pCurrentLevel = newLevel;
314 m_iNumLevels++;
315 m_iCurrentLevelNr++;
316 }
317 m_pCoarsestLevel = m_pCurrentLevel;
318 m_pCurrentGraph = m_pCurrentLevel->m_pGraph;
319 }
320
321
writeCurrentToGraphAttributes(GraphAttributes & GA)322 void FastMultipoleMultilevelEmbedder::writeCurrentToGraphAttributes(GraphAttributes& GA)
323 {
324 for(node v : m_pCurrentGraph->nodes)
325 {
326 GA.x(v) = (*m_pCurrentNodeXPos)[v];
327 GA.y(v) = (*m_pCurrentNodeYPos)[v];
328 }
329 }
330
nextLevel()331 void FastMultipoleMultilevelEmbedder::nextLevel()
332 {
333 m_pCurrentLevel = m_pCurrentLevel->m_pFinerMultiLevel;
334 std::swap(m_pLastNodeXPos, m_pCurrentNodeXPos);
335 std::swap(m_pLastNodeYPos, m_pCurrentNodeYPos);
336 m_iCurrentLevelNr--;
337 }
338
initFinestLevel(GraphAttributes & GA,const EdgeArray<float> & edgeLength)339 void FastMultipoleMultilevelEmbedder::initFinestLevel(GraphAttributes &GA, const EdgeArray<float>& edgeLength)
340 {
341 #if 0
342 NodeArray<float> perimeter(GA.constGraph(), 0.0);
343 #endif
344 for(node v : GA.constGraph().nodes)
345 {
346 GalaxyMultilevel::LevelNodeInfo& nodeInfo = (*(m_pFinestLevel->m_pNodeInfo))[v];
347 nodeInfo.mass = 1.0;
348 float r = (float)sqrt(GA.width(v)*GA.width(v) + GA.height(v)*GA.height(v)) * 0.5f;
349 nodeInfo.radius = r;
350 }
351
352 for(edge e : GA.constGraph().edges)
353 {
354 GalaxyMultilevel::LevelEdgeInfo& edgeInfo = (*(m_pFinestLevel->m_pEdgeInfo))[e];
355 node v = e->source();
356 node w = e->target();
357 GalaxyMultilevel::LevelNodeInfo& vNodeInfo = (*(m_pFinestLevel->m_pNodeInfo))[v];
358 GalaxyMultilevel::LevelNodeInfo& wNodeInfo = (*(m_pFinestLevel->m_pNodeInfo))[w];
359 edgeInfo.length = (vNodeInfo.radius + wNodeInfo.radius) + edgeLength[e];
360 }
361 }
362
initCurrentLevel()363 void FastMultipoleMultilevelEmbedder::initCurrentLevel()
364 {
365 m_pCurrentGraph = m_pCurrentLevel->m_pGraph;
366 m_pCurrentNodeXPos->init(*m_pCurrentGraph, 0.0f);
367 m_pCurrentNodeYPos->init(*m_pCurrentGraph, 0.0f);
368 m_pCurrentEdgeLength->init(*m_pCurrentGraph, 1.0f);
369 m_pCurrentNodeSize->init(*m_pCurrentGraph, 1.0f);
370 const Graph& G = *(m_pCurrentLevel->m_pGraph);
371
372 for(node v : G.nodes)
373 {
374 GalaxyMultilevel::LevelNodeInfo& nodeInfo = (*(m_pCurrentLevel->m_pNodeInfo))[v];
375 (*m_pCurrentNodeSize)[v] = ((float)nodeInfo.radius);//(((float)nodeInfo.radius));
376 }
377
378 for(edge e : G.edges)
379 {
380 GalaxyMultilevel::LevelEdgeInfo& edgeInfo = (*(m_pCurrentLevel->m_pEdgeInfo))[e];
381 (*m_pCurrentEdgeLength)[e] = edgeInfo.length*0.25f;
382 }
383 }
384
assignPositionsFromPrevLevel()385 void FastMultipoleMultilevelEmbedder::assignPositionsFromPrevLevel()
386 {
387 float scaleFactor = 1.4f;// 1.4f;//1.4f; //1.4f
388 // init m_pCurrent Pos from m_pLast Pos
389 const Graph& G = *(m_pCurrentLevel->m_pGraph);
390
391 for(node v : G.nodes)
392 {
393 GalaxyMultilevel::LevelNodeInfo& nodeInfo = (*(m_pCurrentLevel->m_pNodeInfo))[v];
394 float x = (float)((*m_pLastNodeXPos)[nodeInfo.parent] + (float)randomDouble(-1.0, 1.0));
395 float y = (float)((*m_pLastNodeYPos)[nodeInfo.parent] + (float)randomDouble(-1.0, 1.0));
396 (*m_pCurrentNodeXPos)[v] = x*scaleFactor;
397 (*m_pCurrentNodeYPos)[v] = y*scaleFactor;
398 }
399 }
400
layoutCurrentLevel()401 void FastMultipoleMultilevelEmbedder::layoutCurrentLevel()
402 {
403 FastMultipoleEmbedder fme;
404 fme.setNumberOfThreads(this->m_iMaxNumThreads);
405 fme.setRandomize(m_iCurrentLevelNr == (m_iNumLevels-1));
406 fme.setNumIterations(numberOfIterationsByLevelNr(m_iCurrentLevelNr));
407 fme.call((*m_pCurrentGraph), (*m_pCurrentNodeXPos), (*m_pCurrentNodeYPos), (*m_pCurrentEdgeLength), (*m_pCurrentNodeSize));
408 }
409
deleteMultiLevelGraphs()410 void FastMultipoleMultilevelEmbedder::deleteMultiLevelGraphs()
411 {
412 GalaxyMultilevel* level = m_pCoarsestLevel;
413 GalaxyMultilevel* toDelete;
414 while (level)
415 {
416 toDelete = level;
417 level = level->m_pFinerMultiLevel;
418 delete toDelete->m_pNodeInfo;
419 delete toDelete->m_pEdgeInfo;
420 if (toDelete != m_pFinestLevel)
421 delete toDelete->m_pGraph;
422 delete toDelete;
423 }
424 }
425
numberOfIterationsByLevelNr(uint32_t levelNr)426 uint32_t FastMultipoleMultilevelEmbedder::numberOfIterationsByLevelNr(uint32_t levelNr)
427 {
428 return 200*(levelNr+1)*(levelNr+1);
429 }
430
431 }
432