ext/OGDF/src/planarity/PlanarizationGridLayout.cpp

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements 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 #include <ogdf/planarity/PlanarizationGridLayout.h>
  45 #include <ogdf/planarity/FastPlanarSubgraph.h>
  46 #include <ogdf/planarity/FixedEmbeddingInserter.h>
  47 #include <ogdf/planarlayout/MixedModelLayout.h>
  48 #include <ogdf/packing/TileToRowsCCPacker.h>
  49
  50
  51 namespace ogdf {
  52
  53
  54 PlanarizationGridLayout::PlanarizationGridLayout()
  55 {
  56         m_subgraph      .set(new FastPlanarSubgraph);
  57         m_inserter      .set(new FixedEmbeddingInserter);
  58         m_planarLayouter.set(new MixedModelLayout);
  59         m_packer        .set(new TileToRowsCCPacker);
  60
  61         m_pageRatio = 1.0;
  62 }
  63
  64
  65 void PlanarizationGridLayout::doCall(
  66         const Graph &G,
  67         GridLayout &gridLayout,
  68         IPoint &bb)
  69 {
  70         m_nCrossings = 0;
  71         if(G.empty()) return;
  72
  73         PlanRep PG(G);
  74
  75         const int numCC = PG.numberOfCCs();
  76         // (width,height) of the layout of each connected component
  77         Array<IPoint> boundingBox(numCC);
  78
  79         int i;
  80         for(i = 0; i < numCC; ++i)
  81         {
  82                 PG.initCC(i);
  83                 const int nOrigVerticesPG = PG.numberOfNodes();
  84
  85                 List<edge> deletedEdges;
  86                 m_subgraph.get().callAndDelete(PG, deletedEdges);
  87
  88                 m_inserter.get().call(PG,deletedEdges);
  89
  90                 m_nCrossings += PG.numberOfNodes() - nOrigVerticesPG;
  91
  92                 GridLayout gridLayoutPG(PG);
  93                 m_planarLayouter.get().callGrid(PG,gridLayoutPG);
  94
  95                 // copy grid layout of PG into grid layout of G
  96                 ListConstIterator<node> itV;
  97                 for(itV = PG.nodesInCC(i).begin(); itV.valid(); ++itV)
  98                 {
  99                         node vG = *itV;
 100
 101                         gridLayout.x(vG) = gridLayoutPG.x(PG.copy(vG));
 102                         gridLayout.y(vG) = gridLayoutPG.y(PG.copy(vG));
 103
 104                         adjEntry adj;
 105                         forall_adj(adj,vG) {
 106                                 if ((adj->index() & 1) == 0) continue;
 107                                 edge eG = adj->theEdge();
 108                                 IPolyline &ipl = gridLayout.bends(eG);
 109                                 ipl.clear();
 110
 111                                 bool firstTime = true;
 112                                 ListConstIterator<edge> itE;
 113                                 for(itE = PG.chain(eG).begin(); itE.valid(); ++itE) {
 114                                         if(!firstTime) {
 115                                                 node v = (*itE)->source();
 116                                                 ipl.pushBack(IPoint(gridLayoutPG.x(v),gridLayoutPG.y(v)));
 117                                         } else
 118                                                 firstTime = false;
 119                                         ipl.conc(gridLayoutPG.bends(*itE));
 120                                 }
 121                         }
 122                 }
 123
 124                 boundingBox[i] = m_planarLayouter.get().gridBoundingBox();
 125                 boundingBox[i].m_x += 1; // one row/column space between components
 126                 boundingBox[i].m_y += 1;
 127         }
 128
 129         Array<IPoint> offset(numCC);
 130         m_packer.get().call(boundingBox,offset,m_pageRatio);
 131
 132         bb.m_x = bb.m_y = 0;
 133         for(i = 0; i < numCC; ++i)
 134         {
 135                 const List<node> &nodes = PG.nodesInCC(i);
 136
 137                 const int dx = offset[i].m_x;
 138                 const int dy = offset[i].m_y;
 139
 140                 if(boundingBox[i].m_x + dx > bb.m_x)
 141                         bb.m_x = boundingBox[i].m_x + dx;
 142                 if(boundingBox[i].m_y + dy > bb.m_y)
 143                         bb.m_y = boundingBox[i].m_y + dy;
 144
 145                 // iterate over all nodes in i-th cc
 146                 ListConstIterator<node> it;
 147                 for(it = nodes.begin(); it.valid(); ++it)
 148                 {
 149                         node vG = *it;
 150
 151                         gridLayout.x(vG) += dx;
 152                         gridLayout.y(vG) += dy;
 153
 154                         adjEntry adj;
 155                         forall_adj(adj,vG) {
 156                                 if ((adj->index() & 1) == 0) continue;
 157                                 edge eG = adj->theEdge();
 158
 159                                 ListIterator<IPoint> it;
 160                                 for(it = gridLayout.bends(eG).begin(); it.valid(); ++it) {
 161                                         (*it).m_x += dx;
 162                                         (*it).m_y += dy;
 163                                 }
 164                         }
 165                 }
 166         }
 167
 168         bb.m_x -= 1; // remove margin of topmost/rightmost box
 169         bb.m_y -= 1;
 170 }
 171
 172
 173 } // end namespace ogdf
 174