ext/OGDF/src/basic/GridLayoutModule.cpp

   1 /*
   2  * $Revision: 2549 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-04 23:09:19 +0200 (Mi, 04. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements grid mapping mechanism of class GridLayoutModule
  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 #include <ogdf/module/GridLayoutModule.h>
  45
  46
  47 namespace ogdf {
  48
  49
  50 void GridLayoutModule::call(GraphAttributes &AG)
  51 {
  52         const Graph &G = AG.constGraph();
  53
  54         // compute grid layout
  55         GridLayout gridLayout(G);
  56         doCall(G,gridLayout,m_gridBoundingBox);
  57
  58         // transform grid layout to real layout
  59         mapGridLayout(G,gridLayout,AG);
  60 }
  61
  62
  63 void GridLayoutModule::callGrid(const Graph &G, GridLayout &gridLayout)
  64 {
  65         gridLayout.init(G);
  66         doCall(G,gridLayout,m_gridBoundingBox);
  67 }
  68
  69
  70 void GridLayoutModule::mapGridLayout(const Graph &G,
  71         GridLayout &gridLayout,
  72         GraphAttributes &AG)
  73 {
  74         double maxWidth = 0; // maximum width of columns and rows;
  75         double yMax = 0;
  76
  77         node v;
  78         forall_nodes(v,G) {
  79                 if (AG.width (v) > maxWidth) maxWidth = AG.width (v);
  80                 if (AG.height(v) > maxWidth) maxWidth = AG.height(v);
  81                 if (gridLayout.y(v) > yMax) yMax = gridLayout.y(v);
  82         }
  83
  84         maxWidth += m_separation;
  85
  86         // set position of nodes
  87         forall_nodes(v,G) {
  88                 AG.x(v) = gridLayout.x(v) * maxWidth;
  89                 AG.y(v) = (yMax - gridLayout.y(v)) * maxWidth;
  90         }
  91
  92         // transform bend points of edges
  93         edge e;
  94         forall_edges(e,G) {
  95                 DPolyline &dpl = AG.bends(e);
  96                 dpl.clear();
  97
  98                 IPolyline ipl = gridLayout.polyline(e);
  99                 ListConstIterator<IPoint> it;
 100                 for(it = ipl.begin(); it.valid(); ++it) {
 101                         const IPoint &ip = *it;
 102                         dpl.pushBack(DPoint(ip.m_x*maxWidth, (yMax-ip.m_y)*maxWidth));
 103                 }
 104         }
 105 }
 106
 107
 108 void PlanarGridLayoutModule::callFixEmbed(GraphAttributes &AG, adjEntry adjExternal)
 109 {
 110         const Graph &G = AG.constGraph();
 111
 112         // compute grid layout
 113         GridLayout gridLayout(G);
 114         doCall(G,adjExternal,gridLayout,m_gridBoundingBox,true);
 115
 116         // transform grid layout to real layout
 117         mapGridLayout(G,gridLayout,AG);
 118 }
 119
 120
 121 void PlanarGridLayoutModule::callGridFixEmbed(
 122         const Graph &G,
 123         GridLayout &gridLayout,
 124         adjEntry adjExternal)
 125 {
 126         gridLayout.init(G);
 127         doCall(G,adjExternal,gridLayout,m_gridBoundingBox,true);
 128 }
 129
 130
 131 void GridLayoutPlanRepModule::callGrid(PlanRep &PG, GridLayout &gridLayout)
 132 {
 133         gridLayout.init(PG);
 134         doCall(PG,0,gridLayout,m_gridBoundingBox,false);
 135 }
 136
 137 void GridLayoutPlanRepModule::callGridFixEmbed(
 138         PlanRep &PG,
 139         GridLayout &gridLayout,
 140         adjEntry adjExternal)
 141 {
 142         gridLayout.init(PG);
 143         doCall(PG,adjExternal,gridLayout,m_gridBoundingBox,true);
 144 }
 145
 146 void GridLayoutPlanRepModule::doCall(
 147         const Graph &G,
 148         adjEntry adjExternal,
 149         GridLayout &gridLayout,
 150         IPoint &boundingBox,
 151         bool fixEmbedding)
 152 {
 153         // create temporary graph copy and grid layout
 154         PlanRep PG(G);
 155         PG.initCC(0); // currently only for a single component!
 156         GridLayout glPG(PG);
 157
 158         // determine adjacency entry on external face of PG (if required)
 159         if(adjExternal != 0) {
 160                 edge eG  = adjExternal->theEdge();
 161                 edge ePG = PG.copy(eG);
 162                 adjExternal = (adjExternal == eG->adjSource()) ? ePG->adjSource() : ePG->adjTarget();
 163         }
 164
 165         // call algorithm for copy
 166         doCall(PG,adjExternal,glPG,boundingBox,fixEmbedding);
 167
 168         // extract layout for original graph
 169         node v;
 170         forall_nodes(v,G) {
 171                 node vPG = PG.copy(v);
 172                 gridLayout.x(v) = glPG.x(vPG);
 173                 gridLayout.y(v) = glPG.y(vPG);
 174         }
 175
 176         edge e;
 177         forall_edges(e,G) {
 178                 IPolyline &ipl = gridLayout.bends(e);
 179                 ipl.clear();
 180
 181                 ListConstIterator<edge> it;
 182                 for(it = PG.chain(e).begin(); it.valid(); ++it)
 183                         ipl.conc(glPG.bends(*it));
 184         }
 185 }
 186
 187
 188 } // end namespace ogdf
 189