ext/OGDF/src/energybased/FastMultipoleEmbedder.cpp

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