ext/OGDF/ogdf/energybased/GEMLayout.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 class GEMLayout.
  11  *
  12  * Fast force-directed layout algorithm (GEMLayout)
  13  * based on Frick et al.'s algorithm.
  14  *
  15  * \author Christoph Buchheim
  16  *
  17  * \par License:
  18  * This file is part of the Open Graph Drawing Framework (OGDF).
  19  *
  20  * \par
  21  * Copyright (C)<br>
  22  * See README.txt in the root directory of the OGDF installation for details.
  23  *
  24  * \par
  25  * This program is free software; you can redistribute it and/or
  26  * modify it under the terms of the GNU General Public License
  27  * Version 2 or 3 as published by the Free Software Foundation;
  28  * see the file LICENSE.txt included in the packaging of this file
  29  * for details.
  30  *
  31  * \par
  32  * This program is distributed in the hope that it will be useful,
  33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35  * GNU General Public License for more details.
  36  *
  37  * \par
  38  * You should have received a copy of the GNU General Public
  39  * License along with this program; if not, write to the Free
  40  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  41  * Boston, MA 02110-1301, USA.
  42  *
  43  * \see  http://www.gnu.org/copyleft/gpl.html
  44  ***************************************************************/
  45
  46
  47 #ifdef _MSC_VER
  48 #pragma once
  49 #endif
  50
  51 #ifndef OGDF_FAST_LAYOUT_H
  52 #define OGDF_FAST_LAYOUT_H
  53
  54 #include <ogdf/module/LayoutModule.h>
  55 #include <ogdf/basic/Math.h>
  56
  57
  58 namespace ogdf {
  59
  60         class OGDF_EXPORT GraphCopy;
  61         class OGDF_EXPORT GraphCopyAttributes;
  62
  63 //---------------------------------------------------------
  64 // GEMLayout
  65 //
  66 // Fast force-directed layout algorithm. See
  67 // - A. Frick, A. Ludwig, H. Mehldau: "A Fast Adaptive
  68 //       Layout Algorithm for Undirected Graphs"
  69 //
  70 //---------------------------------------------------------
  71
  72 //! The energy-based GEM layout algorithm.
  73 /**
  74  * The implementation used in GEMLayout is based on the following publication:
  75  *
  76  * Arne Frick, Andreas Ludwig, Heiko Mehldau: <i>A Fast Adaptive %Layout
  77  * Algorithm for Undirected Graphs</i>. Proc. %Graph Drawing 1994,
  78  * LNCS 894, pp. 388-403, 1995.
  79  *
  80  * <H3>Optional parameters</H3>
  81  * GEM layout provides the following optional parameters.
  82  *
  83  * <table>
  84  *   <tr>
  85  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  86  *   </tr><tr>
  87  *     <td><i>numberOfRounds</i><td>int<td>20000
  88  *     <td>The maximal number of rounds per node.
  89  *   </tr><tr>
  90  *     <td><i>minimalTemperature</i><td>double<td>0.005
  91  *     <td>The minimal temperature.
  92  *   </tr><tr>
  93  *     <td><i>initialTemperature</i><td>double<td>10.0
  94  *     <td>The initial temperature.
  95  *   </tr><tr>
  96  *     <td><i>gravitationalConstant</i><td>double<td>1/16
  97  *     <td>The gravitational constant.
  98  *   </tr><tr>
  99  *     <td><i>desiredLength</i><td>double<td>5.0
 100  *     <td>The desired edge length.
 101  *   </tr><tr>
 102  *     <td><i>maximalDisturbance</i><td>double<td>0
 103  *     <td>The maximal disturbance.
 104  *   </tr><tr>
 105  *     <td><i>rotationAngle</i><td>double<td>pi/3.0
 106  *     <td>The opening angle for rotations.
 107  *   </tr><tr>
 108  *     <td><i>oscillationAngle</i><td>double<td>pi/2.0
 109  *     <td>The opening angle for oscillations.
 110  *   </tr><tr>
 111  *     <td><i>rotationSensitivity</i><td>double<td>0.01
 112  *     <td>The rotation sensitivity.
 113  *   </tr><tr>
 114  *     <td><i>oscillationSensitivity</i><td>double<td>0.3
 115  *     <td>The oscillation sensitivity.
 116  *   </tr><tr>
 117  *     <td><i>attractionFormula</i><td>int<td>1
 118  *     <td>The used formula for attraction (1 = Fruchterman / Reingold, 2 = GEM).
 119  *   </tr><tr>
 120  *     <td><i>minDistCC</i><td>double<td>20
 121  *     <td>The minimal distance between connected components.
 122  *   </tr><tr>
 123  *     <td><i>pageRatio</i><td>double<td>1.0
 124  *     <td>The page ratio used for the layout of connected components.
 125  *   </tr>
 126  * </table>
 127 */
 128 class OGDF_EXPORT GEMLayout : public LayoutModule
 129 {
 130
 131         // algorithm parameters (see below)
 132
 133         int m_numberOfRounds;               //!< The maximal number of rounds per node.
 134         double m_minimalTemperature;    //!< The minimal temperature.
 135         double m_initialTemperature;    //!< The initial temperature.
 136         double m_gravitationalConstant; //!< The gravitational constant.
 137         double m_desiredLength;         //!< The desired edge length.
 138         double m_maximalDisturbance;    //!< The maximal disturbance.
 139         double m_rotationAngle;         //!< The opening angle for rotations.
 140         double m_oscillationAngle;      //!< The opening angle for oscillations.
 141         double m_rotationSensitivity;   //!< The rotation sensitivity.
 142         double m_oscillationSensitivity;//!< The oscillation sensitivity.
 143         int m_attractionFormula;        //!< The used formula for attraction.
 144         double m_minDistCC;             //!< The minimal distance between connected components.
 145         double m_pageRatio;             //!< The page ratio used for the layout of connected components.
 146
 147         // node data used by the algorithm
 148
 149         NodeArray<double> m_impulseX; //!< x-coordinate of the last impulse of the node
 150         NodeArray<double> m_impulseY; //!< y-coordinate of the last impulse of the node
 151         NodeArray<double> m_localTemperature; //!< local temperature of the node
 152         NodeArray<double> m_skewGauge; //!< skew gauge of the node
 153
 154         // other data used by the algorithm
 155
 156         double m_barycenterX; //!< Weighted sum of x-coordinates of all nodes.
 157         double m_barycenterY; //!< Weighted sum of y-coordinates of all nodes.
 158         double m_newImpulseX; //!< x-coordinate of the new impulse of the current node.
 159         double m_newImpulseY; //!< y-coordinate of the new impulse of the current node.
 160         double m_globalTemperature; //!< Average of all node temperatures.
 161         double m_cos; //!< Cosine of m_oscillationAngle / 2.
 162         double m_sin; //!< Sine of (pi + m_rotationAngle) / 2.
 163
 164 public:
 165
 166         //! Creates an instance of GEM layout.
 167         GEMLayout();
 168
 169         //! Copy constructor.
 170         GEMLayout(const GEMLayout &fl);
 171
 172         // destructor
 173         ~GEMLayout();
 174
 175         //! Assignment operator.
 176         GEMLayout &operator=(const GEMLayout &fl);
 177
 178         //! Calls the layout algorithm for graph attributes \a GA.
 179         void call(GraphAttributes &GA);
 180
 181         //! Returns the maximal number of rounds per node.
 182         int numberOfRounds() const { return m_numberOfRounds; }
 183
 184         //! Sets the maximal number of round per node to \a n.
 185         void numberOfRounds(int n) {
 186                 m_numberOfRounds = (n < 0) ? 0 : n;
 187         }
 188
 189         //! Returns the minimal temperature.
 190         double minimalTemperature() const { return m_minimalTemperature; }
 191
 192         //! Sets the minimal temperature to \a x.
 193         void minimalTemperature(double x) {
 194                 m_minimalTemperature = (x < 0) ? 0 : x;
 195         }
 196
 197         //! Returns the initial temperature.
 198         double initialTemperature() const { return m_initialTemperature; }
 199
 200         //! Sets the initial temperature to \a x; must be >= minimalTemperature.
 201         void initialTemperature(double x) {
 202                 m_initialTemperature = (x < m_minimalTemperature) ? m_minimalTemperature : x;
 203         }
 204
 205         //! Returns the gravitational constant.
 206         double gravitationalConstant() const { return m_gravitationalConstant; }
 207
 208         //! Sets the gravitational constant to \a x; must be >= 0.
 209         //! Attention! Only (very) small values give acceptable results.
 210         void gravitationalConstant(double x) {
 211                 m_gravitationalConstant = (x < 0) ? 0 : x;
 212         }
 213
 214         //! Returns the desired edge length.
 215         double desiredLength() const { return m_desiredLength; }
 216
 217         //! Sets the desired edge length to \a x; must be >= 0.
 218         void desiredLength(double x) {
 219                 m_desiredLength = (x < 0) ? 0 : x;
 220         }
 221
 222         //! Returns the maximal disturbance.
 223         double maximalDisturbance() const { return m_maximalDisturbance; }
 224
 225         //! Sets the maximal disturbance to \a x; must be >= 0.
 226         void maximalDisturbance(double x) {
 227                 m_maximalDisturbance = (x < 0) ? 0 : x;
 228         }
 229
 230         //! Returns the opening angle for rotations.
 231         double rotationAngle() const { return m_rotationAngle; }
 232
 233         //! Sets the opening angle for rotations to \a x (0 <= \a x <= pi / 2).
 234         void rotationAngle(double x) {
 235                 if(x < 0) x = 0;
 236                 if(x > Math::pi / 2.0) x = Math::pi / 2.0;
 237                 m_rotationAngle = x;
 238         }
 239
 240         //! Returns the opening angle for oscillations.
 241         double oscillationAngle() const { return m_oscillationAngle; }
 242
 243         //! Sets the opening angle for oscillations to \a x (0 <= \a x <= pi / 2).
 244         void oscillationAngle(double x) {
 245                 if(x < 0) x = 0;
 246                 if(x > Math::pi / 2.0) x = Math::pi / 2.0;
 247                 m_oscillationAngle = x;
 248         }
 249
 250         //! Returns the rotation sensitivity.
 251         double rotationSensitivity() const { return m_rotationSensitivity; }
 252
 253         //! Sets the rotation sensitivity to \a x (0 <= \a x <= 1).
 254         void rotationSensitivity(double x) {
 255                 if(x < 0) x = 0;
 256                 if(x > 1) x = 1;
 257                 m_rotationSensitivity = x;
 258         }
 259
 260         //! Returns the oscillation sensitivity.
 261         double oscillationSensitivity() const { return m_oscillationSensitivity; }
 262
 263         //! Sets the oscillation sensitivity to \a x (0 <= \a x <= 1).
 264         void oscillationSensitivity(double x) {
 265                 if(x < 0) x = 0;
 266                 if(x > 1) x = 1;
 267                 m_oscillationSensitivity = x;
 268         }
 269
 270         //! Returns the used formula for attraction (1 = Fruchterman / Reingold, 2 = GEM).
 271         int attractionFormula() const { return m_attractionFormula; }
 272
 273         //! sets the formula for attraction to \a n (1 = Fruchterman / Reingold, 2 = GEM).
 274         void attractionFormula(int n) {
 275                 if(n == 1 || n == 2) m_attractionFormula = n;
 276         }
 277
 278         //! Returns the minimal distance between connected components.
 279         double minDistCC() const { return m_minDistCC; }
 280
 281         //! Sets the minimal distance between connected components to \a x.
 282         void minDistCC(double x) { m_minDistCC = x; }
 283
 284         //! Returns the page ratio used for the layout of connected components.
 285         double pageRatio() const { return m_pageRatio; }
 286
 287         //! Sets the page ratio used for the layout of connected components to \a x.
 288         void pageRatio(double x) { m_pageRatio = x; }
 289
 290
 291 private:
 292         //! Returns the length of the vector (\a x,\a y).
 293         double length(double x,double y = 0) const {
 294                 return sqrt(x * x + y * y);
 295         }
 296
 297         //! Returns the weight of node \a v according to its degree.
 298         double weight(node v) const {
 299                 return (double)(v->degree()) / 2.5 + 1.0;
 300         }
 301
 302         //! Computes the new impulse for node \a v.
 303         void computeImpulse(GraphCopy &GC, GraphCopyAttributes &AGC,node v);
 304
 305         //! Updates the node data for node \a v.
 306         void updateNode(GraphCopy &GC, GraphCopyAttributes &AGC,node v);
 307
 308         OGDF_NEW_DELETE
 309 };
 310
 311 } // end namespace ogdf
 312
 313 #endif
 314