ext/OGDF/src/upward/LayerBasedUPRLayout.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 Implementation of OrderComparer and LayerBasedUPRLayout classes.
  11  *
  12  * \author Hoi-Ming Wong
  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/upward/LayerBasedUPRLayout.h>
  44 #include <ogdf/basic/simple_graph_alg.h>
  45 #include <ogdf/basic/Queue.h>
  46 #include <ogdf/basic/Stack.h>
  47
  48
  49 namespace ogdf {
  50
  51
  52 OrderComparer::OrderComparer(const UpwardPlanRep &_UPR, Hierarchy &_H) : UPR(_UPR), H(_H)
  53 {
  54         dfsNum.init(UPR, -1);
  55         crossed.init(UPR, false);
  56
  57         //compute dfs number
  58         node start;
  59         hasSingleSource(UPR, start);
  60         NodeArray<bool> visited(UPR, false);
  61         adjEntry rightAdj = UPR.getAdjEntry(UPR.getEmbedding(), start, UPR.getEmbedding().externalFace());
  62         int num = 0;
  63         dfsNum[start] = num++;
  64         adjEntry run = rightAdj;
  65         do {
  66                 run = run->cyclicSucc();
  67                 if (!visited[run->theEdge()->target()])
  68                         dfs_LR(run->theEdge(), visited, dfsNum, num);
  69         } while(run != rightAdj);
  70
  71 }
  72
  73
  74
  75 bool OrderComparer::left(edge e1UPR, edge e2UPR) const
  76 {
  77         OGDF_ASSERT(e1UPR->source() == e2UPR->source() || e1UPR->target() == e2UPR->target());
  78         OGDF_ASSERT(e1UPR != e2UPR);
  79
  80         node v = e1UPR->source();
  81         if (e2UPR->source() != v)
  82                 v = e1UPR->target();
  83
  84         adjEntry inLeft = 0, outLeft = 0;
  85         //compute left in and left out edge of the common node v if exist
  86         if (v->indeg() != 0) {
  87                 adjEntry run;
  88                 forall_adj(run, v) {
  89                         if (run->cyclicSucc()->theEdge()->source() == v)
  90                                 break;
  91                 }
  92                 inLeft = run;
  93         }
  94         if (v->outdeg() != 0) {
  95                 adjEntry run;
  96                 forall_adj(run, v) {
  97                         if (run->cyclicPred()->theEdge()->target() == v)
  98                                 break;
  99                         if (UPR.getEmbedding().leftFace(run) == UPR.getEmbedding().externalFace())
 100                                 break;
 101                 }
 102                 outLeft = run;
 103         }
 104
 105         //same source;
 106         if (v == e2UPR->source()) {
 107                 do {
 108                         if (outLeft->theEdge() == e1UPR)
 109                                 return false;
 110                         if (outLeft->theEdge() == e2UPR)
 111                                 return true;
 112                         outLeft = outLeft->cyclicSucc();
 113                 } while (true);
 114         }
 115         //same target
 116         else {
 117                 do {
 118                         if (inLeft->theEdge() == e1UPR)
 119                                 return false;
 120                         if (inLeft->theEdge() == e2UPR)
 121                                 return true;
 122                         inLeft = inLeft->cyclicPred();
 123                 } while (true);
 124         }
 125 }
 126
 127
 128
 129 bool OrderComparer::left(node v1UPR, List<edge> chain1, node v2UPR , List<edge> chain2) const
 130 {
 131         //mark the edges an nodes of chain2 list
 132         NodeArray<bool> visitedNode(UPR, false);
 133         EdgeArray<bool> visitedEdge(UPR, false);
 134         forall_listiterators(edge, it, chain2) {
 135                 edge e = *it;
 136                 visitedNode[e->source()] =  visitedNode[e->target()] = true;
 137                 visitedEdge[e] = true;
 138         }
 139
 140         // traverse from vUPR2 to the super source using left path p and marks it.
 141         visitedNode[v2UPR] = true;
 142         adjEntry run = UPR.leftInEdge(v2UPR);
 143         while (run != 0) {
 144                 visitedNode[run->theEdge()->source()] = visitedNode[run->theEdge()->target()] = true;
 145                 visitedEdge[run->theEdge()] = true;
 146                 run = UPR.leftInEdge(run->theEdge()->source());
 147         }
 148
 149         //is one of the node of chain1 marked?
 150         ListIterator<edge> it;
 151         for(it = chain1.rbegin(); it.valid(); --it) {
 152                 node u = (*it)->source();
 153                 if (visitedNode[u]) {
 154                         adjEntry run;
 155                         forall_adj(run, u) {
 156                                 if (visitedEdge[run->theEdge()] && run->theEdge()->source() == run->theNode()) // outgoing edges only
 157                                         return left(*it, run->theEdge()); //(outEdgeOrder[*it] > outEdgeOrder[run->theEdge()]);
 158                         }
 159                 }
 160         }
 161
 162         // traverse from vUPR1 to a node of path p (using left path).
 163         adjEntry adj_v1 = 0, adj_v2 = 0;
 164         run = UPR.leftInEdge(v1UPR);
 165         while (run != 0) {
 166                 if (visitedNode[run->theEdge()->source()]) {
 167                         adj_v1 = run->twin(); //reached a marked node
 168                         break;
 169                 }
 170                 run = UPR.leftInEdge(run->theEdge()->source());
 171         }
 172
 173         OGDF_ASSERT(adj_v1 != 0);
 174
 175         forall_adj(run, adj_v1->theNode()) {
 176                 if (visitedEdge[run->theEdge()] && run->theEdge()->source() == run->theNode()){ // outgoing edges only
 177                         adj_v2 = run;
 178                         break;
 179                 }
 180         }
 181
 182         OGDF_ASSERT(adj_v2 != 0);
 183
 184         return left(adj_v1->theEdge(), adj_v2->theEdge());
 185 }
 186
 187
 188
 189 bool OrderComparer::checkUp(node vUPR, int level) const
 190 {
 191         const GraphCopy &GC = H;
 192
 193         //traverse from vUPR (going up)
 194         NodeArray<bool> inList(UPR, false);
 195         List<node> l;
 196         l.pushBack(vUPR);
 197         inList[vUPR] = true;
 198         while (!l.empty()) {
 199                 node v = l.popFrontRet();
 200                 node vOrig = UPR.original(v);
 201                 if (vOrig != 0 && H.rank(GC.copy(vOrig)) <= level)
 202                         return true;
 203                 List<edge> outEdges;
 204                 UPR.outEdges(v, outEdges);
 205                 forall_listiterators(edge, it, outEdges) {
 206                         node tgt = (*it)->target();
 207                         if (!inList[tgt]) {
 208                                 l.pushBack(tgt);
 209                                 inList[tgt] = true;
 210                         }
 211                 }
 212         }
 213         return false;
 214 }
 215
 216
 217
 218 bool OrderComparer::left(List<edge> &chain1, List<edge> &chain2, int level) const
 219 {
 220         //mark the source nodes of the edges of chain1
 221         NodeArray<bool> markedNodes(UPR, false);
 222         EdgeArray<bool> markedEdges(UPR, false);
 223         forall_listiterators(edge, iter, chain1) {
 224                 node v = (*iter)->source();
 225                 markedNodes[v] = true;
 226                 markedEdges[*iter] = true;
 227         }
 228
 229         //compute the list of common nodes of chain1 and chain2
 230         List< Tuple2<node, bool> > commonNodeList; // first: common node; second: true if vH1 (associated with chain1) is on the left hand side
 231         forall_listiterators(edge, iter, chain2) {
 232                 node v = (*iter)->source();
 233                 if (markedNodes[v]) {
 234                         edge e = *iter;
 235                         bool value = true;
 236                         adjEntry adj = e->adjSource();
 237                         while (true) {
 238                                 adj = adj->cyclicSucc();
 239                                 if (adj->theEdge()->target() == v) {
 240                                         value = false;
 241                                         break;
 242                                 }
 243                                 if (markedEdges[adj->theEdge()]) {
 244                                         break;
 245                                 }
 246
 247                         }
 248                         Tuple2<node, bool> tulp(v, value);
 249                         commonNodeList.pushFront(tulp);
 250                 }
 251         }
 252
 253         //no crossings between the associated edges
 254         if (commonNodeList.empty()) {
 255                 if (chain1.front()->source() == chain2.front()->source()) {
 256                                 return left(chain1.front(), chain2.front());
 257                         }
 258                         else
 259                                 return left(chain1.front()->source(), chain1, chain2.front()->source(), chain2);
 260         }
 261
 262         // there is a least one crossing
 263         ListIterator< Tuple2<node, bool> > it = commonNodeList.begin();
 264         while(it.valid()) {
 265                 Tuple2<node, bool> tulp = *it;
 266                 // is there a node above which level is lower or equal the given level?
 267                 // if so, then return the value
 268                 if (checkUp(tulp.x1(), level)) {
 269                         // there is a node above, which is lower or equal the given level
 270                         return tulp.x2();
 271                 }
 272                 it = it.succ();
 273         }
 274
 275         // the both edges are on the "first segment" of the crossing
 276         Tuple2<node, bool> tulp = *(commonNodeList.rbegin());
 277         return !tulp.x2();
 278 }
 279
 280
 281
 282 bool OrderComparer::less(node vH1, node vH2) const
 283 {
 284         if (vH1 == vH2)
 285                 return false;
 286
 287         /*
 288         case:vH1 and vH2 are not long-edge dummies.
 289         */
 290         const GraphCopy &GC = H;
 291         if (!H.isLongEdgeDummy(vH1) && !H.isLongEdgeDummy(vH2)) {
 292                 node v1 = UPR.copy(GC.original(vH1));
 293                 node v2 = UPR.copy(GC.original(vH2));
 294                 if (dfsNum[v1] > dfsNum[v2])
 295                         return true;
 296                 else
 297                         return false;
 298         }
 299
 300         /*
 301         vH1 and vH2 are long-edge-dummies
 302         */
 303         if (H.isLongEdgeDummy(vH1) && H.isLongEdgeDummy(vH2)) {
 304                 List<edge> chain1 = UPR.chain(GC.original(vH1->firstAdj()->theEdge()));
 305                 List<edge> chain2 = UPR.chain(GC.original(vH2->firstAdj()->theEdge()));
 306
 307                 OGDF_ASSERT(!chain1.empty() && !chain2.empty());
 308
 309                 int level = H.rank(vH1);
 310                 return (left(chain1, chain2, level));
 311         }//end both are long edge dummies
 312
 313         /*
 314         only vH1 or vH2 is a long-edge dummy
 315         */
 316         node v;
 317         List<edge> chain1, chain2;
 318         if (H.isLongEdgeDummy(vH1)) {
 319                 chain1 = UPR.chain(GC.original(vH1->firstAdj()->theEdge()));
 320                 v = UPR.copy(GC.original(vH2));
 321
 322                 OGDF_ASSERT(!chain1.empty());
 323
 324                 return left(chain1.front()->source(), chain1, v, chain2);
 325         }
 326         else {
 327                 chain2 = UPR.chain(GC.original(vH2->firstAdj()->theEdge()));
 328                 v = UPR.copy(GC.original(vH1));
 329
 330                 OGDF_ASSERT(!chain2.empty());
 331
 332                 return left(v, chain1, chain2.front()->source(), chain2);
 333         }
 334 }
 335
 336
 337
 338 void OrderComparer::dfs_LR(
 339         edge e,
 340         NodeArray<bool> &visited,
 341         NodeArray<int> &dfsNum,
 342         int &num)
 343 {
 344         node v = e->target();
 345         //outEdgeOrder[e] = num++;
 346         dfsNum[v] = num++;
 347         if (e->target()->outdeg() > 0) {
 348                 // compute left out edge
 349                 adjEntry run;
 350                 forall_adj(run, v) {
 351                         adjEntry adj_pred = run->cyclicPred();
 352                         if (adj_pred->theEdge()->target() == v && run->theEdge()->source() == v)
 353                                 break; // run is the left out-edge
 354                 }
 355
 356                 do {
 357                         if (!visited[run->theEdge()->target()]) {
 358                                 dfs_LR(run->theEdge(), visited, dfsNum, num);
 359                         }
 360                         run = run->cyclicSucc();
 361                 } while(run->theEdge()->target() != e->target());
 362         }
 363         visited[v] = true;
 364 }
 365
 366
 367
 368 void LayerBasedUPRLayout::doCall(const UpwardPlanRep &UPR, GraphAttributes &AG)
 369 {
 370         OGDF_ASSERT(UPR.augmented());
 371
 372         numberOfLevels = 0;
 373         m_numLevels = 0;
 374         m_crossings = 0;
 375
 376         const Graph &G = UPR.original();
 377         NodeArray<int> rank_G(G);
 378         computeRanking(UPR, rank_G);
 379         Hierarchy H(G, rank_G);
 380         const GraphCopy &GC = H;
 381
 382         /*
 383         //debug
 384         //UPR.outputFaces(UPR.getEmbedding());
 385         node x;
 386         forall_nodes(x, G) {
 387                 cout << "vOrig " << x << ";   vUPR " << UPR.copy(x) << endl;
 388         }
 389         forall_nodes(x, UPR) {
 390                 cout << "UPR edge order:" << endl;
 391                 adjEntry adj = x->firstAdj();
 392                 cout << "node " << x << endl;
 393                 do {
 394                         cout << " edge : " << adj->theEdge() << endl;
 395                         adj = adj->cyclicSucc();
 396                 } while (adj != x->firstAdj());
 397         }
 398         */
 399
 400         //adjust order
 401         OrderComparer oComparer(UPR, H);
 402         for(int i = 0; i < H.size(); ++i) {
 403                 Level &l = H[i];
 404                 l.sortOrder(oComparer);
 405         }
 406
 407
 408         // ********************** postprocessing *******************************************
 409         node vTmp;
 410         List<node> sources;
 411         forall_nodes(vTmp, GC) {
 412                 if (vTmp->indeg() == 0)
 413                         sources.pushBack(vTmp);
 414         }
 415
 416         RankComparer comp;
 417         comp.H = &H;
 418         sources.quicksort(comp);
 419         sources.reverse();
 420
 421
 422
 423         postProcessing_reduceLED(H, sources);
 424         H.buildAdjNodes();
 425
 426         /*
 427         //debug
 428         cout << endl << endl;
 429         for(int i = 0; i <= H.high(); i++) {
 430                 Level &lvl = H[i];
 431                 cout << "level : " << lvl.index() << endl;
 432                 cout << "nodes : ";
 433                 for(int j = 0; j <= lvl.high(); j++) {
 434                         cout << lvl[j] << " ";
 435                 }
 436                 cout << endl;
 437         }
 438         */
 439
 440         postProcessing_sourceReorder(H, sources);
 441         m_crossings = H.calculateCrossings();
 442
 443         OGDF_ASSERT(m_crossings <= UPR.numberOfCrossings());
 444         OGDF_ASSERT(m_layout.valid());
 445
 446         GraphCopyAttributes AGC(H, AG);
 447         m_layout.get().call(H,AG);
 448         // ********************** end postprocessing *******************************************
 449
 450         numberOfLevels = H.size();
 451         m_maxLevelSize = 0;
 452         for(int i = 0; i <= H.high(); i++) {
 453                 Level &l = H[i];
 454                 if (m_maxLevelSize < l.size())
 455                         m_maxLevelSize = l.size();
 456         }
 457 }
 458
 459
 460 void LayerBasedUPRLayout::computeRanking(const UpwardPlanRep &UPR, NodeArray<int> &rank)
 461 {
 462         OGDF_ASSERT(UPR.augmented());
 463
 464         GraphCopy GC = UPR.original();
 465         edge e;
 466         forall_edges(e, UPR.original()) {
 467                 if (UPR.isReversed(e)) {
 468                         GC.reverseEdge(GC.copy(e));
 469                 }
 470         }
 471
 472         // compute auxiliary edges
 473         EdgeArray<int> cost(GC,1);
 474         List< Tuple2<node, node> > auxEdges;
 475         NodeArray<int> inL(UPR, -1);
 476         int num = -1;
 477         node v;
 478         forall_nodes(v, UPR) {
 479
 480                 if (UPR.isDummy(v) || v->indeg()==0)
 481                         continue;
 482
 483                 num = num +1;
 484                 //compute all "adjacent" non dummy nodes
 485                 List<node> toDo, srcNodes;
 486                 toDo.pushBack(v);
 487                 inL[v] = num;
 488                 while (!toDo.empty()) {
 489                         node u = toDo.popFrontRet();
 490                         List<edge> inEdges;
 491                         UPR.inEdges(u, inEdges);
 492                         forall_listiterators(edge, it, inEdges) {
 493                                 node w = (*it)->source();
 494                                 if (UPR.isDummy(w)) {
 495                                         if (inL[w] != num) {
 496                                                 toDo.pushBack(w);
 497                                                 inL[w] = num;
 498                                         }
 499                                 }
 500                                 else {
 501
 502                                         OGDF_ASSERT(UPR.original(w) != 0 && UPR.original(v) != 0);
 503
 504                                         node wGC = GC.copy(UPR.original(w));
 505                                         node vGC = GC.copy(UPR.original(v));
 506                                         edge eNew = GC.newEdge(wGC, vGC);
 507                                         cost[eNew] = 0;
 508                                 }
 509                         }
 510                 }
 511         }
 512
 513         makeSimple(GC);
 514
 515         OGDF_ASSERT(isAcyclic(GC));
 516
 517
 518         // ****************************debug*******************************
 519         /*
 520         GraphAttributes GA(GC, GraphAttributes::nodeGraphics|
 521                                                 GraphAttributes::edgeGraphics|
 522                                                 GraphAttributes::nodeColor|
 523                                                 GraphAttributes::edgeColor|
 524                                                 GraphAttributes::nodeLabel|
 525                                                 GraphAttributes::edgeLabel);
 526         node vTmp;
 527         // label the nodes with their index
 528         forall_nodes(vTmp, GC) {
 529                 char str[255];
 530                 node w = GC.original(vTmp);
 531                 sprintf_s(str, 255, "%d", w->index());  // convert to string
 532                 GA.labelNode(vTmp) = str;
 533         }
 534         GA.writeGML("c:/temp/ranking_graph.gml");
 535         */
 536         //********************************************************************
 537
 538
 539         NodeArray<int> ranking(GC, 0);
 540         EdgeArray<int> length(GC,1);
 541
 542         m_ranking.get().call(GC, length, cost, ranking);
 543
 544         // adjust ranking
 545         int minRank = INT_MAX;
 546         forall_nodes(v,GC) {
 547                 if(ranking[v] < minRank)
 548                         minRank = ranking[v];
 549         }
 550
 551         if(minRank != 0) {
 552                 forall_nodes(v, GC)
 553                         ranking[v] -= minRank;
 554         }
 555
 556         forall_nodes(v, GC){
 557                 node vOrig = GC.original(v);
 558                 rank[vOrig] = ranking[v];
 559         }
 560
 561         /*
 562         //debug output ranking
 563         cout << "Ranking GOrig: " << endl;
 564         forall_nodes(v, UPR.original())
 565                 cout << "node :" << v << " ranking : "<< rank[v] << endl;
 566         */
 567 }
 568
 569
 570
 571 void LayerBasedUPRLayout::postProcessing_sourceReorder(Hierarchy &H, List<node> &sources)
 572 {
 573         //reorder the sources;
 574         forall_listiterators(node, it, sources) {
 575                 node s = *it;
 576                 Level &l = H[H.rank(s)];
 577
 578                 //compute the desire position (heuristic)
 579                 int wantedPos = 0;
 580                 adjEntry adj;
 581                 if (s->outdeg() == 1) {
 582                         node tgt =  s->firstAdj()->theEdge()->target();
 583                         List<node> nodes;
 584
 585                         forall_adj(adj, tgt) {
 586                                 if (adj->theEdge()->target() == tgt)
 587                                         nodes.pushBack(adj->theEdge()->source());
 588                         }
 589
 590                         RankComparer comp;
 591                         comp.H = &H;
 592                         nodes.quicksort(comp);
 593
 594                         //postion of the median
 595                         node v = *nodes.get(nodes.size()/2);
 596                         wantedPos = H.pos(v);
 597                 }
 598                 else {
 599                         List<node> nodes;
 600
 601                         forall_adj(adj, s)
 602                                 nodes.pushBack(adj->theEdge()->source());
 603
 604                         RankComparer comp;
 605                         comp.H = &H;
 606                         nodes.quicksort(comp);
 607
 608                         //postion of the median
 609                         node v = *nodes.get(nodes.size()/2);
 610                         wantedPos = H.pos(v);
 611                 }
 612
 613                 //move s to front of the array
 614                 int pos = H.pos(s);
 615                 while (pos != 0) {
 616                         l.swap(pos-1, pos);
 617                         pos--;
 618                 }
 619
 620                 // compute the position of s, which cause min. crossing
 621                 int minPos = pos;
 622                 int oldCr = H.calculateCrossings(l.index());;
 623                 while(pos != l.size()-1) {
 624                         l.swap(pos, pos+1);
 625                         int newCr = H.calculateCrossings(l.index());
 626                         if (newCr <= oldCr) {
 627                                 if (newCr < oldCr) {
 628                                         minPos = H.pos(s);
 629                                         oldCr = newCr;
 630                                 }
 631                                 else {
 632                                         if (abs(minPos - wantedPos) > abs(pos+1 - wantedPos)) {
 633                                                 minPos = H.pos(s);
 634                                                 oldCr = newCr;
 635                                         }
 636
 637                                 }
 638                         }
 639                         pos++;
 640                 }
 641
 642                 //move s to minPos
 643                 while (pos != minPos) {
 644                         if (minPos > pos) {
 645                                 l.swap(pos, pos+1);
 646                                 pos++;
 647                         }
 648                         if (minPos < pos) {
 649                                 l.swap(pos, pos-1);
 650                                 pos--;
 651                         }
 652                 }
 653         }
 654 }
 655
 656
 657
 658 void LayerBasedUPRLayout::postProcessing_markUp(Hierarchy &H, node s, NodeArray<bool> &markedNodes)
 659 {
 660         const GraphCopy &GC = H;
 661         NodeArray<bool> inQueue(GC, false);
 662         Queue<node> nodesToDo;
 663         nodesToDo.append(s);
 664
 665         while(!nodesToDo.empty()) {
 666                 node w = nodesToDo.pop();
 667                 markedNodes[w] = true;
 668                 List<edge> outEdges;
 669                 GC.outEdges(w, outEdges);
 670                 ListIterator <edge> it;
 671                 for (it = outEdges.begin(); it.valid(); ++it) {
 672                         edge e = *it;
 673                         if (!inQueue[e->target()] && !markedNodes[e->target()]) { // put the next node in queue if it is not already in queue
 674                                 nodesToDo.append( e->target() );
 675                                 inQueue[e->target()] = true;
 676                         }
 677                 }
 678         }
 679 }
 680
 681
 682
 683 void LayerBasedUPRLayout::postProcessing_reduceLED(Hierarchy &H, node s)
 684 {
 685         const GraphCopy &GC = H;
 686         NodeArray<bool> markedNodes(GC, false);
 687
 688         // mark all nodes dominated by s, we call the graph induced by the marked node G*
 689         // note that not necessary all nodes are marked.
 690         postProcessing_markUp(H, s, markedNodes);
 691
 692
 693         for (int i = H.rank(s) + 1; i <= H.high(); i++) {
 694                 const Level &lvl = H[i];
 695
 696                 // Compute the start and end index of the marked graph on this level.
 697                 int minIdx = INT_MAX;
 698                 int maxIdx = -1;
 699                 List<node> sList;
 700
 701                 int numEdges = 0;
 702                 int sumInDeg = 0;
 703                 int numMarkedNodes = 0;
 704                 int numDummies = 0;
 705                 for(int j = 0; j <= lvl.high(); j++) {
 706                         node u = lvl[j];
 707
 708                         if (markedNodes[u]) {
 709                                 numMarkedNodes++;
 710
 711                                 if (H.isLongEdgeDummy(u))
 712                                         numDummies++;
 713
 714                                 if (H.pos(u)< minIdx)
 715                                         minIdx = H.pos(u);
 716                                 if (H.pos(u) > maxIdx)
 717                                         maxIdx = H.pos(u);
 718
 719                                 sumInDeg += u->indeg();
 720                                 adjEntry adj;
 721                                 forall_adj(adj, u) {
 722                                         if (adj->theEdge()->target()==u && markedNodes[adj->theEdge()->source()])
 723                                                 numEdges++;
 724                                 }
 725                         }
 726                 }
 727                 if (numEdges!=sumInDeg || maxIdx-minIdx+1!=numMarkedNodes )
 728                         return;
 729
 730                 if (numDummies!=numMarkedNodes)
 731                         continue;
 732
 733                 //delete long edge dummies
 734                 for (int k = minIdx; k <= maxIdx; k++) {
 735                         node u = lvl[k];
 736
 737                         OGDF_ASSERT(H.isLongEdgeDummy(u));
 738
 739                         edge inEdge = u->firstAdj()->theEdge();
 740                         edge outEdge = u->lastAdj()->theEdge();
 741                         if (inEdge->target() != u)
 742                                 swap(inEdge, outEdge);
 743                         H.m_GC.unsplit(inEdge, outEdge);
 744                 }
 745
 746                 /*
 747                 //debug
 748                 cout << endl << endl;
 749                 cout << "vor :                                  " << endl;
 750                 for(int ii = 0; ii <= H.high(); ii++) {
 751                         Level &lvl = H[ii];
 752                         cout << endl;
 753                         cout << "level : " << lvl.index() << endl;
 754                         cout << "nodes : ";
 755                         for(int jj = 0; jj <= lvl.high(); jj++) {
 756                                 cout << lvl[jj] << "/" << H.pos(lvl[jj]) << "  ";
 757                         }
 758                         cout << endl;
 759                 }
 760                 */
 761
 762                 post_processing_reduce(H, i, s, minIdx, maxIdx, markedNodes);
 763
 764                 /*
 765                 //debug
 766                 cout << endl << endl;
 767                 cout << endl << endl;
 768                 cout << "nach :                                 " << endl;
 769                 for(int ii = 0; ii <= H.high(); ii++) {
 770                         Level &lvl = H[ii];
 771                         cout << endl;
 772                         cout << "level : " << lvl.index() << endl;
 773                         cout << "nodes : ";
 774                         for(int jj = 0; jj <= lvl.high(); jj++) {
 775                                 cout << lvl[jj] << "/" << H.pos(lvl[jj]) << "  ";
 776                         }
 777                         cout << endl;
 778                 }
 779                 */
 780
 781         }
 782 }
 783
 784
 785 void LayerBasedUPRLayout::post_processing_reduce(
 786         Hierarchy &H,
 787         int &i,
 788         node s,
 789         int minIdx,
 790         int maxIdx,
 791         NodeArray<bool> &markedNodes)
 792 {
 793         const Level &lvl = H[i];
 794
 795         if (maxIdx-minIdx+1 == lvl.size()) {
 796                 post_processing_deleteLvl(H, i);
 797                 i--;
 798                 return;
 799         }
 800
 801         // delete the dummies in interval[minIdx,maxIdx] and copy the nodes in lvl i-1 to lvl i for i={0,..,i-1}
 802         int startLvl = H.rank(s);
 803         for (int j = i; j > startLvl; j--) {
 804
 805                 int idxl1 = INT_MAX;
 806                 int idxl2 = INT_MAX;
 807                 int idxh1 = -1;
 808                 int idxh2 = -1;
 809                 for (int k = 0; k<=H[j].high(); k++) {
 810                         node u = H[j][k];
 811
 812                         if (markedNodes[u]) {
 813                                 if (k<idxl1)
 814                                         idxl1 = k;
 815                                 if (k>idxh1)
 816                                         idxh1 = k;
 817                         }
 818                 }
 819
 820                 for (int k = 0; k<=H[j-1].high(); k++) {
 821                         node u = H[j-1][k];
 822
 823                         if (markedNodes[u]) {
 824                                 if (k<idxl2)
 825                                         idxl2 = k;
 826                                 if (k>idxh2)
 827                                         idxh2 = k;
 828                         }
 829                 }
 830
 831                 int jTmp = j;
 832                 post_processing_deleteInterval(H, idxl1, idxh1, j);
 833                 if (jTmp!=j) {
 834                         i--;
 835                         return; //a level was deleted, we are done
 836                 }
 837
 838                 /*
 839                 //debug
 840                 cout << endl << endl;
 841                 cout << "nach delete :                                  " << endl;
 842                 for(int ii = 0; ii <= H.high(); ii++) {
 843                         Level &lvl = H[ii];
 844                         cout << endl;
 845                         cout << "level : " << lvl.index() << endl;
 846                         cout << "nodes : ";
 847                         for(int jj = 0; jj <= lvl.high(); jj++) {
 848                                 cout << lvl[jj] << "/" << H.pos(lvl[jj]) << "  ";
 849                         }
 850                         cout << endl;
 851                 }
 852                 */
 853
 854                 post_processing_CopyInterval(H, j, idxl2, idxh2, idxl1);
 855
 856                 /*
 857                 //debug
 858                 cout << endl << endl;
 859                 cout << "nach copy :                                    " << endl;
 860                 for(int ii = 0; ii <= H.high(); ii++) {
 861                         Level &lvl = H[ii];
 862                         cout << endl;
 863                         cout << "level : " << lvl.index() << endl;
 864                         cout << "nodes : ";
 865                         for(int jj = 0; jj <= lvl.high(); jj++) {
 866                                 cout << lvl[jj] << "/" << H.pos(lvl[jj]) << "  ";
 867                         }
 868                         cout << endl;
 869                 }
 870                 */
 871
 872         }
 873
 874         int idxl1 = INT_MAX;
 875         int idxh1 = -1;
 876         for (int k = 0; k<=H[startLvl].high(); k++) {
 877                         node u = H[startLvl][k];
 878
 879                         if (markedNodes[u]) {
 880                                 if (k<idxl1)
 881                                         idxl1 = k;
 882                                 if (k>idxh1)
 883                                         idxh1 = k;
 884                         }
 885                 }
 886         int tmp = startLvl;
 887         post_processing_deleteInterval(H, idxl1, idxh1, startLvl);
 888         if (tmp!=startLvl)
 889                 i--;
 890 }
 891
 892
 893 void LayerBasedUPRLayout::post_processing_CopyInterval(Hierarchy &H, int i, int beginIdx, int endIdx, int pos)
 894 {
 895         Level &lvl_cur = H[i];
 896         int intervalSize = endIdx - beginIdx +1;
 897         int lastIdx = lvl_cur.high();
 898
 899         OGDF_ASSERT(intervalSize > 0);
 900
 901         // grow array
 902         lvl_cur.m_nodes.grow(intervalSize);
 903         //move all the data block [pos,lvl_cur.high()] to the end of the array
 904         for (int k = 0; k < (lastIdx - pos + 1) ; k++) {
 905                 //update position
 906                 H.m_pos[lvl_cur[lastIdx - k]] = lvl_cur.high() - k;
 907                 lvl_cur[lvl_cur.high() - k] = lvl_cur[lastIdx - k];
 908         }
 909
 910         /*
 911         //debug
 912         cout << endl << endl;
 913         cout << "level after shift block to end of array : " << lvl.index() << endl;
 914         cout << "nodes : ";
 915         for(int j = 0; j <= lvl.high(); j++) {
 916                 cout << lvl[j] << " ; pos() " << pos(lvl[j]) << "  ";
 917         }
 918         cout << endl;
 919         */
 920
 921         //copy the nodes of nodeList into the array
 922         Level &lvl_low = H[i-1];
 923         int idx = pos;
 924         for (int k = beginIdx; k <= endIdx; k++) {
 925                 node u = lvl_low[k];
 926                 lvl_cur[idx] = u;
 927                 // update member data
 928                 H.m_pos[u] = idx;
 929                 H.m_rank[u] = lvl_cur.index();
 930                 idx++;
 931         }
 932 }
 933
 934
 935
 936 void LayerBasedUPRLayout::post_processing_deleteInterval(Hierarchy &H, int beginIdx, int endIdx, int &j)
 937 {
 938         Level &lvl = H[j];
 939
 940         int i = 0;
 941         while ((endIdx + i) < lvl.high()) {
 942                 lvl[beginIdx + i] = lvl[endIdx + i +1];
 943                 H.m_pos[lvl[endIdx + i +1]] = beginIdx + i;
 944                 i++;
 945         }
 946
 947         int blockSize = endIdx - beginIdx + 1;
 948
 949         if (lvl.m_nodes.size()==blockSize) {
 950                 int l = lvl.index();
 951                 post_processing_deleteLvl(H, l); //delete the lvl
 952                 j--;
 953         }
 954         else
 955                 lvl.m_nodes.grow(-blockSize); // reduce the size of the lvl
 956 }
 957
 958
 959
 960 void LayerBasedUPRLayout::post_processing_deleteLvl(Hierarchy &H, int i)
 961 {
 962         //move the pointer to end, then delete the lvl
 963         int curPos = i;
 964         while (curPos < H.high()) {
 965                 swap(H.m_pLevel[curPos], H.m_pLevel[curPos+1]);
 966                 Level &lvlTmp = H[curPos];
 967                 lvlTmp.m_index = curPos;
 968                 //update rank
 969                 for(int i = 0; i <= lvlTmp.high(); i++) {
 970                         H.m_rank[lvlTmp[i]] = curPos;
 971                 }
 972                 curPos++;
 973         }
 974         //delete
 975         delete H.m_pLevel[H.high()];
 976         H.m_pLevel.grow(-1);
 977 }
 978
 979
 980
 981
 982 void LayerBasedUPRLayout::UPRLayoutSimple(const UpwardPlanRep &UPR, GraphAttributes &GA)
 983 {
 984         //clear some data
 985         edge e;
 986         forall_edges(e, GA.constGraph()) {
 987                 GA.bends(e).clear();
 988         }
 989
 990         // -------------layout the representation-------------------
 991         GraphAttributes GA_UPR(UPR);
 992         node v;
 993         forall_nodes(v, GA.constGraph()) {
 994                 node vUPR = UPR.copy(v);
 995                 GA_UPR.height(vUPR) = GA.height(v);
 996                 GA_UPR.width(vUPR) = GA.width(v);
 997         }
 998
 999
1000         //compute the left edge
1001         adjEntry adj;
1002         forall_adj(adj, UPR.getSuperSource()) {
1003                 if (UPR.getEmbedding().rightFace(adj) == UPR.getEmbedding().externalFace())
1004                         break;
1005         }
1006         adj = adj->cyclicSucc();
1007         callSimple(GA_UPR, adj);
1008
1009         //map to AG
1010         forall_nodes(v, GA.constGraph()) {
1011                 double vX = GA_UPR.x(UPR.copy(v));
1012                 double vY = GA_UPR.y(UPR.copy(v));
1013                 GA.x(v) = vX;
1014                 GA.y(v) = vY;
1015         }
1016
1017         // add bends to original edges
1018         forall_edges(e, GA.constGraph()) {
1019                 List<edge> chain = UPR.chain(e);
1020                 forall_nonconst_listiterators(edge, it, chain) {
1021                         edge eUPR = *it;
1022                         node tgtUPR = eUPR->target();
1023
1024                         //add bend point of eUPR to original edge
1025                         ListIterator<DPoint> iter;
1026                         DPolyline &line = GA_UPR.bends(eUPR);
1027                         for(iter = line.begin(); iter.valid(); iter++) {
1028                                 double x2 = (*iter).m_x;
1029                                 double y2 = (*iter).m_y;
1030                                 DPoint p(x2, y2);
1031                                 GA.bends(e).pushBack(p);
1032                         }
1033                         //add target node of a edge segment as bend point
1034                         if (tgtUPR != chain.back()->target()) {
1035                                 double pX = GA_UPR.x(tgtUPR);
1036                                 double pY = GA_UPR.y(tgtUPR);
1037                                 DPoint p(pX, pY);
1038                                 GA.bends(e).pushBack(p);
1039                         }
1040                 }
1041
1042                 DPolyline &poly = GA.bends(e);
1043                 DPoint pSrc(GA.x(e->source()), GA.y(e->source()));
1044                 DPoint pTgt(GA.x(e->target()), GA.y(e->target()));
1045                 poly.normalize(pSrc, pTgt);
1046         }
1047
1048         //layers and max. layer size
1049 }
1050
1051
1052 void LayerBasedUPRLayout::callSimple(GraphAttributes &GA, adjEntry adj)
1053 {
1054         m_numLevels = -1;       //not implemented yet!
1055         m_maxLevelSize = -1; //not implemented yet!
1056
1057         const Graph &G = GA.constGraph();
1058
1059         OGDF_ASSERT(adj->graphOf() == &G);
1060
1061         // We make a copy stGraph of the input graph G
1062
1063         GraphCopySimple stGraph(G);
1064
1065         // determine single source s, single sink t and edge (s,t)
1066         node s, t;
1067         hasSingleSource(G, s);
1068         hasSingleSink(G, t);
1069         s = stGraph.copy(s);
1070         t = stGraph.copy(t);
1071
1072         adjEntry adjCopy = stGraph.copy(adj->theEdge())->adjSource();
1073
1074         /*cout << "stGraph:" << endl;
1075         node x;
1076         forall_nodes(x,stGraph) {
1077                 cout << x << ":";
1078                 edge e;
1079                 forall_adj_edges(e,x)
1080                         cout << " " << e;
1081                 cout << endl;
1082         }*/
1083
1084         // For the st-graph, we compute a longest path ranking. Since the graph
1085         // is st-planar, it is also level planar for the computed rank assignment.
1086         NodeArray<int> stRank(stGraph);
1087         longestPathRanking(stGraph,stRank);
1088
1089         edge e;
1090         forall_edges(e,stGraph)
1091                 OGDF_ASSERT(stRank[e->source()] < stRank[e->target()]);
1092
1093
1094         // We translate the rank assignment for stGraph to a rank assignment of G
1095         // a compute a proper hierarchy for G with this ranking. Since G is a
1096         // subgraph of stGraph, G is level planar with this ranking.
1097         NodeArray<int> rank(G);
1098
1099         node vG;
1100         forall_nodes(vG,G)
1101                 rank[vG] = stRank[stGraph.copy(vG)];
1102
1103
1104         /*cout << "rank assignment G:" << endl;
1105         forall_nodes(vG,G) {
1106                 cout << vG << ": " << rank[vG] << endl;
1107         }*/
1108
1109         Hierarchy H(G,rank);
1110
1111         // GC is the underlying graph of the proper hierarchy H.
1112         const GraphCopy &GC = H;
1113
1114
1115         // We compute the positions of the nodes of GC on each level. It is
1116         // important to determine also the positions of the dummy nodes which
1117         // resulted from splitting edges. The node array st2GC maps the nodes in
1118         // stGraph to the nodes in GC.
1119         NodeArray<node> st2GC(stGraph,0);
1120
1121         // For nodes representing real nodes in G this is simple.
1122         forall_nodes(vG,G) {
1123                 OGDF_ASSERT(H.rank(GC.copy(vG)) == stRank[stGraph.copy(vG)]);
1124                 st2GC[stGraph.copy(vG)] = GC.copy(vG);
1125         }
1126
1127         // For the dummy nodes, we first have to split edges in stGraph.
1128         // For an edge e=(v,w), we have to split e stRank[w]-stRank[v]-1 times.
1129         edge eG;
1130         forall_edges(eG,G) {
1131                 edge eSt = stGraph.copy(eG);
1132                 const List<edge> &pathGC = GC.chain(eG);
1133
1134                 ListConstIterator<edge> it;
1135                 int r = stRank[eSt->source()];
1136                 for(it = pathGC.begin().succ(); it.valid(); ++it) {
1137                         eSt = stGraph.split(eSt);
1138                         node v = eSt->source();
1139                         node vGC = (*it)->source();
1140                         stRank[v] = ++r;
1141                         st2GC[v] = vGC;
1142
1143                         OGDF_ASSERT(stRank[v] == H.rank(vGC));
1144                 }
1145         }
1146
1147         node v;
1148         forall_nodes(v,stGraph) {
1149                 node vGC = st2GC[v];
1150                 OGDF_ASSERT(vGC == 0 || stRank[v] == H.rank(vGC));
1151         }
1152
1153         /*cout << "mapping stGraph -> GC -> G:" << endl;
1154         node v;
1155         forall_nodes(v,stGraph)
1156                 cout << v << ": " << st2GC[v] << " " << stGraph.original(v) << endl;*/
1157
1158
1159         // The array nodes contains the sorted nodes of stGraph on each level.
1160         Array<SListPure<node> > nodes(stRank[s],stRank[t]);
1161
1162         dfsSortLevels(adjCopy,stRank,nodes);
1163
1164         /*for(int i = stRank[s]; i <= stRank[t]; ++i) {
1165                 cout << i << ": ";
1166                 SListPure<node> &L = nodes[i];
1167                 SListConstIterator<node> it;
1168                 for(it = L.begin(); it.valid(); ++it) {
1169                         cout << stGraph.original(*it) << " ";
1170                         node vGC = st2GC[*it];
1171                         OGDF_ASSERT(vGC == 0 || H.rank(vGC) == i);
1172                 }
1173                 cout << endl;
1174         }*/
1175
1176         // We translate the node lists to node lists of nodes in GC using node
1177         // array st2GC. Note that there are also nodes in stGraph which have
1178         // no counterpart in GC (these are face nodes of the face-sink graph
1179         // introduced by the augmentation). We can simply ignore such nodes.
1180         int i;
1181         for (i = 0; i <= H.high(); ++i) {
1182                 Level &level = H[i];
1183
1184                 //cout << i << endl;
1185                 //cout << level << endl;
1186
1187                 int j = 0;
1188                 SListConstIterator<node> itSt;
1189                 for(itSt = nodes[i].begin(); itSt.valid(); ++itSt) {
1190                         node vGC = st2GC[*itSt];
1191                         if(vGC != 0)
1192                                 level[j++] = vGC;
1193                 }
1194
1195                 //cout << level << endl;
1196                 //cout << endl;
1197
1198                 level.recalcPos(); // Recalculate some internal data structures in H
1199         }
1200
1201         H.check();
1202
1203
1204         //cout << "crossings: " << H.calculateCrossings() << endl;
1205         OGDF_ASSERT(H.calculateCrossings() == 0);
1206
1207         // Finally, we draw the computed hierarchy applying a hierarchy layout
1208         // module.
1209         m_layout.get().call(H,GA);
1210 }
1211
1212
1213 // This procedure computes the sorted nodes lists on each level of an st-graph.
1214 // adj1 corresponds to the leftmost outgoing edge of v = adj1->theNode().
1215 // Levels are build from left to right.
1216 void LayerBasedUPRLayout::dfsSortLevels(
1217         adjEntry adj1,                   // leftmost outgoing edge
1218         const NodeArray<int> &rank,      // ranking
1219         Array<SListPure<node> > &nodes)  // sorted nodes on levels
1220 {
1221         node v = adj1->theNode();
1222
1223         nodes[rank[v]].pushBack(v);
1224
1225         // iterate over all outgoing edges from left to right
1226         adjEntry adj = adj1;
1227         do {
1228                 node w = adj->theEdge()->target();
1229                 OGDF_ASSERT(v != w);
1230
1231                 // Is adjW the leftmost outgoing edge of w ?
1232                 adjEntry adjW = adj->twin()->cyclicSucc();
1233                 if(adjW->theEdge()->source() == w)
1234                         dfsSortLevels(adjW,rank,nodes);
1235
1236                 adj = adj->cyclicSucc();
1237         } while (adj != adj1 && adj->theEdge()->source() == v);
1238 }
1239
1240
1241 // for UPRLayoutSimple
1242 void LayerBasedUPRLayout::longestPathRanking(
1243         const Graph &G,
1244         NodeArray<int> &rank)
1245 {
1246         StackPure<node> sources;
1247         NodeArray<int> indeg(G);
1248
1249         node v;
1250         forall_nodes(v,G) {
1251                 indeg[v] = v->indeg();
1252                 rank[v] = 0;
1253                 if(indeg[v] == 0) {
1254                         sources.push(v);
1255                 }
1256         }
1257
1258         while(!sources.empty())
1259         {
1260                 v = sources.pop();
1261
1262                 edge e;
1263                 forall_adj_edges(e,v) {
1264                         node w = e->target();
1265                         if (w == v) continue;
1266
1267                         if(rank[w] < rank[v]+1)
1268                                 rank[w] = rank[v]+1;
1269
1270                         if(--indeg[w] == 0) {
1271                                 sources.push(w);
1272                         }
1273                 }
1274         }
1275 }
1276
1277
1278
1279 }// end namespace ogdf