ext/OGDF/ogdf/energybased/SpringEmbedderFRExact.h

   1 /*
   2  * $Revision: 2524 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of Spring-Embedder (Fruchterman,Reingold)
  11  *        algorithm with exact force computations.
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_SPRING_EMBEDDER_FR_EXACT_H
  49 #define OGDF_SPRING_EMBEDDER_FR_EXACT_H
  50
  51
  52 #include <ogdf/module/ForceLayoutModule.h>
  53 #include <ogdf/basic/SList.h>
  54
  55
  56 namespace ogdf {
  57
  58
  59 class OGDF_EXPORT GraphCopyAttributes;
  60 class OGDF_EXPORT GraphCopy;
  61
  62
  63 class OGDF_EXPORT SpringEmbedderFRExact : public ForceLayoutModule
  64 {
  65 public:
  66         enum CoolingFunction { cfFactor, cfLogarithmic };
  67
  68         //! Creates an instance of Fruchterman/Reingold (exact) layout.
  69         SpringEmbedderFRExact();
  70
  71         // destructor
  72         ~SpringEmbedderFRExact() { }
  73
  74
  75         //! Calls the layout algorithm for graph attributes \a GA.
  76         void call(GraphAttributes &GA);
  77
  78
  79         //! Returns the current setting of iterations.
  80         int iterations() const {
  81                 return m_iterations;
  82         }
  83
  84         //! Sets the number of iterations to \a i.
  85         void iterations(int i) {
  86                 OGDF_ASSERT(i > 0)
  87                         m_iterations = i;
  88         }
  89
  90         //! Returns the current setting of nodes.
  91         bool noise() const {
  92                 return m_noise;
  93         }
  94
  95         //! Sets the parameter noise to \a on.
  96         void noise(bool on) {
  97                 m_noise = on;
  98         }
  99
 100         //! Switches use of node weights given in GraphAttributtes
 101         void nodeWeights(bool on) {
 102                 m_useNodeWeight = on;
 103         }
 104         //! Returns the current setting for the cooling function.
 105         CoolingFunction coolingFunction() const {
 106                 return m_coolingFunction;
 107         }
 108
 109         //! Sets the parameter coolingFunction to \a f.
 110         void coolingFunction(CoolingFunction f) {
 111                 m_coolingFunction = f;
 112         }
 113
 114         //! Returns the ideal edge length.
 115         double idealEdgeLength() const { return m_idealEdgeLength; }
 116
 117         //! Sets the ideal edge length to \a len.
 118         void idealEdgeLength(double len) { m_idealEdgeLength = len; }
 119
 120         //! Returns the minimum distance between connected components.
 121         double minDistCC() const { return m_minDistCC; }
 122
 123         //! Sets the minimum distance between connected components to \a x.
 124         void minDistCC(double x) { m_minDistCC = x; }
 125
 126         //! Returns the page ratio.
 127         double pageRatio() { return m_pageRatio; }
 128
 129         //! Sets the page ration to \a x.
 130         void pageRatio(double x) { m_pageRatio = x; }
 131
 132         void checkConvergence(bool b) {m_checkConvergence = b;}
 133         bool checkConvergence() {return m_checkConvergence;}
 134         void convTolerance(double tol) {m_convTolerance = tol;}
 135
 136 private:
 137         class ArrayGraph
 138         {
 139                 int m_numNodes;
 140                 int m_numEdges;
 141                 int m_numCC;
 142
 143                 GraphAttributes *m_ga;
 144                 node *m_orig;
 145                 Array<SList<node> > m_nodesInCC;
 146                 NodeArray<int>      m_mapNode;
 147
 148         public:
 149                 ArrayGraph(GraphAttributes &ga);
 150                 ~ArrayGraph();
 151
 152                 void initCC(int i);
 153
 154                 int numberOfCCs() const { return m_numCC; }
 155                 int numberOfNodes() const { return m_numNodes; }
 156                 int numberOfEdges() const { return m_numEdges; }
 157
 158                 node original(int v) const { return m_orig[v]; }
 159                 const SList<node> &nodesInCC(int i) const { return m_nodesInCC[i]; }
 160
 161                 int *m_src;
 162                 int *m_tgt;
 163                 double *m_x;
 164                 double *m_y;
 165                 double *m_nodeWeight;
 166                 //this should be part of a multilevel layout interface class later on
 167                 bool m_useNodeWeight; //should given nodeweights be used or all set to 1.0?
 168         };
 169
 170         double log2(double x) { return log(x) / log(2.0); }
 171         double mylog2(int x) {
 172                 double l = 0.0;
 173                 while(x > 0) {
 174                         l++;
 175                         x >>= 1;
 176                 }
 177                 return l/2;
 178         }
 179
 180         void initialize(ArrayGraph &component);
 181         void mainStep(ArrayGraph &component);
 182         void mainStep_sse3(ArrayGraph &component);
 183
 184         // Fruchterman, Reingold
 185         //double f_att(double d) { return d*d / m_idealEdgeLength; }
 186         //double f_rep(double d) { return m_idealEdgeLength*m_idealEdgeLength / d; }
 187
 188         // eades
 189         //double f_att(double d) { return 5.0 * d * log2(d/m_idealEdgeLength); }
 190         //double f_rep(double d) { return 20.0 / d; }
 191
 192         // cooling function
 193         void cool(double &tx, double &ty, int &cF);
 194
 195         int    m_iterations; //!< The number of iterations.
 196         bool   m_noise;      //!< Perform random perturbations?
 197         CoolingFunction m_coolingFunction; //!< The selected cooling function
 198
 199
 200         //double m_tx;
 201         //double m_ty;
 202
 203         double m_coolFactor_x;
 204         double m_coolFactor_y;
 205
 206         double m_idealEdgeLength; //!< The ideal edge length.
 207         double m_minDistCC;       //!< The minimal distance between connected components.
 208         double m_pageRatio;       //!< The page ratio.
 209
 210         //int m_cF;
 211         double m_txNull;
 212         double m_tyNull;
 213         //see above at ArrayGraph
 214         bool m_useNodeWeight;
 215         bool m_checkConvergence; //<! If set to true, computation is stopped if movement falls below threshold
 216         double m_convTolerance; //<! Fraction of ideal edge length below which convergence is achieved
 217 };
 218
 219
 220 } // end namespace ogdf
 221
 222
 223 #endif