ext/OGDF/ogdf/basic/GridLayout.h

   1 /*
   2  * $Revision: 2576 $
   3  *
   4  * last checkin:
   5  *   $Author: klein $
   6  *   $Date: 2012-07-11 07:50:24 +0200 (Mi, 11. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class GridLayout.
  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_GRID_LAYOUT_H
  49 #define OGDF_GRID_LAYOUT_H
  50
  51
  52 #include <ogdf/basic/NodeArray.h>
  53 #include <ogdf/basic/geometry.h>
  54
  55
  56 namespace ogdf {
  57
  58         class Layout;
  59
  60
  61
  62 /**
  63  * \brief Representation of a graph's grid layout
  64  */
  65 class OGDF_EXPORT GridLayout
  66 {
  67 public:
  68         //! Creates an instance of a grid layout (associated with no graph).
  69         GridLayout() { }
  70
  71         //! Creates an instance of a grid layout associated with \a G.
  72         GridLayout(const Graph &G) : m_x(G,0), m_y(G,0), m_bends(G) { }
  73
  74         // destruction
  75         virtual ~GridLayout() { }
  76
  77
  78         //! Returns a reference to the array storing the x-coordinates of nodes.
  79         const NodeArray<int> &x() const { return m_x; }
  80         //! Returns a reference to the array storing the x-coordinates of nodes.
  81         NodeArray<int> &x() { return m_x; }
  82
  83         //! Returns a reference to the array storing the y-coordinates of nodes.
  84         const NodeArray<int> &y() const { return m_y; }
  85         //! Returns a reference to the array storing the y-coordinates of nodes.
  86         NodeArray<int> &y() { return m_y; }
  87
  88         //! Returns a reference to the array storing the bend points of edges.
  89         const EdgeArray<IPolyline> &bends() const { return m_bends; }
  90         //! Returns a reference to the array storing the bend points of edges.
  91         EdgeArray<IPolyline> &bends() { return m_bends; }
  92
  93
  94         //! Returns a reference to the x-coordinate of node \a v.
  95         const int &x(node v) const { return m_x[v]; }
  96         //! Returns a reference to the x-coordinate of node \a v.
  97         int &x(node v) { return m_x[v]; }
  98
  99         //! Returns a reference to the y-coordinate of node \a v.
 100         const int &y(node v) const { return m_y[v]; }
 101         //! Returns a reference to the y-coordinate of node \a v.
 102         int &y(node v) { return m_y[v]; }
 103
 104
 105         //! Returns a reference to the bend point list of edge \a e.
 106         const IPolyline &bends(edge e) const { return m_bends[e]; }
 107         //! Returns a reference to the bend point list of edge \a e.
 108         IPolyline &bends(edge e) { return m_bends[e]; }
 109
 110         //! Returns the polyline of edge \a e (including start and end point!).
 111         IPolyline polyline(edge e) const;
 112
 113
 114         //! Initializes the grid layout for graph \a G.
 115         void init(const Graph &G) {
 116                 m_x.init(G,0);
 117                 m_y.init(G,0);
 118                 m_bends.init(G);
 119         }
 120
 121         //! Initializes the grid layout for no graph (frees memory).
 122         void init() {
 123                 m_x.init();
 124                 m_y.init();
 125                 m_bends.init();
 126         }
 127
 128         //! Returns the bend point list of edge \a e without unnecessary bends.
 129         IPolyline getCompactBends(edge e) const;
 130
 131         //! Removes all unnecessary bends.
 132         void compactAllBends();
 133
 134         /**
 135          * \brief Checks if the grid layout is reasonable.
 136          *
 137          * In particular, the following checks are performed:
 138          *   - All nodes have to be assigned to distinct grid points.
 139          *   - All bend points have to be assigned to distinct points.
 140          *   - No bend point coincides with the position of a node.
 141          */
 142         bool checkLayout();
 143
 144         /**
 145          * \brief Computes the bounding box of the grid layout.
 146          *
 147          * The returned bounding box is (0,0,0,0) if the associated graph is empty
 148          * or no graph is associated with the grid layout.
 149          * @param xmin is assigned the minimum x-coordinate in the grid layout.
 150          * @param xmax is assigned the maximum x-coordinate in the grid layout.
 151          * @param ymin is assigned the minimum y-coordinate in the grid layout.
 152          * @param ymax is assigned the maximum y-coordinate in the grid layout.
 153          */
 154         void computeBoundingBox(int &xmin, int &xmax, int &ymin, int &ymax);
 155
 156         //! Computes the total manhattan edge length of the grid layout.
 157         int totalManhattanEdgeLength() const;
 158
 159         int maxManhattanEdgeLength() const;
 160         int manhattanEdgeLength(edge e) const;
 161
 162         //! Computes the total (euclidean) edge length of the grid layout.
 163         double totalEdgeLength() const;
 164
 165         //! Computes the total number of bends in the grid layout.
 166         int numberOfBends() const;
 167
 168         /**
 169          * \brief Transforms the grid layout to a layout.
 170          *
 171          * This implementation only copies the grid coordinates to \a drawing; the
 172          * derived class GridLayoutMapped performs the actual transformation of coordinates.
 173          */
 174         virtual void remap(Layout &drawing);
 175
 176         static int manhattanDistance(const IPoint &ip1, const IPoint &ip2);
 177         static double euclideanDistance(const IPoint &ip1, const IPoint &ip2);
 178
 179 protected:
 180         NodeArray<int> m_x;  //!< The x-coordinates of nodes.
 181         NodeArray<int> m_y;  //!< The y-coordinates of nodes.
 182         EdgeArray<IPolyline> m_bends; //!< The bend points of edges.
 183
 184 private:
 185         static bool isRedundant(IPoint &p1, IPoint &p2, IPoint &p3);
 186         static void compact(IPolyline &ip);
 187
 188
 189         OGDF_MALLOC_NEW_DELETE
 190 }; // class GridLayout
 191
 192
 193 } // end namespace ogdf
 194
 195 #endif