ext/OGDF/ogdf/energybased/SpringEmbedderFR.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of Spring-Embedder (Fruchterman,Reingold)
  11  *        algorithm.
  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
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49 #ifndef OGDF_SPRING_EMBEDDER_FR_H
  50 #define OGDF_SPRING_EMBEDDER_FR_H
  51
  52
  53 #include <ogdf/module/LayoutModule.h>
  54 #include <ogdf/basic/Array2D.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 Fruchterman and Reingold.
  65 /**
  66  * The implementation used in SpringEmbedderFR is based on
  67  * the following publication:
  68  *
  69  * Thomas M. J. Fruchterman, Edward M. Reingold: <i>%Graph Drawing by Force-directed
  70  * Placement</i>. Software - Practice and Experience 21(11), pp. 1129-1164, 1991.
  71  *
  72  * <H3>Optional parameters</H3>
  73  * Fruchterman/Reingold layout provides the following optional parameters.
  74  *
  75  * <table>
  76  *   <tr>
  77  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  78  *   </tr><tr>
  79  *     <td><i>iterations</i><td>int<td>400
  80  *     <td>The number of iterations performed in the optimization.
  81  *   </tr><tr>
  82  *     <td><i>noise</i><td>bool<td>true
  83  *     <td>If set to true, (small) random perturbations are performed.
  84  *   </tr><tr>
  85  *     <td><i>minDistCC</i><td>double<td>20.0
  86  *     <td>The minimum distance between connected components.
  87  *   </tr><tr>
  88  *     <td><i>pageRatio</i><td>double<td>1.0
  89  *     <td>The page ratio.
  90  *   </tr><tr>
  91  *     <td><i>scaling</i><td> #Scaling <td> #scScaleFunction
  92  *     <td>The scaling method for scaling the inital layout.
  93  *   </tr><tr>
  94  *     <td><i>scaleFunctionFactor</i><td>double<td>8.0
  95  *     <td>The scale function factor (used if scaling = scScaleFunction).
  96  *   </tr><tr>
  97  *     <td><i>userBoundingBox</i><td>rectangle<td>(0.0,100.0,0.0,100.0)
  98  *     <td>The user bounding box for scaling (used if scaling = scUserBoundingBox).
  99  *   </tr>
 100  * </table>
 101  */
 102 class OGDF_EXPORT SpringEmbedderFR : public LayoutModule
 103 {
 104 public:
 105         //! The scaling method used by the algorithm.
 106         enum Scaling {
 107                 scInput,           //!< bounding box of input is used.
 108                 scUserBoundingBox, //!< bounding box set by userBoundingBox() is used.
 109                 scScaleFunction    //!< automatic scaling is used with parameter set by scaleFunctionFactor() (larger factor, larger b-box).
 110         };
 111
 112
 113         //! Creates an instance of Fruchterman/Reingold layout.
 114         SpringEmbedderFR();
 115
 116         // destructor
 117         ~SpringEmbedderFR() { }
 118
 119
 120         //! Calls the layout algorithm for graph attributes \a GA.
 121         void call(GraphAttributes &GA);
 122
 123
 124         //! Returns the current setting of iterations.
 125         int iterations() const {
 126                 return m_iterations;
 127         }
 128
 129         //! Sets the number of iterations to \a i.
 130         void iterations(int i) {
 131                 if (i>0)
 132                         m_iterations = i;
 133         }
 134
 135         double fineness() const {
 136                 return m_fineness;
 137         }
 138
 139         void fineness(double f) {
 140                 m_fineness = f;
 141         }
 142
 143         //! Returns the current setting of nodes.
 144         bool noise() const {
 145                 return m_noise;
 146         }
 147
 148         //! Sets the parameter noise to \a on.
 149         void noise(bool on) {
 150                 m_noise = on;
 151         }
 152
 153         //! Returns the minimum distance between connected components.
 154         double minDistCC() const { return m_minDistCC; }
 155
 156         //! Sets the minimum distance between connected components to \a x.
 157         void minDistCC(double x) { m_minDistCC = x; }
 158
 159         //! Returns the page ratio.
 160         double pageRatio() { return m_pageRatio; }
 161
 162         //! Sets the page ration to \a x.
 163         void pageRatio(double x) { m_pageRatio = x; }
 164
 165         //! Returns the current scaling method.
 166         Scaling scaling() const {
 167                 return m_scaling;
 168         }
 169
 170         //! Sets the method for scaling the inital layout to \a sc.
 171         void scaling(Scaling sc) {
 172                 m_scaling = sc;
 173         }
 174
 175         //! Returns the current scale function factor.
 176         double scaleFunctionFactor() const {
 177                 return m_scaleFactor;
 178         }
 179
 180         //! Sets the scale function factor to \a f.
 181         void scaleFunctionFactor(double f) {
 182                 m_scaleFactor = f;
 183         }
 184
 185         //! Sets the user bounding box (used if scaling method is scUserBoundingBox).
 186         void userBoundingBox(double xmin, double ymin, double xmax, double ymax) {
 187                 m_bbXmin = xmin;
 188                 m_bbYmin = ymin;
 189                 m_bbXmax = xmax;
 190                 m_bbYmax = ymax;
 191         }
 192
 193 private:
 194         bool initialize(GraphCopy &G, GraphCopyAttributes &AG);
 195
 196         void mainStep(GraphCopy &G, GraphCopyAttributes &AG);
 197         void cleanup() {
 198                 delete m_A;
 199                 m_A = 0;
 200         }
 201
 202         NodeArray<ListIterator<node> > m_lit;
 203
 204         int m_cF;
 205
 206         double m_width;
 207         double m_height;
 208
 209         double m_txNull;
 210         double m_tyNull;
 211         double m_tx;
 212         double m_ty;
 213
 214         double m_k;
 215         double m_k2;
 216         double m_kk;
 217         int m_ki;
 218
 219         int m_xA;
 220         int m_yA;
 221
 222         Array2D<List<node> > *m_A;
 223
 224
 225         double mylog2(int x) {
 226                 double l = 0.0;
 227                 while(x > 0) {
 228                         l++;
 229                         x >>= 1;
 230                 }
 231                 return l/2;
 232         }
 233
 234         int    m_iterations;  //!< The number of iterations.
 235         double m_fineness;    //!< The fineness of the grid.
 236         double m_edgeLength;
 237
 238         double m_xleft;       //!< Bounding box (minimal x-coordinate).
 239         double m_xright;      //!< Bounding box (maximal x-coordinate).
 240         double m_ysmall;      //!< Bounding box (minimal y-coordinate).
 241         double m_ybig;        //!< Bounding box (maximal y-coordinate).
 242
 243         bool m_noise;         //!< Perform random perturbations?
 244
 245         Scaling m_scaling;    //!< The scaling method.
 246         double m_scaleFactor; //!< The factor used if scaling type is scScaleFunction.
 247
 248         double m_bbXmin; //!< User bounding box (minimal x-coordinate).
 249         double m_bbYmin; //!< User bounding box (maximal x-coordinate).
 250         double m_bbXmax; //!< User bounding box (minimal y-coordinate).
 251         double m_bbYmax; //!< User bounding box (maximal y-coordinate).
 252
 253         double m_minDistCC; //!< The minimal distance between connected components.
 254         double m_pageRatio; //!< The page ratio.
 255 };
 256
 257
 258 } // end namespace ogdf
 259
 260
 261 #endif