ext/OGDF/ogdf/energybased/FastMultipoleEmbedder.h

   1 /*
   2  * $Revision: 2564 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of Fast-Multipole-Embedder layout algorithm.
  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 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47 #ifndef OGDF_FAST_MULTIPOLE_EMBEDDER_H
  48 #define OGDF_FAST_MULTIPOLE_EMBEDDER_H
  49
  50 #include <ogdf/basic/Graph.h>
  51 #include <ogdf/module/LayoutModule.h>
  52 #include <ogdf/internal/energybased/MultilevelGraph.h>
  53
  54 namespace ogdf {
  55
  56 class ArrayGraph;
  57 class LinearQuadtree;
  58 class LinearQuadtreeExpansion;
  59 class FMEThreadPool;
  60 class FMEThread;
  61 struct FMEGlobalOptions;
  62 class GalaxyMultilevel;
  63
  64 class OGDF_EXPORT FastMultipoleEmbedder : public LayoutModule
  65 {
  66 public:
  67         //! constructor
  68         FastMultipoleEmbedder();
  69
  70         //! destructor
  71         ~FastMultipoleEmbedder();
  72
  73         //! Calls the algorithm for graph \a MLG.
  74         //Does not do anything smart, can be safely removed
  75         //void call(MultilevelGraph &MLG);
  76
  77         //! Calls the algorithm for graph \a G with the given edgelength and returns the layout information in \a nodeXPosition, nodeYPosition.
  78         void call(
  79                 const Graph& G,
  80                 NodeArray<float>& nodeXPosition,
  81                 NodeArray<float>& nodeYPosition,
  82                 const EdgeArray<float>& edgeLength,
  83                 const NodeArray<float>& nodeSize);
  84
  85         //! Calls the algorithm for graph \a GA with the given edgelength and returns the layout information in \a GA.
  86         void call(GraphAttributes &GA, const EdgeArray<float>& edgeLength, const NodeArray<float>& nodeSize);
  87
  88         //! Calls the algorithm for graph \a GA and returns the layout information in \a GA.
  89         void call(GraphAttributes &GA);
  90
  91         //! sets the maximum number of iterations
  92         void setNumIterations(__uint32 numIterations) { m_numIterations = numIterations; }
  93
  94         //! sets the number of coefficients for the expansions. default = 4
  95         void setMultipolePrec(__uint32 precision) { m_precisionParameter = precision; }
  96
  97         //! if true, layout algorithm will randomize the layout in the beginning
  98         void setRandomize(bool b) { m_randomize = b; }
  99
 100         //!
 101         void setDefaultEdgeLength(float edgeLength) { m_defaultEdgeLength = edgeLength; }
 102
 103         //!
 104         void setDefaultNodeSize(float nodeSize) { m_defaultNodeSize = nodeSize; }
 105
 106         //!
 107         void setNumberOfThreads(__uint32 numThreads) { m_maxNumberOfThreads = numThreads; }
 108
 109         //void setEnablePostProcessing(bool b) { m_doPostProcessing = b; }
 110 private:
 111         void initOptions();
 112
 113         void runMultipole();
 114
 115         void runSingle();
 116
 117         //! runs the simulation with the given number of iterations
 118         void run(__uint32 numIterations);
 119
 120         //! allocates the memory
 121         void allocate(__uint32 numNodes, __uint32 numEdges);
 122
 123         //! frees the memory
 124         void deallocate();
 125
 126         __uint32 m_numIterations;
 127
 128         ArrayGraph* m_pGraph;
 129
 130         FMEThreadPool* m_threadPool;
 131
 132         FMEGlobalOptions* m_pOptions;
 133
 134         __uint32 m_precisionParameter;
 135
 136         bool m_randomize;
 137
 138         float m_defaultEdgeLength;
 139
 140         float m_defaultNodeSize;
 141
 142         __uint32 m_numberOfThreads;
 143
 144         __uint32 m_maxNumberOfThreads;
 145 };
 146
 147
 148 class OGDF_EXPORT FastMultipoleMultilevelEmbedder : public LayoutModule
 149 {
 150 public:
 151         //! Constructor, just sets number of maximum threads
 152         FastMultipoleMultilevelEmbedder() : m_iMaxNumThreads(1) {}
 153         //! Calls the algorithm for graph \a GA and returns the layout information in \a GA.
 154         void call(GraphAttributes &GA);
 155
 156         //! sets the bound for the number of nodes for multilevel step
 157         void multilevelUntilNumNodesAreLess(int nodesBound) { m_multiLevelNumNodesBound = nodesBound; }
 158
 159         void maxNumThreads(int numThreads) { m_iMaxNumThreads = numThreads; }
 160 private:
 161         //! internal function to compute a good edgelength
 162         void computeAutoEdgeLength(const GraphAttributes& GA, EdgeArray<float>& edgeLength, float factor = 1.0f);
 163
 164         //! internal main function for the multilevel layout
 165         void run(GraphAttributes& GA, const EdgeArray<float>& edgeLength);
 166
 167         //! creates all multilevels
 168         void createMultiLevelGraphs(Graph* pGraph, GraphAttributes& GA, const EdgeArray<float>& edgeLength);
 169
 170         //! init the original graphs multilevel
 171         void initFinestLevel(GraphAttributes &GA, const EdgeArray<float>& edgeLength);
 172
 173         //! calls the fast multipole embedder on current level
 174         void layoutCurrentLevel();
 175
 176         //! assigns the nodes in the current level coords by coarser level
 177         void assignPositionsFromPrevLevel();
 178
 179         //! writes the current level to graph attributes. used for output
 180         void writeCurrentToGraphAttributes(GraphAttributes& GA);
 181
 182         //! refine
 183         void nextLevel();
 184
 185         //! initialize datastructure by current level
 186         void initCurrentLevel();
 187
 188         //! clean up the multilevel graphs
 189         void deleteMultiLevelGraphs();
 190
 191         //! for debugging only
 192         void dumpCurrentLevel(const String& filename);
 193
 194         //! computes the maximum number of iterations by level nr
 195         __uint32 numberOfIterationsByLevelNr(__uint32 levelNr);
 196
 197         int                               m_iMaxNumThreads;
 198         int                               m_iNumLevels;
 199         int                               m_multiLevelNumNodesBound;
 200
 201         GalaxyMultilevel* m_pCurrentLevel;
 202         GalaxyMultilevel* m_pFinestLevel;
 203         GalaxyMultilevel* m_pCoarsestLevel;
 204
 205         Graph*                    m_pCurrentGraph;
 206         NodeArray<float>* m_pCurrentNodeXPos;
 207         NodeArray<float>* m_pCurrentNodeYPos;
 208         EdgeArray<float>* m_pCurrentEdgeLength;
 209         NodeArray<float>* m_pCurrentNodeSize;
 210         NodeArray<float>  m_adjustedNodeSize;
 211         int                               m_iCurrentLevelNr;
 212
 213         Graph*                    m_pLastGraph;
 214         NodeArray<float>* m_pLastNodeXPos;
 215         NodeArray<float>* m_pLastNodeYPos;
 216 };
 217
 218 } // end of namespace ogdf
 219
 220 #endif
 221