ext/OGDF/ogdf/planarlayout/PlanarDrawLayout.h

   1 /*
   2  * $Revision: 2547 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-04 22:05:45 +0200 (Mi, 04. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class PlanarDrawLayout which represents
  11  *        a planar straight-line drawing 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
  50 #ifndef OGDF_PLANAR_DRAW_LAYOUT_H
  51 #define OGDF_PLANAR_DRAW_LAYOUT_H
  52
  53
  54 #include <ogdf/module/GridLayoutModule.h>
  55 #include <ogdf/basic/ModuleOption.h>
  56 #include <ogdf/module/AugmentationModule.h>
  57 #include <ogdf/module/ShellingOrderModule.h>
  58 #include <ogdf/module/EmbedderModule.h>
  59
  60
  61 namespace ogdf {
  62
  63         class ShellingOrder;
  64
  65 /**
  66  * \brief Implementation of the Planar-Draw layout algorithm.
  67  *
  68  * The class PlanarDrawLayout implements a straight-line drawing algorithm
  69  * for planar graphs. It draws a planar graph on a grid of size at
  70  * most (<i>n</i>-2) * (<i>n</i>-2) without edge crossings.
  71  *
  72  * The algorithm runs in several phases. In the first phase,
  73  * the graph is augmented by adding edges to achieve a certain connectivity
  74  * (e.g., biconnected or triconnected). Then, a shelling order of the
  75  * the resulting graph is computed. Both phases are implemented by using
  76  * module options, so you can replace them with different implementations.
  77  * However, you have to make sure, that the connectivity achieved by the
  78  * augmentation module is sufficient for the shelling order module (or the
  79  * input graph already has the required connectivity).
  80  *
  81  * The implementation used in PlanarDrawLayout is an improved version of
  82  * the following publication:
  83  *
  84  * M. Chrobak, G. Kant: <i>Convex Grid Drawings of 3-connected Planar
  85  * Graphs</i>. International Journal of Computational Geometry and Applications
  86  * 7(3), pp. 211-223, 1997.
  87  *
  88  * <H3>Precondition</H3>
  89  * The input graph needs to be planar and simple (i.e., no self-loops and no
  90  * multiple edges).
  91  *
  92  * <H3>Optional parameters</H3>
  93  *
  94  * <table>
  95  *   <tr>
  96  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  97  *   </tr><tr>
  98  *     <td><i>sizeOptimization</i><td>bool<td>true
  99  *     <td>If this option is set to true, the algorithm tries to reduce the
 100  *     size of the resulting grid layout.
 101  *   </tr><tr>
 102  *     <td><i>sideOptimization</i><td>bool<td>false
 103  *     <td>If this option is set to true, slopes different from +1, 0, -1
 104  *     are allowed on the contour for reducing the resulting grid size.
 105  *   </tr><tr>
 106  *     <td><i>baseRatio</i><td>double<td>0.33
 107  *     <td>This option specifies the maximal number of nodes placed on the base line.
 108  *     The algorithm tries to place as many nodes as possible on the base
 109  *     line, but takes at most max(2, \a baseRatio * size of external face) many.
 110  *   </tr>
 111  * </table>
 112  *
 113  * <H3>%Module options</H3>
 114  * Instances of type PlanarDrawLayout provide the following module options:
 115  *
 116  * <table>
 117  *   <tr>
 118  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
 119  *   </tr><tr>
 120  *     <td><i>augmenter</i><td>AugmentationModule<td>PlanarAugmentation
 121  *     <td>Augments the graph by adding edges to obtain a planar graph with
 122  *     a certain connectivity (e.g., biconnected or triconnected).
 123  *   </tr><tr>
 124  *     <td><i>embedder</i><td>EmbedderModule<td>SimpleEmbedder
 125  *     <td>Planar embedding algorithm applied after planar augmentation.
 126  *   </tr><tr>
 127  *     <td><i>shellingOrder</i><td>ShellingOrderModule<td>BiconnectedShellingOrder
 128  *     <td>The algorithm to compute a shelling order. The connectivity assured
 129  *     by the planar augmentation module has to be sufficient for the shelling
 130  *     order module!
 131  *   </tr>
 132  * </table>
 133  *
 134  * <H3>Running Time</H3>
 135  * The computation of the layout takes time O(<I>n</I>), where <I>n</I> is
 136  * the number of nodes of the input graph.
 137  */
 138 class OGDF_EXPORT PlanarDrawLayout : public PlanarGridLayoutModule
 139 {
 140 public:
 141         //! Constructs an instance of the Planar-Draw layout algorithm.
 142         PlanarDrawLayout();
 143
 144         ~PlanarDrawLayout() { }
 145
 146
 147         /**
 148          *  @name Optional parameters
 149          *  @{
 150          */
 151
 152         /**
 153          * \brief Returns the current setting of option sizeOptimization.
 154          *
 155          * If this option is set to true, the algorithm tries to reduce the
 156          * size of the resulting grid layout.
 157          */
 158         bool sizeOptimization() const { return m_sizeOptimization; }
 159
 160         //! Sets the option sizeOptimization to \a opt.
 161         void sizeOptimization(bool opt) { m_sizeOptimization = opt; }
 162
 163         /**
 164          * \brief Returns the current setting of option sideOptimization.
 165          *
 166          * If this option is set to true, slopes different from +1, 0, -1
 167          * are allowed on the contour for reducing the resulting grid size.
 168          */
 169         bool sideOptimization() const { return m_sizeOptimization; }
 170
 171         //! Sets the option sideOptimization to \a opt.
 172         void sideOptimization(bool opt) { m_sizeOptimization = opt; }
 173
 174         /**
 175          * \brief Returns the current setting of option baseRatio.
 176          *
 177          * This option specifies the maximal number of nodes placed on the base line.
 178          * The algorithm tries to place as many nodes as possible on the base
 179          * line, but takes at most max(2, \a baseRatio * size of external face) many.
 180          */
 181         double baseRatio() const { return m_baseRatio; }
 182
 183         //! Sets the option baseRatio to \a ratio.
 184         void baseRatio(double ratio) { m_baseRatio = ratio; }
 185
 186
 187         /** @}
 188          *  @name Module options
 189          *  @{
 190          */
 191
 192         /**
 193          * \brief Sets the augmentation module.
 194          *
 195          * The augmentation module needs to make sure that the graph gets the
 196          * connectivity required for calling the shelling order module.
 197          */
 198         void setAugmenter(AugmentationModule *pAugmenter) {
 199                 m_augmenter.set(pAugmenter);
 200         }
 201
 202         //! Sets the shelling order module.
 203         void setShellingOrder(ShellingOrderModule *pOrder){
 204                 m_computeOrder.set(pOrder);
 205         }
 206
 207         //! Sets the module option for the graph embedding algorithm.
 208         void setEmbedder(EmbedderModule *pEmbedder) {
 209                 m_embedder.set(pEmbedder);
 210         }
 211
 212         //! @}
 213
 214 private:
 215         bool   m_sizeOptimization; //!< The option for allowing arbitrary slopes.
 216         bool   m_sideOptimization; //!< The option for size optimization.
 217         double m_baseRatio;        //!< The option for specifying the base ratio.
 218
 219         ModuleOption<EmbedderModule>      m_embedder;       //!< The planar embedder module.
 220         ModuleOption<AugmentationModule>  m_augmenter;          //!< The augmentation module.
 221         ModuleOption<ShellingOrderModule> m_computeOrder;       //!< The shelling order module.
 222
 223         // computes grid layout for graph G
 224         void doCall(
 225                 const Graph &G,
 226                 adjEntry adjExternal,
 227                 GridLayout &gridLayout,
 228                 IPoint &boundingBox,
 229                 bool fixEmbedding);
 230
 231         void computeCoordinates(const Graph &G,
 232                 ShellingOrder &order,
 233                 NodeArray<int> &x,
 234                 NodeArray<int> &y);
 235
 236 };
 237
 238
 239 } // end namespace ogdf
 240
 241
 242 #endif