ext/OGDF/ogdf/planarity/PlanarizationGridLayout.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 planarization with grid layout.
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_PLANARIZATION_GRID_LAYOUT_H
  49 #define OGDF_PLANARIZATION_GRID_LAYOUT_H
  50
  51
  52
  53 #include <ogdf/module/GridLayoutModule.h>
  54 #include <ogdf/basic/ModuleOption.h>
  55 #include <ogdf/module/PlanarSubgraphModule.h>
  56 #include <ogdf/module/EdgeInsertionModule.h>
  57 #include <ogdf/module/GridLayoutModule.h>
  58 #include <ogdf/module/CCLayoutPackModule.h>
  59
  60
  61 namespace ogdf {
  62
  63
  64 /**
  65  * \brief The planarization grid layout algorithm.
  66  *
  67  * The class PlanarizationGridLayout represents a customizable implementation
  68  * of the planarization approach for drawing graphs. The class uses a
  69  * planar grid layout algorithm as a subroutine and allows to generate
  70  * a usual layout or a grid layout.
  71  *
  72  * If the planarization layout algorithm shall be used for simultaneous drawing,
  73  * you need to define the different subgraphs by setting the <i>subgraphs</i>
  74  * option.
  75  *
  76  * The implementation used in PlanarizationGridLayout is based on the following
  77  * publication:
  78  *
  79  * C. Gutwenger, P. Mutzel: <i>An Experimental Study of Crossing
  80  * Minimization Heuristics</i>. 11th International Symposium on %Graph
  81  * Drawing 2003, Perugia (GD '03), LNCS 2912, pp. 13-24, 2004.
  82  *
  83  * <H3>Optional parameters</H3>
  84  *
  85  * <table>
  86  *   <tr>
  87  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  88  *   </tr><tr>
  89  *     <td><i>pageRatio</i><td>double<td>1.0
  90  *     <td>Specifies the desired ration of width / height of the computed
  91  *     layout. It is currently only used when packing connected components.
  92  *   </tr>
  93  * </table>
  94  *
  95  * <H3>%Module options</H3>
  96  * The various phases of the algorithm can be exchanged by setting
  97  * module options allowing flexible customization. The algorithm provides
  98  * the following module options:
  99  *
 100  * <table>
 101  *   <tr>
 102  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
 103  *   </tr><tr>
 104  *     <td><i>subgraph</i><td>PlanarSubgraphModule<td>FastPlanarSubgraph
 105  *     <td>The module for the computation of the planar subgraph.
 106  *   </tr><tr>
 107  *     <td><i>inserter</i><td>EdgeInsertionModule<td>FixedEmbeddingInserter
 108  *     <td>The module used for edge insertion which is applied in the second
 109  *     step of the planarization method. The edges not contained in the planar
 110  *     subgraph are re-inserted one-by-one, each with as few crossings as possible.
 111  *   </tr><tr>
 112  *     <td><i>planarLayouter</i><td>GridLayoutPlanRepModule<td>MixedModelLayout
 113  *     <td>The planar layout algorithm used to compute a planar layout
 114  *     of the planarized representation resulting from the crossing minimization step.
 115  *   </tr><tr>
 116  *     <td><i>packer</i><td>CCLayoutPackModule<td>TileToRowsCCPacker
 117  *     <td>The packer module used for arranging connected components.
 118  *   </tr>
 119  * </table>
 120  */
 121 class OGDF_EXPORT PlanarizationGridLayout : public GridLayoutModule
 122 {
 123 public:
 124         //! Creates an instance of planarization layout and sets options to default values.
 125         PlanarizationGridLayout();
 126
 127         ~PlanarizationGridLayout() { }
 128
 129         /**
 130          *  @name Optional parameters
 131          *  @{
 132          */
 133
 134         /**
 135          * \brief Returns the current setting of option pageRatio.
 136          *
 137          * This option specifies the desired ration width / height of the computed
 138          * layout. It is currently only used for packing connected components.
 139          */
 140         double pageRatio() const {
 141                 return m_pageRatio;
 142         }
 143
 144         //! Sets the option pageRatio to \a ratio.
 145         void pageRatio(double ratio) {
 146                 m_pageRatio = ratio;
 147         }
 148
 149         /** @}
 150          *  @name Module options
 151          *  @{
 152          */
 153
 154         /**
 155          * \brief Sets the module option for the computation of the planar subgraph.
 156          *
 157          * The computation of a planar subgraph is the first step in the crossing
 158          * minimization procedure of the planarization approach.
 159          */
 160         void setSubgraph(PlanarSubgraphModule *pSubgraph) {
 161                 m_subgraph.set(pSubgraph);
 162         }
 163
 164         /**
 165          * \brief Sets the module option for edge insertion.
 166          *
 167          * The edge insertion module is applied in the second step of the planarization
 168          * method. The edges not contained in the planar subgraph are re-inserted
 169          * one-by-one, each with as few crossings as possible. The edge insertion
 170          * module implements the whole second step, i.e., it inserts all edges.
 171          */
 172         void setInserter(EdgeInsertionModule *pInserter) {
 173                 m_inserter.set(pInserter);
 174         }
 175
 176         /**
 177          * \brief Sets the module option for the planar grid layout algorithm.
 178          *
 179          * The planar layout algorithm is used to compute a planar layout
 180          * of the planarized representation resulting from the crossing
 181          * minimization step. Planarized representation means that edge crossings
 182          * are replaced by dummy nodes of degree four, so the actual layout
 183          * algorithm obtains a planar graph as input. By default, the planar
 184          * layout algorithm produces an orthogonal drawing.
 185          */
 186         void setPlanarLayouter(GridLayoutPlanRepModule *pPlanarLayouter) {
 187                 m_planarLayouter.set(pPlanarLayouter);
 188         }
 189
 190         /**
 191          * \brief Sets the module option for the arrangement of connected components.
 192          *
 193          * The planarization layout algorithm draws each connected component of
 194          * the input graph seperately, and then arranges the resulting drawings
 195          * using a packing algorithm.
 196          */
 197         void setPacker(CCLayoutPackModule *pPacker) {
 198                 m_packer.set(pPacker);
 199         }
 200
 201
 202         /** @}
 203          *  @name Further information
 204          *  @{
 205          */
 206
 207         //! Returns the number of crossings in computed layout.
 208         int numberOfCrossings() const {
 209                 return m_nCrossings;
 210         }
 211
 212         //! @}
 213
 214 protected:
 215         void doCall(const Graph &G, GridLayout &gridLayout, IPoint &boundingBox);
 216
 217
 218 private:
 219         //! The module for computing a planar subgraph.
 220         ModuleOption<PlanarSubgraphModule>    m_subgraph;
 221
 222         //! The module for edge re-insertion.
 223         ModuleOption<EdgeInsertionModule>     m_inserter;
 224
 225         //! The module for computing a planar grid layout.
 226         ModuleOption<GridLayoutPlanRepModule> m_planarLayouter;
 227
 228         //! The module for arranging connected components.
 229         ModuleOption<CCLayoutPackModule>      m_packer;
 230
 231         double m_pageRatio; //!< The desired page ratio.
 232
 233         int m_nCrossings; //!< The number of crossings in the computed layout.
 234 };
 235
 236
 237 } // end namespace ogdf
 238
 239
 240 #endif