ext/OGDF/src/planarlayout/PlanarStraightLayout.cpp

   1 /*
   2  * $Revision: 2554 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 11:39:38 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements class PlanarStraightLayout
  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/planarlayout/PlanarStraightLayout.h>
  45 #include <ogdf/basic/GraphCopy.h>
  46 #include <ogdf/basic/simple_graph_alg.h>
  47 #include <ogdf/augmentation/PlanarAugmentation.h>
  48 #include <ogdf/augmentation/PlanarAugmentationFix.h>
  49 #include <ogdf/module/ShellingOrderModule.h>
  50 #include <ogdf/planarlayout/BiconnectedShellingOrder.h>
  51 #include <ogdf/planarity/SimpleEmbedder.h>
  52
  53 namespace ogdf {
  54
  55
  56 PlanarStraightLayout::PlanarStraightLayout()
  57 {
  58         m_sizeOptimization = true;
  59         m_baseRatio        = 0.33;
  60
  61         m_augmenter.set(new PlanarAugmentation);
  62         m_computeOrder.set(new BiconnectedShellingOrder);
  63         m_embedder.set(new SimpleEmbedder);
  64 }
  65
  66
  67 void PlanarStraightLayout::doCall(
  68         const Graph &G,
  69         adjEntry adjExternal,
  70         GridLayout &gridLayout,
  71         IPoint &boundingBox,
  72         bool fixEmbedding)
  73 {
  74         // require to have a planar graph without multi-edges and self-loops;
  75         // planarity is checked below
  76         OGDF_ASSERT(isSimple(G) && isLoopFree(G));
  77
  78         // handle special case of graphs with less than 3 nodes
  79         if(G.numberOfNodes() < 3)
  80         {
  81                 node v1, v2;
  82                 switch(G.numberOfNodes())
  83                 {
  84                 case 0:
  85                         boundingBox = IPoint(0,0);
  86                         return;
  87
  88                 case 1:
  89                         v1 = G.firstNode();
  90                         gridLayout.x(v1) = gridLayout.y(v1) = 0;
  91                         boundingBox = IPoint(0,0);
  92                         return;
  93
  94                 case 2:
  95                         v1 = G.firstNode();
  96                         v2 = G.lastNode ();
  97                         gridLayout.x(v1) = gridLayout.y(v1) = gridLayout.y(v2) = 0;
  98                         gridLayout.x(v2) = 1;
  99                         boundingBox = IPoint(1,0);
 100                         return;
 101                 }
 102         }
 103
 104         // we make a copy of G since we use planar biconnected augmentation
 105         GraphCopySimple GC(G);
 106
 107         if(fixEmbedding) {
 108                 // determine adjacency entry on external face of GC (if required)
 109                 if(adjExternal != 0) {
 110                         edge eG  = adjExternal->theEdge();
 111                         edge eGC = GC.copy(eG);
 112                         adjExternal = (adjExternal == eG->adjSource()) ? eGC->adjSource() : eGC->adjTarget();
 113                 }
 114
 115                 PlanarAugmentationFix augmenter;
 116                 augmenter.call(GC);
 117
 118         } else {
 119                 adjExternal = 0;
 120
 121                 // augment graph planar biconnected
 122                 m_augmenter.get().call(GC);
 123
 124                 // embed augmented graph
 125                 m_embedder.get().call(GC,adjExternal);
 126         }
 127
 128         // compute shelling order with shelling order module
 129         m_computeOrder.get().baseRatio(m_baseRatio);
 130
 131         ShellingOrder order;
 132         m_computeOrder.get().callLeftmost(GC,order,adjExternal);
 133
 134         // compute grid coordinates for GC
 135         NodeArray<int> x(GC), y(GC);
 136         computeCoordinates(GC,order,x,y);
 137
 138         boundingBox.m_x = x[order(1,order.len(1))];
 139         boundingBox.m_y = 0;
 140         node v;
 141         forall_nodes(v,GC)
 142                 if(y[v] > boundingBox.m_y) boundingBox.m_y = y[v];
 143
 144         // copy coordinates from GC to G
 145         forall_nodes(v,G) {
 146                 node vCopy = GC.copy(v);
 147                 gridLayout.x(v) = x[vCopy];
 148                 gridLayout.y(v) = y[vCopy];
 149         }
 150 }
 151
 152
 153 void PlanarStraightLayout::computeCoordinates(const Graph &G,
 154         ShellingOrder &lmc,
 155         NodeArray<int> &x,
 156         NodeArray<int> &y)
 157 {
 158         // let c_1,...,c_q be the the current contour, then
 159         // next[c_i] = c_i+1, prev[c_i] = c_i-1
 160         NodeArray<node> next(G), prev(G);
 161
 162         // upper[v] = w means x-coord. of v is relative to w
 163         // (abs. x-coord. of v = x[v] + abs. x-coord of w)
 164         NodeArray<node> upper(G,0);
 165
 166         // initialize contour with base
 167         const ShellingOrderSet &V1 = lmc[1];
 168         node v1 = V1[1];
 169         node v2 = V1[V1.len()];
 170
 171         int i;
 172         for (i = 1; i <= V1.len(); ++i)
 173         {
 174                 y [V1[i]] = 0;
 175                 x [V1[i]] = (i == 1) ? 0 : 2;
 176                 if (i < V1.len())
 177                         next[V1[i]] = V1[i+1];
 178                 if (i > 1)
 179                         prev[V1[i]] = V1[i-1];
 180         }
 181         prev[v1] = next[v2] = 0;
 182
 183         // process shelling order from bottom to top
 184         const int n = lmc.length();
 185         int k;
 186         for (k = 2; k <= n; ++k)
 187         {
 188                 const ShellingOrderSet &Vk = lmc[k]; // Vk = { z_1,...,z_l }
 189                 int l = Vk.len();
 190                 node z1 = Vk[1];
 191                 node cl = Vk.left();  // left vertex
 192                 node cr = Vk.right(); // right vertex
 193
 194                 // compute relative x-distance from c_i to cl for i = l+1, ..., r
 195                 int x_cr = 0;
 196                 node v;
 197                 for (v = next[cl]; v != cr; v = next[v])
 198                 {
 199                         x_cr += x[v];
 200                         x[v] = x_cr;
 201                 }
 202                 x_cr += x[cr]; // x_cr = abs. x-coord(cr) - abs. x-coord(cl)
 203
 204                 int offset;
 205                 if (m_sizeOptimization == true)
 206                 {
 207                         // optimization: compute minimal value offset by which cr must be
 208                         // shift to right
 209                         int yMax = y[cr];
 210
 211                         // if there is an edge from cl to right with slope +1, or from cr
 212                         // to left with slope -1, then offset must be at least 2
 213                         offset = (y[cl] < y[next[cl]] || y[cr] < y[prev[cr]]) ? 2 : 0;
 214
 215                         // y_max = max { y[c_i] | l <= i <= r }
 216                         for (v = cl; v != cr; v = next[v]) {
 217                                 if (y[v] > yMax)
 218                                         yMax = y[v];
 219                         }
 220
 221                         // offset must be at least so large, such that
 222                         // y[z_i] > y_max for all i
 223                         offset = max (offset, 2*(yMax+l) - x_cr - y[cl] - y[cr]);
 224
 225                 } else // no size optimization
 226                         offset = 2*l;
 227
 228                 x_cr += offset;
 229
 230                 // compute insert coordinates of z_i for 1 <= i <= l
 231                 x[z1] = (x_cr + y[cr] - y[cl]) / 2 - l + 1;
 232                 y[z1] = (x_cr + y[cr] + y[cl]) / 2 - l + 1;
 233
 234                 for (i = 2; i <= l; i++) {
 235                         x[Vk[i]] = 2;
 236                         y[Vk[i]] = y[z1];
 237                 }
 238
 239                 // Compute shift values for cl,...,cr and relative x-coord. to a node
 240                 // upper[v] for inner nodes
 241                 // Let l <= c_alpha <= c_beta <= r max. with
 242                 //              y[cl] > ... > y[c_alpha] and y[c_beta] < ... < y[cr]
 243                 // Shift c_alpha,...,c_beta by offset/2 (c_alpha,c_beta only if != cl,
 244                 // cr)
 245                 // Shift c_beta+1,...,cr by offset
 246                 // x-coord. of c_l+1,    ...,c_alpha  relative to cl
 247                 //       -"-   c_alpha+1,...,c_beta-1 relative to z1
 248                 //       -"-   c_beta,   ...,cr       relative to cr
 249                 node c_alpha, c_beta;
 250                 if (y[cl] <= y[next[cl]]) {
 251                         c_alpha = cl;
 252
 253                 } else {
 254                         for (c_alpha = next[cl], v = next[c_alpha];
 255                                 c_alpha != cr && y[v] < y[c_alpha];
 256                                 c_alpha = v, v = next[v])
 257                         {
 258                                 x    [c_alpha] += 0;
 259                                 upper[c_alpha]  = cl;
 260                         }
 261                         if (c_alpha != cr) {
 262                                 x    [c_alpha] += (offset/2);
 263                                 upper[c_alpha]  = cl;
 264                         }
 265                 }
 266
 267                 if (y[cr] <= y[prev[cr]]) {
 268                         c_beta = cr;
 269
 270                 } else {
 271                         for (c_beta = prev[cr], v = prev[c_beta];
 272                                 c_beta != cl && y[v] < y[c_beta];
 273                                 c_beta = v, v = prev[v])
 274                         {
 275                                 x    [c_beta] += offset - x_cr;
 276                                 upper[c_beta]  = cr;
 277                         }
 278                         if (c_beta != cl && c_beta != c_alpha) {
 279                                 x    [c_beta] += (offset/2) - x_cr;
 280                                 upper[c_beta]  = cr;
 281                         }
 282                 }
 283
 284                 if (c_alpha != c_beta)
 285                         for (v = next[c_alpha]; v != c_beta; v = next[v]) {
 286                                 x    [v] += (offset/2) - x[z1];
 287                                 upper[v]  = z1;
 288                         }
 289
 290                 x[cr] = x_cr - (x[z1] + 2*(l-1));
 291
 292                 // update contour after insertion of z_1,...,z_l
 293                 for (i = 1; i <= l; i++)
 294                 {
 295                         if (i < l)
 296                                 next[Vk[i]] = Vk[i+1];
 297                         if (i > 1)
 298                                 prev[Vk[i]] = Vk[i-1];
 299                 }
 300                 next [cl]    = z1;
 301                 next [Vk[l]] = cr;
 302                 prev [cr]    = Vk[l];
 303                 prev [z1]    = cl;
 304         }
 305
 306         // compute final x-coordinates for the nodes on the (final) contour
 307         int sum = 0;
 308         for (node v = v1; v != 0; v = next[v]) {
 309                 x[v] = (sum += x[v]);
 310         }
 311
 312         // compute final x-coordinates for the inner nodes
 313         for (k = n-1; k >= 1; k--)
 314         {
 315                 for (i = 1; i <= lmc.len(k); i++)
 316                 {
 317                         node zi = lmc (k,i);
 318                         if (upper[zi] != 0)     // upper[zi] == 0 <=> z_i on contour
 319                                 x[zi] += x[upper[zi]];
 320                 }
 321         }
 322 }
 323
 324 } // end namespace ogdf
 325