ext/OGDF/ogdf/energybased/SpringEmbedderKK.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 algorithm (Kamada,Kawai).
  11  *
  12  *
  13  * \author Karsten Klein
  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_KK_H
  49 #define OGDF_SPRING_EMBEDDER_KK_H
  50
  51
  52 #include <ogdf/module/LayoutModule.h>
  53 #include <ogdf/basic/Array2D.h>
  54 #include <ogdf/basic/tuples.h>
  55
  56
  57 namespace ogdf {
  58
  59
  60         class OGDF_EXPORT GraphCopyAttributes;
  61         class OGDF_EXPORT GraphCopy;
  62
  63
  64 //! The spring-embedder layout algorithm by Kamada and Kawai.
  65 /**
  66  * The implementation used in SpringEmbedderKK is based on
  67  * the following publication:
  68  *
  69  * Tomihisa Kamada, Satoru Kawai: <i>%An Algorithm for Drawing
  70  * General Undirected Graphs</i>. Information Processing Letters 31, pp. 7-15, 1989.
  71  *
  72  * Precondition: The input graph has to be connected.
  73  * <H3>Optional parameters</H3>
  74  * There are some parameters that can be tuned to optimize the
  75  * algorithm's behavior regarding runtime and layout quality.
  76  * First of all note that the algorithm uses all pairs shortest path
  77  * to compute the graph theoretic distance. This can be done either
  78  * with BFS (ignoring node sizes) in quadratic time or by using
  79  * e.g. Floyd's algorithm in cubic time with given edge lengths
  80  * that may reflect the node sizes.  Also m_computeMaxIt decides
  81  * if the computation is stopped after a fixed maximum number of
  82  * iterations. The desirable edge length can either be set or computed
  83  * from the graph and the given layout.
  84  * Kamada-Kawai layout provides the following optional parameters.
  85  *
  86  * <table>
  87  *   <tr>
  88  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  89  *   </tr><tr>
  90  *     <td><i>tolerance</i><td>int<td>0.0001
  91  *     <td>Tolerance for the energy level (below which the main loop stops).
  92  *   </tr>
  93  * </table>
  94  */
  95 class OGDF_EXPORT SpringEmbedderKK : public LayoutModule
  96 {
  97 public:
  98         typedef Tuple2<double, double> dpair;
  99
 100         //! The scaling method used for the desirable length.
 101         //! TODO: Non-functional so far, scScaleFunction is used
 102         enum Scaling {
 103                 scInput,           //!< bounding box of input is used.
 104                 scUserBoundingBox, //!< bounding box set by userBoundingBox() is used.
 105                 scScaleFunction,    //!< automatic scaling is used, computed using only the node sizes.
 106                 scScaleAdaptive    //!< automatic scaling is used, adapting the value per iteration.
 107         };
 108
 109         //! Constructor: Constructs instance of Kamada Kawai Layout
 110         SpringEmbedderKK() : m_tolerance(0.001), m_ltolerance(0.0001), m_computeMaxIt(true),
 111                 m_K(5.0), m_desLength(0.0), m_distFactor(2.0), m_useLayout(true),
 112                 m_gItBaseVal(50), m_gItFactor(16)
 113         {
 114                 m_maxLocalIt = m_maxGlobalIt = maxVal;
 115         }
 116
 117         //! Destructor
 118         ~SpringEmbedderKK() {}
 119
 120         //! Calls the layout algorithm for graph attributes \a GA.
 121         //! Currently, GA.doubleWeight is NOT used to allow simple
 122         //! distinction of BFS/APSS. Precondition: Graph is connected.
 123         void call(GraphAttributes& GA);
 124         //! Calls the layout algorithm for graph attributes \a GA
 125         //! using values in eLength for distance computation.
 126         //! Precondition: Graph is connected.
 127         void call(GraphAttributes& GA, const EdgeArray<double>& eLength);
 128
 129         //! Sets the value for the stop tolerance, below which the
 130         //! system is regarded stable (balanced) and the optimization stopped
 131         void setStopTolerance(double s) {m_tolerance = s;}
 132
 133         //! If set to true, the given layout is used for the initial positions
 134         void setUseLayout(bool b) {m_useLayout = b;}
 135         bool useLayout() {return m_useLayout;}
 136
 137         //! If set != 0, value zerolength is used to determine the
 138         //! desirable edge length by L = zerolength / max distance_ij.
 139         //! Otherwise, zerolength is determined using the node number and sizes.
 140         void setZeroLength(double d) {m_zeroLength = d;}
 141         double zeroLength() {return m_zeroLength;}
 142
 143         //! Sets desirable edge length directly
 144         void setDesLength(double d) {m_desLength = d;}
 145
 146
 147         //! It is possible to limit the number of iterations to a fixed value
 148         //! Returns the current setting of iterations.
 149         //! These values are only used if m_computeMaxIt is set to true.
 150         int maxLocalIterations() const {
 151                 return m_maxLocalIt;
 152         }
 153         void setGlobalIterationFactor(int i) {if (i>0) m_gItFactor = i;}
 154         int maxGlobalIterations() const {
 155                 return m_maxGlobalIt;
 156         }
 157         //! Sets the number of global iterations to \a i.
 158         void setMaxGlobalIterations(int i) {
 159                 if (i>0)
 160                         m_maxGlobalIt = i;
 161         }
 162         //! Sets the number of local iterations to \a i.
 163         void setMaxLocalIterations(int i) {
 164                 if (i>0)
 165                         m_maxLocalIt = i;
 166         }
 167         //! If set to true, number of iterations is computed depending on G
 168         void computeMaxIterations(bool b)
 169         {
 170                 m_computeMaxIt = b;
 171         }
 172         //We could add some noise to the computation
 173         // Returns the current setting of nodes.
 174         //bool noise() const {
 175         //      return m_noise;
 176         //}
 177         // Sets the parameter noise to \a on.
 178         //void noise(bool on) {
 179         //      m_noise = on;
 180         //}
 181
 182
 183 protected:
 184         //! Does the actual call
 185         void doCall(GraphAttributes& GA, const EdgeArray<double>& eLength, bool simpleBFS);
 186         //! Checks if main loop is finished because local optimum reached
 187         bool finished(double maxdelta)
 188         {
 189                 if (m_prevEnergy == startVal) //first step
 190                 {
 191                         m_prevEnergy = maxdelta;
 192                         return false;
 193                 }
 194
 195                 double diff = m_prevEnergy - maxdelta; //energy difference
 196                 if (diff < 0.0) diff = -diff;
 197                 //#ifdef OGDF_DEBUG
 198                 //        cout << "Finished(): maxdelta: "<< maxdelta<<" diff/prev: "<<diff / m_prevEnergy<<"\n";
 199                 //#endif
 200                 //check if we want to stop
 201                 bool done = (maxdelta < m_tolerance);// || (diff / m_prevEnergy) < m_tolerance);
 202
 203                 m_prevEnergy = maxdelta;   //save previous energy level
 204                 m_prevLEnergy =  startVal; //reset energy level for local node decision
 205
 206                 return done;
 207         }//finished
 208         //! Checks if inner loop (current node) is finished
 209         bool finishedNode(double deltav)
 210         {
 211                 if (m_prevLEnergy == startVal)
 212                 {
 213                         m_prevLEnergy = deltav;
 214                         return deltav == 0.0;//<m_ltolerance; //locally stable
 215                 }
 216                 //#ifdef OGDF_DEBUG
 217                 //        cout << "Local delta: "<<deltav<<"\n";
 218                 //#endif
 219                 double diff = m_prevLEnergy - deltav;
 220                 //check if we want to stop
 221                 bool done = (deltav == 0.0 || (diff / m_prevLEnergy) < m_ltolerance);
 222
 223                 m_prevLEnergy = deltav; //save previous energy level
 224
 225                 return done;
 226         }//finishedNode
 227         //! Changes given edge lengths (interpreted as weight factors)
 228         //! according to additional parameters like node size etc.
 229         void adaptLengths(const Graph& G,
 230                 const GraphAttributes& GA,
 231                 const EdgeArray<double>& eLengths,
 232                 EdgeArray<double>& adaptedLengths);
 233         //! Adapts positions to avoid degeneracy (all nodes on a single point)
 234         void shufflePositions(GraphAttributes& GA);
 235         //! Computes contribution of node u to the first partial
 236         //! derivatives (dE/dx_m, dE/dy_m) (for node m) (eq. 7 and 8 in paper)
 237         dpair computeParDer(node m,
 238                 node u,
 239                 GraphAttributes& GA,
 240                 NodeArray< NodeArray<double> >& ss,
 241                 NodeArray< NodeArray<double> >& dist);
 242         //! Compute partial derivative for v
 243         dpair computeParDers(node v,
 244                 GraphAttributes& GA,
 245                 NodeArray< NodeArray<double> >& ss,
 246                 NodeArray< NodeArray<double> >& dist);
 247         //! Does the necessary initialization work for the call functions
 248         void initialize(GraphAttributes& GA,
 249                 NodeArray<dpair>& partialDer,
 250                 const EdgeArray<double>& eLength,
 251                 NodeArray< NodeArray<double> >& oLength,
 252                 NodeArray< NodeArray<double> >& sstrength,
 253                 double & maxDist,
 254                 bool simpleBFS);
 255         //! Main computation loop, nodes are moved here
 256         void mainStep(GraphAttributes& GA,
 257                 NodeArray<dpair>& partialDer,
 258                 NodeArray< NodeArray<double> >& oLength,
 259                 NodeArray< NodeArray<double> >& sstrength,
 260                 const double maxDist);
 261         //! Does the scaling if no edge lengths are given but node sizes
 262         //! are respected
 263         void scale(GraphAttributes& GA);
 264
 265 private:
 266         //! The stop criterion when the forces of all strings are
 267         //! considered to be balanced
 268         double m_tolerance;  //!<value for stop criterion
 269         double m_ltolerance;  //!<value for local stop criterion
 270         int m_maxGlobalIt;   //!< Maximum number of global iterations
 271         int m_maxLocalIt;   //!< Maximum number of local iterations
 272         bool m_computeMaxIt; //!< If true, number of iterations is computed
 273         //! depending on number of nodes
 274         double m_K; //! Big K constant for strength computation
 275         double m_prevEnergy; //!<max energy value
 276         double m_prevLEnergy;//!<local energy
 277         double m_zeroLength; //!< Length of a side of the display area, used for
 278         //! edge length computation if > 0
 279         double m_desLength; //!< Desirable edge length, used instead if > 0
 280         double m_distFactor; //introduces some distance for scaling in case BFS is used
 281
 282         bool m_useLayout; //!< use positions or allow to shuffle nodes to
 283         //!< avoid degeneration
 284         int m_gItBaseVal; //!< minimum number of global iterations
 285         int m_gItFactor;  //!< factor for global iterations: m_gItBaseVal+m_gItFactor*|V|
 286
 287         static const double startVal;
 288         static const double minVal;
 289         static const double desMinLength; //!< Defines minimum desired edge length.
 290         //! Smaller values are treated as zero
 291         static const int maxVal = INT_MAX; //! defines infinite upper bound for iteration number
 292
 293         double allpairsspBFS(const Graph& G, NodeArray< NodeArray<double> >& distance);
 294         double allpairssp(const Graph& G, const EdgeArray<double>& eLengths,
 295                 NodeArray< NodeArray<double> >& distance,       const double threshold = DBL_MAX);
 296 };//SpringEmbedderKK
 297
 298 //Things that potentially could be added
 299 //      //! Returns the page ratio.
 300 //    double pageRatio() { return m_pageRatio; }
 301 //
 302 //      //! Sets the page ration to \a x.
 303 //    void pageRatio(double x) { m_pageRatio = x; }
 304 //
 305 //      //! Returns the current scaling method.
 306 //      Scaling scaling() const {
 307 //              return m_scaling;
 308 //      }
 309 //
 310 //      //! Sets the method for scaling the inital layout to \a sc.
 311 //      void scaling(Scaling sc) {
 312 //              m_scaling = sc;
 313 //      }
 314 //
 315 //      //! Returns the current scale function factor.
 316 //      double scaleFunctionFactor() const {
 317 //              return m_scaleFactor;
 318 //      }
 319 //
 320 //      //! Sets the scale function factor to \a f.
 321 //      void scaleFunctionFactor(double f) {
 322 //              m_scaleFactor = f;
 323 //      }
 324 //
 325 //      //! Sets the user bounding box (used if scaling method is scUserBoundingBox).
 326 //      void userBoundingBox(double xmin, double ymin, double xmax, double ymax) {
 327 //              m_bbXmin = xmin;
 328 //              m_bbYmin = ymin;
 329 //              m_bbXmax = xmax;
 330 //              m_bbYmax = ymax;
 331 //      }
 332
 333
 334 } // end namespace ogdf
 335
 336
 337 #endif