ext/OGDF/ogdf/energybased/StressMajorizationSimple.h

   1 /*
   2  * $Revision: 2583 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of simple distance-based layout. Non-final Code (Status: purely experimental).
  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_STRESS_MAJORIZATION_H
  49 #define OGDF_STRESS_MAJORIZATION_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 //! Simple stress majorization version that allows radial constraints
  65 //! based on shortest path distances
  66 /**
  67 * The implementation used in  StressMajorization is based on
  68 * the following publication:
  69 *
  70 * Brandes, Pich: <i>%More flexible radial layout</i>. Graph Drawing 2009.
  71 *
  72 * Precondition: The input graph has to be connected.
  73 * In order to obtain a radial style layout, the stress majorization
  74 * is applied to the graph plus an additional virtual node at the center.
  75 * <H3>Optional parameters</H3>
  76 * There are some parameters that can be tuned to optimize the
  77 * algorithm's behavior regarding runtime and layout quality.
  78 * First of all note that the algorithm uses all pairs shortest path
  79 * to compute the graph theoretic distance. This can be done either
  80 * with BFS (ignoring node sizes) in quadratic time or by using
  81 * e.g. Floyd's algorithm in cubic time with given edge lengths
  82 * that may reflect the node sizes.
  83 * TODO: Fixed number of iterations vs stop criterion
  84 *       Radii computation
  85 * The layout provides the following optional parameters.
  86 *
  87 * <table>
  88 *   <tr>
  89 *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  90 *   </tr><tr>
  91 *     <td><i>iterations</i><td>int<td>50
  92 *     <td>Number of iterations (determines how often the main loop is executed ).
  93 *   </tr>
  94 * </table>
  95 */
  96 class OGDF_EXPORT  StressMajorization : public LayoutModule
  97 {
  98 public:
  99         typedef Tuple2<double, double> dpair;
 100
 101         //! The scaling method used for the desirable length.
 102         //! TODO: Non-functional so far, scScaleFunction is used
 103         enum Scaling {
 104                 scInput,           //!< bounding box of input is used.
 105                 scUserBoundingBox, //!< bounding box set by userBoundingBox() is used.
 106                 scScaleFunction,    //!< automatic scaling is used, computed using only the node sizes.
 107                 scScaleAdaptive    //!< automatic scaling is used, adapting the value per iteration.
 108         };
 109
 110         enum Constraints {
 111                 cRadial = 0x0001,       //radial level depending on some centrality measure
 112                 cUpward = 0x0002  //level depending on edge direction
 113         };
 114
 115         //! Constructor: Constructs instance of Kamada Kawai Layout
 116         StressMajorization()
 117                 : m_tolerance(0.001),
 118                 m_ltolerance(0.0001),
 119                 m_computeMaxIt(true),
 120                 m_K(5.0),
 121                 m_desLength(0.0),
 122                 m_distFactor(2.0),
 123                 m_useLayout(false),
 124                 m_constraints(cUpward),
 125                 m_radial(false),
 126                 m_upward(false),
 127                 m_radiiStyle(0),
 128                 m_baseRadius(50.0),
 129                 m_numSteps(300),
 130                 m_itFac(0.0),
 131                 m_radiusFactor(1.1),
 132                 m_gItBaseVal(50),
 133                 m_gItFactor(16)
 134         {
 135                 m_maxLocalIt = m_maxGlobalIt = maxVal;
 136         }
 137
 138         //! Destructor
 139         ~ StressMajorization() {}
 140
 141         //! Calls the layout algorithm for graph attributes \a GA.
 142         //! Currently, GA.doubleWeight is NOT used to allow simple
 143         //! distinction of BFS/APSS. Precondition: Graph is connected.
 144         void call(GraphAttributes& GA);
 145
 146         //! Calls the layout algorithm for graph attributes \a GA
 147         //! using values in eLength for distance computation.
 148         //! Precondition: Graph is connected.
 149         void call(GraphAttributes& GA, const EdgeArray<double>& eLength);
 150
 151         //! Sets a fixed number of iterations for stress majorization in main step
 152         void setIterations(int i) { if (i > 0) m_numSteps = i;}
 153
 154         //! Number of total iterations is \a m_numSteps + \a m_itFac * number of nodes.
 155         void setGraphSizeIterationFactor(double d) {if (DIsGreaterEqual(d, 0.0)) m_itFac = d; }
 156
 157         //! Sets the value for the stop tolerance, below which the
 158         //! system is regarded stable (balanced) and the optimization stopped
 159         void setStopTolerance(double s) {m_tolerance = s;}
 160
 161         //! If set to true, the given layout is used for the initial positions
 162         void setUseLayout(bool b) {m_useLayout = b;}
 163         bool useLayout() {return m_useLayout;}
 164
 165         //! It is possible to limit the number of iterations to a fixed value
 166         //! Returns the current setting of iterations.
 167         //! These values are only used if m_computeMaxIt is set to true.
 168         int maxLocalIterations() const {
 169                 return m_maxLocalIt;
 170         }
 171         void setGlobalIterationFactor(int i) {if (i>0) m_gItFactor = i;}
 172         int maxGlobalIterations() const {
 173                 return m_maxGlobalIt;
 174         }
 175         //! Sets the number of global iterations to \a i.
 176         void setMaxGlobalIterations(int i) {
 177                 if (i>0)
 178                         m_maxGlobalIt = i;
 179         }
 180         //! Sets the number of local iterations to \a i.
 181         void setMaxLocalIterations(int i) {
 182                 if (i>0)
 183                         m_maxLocalIt = i;
 184         }
 185         //! If set to true, number of iterations is computed depending on G
 186         void computeMaxIterations(bool b)
 187         {
 188                 m_computeMaxIt = b;
 189         }
 190         //We could add some noise to the computation
 191         // Returns the current setting of nodes.
 192         //bool noise() const {
 193         //      return m_noise;
 194         //}
 195         // Sets the parameter noise to \a on.
 196         //void noise(bool on) {
 197         //      m_noise = on;
 198         //}
 199         //! If set to true, radial constraints are added
 200         void radial(bool b) {m_radial = b;}
 201         //! If set to true, radial constraints are added
 202         void upward(bool b) {m_upward = b;}
 203
 204 protected:
 205         //! Does the actual call
 206         void doCall(GraphAttributes& GA, const EdgeArray<double>& eLength, bool simpleBFS);
 207
 208         //radius on level \a level, (1 denotes first level)
 209         double radius(int level)
 210         {
 211                 if (m_radiiStyle == 0) return m_baseRadius*level;
 212                 else
 213                 {
 214                         double rad = m_baseRadius;
 215                         for (int i = 1; i < level; i++)
 216                         {
 217                                 rad*= m_radiusFactor;
 218                         }
 219                         rad+=m_baseRadius;
 220                         return rad;
 221                 }
 222         }
 223
 224         //radius of a specific node, depending on its level
 225         double radius(node v)
 226         {
 227                 return m_radii[v];
 228         }
 229         //computes radii for all nodes based on closeness and saves them in \a m_radii
 230         void computeRadii(const Graph& G, const NodeArray< NodeArray<double> >& distances, double diameter);
 231
 232         //! Checks if main loop is finished because local optimum reached
 233         bool finished(double maxdelta)
 234         {
 235                 if (m_prevEnergy == startVal) //first step
 236                 {
 237                         m_prevEnergy = maxdelta;
 238                         return false;
 239                 }
 240
 241                 double diff = m_prevEnergy - maxdelta; //energy difference
 242                 if (diff < 0.0) diff = -diff;
 243 #ifdef OGDF_DEBUG
 244                 cout << "Finished(): maxdelta: "<< maxdelta<<" diff/prev: "<<diff / m_prevEnergy<<"\n";
 245 #endif
 246                 //check if we want to stop
 247                 bool done = ((maxdelta < m_tolerance) || (diff / m_prevEnergy) < m_tolerance);
 248
 249                 m_prevEnergy = maxdelta;   //save previous energy level
 250                 m_prevLEnergy =  startVal; //reset energy level for local node decision
 251
 252                 return done;
 253         }//finished
 254         //! Checks if inner loop (current node) is finished
 255         bool finishedNode(double deltav)
 256         {
 257                 if (m_prevLEnergy == startVal)
 258                 {
 259                         m_prevLEnergy = deltav;
 260                         return deltav == 0.0;//<m_ltolerance; //locally stable
 261                 }
 262 #ifdef OGDF_DEBUG
 263                 cout << "Local delta: "<<deltav<<"\n";
 264 #endif
 265                 double diff = m_prevLEnergy - deltav;
 266                 //check if we want to stop
 267                 bool done = (deltav == 0.0 || (diff / m_prevLEnergy) < m_ltolerance);
 268
 269                 m_prevLEnergy = deltav; //save previous energy level
 270
 271                 return done;
 272         }//finishedNode
 273         //! Changes given edge lengths (interpreted as weight factors)
 274         //! according to additional parameters like node size etc.
 275         void adaptLengths(const Graph& G,
 276                 const GraphAttributes& GA,
 277                 const EdgeArray<double>& eLengths,
 278                 EdgeArray<double>& adaptedLengths);
 279         //! Adapts positions to avoid degeneracy (all nodes on a single point)
 280         void shufflePositions(GraphAttributes& GA);
 281         //! Computes contribution of node u to the first partial
 282         //! derivatives (dE/dx_m, dE/dy_m) (for node m) (eq. 7 and 8 in paper)
 283         dpair computeParDer(node m,
 284                 node u,
 285                 GraphAttributes& GA,
 286                 NodeArray< NodeArray<double> >& ss,
 287                 NodeArray< NodeArray<double> >& dist);
 288         //! Compute partial derivative for v
 289         dpair computeParDers(node v,
 290                 GraphAttributes& GA,
 291                 NodeArray< NodeArray<double> >& ss,
 292                 NodeArray< NodeArray<double> >& dist);
 293         //! Does the necessary initialization work for the call functions
 294         void initialize(GraphAttributes& GA,
 295                 const EdgeArray<double>& eLength,
 296                 NodeArray< NodeArray<double> >& oLength,
 297                 NodeArray< NodeArray<double> >& weights,
 298                 double & maxDist,
 299                 bool simpleBFS);
 300         //! Main computation loop, nodes are moved here
 301         void mainStep(GraphAttributes& GA,
 302                 NodeArray< NodeArray<double> >& oLength,
 303                 NodeArray< NodeArray<double> >& weights,
 304                 const double maxDist);
 305         //! Does the scaling if no edge lengths are given but node sizes
 306         //! are respected
 307         void scale(GraphAttributes& GA);
 308
 309 private:
 310         //! The stop criterion when the forces of all strings are
 311         //! considered to be balanced
 312         double m_tolerance;  //!<value for stop criterion
 313         double m_ltolerance;  //!<value for local stop criterion
 314         int m_maxGlobalIt;   //!< Maximum number of global iterations
 315         int m_maxLocalIt;   //!< Maximum number of local iterations
 316         bool m_computeMaxIt; //!< If true, number of iterations is computed
 317         //! depending on number of nodes
 318         double m_K; //! Big K constant for strength computation
 319         double m_prevEnergy; //!<max energy value
 320         double m_prevLEnergy;//!<local energy
 321         double m_zeroLength; //!< Length of a side of the display area, used for
 322         //! edge length computation if > 0
 323         double m_desLength; //!< Desirable edge length, used instead if > 0
 324         double m_distFactor; //introduces some distance for scaling in case BFS is used
 325
 326         bool m_useLayout; //!< use positions or allow to shuffle nodes to
 327
 328         int m_constraints; //constraints bit pattern
 329
 330         bool m_radial; //!< if set to true, radial constraints are added
 331
 332         //!< avoid degeneration
 333         bool m_upward;
 334         int m_radiiStyle; //!< defines how radii are calculated:
 335         //!  0 = fixed distance m_firstRadius
 336         //!  1 = increasing with factor m_radiusFactor
 337         //!  2 = ...functions?
 338         NodeArray<double> m_radii; //!< stores computed radius for each node
 339         double m_baseRadius; //!< radius of first level
 340         int m_numSteps;     //!< number of iteration steps
 341         double m_itFac;     //!< Factor for additional number of iterations based on graph size
 342         double m_radiusFactor; //!< defines radius transformation from level 1 to k
 343         int m_gItBaseVal; //!< minimum number of global iterations
 344         int m_gItFactor;  //!< factor for global iterations: m_gItBaseVal+m_gItFactor*|V|
 345
 346
 347         double allpairsspBFS(const Graph& G, NodeArray< NodeArray<double> >& distance,
 348                 NodeArray< NodeArray<double> >& weights);
 349         double allpairssp(const Graph& G, const EdgeArray<double>& eLengths,
 350                 NodeArray< NodeArray<double> >& distance, NodeArray< NodeArray<double> >& weights,
 351                 const double threshold = DBL_MAX);
 352
 353         static const double startVal;
 354         static const double minVal;
 355         static const double desMinLength; //!< Defines minimum desired edge length.
 356         //! Smaller values are treated as zero
 357         static const int maxVal = INT_MAX; //! defines infinite upper bound for iteration number
 358
 359 };// StressMajorization
 360
 361 //Things that potentially could be added
 362 //      //! Returns the page ratio.
 363 //    double pageRatio() { return m_pageRatio; }
 364 //
 365 //      //! Sets the page ration to \a x.
 366 //    void pageRatio(double x) { m_pageRatio = x; }
 367 //
 368 //      //! Returns the current scaling method.
 369 //      Scaling scaling() const {
 370 //              return m_scaling;
 371 //      }
 372 //
 373 //      //! Sets the method for scaling the inital layout to \a sc.
 374 //      void scaling(Scaling sc) {
 375 //              m_scaling = sc;
 376 //      }
 377 //
 378 //      //! Returns the current scale function factor.
 379 //      double scaleFunctionFactor() const {
 380 //              return m_scaleFactor;
 381 //      }
 382 //
 383 //      //! Sets the scale function factor to \a f.
 384 //      void scaleFunctionFactor(double f) {
 385 //              m_scaleFactor = f;
 386 //      }
 387 //
 388 //      //! Sets the user bounding box (used if scaling method is scUserBoundingBox).
 389 //      void userBoundingBox(double xmin, double ymin, double xmax, double ymax) {
 390 //              m_bbXmin = xmin;
 391 //              m_bbYmin = ymin;
 392 //              m_bbXmax = xmax;
 393 //              m_bbYmax = ymax;
 394 //      }
 395
 396
 397 } // end namespace ogdf
 398
 399
 400 #endif