6 * $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of Fast-Multipole-Embedder layout algorithm.
12 * \author Martin Gronemann
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
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
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.
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.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
47 #ifndef OGDF_FAST_MULTIPOLE_EMBEDDER_H
48 #define OGDF_FAST_MULTIPOLE_EMBEDDER_H
50 #include <ogdf/basic/Graph.h>
51 #include <ogdf/module/LayoutModule.h>
52 #include <ogdf/internal/energybased/MultilevelGraph.h>
58 class LinearQuadtreeExpansion
;
61 struct FMEGlobalOptions
;
62 class GalaxyMultilevel
;
64 class OGDF_EXPORT FastMultipoleEmbedder
: public LayoutModule
68 FastMultipoleEmbedder();
71 ~FastMultipoleEmbedder();
73 //! Calls the algorithm for graph \a MLG.
74 //Does not do anything smart, can be safely removed
75 //void call(MultilevelGraph &MLG);
77 //! Calls the algorithm for graph \a G with the given edgelength and returns the layout information in \a nodeXPosition, nodeYPosition.
80 NodeArray
<float>& nodeXPosition
,
81 NodeArray
<float>& nodeYPosition
,
82 const EdgeArray
<float>& edgeLength
,
83 const NodeArray
<float>& nodeSize
);
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
);
88 //! Calls the algorithm for graph \a GA and returns the layout information in \a GA.
89 void call(GraphAttributes
&GA
);
91 //! sets the maximum number of iterations
92 void setNumIterations(__uint32 numIterations
) { m_numIterations
= numIterations
; }
94 //! sets the number of coefficients for the expansions. default = 4
95 void setMultipolePrec(__uint32 precision
) { m_precisionParameter
= precision
; }
97 //! if true, layout algorithm will randomize the layout in the beginning
98 void setRandomize(bool b
) { m_randomize
= b
; }
101 void setDefaultEdgeLength(float edgeLength
) { m_defaultEdgeLength
= edgeLength
; }
104 void setDefaultNodeSize(float nodeSize
) { m_defaultNodeSize
= nodeSize
; }
107 void setNumberOfThreads(__uint32 numThreads
) { m_maxNumberOfThreads
= numThreads
; }
109 //void setEnablePostProcessing(bool b) { m_doPostProcessing = b; }
117 //! runs the simulation with the given number of iterations
118 void run(__uint32 numIterations
);
120 //! allocates the memory
121 void allocate(__uint32 numNodes
, __uint32 numEdges
);
126 __uint32 m_numIterations
;
128 ArrayGraph
* m_pGraph
;
130 FMEThreadPool
* m_threadPool
;
132 FMEGlobalOptions
* m_pOptions
;
134 __uint32 m_precisionParameter
;
138 float m_defaultEdgeLength
;
140 float m_defaultNodeSize
;
142 __uint32 m_numberOfThreads
;
144 __uint32 m_maxNumberOfThreads
;
148 class OGDF_EXPORT FastMultipoleMultilevelEmbedder
: public LayoutModule
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
);
156 //! sets the bound for the number of nodes for multilevel step
157 void multilevelUntilNumNodesAreLess(int nodesBound
) { m_multiLevelNumNodesBound
= nodesBound
; }
159 void maxNumThreads(int numThreads
) { m_iMaxNumThreads
= numThreads
; }
161 //! internal function to compute a good edgelength
162 void computeAutoEdgeLength(const GraphAttributes
& GA
, EdgeArray
<float>& edgeLength
, float factor
= 1.0f
);
164 //! internal main function for the multilevel layout
165 void run(GraphAttributes
& GA
, const EdgeArray
<float>& edgeLength
);
167 //! creates all multilevels
168 void createMultiLevelGraphs(Graph
* pGraph
, GraphAttributes
& GA
, const EdgeArray
<float>& edgeLength
);
170 //! init the original graphs multilevel
171 void initFinestLevel(GraphAttributes
&GA
, const EdgeArray
<float>& edgeLength
);
173 //! calls the fast multipole embedder on current level
174 void layoutCurrentLevel();
176 //! assigns the nodes in the current level coords by coarser level
177 void assignPositionsFromPrevLevel();
179 //! writes the current level to graph attributes. used for output
180 void writeCurrentToGraphAttributes(GraphAttributes
& GA
);
185 //! initialize datastructure by current level
186 void initCurrentLevel();
188 //! clean up the multilevel graphs
189 void deleteMultiLevelGraphs();
191 //! for debugging only
192 void dumpCurrentLevel(const String
& filename
);
194 //! computes the maximum number of iterations by level nr
195 __uint32
numberOfIterationsByLevelNr(__uint32 levelNr
);
197 int m_iMaxNumThreads
;
199 int m_multiLevelNumNodesBound
;
201 GalaxyMultilevel
* m_pCurrentLevel
;
202 GalaxyMultilevel
* m_pFinestLevel
;
203 GalaxyMultilevel
* m_pCoarsestLevel
;
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
;
214 NodeArray
<float>* m_pLastNodeXPos
;
215 NodeArray
<float>* m_pLastNodeYPos
;
218 } // end of namespace ogdf