ext/OGDF/src/planarlayout/SchnyderLayout.cpp

   1 /*
   2  * $Revision: 2599 $
   3  *
   4  * last checkin:
   5  *   $Author: chimani $
   6  *   $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Definition of the Schnyder Layout Algorithm (SchnyderLayout)
  11  *
  12  * \author Till Sch&auml;fer
  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 #include <ogdf/planarlayout/SchnyderLayout.h>
  44 #include <ogdf/basic/extended_graph_alg.h>
  45 #include <ogdf/basic/simple_graph_alg.h>
  46 #include <ogdf/basic/GraphCopy.h>
  47 #include <ogdf/basic/List.h>
  48
  49 namespace ogdf {
  50
  51 SchnyderLayout::SchnyderLayout() : PlanarGridLayoutModule() {
  52 }
  53
  54
  55 void SchnyderLayout::doCall(
  56         const Graph &G,
  57         adjEntry adjExternal,
  58         GridLayout &gridLayout,
  59         IPoint &boundingBox,
  60         bool fixEmbedding)
  61 {
  62         // check for double edges & self loops
  63         OGDF_ASSERT(isSimple(G));
  64
  65         // handle special case of graphs with less than 3 nodes
  66         if (G.numberOfNodes() < 3) {
  67                 node v1, v2;
  68                 switch (G.numberOfNodes()) {
  69                 case 0:
  70                         boundingBox = IPoint(0, 0);
  71                         return;
  72
  73                 case 1:
  74                         v1 = G.firstNode();
  75                         gridLayout.x(v1) = gridLayout.y(v1) = 0;
  76                         boundingBox = IPoint(0, 0);
  77                         return;
  78
  79                 case 2:
  80                         v1 = G.firstNode();
  81                         v2 = G.lastNode();
  82                         gridLayout.x(v1) = gridLayout.y(v1) = gridLayout.y(v2) = 0;
  83                         gridLayout.x(v2) = 1;
  84                         boundingBox = IPoint(1, 0);
  85                         return;
  86                 }
  87         }
  88
  89         // make a copy for triangulation
  90         GraphCopy GC(G);
  91
  92         // embed
  93         if (!fixEmbedding) {
  94                 if (planarEmbed(GC) == false) {
  95                         OGDF_THROW_PARAM(PreconditionViolatedException, pvcPlanar);
  96                 }
  97         }
  98
  99         triangulate(GC);
 100
 101         schnyderEmbedding(GC, gridLayout, adjExternal);
 102 }
 103
 104
 105 void SchnyderLayout::schnyderEmbedding(
 106         GraphCopy& GC,
 107         GridLayout &gridLayout,
 108         adjEntry adjExternal)
 109 {
 110         NodeArray<int> &xcoord = gridLayout.x();
 111         NodeArray<int> &ycoord = gridLayout.y();
 112
 113         node v;
 114         List<node> L;                                           // (un)contraction order
 115         GraphCopy T = GraphCopy(GC);            // the realizer tree (reverse direction of edges!!!)
 116         EdgeArray<int> rValues(T);                      // the realizer values
 117
 118         // choose outer face a,b,c
 119         adjEntry adja;
 120         if (adjExternal != 0) {
 121                 edge eG  = adjExternal->theEdge();
 122                 edge eGC = GC.copy(eG);
 123                 adja = (adjExternal == eG->adjSource()) ? eGC->adjSource() : eGC->adjTarget();
 124         }
 125         else {
 126                 adja = GC.firstEdge()->adjSource();
 127         }
 128         adjEntry adjb = adja->faceCyclePred();
 129         adjEntry adjc = adjb->faceCyclePred();
 130
 131         node a = adja->theNode();
 132         node b = adjb->theNode();
 133         node c = adjc->theNode();
 134
 135         node a_in_T = T.copy(GC.original(a));
 136         node b_in_T = T.copy(GC.original(b));
 137         node c_in_T = T.copy(GC.original(c));
 138
 139         contract(GC, a, b, c, L);
 140
 141         realizer(GC, L, a, b, c, rValues, T);
 142
 143         //DEBUG CODE !!!
 144         /*      edge ex;
 145                 GraphAttributes GA(T,GraphAttributes::edgeLabel | GraphAttributes::edgeArrow);
 146                 forall_edges(ex, T) {
 147                         char buffer[10];
 148                         int n = sprintf(buffer, 10, "%d", rValues[ex]);
 149                         GA.labelEdge(ex) = buffer;
 150                         GA.arrowEdge(ex) = GraphAttributes::last;
 151                 }
 152
 153                 GC.writeGML("/home/till/temp/gml/after_realizer_gc.gml");
 154                 GA.writeGML("/home/till/temp/gml/tree.gml");*/
 155
 156         NodeArray<int>  t1(T);
 157         NodeArray<int>  t2(T);
 158         NodeArray<int>  val(T, 1);
 159
 160         NodeArray<int>  P1(T);
 161         NodeArray<int>  P3(T);
 162         NodeArray<int>  v1(T);
 163         NodeArray<int>  v2(T);
 164
 165         subtreeSizes(rValues, 1, a_in_T, t1);
 166         subtreeSizes(rValues, 2, b_in_T, t2);
 167
 168         prefixSum(rValues, 1, a_in_T, val, P1);
 169         prefixSum(rValues, 3, c_in_T, val, P3);
 170         // now Pi  =  depth of all nodes in Tree T(i) (depth[root] = 1)
 171
 172         prefixSum(rValues, 2, b_in_T, t1, v1);
 173         // special treatment for a
 174         v1[a_in_T] = t1[a_in_T];
 175
 176         /*
 177          * v1[v] now is the sum of the
 178          * "count of nodes in t1" minus the "subtree size for node x"
 179          * for every node x on a path from b to v in t2
 180          */
 181
 182         prefixSum(rValues, 3, c_in_T, t1, val);
 183         // special treatment for a
 184         val[a_in_T] = t1[a_in_T];
 185
 186         /*
 187          * val[v] now is the sum of the
 188          * "count of nodes in t1" minus the "subtree size for node x"
 189          * for every node x on a path from c to v in t3
 190          */
 191
 192         // r1[v]=v1[v]+val[v]-t1[v] is the number of nodes in region 1 from v
 193         forall_nodes(v, T) {
 194                 // calc v1'
 195                 v1[v] += val[v] - t1[v] - P3[v];
 196         }
 197
 198         prefixSum(rValues, 3, c_in_T, t2, v2);
 199         // special treatment for b
 200         v2[b_in_T] = t2[b_in_T];
 201
 202         prefixSum(rValues, 1, a_in_T, t2, val);
 203         // special treatment for b
 204         val[b_in_T] = t2[b_in_T];
 205
 206         forall_nodes(v, T) {
 207                 // calc v2'
 208                 v2[v] += val[v] - t2[v] - P1[v];
 209         }
 210
 211         // copy coordinates to the GridLayout
 212         forall_nodes(v, GC) {
 213                 xcoord[GC.original(v)] = v1[T.copy(GC.original(v))];
 214                 ycoord[GC.original(v)] = v2[T.copy(GC.original(v))];
 215         }
 216 }
 217
 218
 219 /*
 220  * Constructs List L
 221  * L is the ordering for uncontracting the nodes in realizer
 222  */
 223 void SchnyderLayout::contract(Graph& G, node a, node b, node c, List<node>& L)
 224 {
 225         adjEntry adj1, adj2;
 226         List<node> candidates;
 227         NodeArray<bool> marked(G, false);                       // considered nodes
 228         NodeArray<int> deg(G, 0);                                       // # virtual neighbours
 229
 230         int N = G.numberOfEdges();
 231
 232         marked[a] = marked[b] = marked[c] = true;       // init outer face
 233
 234         deg[a] = deg[b] = deg[c] = N;
 235
 236         // mark neighbours of a and calc the degree of the second (virtual) neighbours
 237         forall_adj(adj1, a) {
 238                 marked[adj1->twinNode()] = true;
 239                 forall_adj(adj2, adj1->twinNode()) {
 240                         deg[adj2->twinNode()]++;
 241                 }
 242         }
 243
 244         // find first candidates
 245         forall_adj(adj1, a) {
 246                 if (deg[adj1->twinNode()] <= 2) {
 247                         candidates.pushBack(adj1->twinNode());
 248                 }
 249         }
 250
 251         while (!candidates.empty()) {
 252                 node u = candidates.popFrontRet();
 253                 if (deg[u] == 2) {
 254                         L.pushFront(u);
 255                         deg[u] = N;
 256                         forall_adj(adj1, u) {
 257                                 node v = adj1->twinNode();
 258                                 deg[v]--;                                                                               // u is virtualy deleted
 259                                 if (!marked[v]) {                                                               // v is new neighbour of a
 260                                         marked[v] = true;
 261                                         forall_adj(adj2, v) {
 262                                                 deg[adj2->twinNode()]++;                                // degree of virtaul neighbours increase
 263                                         }
 264                                         if (deg[v] <= 2) candidates.pushBack(v);        // next candidate v
 265                                 }
 266                                 else
 267                                         if (deg[v] == 2) candidates.pushBack(v);        // next candidate v
 268                         }
 269                 }
 270         }
 271 }
 272
 273
 274 /*
 275  * Construct the realiszer and the Tree T
 276  * rValues = realizer value
 277  * T = Tree
 278  */
 279 void SchnyderLayout::realizer(
 280         GraphCopy& G,
 281         const List<node>& L,
 282         node a,
 283         node b,
 284         node c,
 285         EdgeArray<int>& rValues,
 286         GraphCopy& T)
 287 {
 288         int  i = 0;
 289         edge e;
 290         NodeArray<int> ord(G, 0);
 291         adjEntry adj;
 292
 293         // ordering: b,c,L,a
 294         ord[b] = i++;
 295         ord[c] = i++;
 296
 297         forall_listiterators(node, it, L) {
 298                 ord[*it] = i++;                         // enumerate V(G)
 299         }
 300         ord[a] = i++;
 301
 302         // remove all edges (they will be re-added later with different orientation)
 303         while (T.numberOfEdges() > 0) {
 304                 e = T.firstEdge();
 305                 T.delCopy(e);
 306         }
 307
 308         forall_listiterators(node, it, L) {
 309                 node v = *it;
 310                 node u = T.copy(G.original(v));   // u is copy of v in T
 311
 312                 forall_adj(adj, v) {
 313                         if (ord[adj->twinNode()] > ord[v]) {
 314                                 break;
 315                         }
 316                 }
 317
 318                 adjEntry adj1 = adj;
 319                 while (ord[adj1->twinNode()] > ord[v]) {
 320                         adj1 = adj1->cyclicSucc();
 321                 }
 322                 e = T.newEdge(T.copy(G.original(adj1->twinNode())), u);
 323                 rValues[e] = 2;
 324
 325                 adjEntry adj2 = adj;
 326                 while (ord[adj2->twinNode()] > ord[v]) {
 327                         adj2 = adj2->cyclicPred();
 328                 }
 329                 e = T.newEdge(T.copy(G.original(adj2->twinNode())), u);
 330                 rValues[e] = 3;
 331
 332                 for (adj = adj1->cyclicSucc(); adj != adj2; adj = adj->cyclicSucc()) {
 333                         e =  T.newEdge(u, T.copy(G.original(adj->twinNode())));
 334                         rValues[e] = 1;
 335                 }
 336         }
 337
 338         // special treatement of a,b,c
 339         node a_in_T = T.copy(G.original(a));
 340         node b_in_T = T.copy(G.original(b));
 341         node c_in_T = T.copy(G.original(c));
 342
 343         // all edges to node a get realizer value 1
 344         forall_adj(adj, a) {
 345                 e = T.newEdge(a_in_T, T.copy(G.original(adj->twinNode())));
 346                 rValues[e] = 1;
 347         }
 348
 349         // rest of outer triangle (reciprocal linked, realizer values 2 and 3)
 350         e = T.newEdge(b_in_T, a_in_T);
 351         rValues[e] = 2;
 352         e = T.newEdge(b_in_T, c_in_T);
 353         rValues[e] = 2;
 354
 355         e = T.newEdge(c_in_T, a_in_T);
 356         rValues[e] = 3;
 357         e = T.newEdge(c_in_T, b_in_T);
 358         rValues[e] = 3;
 359 }
 360
 361
 362 /*
 363  * computes the sizes of all subtrees of a tree with root r
 364  */
 365 void SchnyderLayout::subtreeSizes(
 366         EdgeArray<int>& rValues,
 367         int i,
 368         node r,
 369         NodeArray<int>& size)
 370 {
 371         int  sum = 0;
 372         adjEntry adj;
 373         forall_adj(adj, r) {
 374                 if (adj->theEdge()->source() == r && rValues[adj->theEdge()] == i) {
 375                         node w = adj->twinNode();
 376                         subtreeSizes(rValues, i, w, size);
 377                         sum += size[w];
 378                 }
 379         }
 380         size[r] = sum + 1;
 381 }
 382
 383 /*
 384  * computes for every node u in the subtree of T(i) with root r
 385  * the sum of all val[v] where v is a node on the path from r to u
 386  */
 387 void SchnyderLayout::prefixSum(
 388         EdgeArray<int>& rValues,
 389         int i,
 390         node r,
 391         const NodeArray<int>& val,
 392         NodeArray<int>& sum)
 393 {
 394         List<node> Q;
 395
 396         Q.pushBack(r);
 397         sum[r] = val[r];
 398
 399         while (!Q.empty()) {
 400                 node v = Q.popFrontRet();
 401                 adjEntry adj;
 402                 forall_adj(adj, v)
 403                 if (adj->theEdge()->source() == v && rValues[adj->theEdge()] == i) {
 404                         node w = adj->twinNode();
 405                         Q.pushBack(w);
 406                         sum[w] = val[w] + sum[v];
 407                 }
 408         }
 409 }
 410
 411
 412 } //namespace ogdf