ext/OGDF/src/upward/FixedEmbeddingUpwardEdgeInserter.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of FixedEmbeddingUpwardInserter class.
  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/basic/Queue.h>
  44 #include <ogdf/basic/BinaryHeap.h>
  45 #include <ogdf/basic/simple_graph_alg.h>
  46 #include <ogdf/upward/UpwardPlanRep.h>
  47 #include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>
  48
  49
  50 //debug only
  51 #include <ogdf/upward/LayerBasedUPRLayout.h>
  52
  53
  54 namespace ogdf {
  55
  56 Module::ReturnType FixedEmbeddingUpwardEdgeInserter::doCall(
  57         UpwardPlanRep &UPR,
  58         const List<edge> &origEdges,
  59         const EdgeArray<int>  *costOrig,
  60         const EdgeArray<bool> *forbiddenEdgeOrig)
  61 {
  62         if (origEdges.empty())
  63                 return Module::retFeasible;
  64
  65         List<edge> toInsert = origEdges;
  66
  67         if (!UPR.augmented())
  68                 UPR.augment();
  69
  70         EdgeArray<int> cost;
  71         if (costOrig != 0)
  72                 cost = *costOrig;
  73         else
  74                 cost.init(UPR.original(), 1);
  75
  76         if (forbiddenEdgeOrig != 0) {
  77                 edge e;
  78                 forall_edges(e, UPR.original()) {
  79                         if ((*forbiddenEdgeOrig)[e])
  80                                 cost[e] = INT_MAX;
  81                 }
  82         }
  83
  84         /*
  85         debug
  86         */
  87         //cout << endl << endl << "edge to insert " << toInsert.size() << " : " << endl;
  88         //forall_listiterators(edge, it, toInsert) {
  89         //      cout << "edge : " << *it << endl;
  90         //}
  91         //cout << endl << endl << "number of edges to insert: " << toInsert.size() << endl;
  92
  93         return insertAll(UPR, toInsert, cost);
  94 }
  95
  96
  97
  98 Module::ReturnType FixedEmbeddingUpwardEdgeInserter::insertAll(
  99         UpwardPlanRep &UPR,
 100         List<edge> &toInsert,
 101         EdgeArray<int>  &costOrig)
 102 {
 103         if (toInsert.empty())
 104                 return Module::retFeasible;
 105
 106         List<edge> l;
 107         int size_new = toInsert.size();
 108         int size_old = 0;
 109         while (size_old != size_new) {
 110                 size_old = size_new;
 111                 while (!toInsert.empty()) {
 112                         edge e_orig = toInsert.popFrontRet();
 113                         SList<adjEntry> path;
 114
 115                         /*
 116                         //debug
 117                         cout << endl;
 118                         cout << "  insertion path for e_orig :" << e_orig << ";  e_UPR: (" << UPR.copy(e_orig->source()) << ","
 119                                  << UPR.copy(e_orig->target()) << ")" << endl;
 120                         */
 121
 122                         minFIP(UPR, toInsert, costOrig, e_orig, path);
 123
 124
 125                         /*
 126                         //--------------------------------------debug
 127                         forall_slistiterators(adjEntry, it, path) {
 128                                 cout << (*it)->theEdge() << ";  node: " << (*it)->theNode() << endl;
 129                         }
 130                         //--------------------------------------end debug
 131                         */
 132
 133                         List<edge> lEdges = toInsert, lTmp = l;
 134                         lEdges.conc(lTmp);
 135                         bool ok = isConstraintFeasible(UPR, lEdges, e_orig, path);
 136                         if (ok) {
 137                                 UPR.insertEdgePathEmbedded(e_orig, path, costOrig);
 138
 139                                 OGDF_ASSERT(isUpwardPlanar(UPR));
 140                                 OGDF_ASSERT(isSimple(UPR));
 141                                 OGDF_ASSERT(isConnected(UPR));
 142                                 OGDF_ASSERT(hasSingleSource(UPR));
 143
 144                         }
 145                         else
 146                                 l.pushBack(e_orig);
 147
 148                         /*
 149                         if (false) {
 150                         //---------------------------------------------------debug
 151                         //UPR.outputFaces(UPR.getEmbedding());
 152                         //UPR.writeGML("c:/temp/bug5.gml");
 153
 154                         LayerBasedUPRLayout uprLayout;
 155                         Graph GTmp( (const Graph &) UPR);
 156                         CombinatorialEmbedding embTmp(GTmp);
 157                         node tTmp = 0;
 158                         //GTmp.writeGML("c:/temp/bug4.gml");
 159                         hasSingleSink(GTmp, tTmp);
 160                         OGDF_ASSERT(tTmp != 0);
 161                         embTmp.setExternalFace(embTmp.rightFace(tTmp->firstAdj()));
 162                         //adjEntry adjTmp = GCTmp.copy(UPR.extFaceHandle->theEdge())->adjTarget();
 163                         UpwardPlanRep upr_bug(embTmp);
 164                         adjEntry adj_bug = upr_bug.getAdjEntry(upr_bug.getEmbedding(), upr_bug.getSuperSource(), upr_bug.getEmbedding().externalFace());
 165                         node s_upr_bug = upr_bug.newNode();
 166                         upr_bug.getEmbedding().splitFace(s_upr_bug, adj_bug);
 167                         upr_bug.m_isSourceArc.init(upr_bug, false);
 168                         upr_bug.m_isSourceArc[s_upr_bug->firstAdj()->theEdge()] = true;
 169                         upr_bug.s_hat = s_upr_bug;
 170                         upr_bug.augment();
 171
 172                         GraphAttributes GA_UPR_tmp(GTmp, GraphAttributes::nodeGraphics|
 173                                         GraphAttributes::edgeGraphics|
 174                                         GraphAttributes::nodeColor|
 175                                         GraphAttributes::edgeColor|
 176                                         GraphAttributes::nodeLabel|
 177                                         GraphAttributes::edgeLabel
 178                                         );
 179                         GA_UPR_tmp.setAllHeight(30.0);
 180                         GA_UPR_tmp.setAllWidth(30.0);
 181
 182                         uprLayout.call(upr_bug, GA_UPR_tmp);
 183
 184                         // label the nodes with their index
 185                         node z;
 186                         forall_nodes(z, GA_UPR_tmp.constGraph()) {
 187                                 char str[255];
 188                                 sprintf_s(str, 255, "%d", z->index());  // convert to string
 189                                 GA_UPR_tmp.labelNode(z) = str;
 190                                 GA_UPR_tmp.y(z)=-GA_UPR_tmp.y(z);
 191                                 GA_UPR_tmp.x(z)=-GA_UPR_tmp.x(z);
 192                         }
 193                         edge eee;
 194                         forall_edges(eee, GA_UPR_tmp.constGraph()) {
 195                                 DPolyline &line = GA_UPR_tmp.bends(eee);
 196                                 ListIterator<DPoint> it;
 197                                 for(it = line.begin(); it.valid(); it++) {
 198                                         (*it).m_y = -(*it).m_y;
 199                                         (*it).m_x = -(*it).m_x;
 200                                 }
 201                         }
 202                         GA_UPR_tmp.writeGML("c:/temp/UPR_int.gml");
 203                         //cout << "face of UPR_int :" << endl;
 204                         //upr_bug.outputFaces(upr_bug.getEmbedding());
 205                         //end -----------------------------------------------debug
 206                         }
 207                         */
 208
 209                 }
 210                 size_new = l.size();
 211                 toInsert = l;
 212                 l.clear();
 213         }
 214
 215         /*
 216          * some edges cannot be inserted, so use heuristic insertion methods
 217          */
 218         if (!toInsert.empty()) {
 219
 220                 //cout << endl << "\a\a\a\a\aheuristical call!! " << endl;
 221
 222                 edge e_orig = toInsert.popFrontRet();
 223
 224                 /*
 225                 cout << endl;
 226                 cout << "heuristical insertion path for e_orig :" << e_orig << ";  e_UPR: (" << UPR.copy(e_orig->source()) << ","
 227                         << UPR.copy(e_orig->target()) << ")" <<  endl;
 228                 */
 229
 230
 231                         /*
 232                         if (false) {
 233                         //---------------------------------------------------debug
 234                         //UPR.outputFaces(UPR.getEmbedding());
 235                         //UPR.writeGML("c:/temp/bug5.gml");
 236
 237                         LayerBasedUPRLayout uprLayout;
 238                         Graph GTmp( (const Graph &) UPR);
 239                         CombinatorialEmbedding embTmp(GTmp);
 240                         node tTmp = 0;
 241                         //GTmp.writeGML("c:/temp/bug4.gml");
 242                         hasSingleSink(GTmp, tTmp);
 243                         OGDF_ASSERT(tTmp != 0);
 244                         embTmp.setExternalFace(embTmp.rightFace(tTmp->firstAdj()));
 245                         //adjEntry adjTmp = GCTmp.copy(UPR.extFaceHandle->theEdge())->adjTarget();
 246                         UpwardPlanRep upr_bug(embTmp);
 247                         adjEntry adj_bug = upr_bug.getAdjEntry(upr_bug.getEmbedding(), upr_bug.getSuperSource(), upr_bug.getEmbedding().externalFace());
 248                         node s_upr_bug = upr_bug.newNode();
 249                         upr_bug.getEmbedding().splitFace(s_upr_bug, adj_bug);
 250                         upr_bug.m_isSourceArc.init(upr_bug, false);
 251                         upr_bug.m_isSourceArc[s_upr_bug->firstAdj()->theEdge()] = true;
 252                         upr_bug.s_hat = s_upr_bug;
 253                         upr_bug.augment();
 254
 255                         GraphAttributes GA_UPR_tmp(GTmp, GraphAttributes::nodeGraphics|
 256                                         GraphAttributes::edgeGraphics|
 257                                         GraphAttributes::nodeColor|
 258                                         GraphAttributes::edgeColor|
 259                                         GraphAttributes::nodeLabel|
 260                                         GraphAttributes::edgeLabel
 261                                         );
 262                         GA_UPR_tmp.setAllHeight(30.0);
 263                         GA_UPR_tmp.setAllWidth(30.0);
 264
 265                         uprLayout.call(upr_bug, GA_UPR_tmp);
 266
 267                         // label the nodes with their index
 268                         node z;
 269                         forall_nodes(z, GA_UPR_tmp.constGraph()) {
 270                                 char str[255];
 271                                 sprintf_s(str, 255, "%d", z->index());  // convert to string
 272                                 GA_UPR_tmp.labelNode(z) = str;
 273                                 GA_UPR_tmp.y(z)=-GA_UPR_tmp.y(z);
 274                                 GA_UPR_tmp.x(z)=-GA_UPR_tmp.x(z);
 275                         }
 276                         edge eee;
 277                         forall_edges(eee, GA_UPR_tmp.constGraph()) {
 278                                 DPolyline &line = GA_UPR_tmp.bends(eee);
 279                                 ListIterator<DPoint> it;
 280                                 for(it = line.begin(); it.valid(); it++) {
 281                                         (*it).m_y = -(*it).m_y;
 282                                         (*it).m_x = -(*it).m_x;
 283                                 }
 284                         }
 285                         GA_UPR_tmp.writeGML("c:/temp/UPR_int.gml");
 286                         //cout << "face of UPR_int :" << endl;
 287                         //upr_bug.outputFaces(upr_bug.getEmbedding());
 288                         //end -----------------------------------------------debug
 289                         }
 290                         */
 291
 292                 SList<adjEntry> path;
 293                 constraintFIP(UPR, toInsert, costOrig, e_orig, path);
 294
 295                 /*
 296                 //--------------------------------------debug
 297
 298                 forall_slistiterators(adjEntry, it, path) {
 299                         cout << (*it)->theEdge() << ";  node: " << (*it)->theNode() << endl;;
 300                 }
 301                 //--------------------------------------end debug
 302                 */
 303
 304                 UPR.insertEdgePathEmbedded(e_orig, path, costOrig);
 305
 306                 OGDF_ASSERT(isUpwardPlanar(UPR));
 307
 308                 return insertAll(UPR, toInsert, costOrig);
 309         }
 310         return Module::retFeasible;
 311 }
 312
 313
 314
 315 void FixedEmbeddingUpwardEdgeInserter::staticLock(
 316         UpwardPlanRep &UPR,
 317         EdgeArray<bool> &locked,
 318         const List<edge> &origEdges,
 319         edge e_orig)
 320 {
 321         // construct merge graph M
 322         GraphCopy M((const Graph &) UPR);
 323
 324         // add deleted edges to M
 325         forall_listiterators(edge, it, origEdges) {
 326                 edge e = *it;
 327                 node u = M.copy(UPR.copy(e->source()));
 328                 node v = M.copy(UPR.copy(e->target()));
 329                 M.newEdge(u,v);
 330         }
 331
 332         EdgeArray<bool> markedEdges(M, false);
 333         markUp(M, M.copy(UPR.copy(e_orig->target())), markedEdges);
 334         markDown(M, M.copy(UPR.copy(e_orig->source())), markedEdges);
 335
 336         edge e;
 337         forall_edges(e, M) {
 338                 if (markedEdges[e] && M.original(e) != 0) {
 339                         locked[M.original(e)] = true;
 340                 }
 341         }
 342 }
 343
 344
 345
 346 void FixedEmbeddingUpwardEdgeInserter::getPath(
 347         UpwardPlanRep &UPR,
 348         List<edge> &origEdges,
 349         EdgeArray<int> &cost,
 350         edge e_orig,
 351         SList<adjEntry> &path,
 352         bool heuristic)
 353 {
 354         path.clear();
 355         node x_1 = UPR.copy(e_orig->source());
 356         node y_1 = UPR.copy(e_orig->target());
 357         const CombinatorialEmbedding &Gamma = UPR.getEmbedding();
 358
 359         EdgeArray<bool> locked(UPR, false);
 360         staticLock(UPR, locked, origEdges, e_orig);
 361
 362         //locked the adjacent edges of x_1 and y_1
 363         adjEntry adjTmp;
 364         forall_adj(adjTmp, x_1)
 365                 locked[adjTmp->theEdge()] = true;
 366         forall_adj(adjTmp, y_1)
 367                 locked[adjTmp->theEdge()] = true;
 368
 369         EdgeArray<adjEntry> predAdj(UPR, 0); // for path reconstruction
 370         EdgeArray<int> dist(UPR, INT_MAX); // current distance to an edge
 371         EdgeArray<adjEntry> toAdjEntry(UPR, 0);
 372
 373
 374         /*
 375         * compute the adjEntry of the adjacent edges of x_1
 376         * this is necessary for the initiliazation of priorQ
 377         */
 378         List<edge> outEdges;
 379         List<adjEntry> adjOut;
 380         UPR.outEdges(x_1, outEdges);
 381         forall_listiterators(edge, it, outEdges) {
 382                 adjEntry adj = (*it)->adjSource();
 383                 adjOut.pushBack(adj);
 384                 if (adj->cyclicPred()->theEdge()->target() == x_1)
 385                         adjOut.pushBack(adj->cyclicPred()); // right face of the left in edge of x_1
 386         }
 387
 388         List<adjEntry> initEdges;
 389         forall_listiterators(adjEntry, it, adjOut) {
 390                 feasibleEdges(UPR, Gamma.rightFace(*it), *it, locked, initEdges, heuristic);
 391                 forall_listiterators(adjEntry, iu, initEdges) {
 392                         edge ee = (*iu)->theEdge();
 393                         if (!locked[ee]) {
 394                                 if (UPR.isSinkArc(ee) || UPR.isSourceArc(ee))
 395                                         dist[ee] = 0;
 396                                 else
 397                                         dist[ee] = 1;
 398                                 predAdj[ee] = *it;
 399                                 // mappe ee to the "correct" adjEntry
 400                                 toAdjEntry[ee] = *iu;
 401                         }
 402
 403                         //check if ee contains the target source y_1
 404                         if ((*iu)->twin()->theNode() == y_1) {
 405                                 adjEntry adjTgt = UPR.getAdjEntry(UPR.getEmbedding(), y_1, UPR.getEmbedding().rightFace(*it));
 406
 407                                 //for the case if there are two adjEntry of y_1 which right face is the external face
 408                                 if (Gamma.rightFace(*it) == Gamma.externalFace()) {
 409                                         //we have to compute the correct adjEntry
 410                                         adjEntry tgtLeft = 0, tgtRight = 0, runAdj;
 411                                         forall_adj(runAdj, y_1) {
 412                                                 if (Gamma.rightFace(runAdj) == Gamma.externalFace()) {
 413                                                         if (runAdj->theEdge()->target() == y_1)
 414                                                                 tgtLeft = runAdj;
 415                                                         else
 416                                                                 tgtRight = runAdj;
 417                                                 }
 418                                         }
 419                                         if ((*it)->theNode() == (*it)->theEdge()->source())
 420                                                 adjTgt = tgtRight; // *it->theEdge() is on the right face side
 421                                         else
 422                                                 adjTgt = tgtLeft; // *it->theEdge() is on the left face side
 423                                 }
 424
 425                                 if (Gamma.rightFace(*it) != Gamma.rightFace(adjTgt))
 426                                         adjTgt = adjTgt->cyclicPred();
 427                                 path.pushFront((*it));
 428                                 path.pushBack(adjTgt);
 429
 430                                 OGDF_ASSERT(Gamma.rightFace(*it) == Gamma.rightFace(adjTgt));
 431
 432                                 break;
 433                         }
 434                 }
 435                 if (path.size() == 2) // edge can be inserted without crossing
 436                         break; //leave forall_listiterators(adjEntry, it, adjOut) loop
 437
 438                 initEdges.clear();
 439         }
 440
 441         // if path.size == 2 then we can insert e_orig without crossing (the path is not necessary constrain feasible)
 442         if (path.size() != 2) {
 443                 // init the priority queque
 444                 BinaryHeap<edge, int> priorQ(UPR.numberOfEdges());
 445                 EdgeArray< const BinaryHeap<edge, int>::Element * > elemArray(UPR, 0); // reference to the elements of priorQ
 446                 edge e;
 447                 forall_edges(e, UPR) {
 448                         if (!locked[e]) {
 449                                 int priority = dist[e];
 450                                 elemArray[e] = &(priorQ.insert(e, priority));
 451                         }
 452                 }
 453                 adjEntry adjLast = 0;
 454                 while (!priorQ.empty()) {
 455
 456                         adjEntry adj_cur = toAdjEntry[priorQ.pop()];
 457
 458                         OGDF_ASSERT(adj_cur != 0);
 459
 460                         face f = Gamma.rightFace(adj_cur);      //current face f
 461                         List<adjEntry> nextAdjs;
 462                         feasibleEdges(UPR, f, adj_cur, locked, nextAdjs, heuristic);
 463
 464                         bool reached = false;
 465                         forall_listiterators(adjEntry, it, nextAdjs) {
 466                                 adjEntry adjNext = *it;
 467
 468                                 if (adjNext->theNode() == y_1) {        // y_1 reached ?
 469
 470                                         adjLast = UPR.getAdjEntry(UPR.getEmbedding(), y_1, f);
 471                                         reached = true;
 472
 473                                         if (Gamma.rightFace(adj_cur) == Gamma.externalFace()) {
 474                                                 //we have to compute the correct adjEntry
 475                                                 adjEntry tgtLeft = 0, tgtRight = 0, runAdj;
 476                                                 forall_adj(runAdj, y_1) {
 477                                                         if (Gamma.rightFace(runAdj) == Gamma.externalFace()) {
 478                                                                 if (runAdj->theEdge()->target() == y_1)
 479                                                                         tgtLeft = runAdj;
 480                                                                 else
 481                                                                         tgtRight = runAdj;
 482                                                         }
 483                                                 }
 484                                                 if (adj_cur->theNode() == adj_cur->theEdge()->source())
 485                                                         adjLast = tgtRight; // adj_cur->theEdge() is on the right face side
 486                                                 else
 487                                                         adjLast = tgtLeft; // adj_cur->theEdge() is on the left face side
 488                                         }
 489
 490                                         OGDF_ASSERT(adjLast != 0)
 491
 492                                         predAdj[adjLast->theEdge()] = adj_cur;
 493                                         break; // leave forall-loop
 494                                 }
 495
 496                                 bool ok = !locked[adjNext->theEdge()];
 497
 498                                 //use heuristic to check curent path
 499                                 if (ok && heuristic)
 500                                         ok = isConstraintFeasible(UPR, origEdges, e_orig, adj_cur, adjNext, predAdj);
 501
 502                                 //relax if ok
 503                                 if (ok) {
 504                                         int c = 0;
 505                                         if (UPR.original(adjNext->theEdge()) != 0)
 506                                                 c = cost[UPR.original(adjNext->theEdge())];
 507
 508                                         int new_dist = dist[adj_cur->theEdge()] + c;
 509                                         if (dist[adjNext->theEdge()] > new_dist) {
 510                                                 const BinaryHeap<edge, int>::Element &el = *(elemArray[adjNext->theEdge()]);
 511                                                 priorQ.decPriority(el, new_dist);
 512                                                 predAdj[adjNext->theEdge()] = adj_cur;
 513                                                 dist[adjNext->theEdge()] = new_dist;
 514                                                 toAdjEntry[adjNext->theEdge()] = adjNext;
 515                                         }
 516                                 }
 517                         } //forall
 518
 519                         if (reached)
 520                                 break; // leave while-loop if y_1 is found
 521
 522                 }//while
 523
 524                 //construct the path
 525                 path.pushBack(adjLast);
 526                 adjEntry run = predAdj[adjLast];
 527                 while (run != 0) {
 528                         path.pushFront(run);
 529                         run = predAdj[run];
 530                 }
 531         }
 532
 533         OGDF_ASSERT(path.size() >= 2);
 534 }
 535
 536
 537
 538 bool FixedEmbeddingUpwardEdgeInserter::isConstraintFeasible(
 539         UpwardPlanRep &UPR,
 540         const List<edge> &orig_edges,
 541         edge e_orig,
 542         adjEntry adjCurrent,
 543         adjEntry adjNext,
 544         EdgeArray<adjEntry> &predAdj)
 545 {
 546         //contruct path to adj->theEdge()
 547         SList<adjEntry> path;
 548         path.pushBack(adjNext);
 549         path.pushFront(adjCurrent);
 550         adjEntry run = predAdj[adjCurrent];
 551         while (run != 0) {
 552                 path.pushFront(run);
 553                 run = predAdj[run->theEdge()];
 554         }
 555
 556         /*
 557         //debug
 558         cout << endl << endl << "current insertion path: " << endl;
 559         forall_slistiterators(adjEntry, it, path) {
 560                 cout << (*it)->theEdge() << ";  node: " << (*it)->theNode() << endl;
 561         }
 562         */
 563
 564         GraphCopy M( (const Graph &) UPR); // merge graph
 565
 566         //convert adjEntry of path to adjEntry of M
 567         SList<adjEntry> path_M;
 568         forall_slistiterators(adjEntry, it, path) {
 569                 adjEntry a = *it;
 570                 edge e_M = M.copy(a->theEdge());
 571                 node v = M.copy(a->theNode());
 572                 if (e_M->source() == v)
 573                         path_M.pushBack(e_M->adjSource());
 574                 else
 575                         path_M.pushBack(e_M->adjTarget());
 576         }
 577
 578         // construct a partial path from src to adjNext
 579         path_M.popFrontRet();
 580         node src = M.copy(UPR.copy(e_orig->source()));
 581         node tgt = M.copy(UPR.copy(e_orig->target()));
 582         while (!path_M.empty()) {
 583                 edge eM = path_M.popFrontRet()->theEdge();
 584                 node d = M.split(eM)->source();
 585                 M.newEdge(src, d);
 586                 src = d;
 587         }
 588
 589         M.newEdge(src, tgt);
 590         //add the deleted edges
 591         forall_listiterators(edge, it, orig_edges) {
 592                 node a = M.copy(UPR.copy((*it)->source()));
 593                 node b = M.copy(UPR.copy((*it)->target()));
 594                 M.newEdge(a, b);
 595         }
 596
 597         return isAcyclic(M);
 598 }
 599
 600
 601 bool FixedEmbeddingUpwardEdgeInserter::isConstraintFeasible(
 602         UpwardPlanRep &UPR,
 603         List<edge> &origEdges,
 604         edge e_orig,
 605         SList<adjEntry> &path)
 606 {
 607         GraphCopy GC( (const Graph &) UPR);
 608         GraphCopy M((const Graph &)GC); // merge graph
 609
 610         //convert adjEntry of path to adjEntry of M
 611         SList<adjEntry> path_M;
 612         forall_slistiterators(adjEntry, it, path) {
 613                 adjEntry a = *it;
 614                 edge e_M = M.copy( GC.copy(a->theEdge()) );
 615                 node v = M.copy(GC.copy(a->theNode()));
 616                 if (e_M->source() == v)
 617                         path_M.pushBack(e_M->adjSource());
 618                 else
 619                         path_M.pushBack(e_M->adjTarget());
 620         }
 621
 622         //debug
 623         /*
 624         cout << " insertion path for " << e_orig << endl;
 625         forall_slistiterators(adjEntry, it, path_M) {
 626                 cout << (*it)->theEdge() << ";  node: " << (*it)->theNode() << endl;
 627         }
 628         */
 629
 630         edge e = GC.newEdge(GC.copy(UPR.copy(e_orig->source())), GC.copy(UPR.copy(e_orig->target())));
 631
 632         CombinatorialEmbedding Gamma(M);
 633         M.insertEdgePathEmbedded(e, Gamma, path_M);
 634
 635         OGDF_ASSERT(isAcyclic(M));
 636
 637         //add the deleted edges
 638         forall_listiterators(edge, it, origEdges) {
 639                 node a = M.copy(GC.copy(UPR.copy((*it)->source())));
 640                 node b = M.copy(GC.copy(UPR.copy((*it)->target())));
 641                 M.newEdge(a, b);
 642         }
 643
 644         return isAcyclic(M);
 645 }
 646
 647
 648 void FixedEmbeddingUpwardEdgeInserter::feasibleEdges(
 649         UpwardPlanRep &UPR,
 650         face f,
 651         adjEntry adj,
 652         EdgeArray<bool> &locked,
 653         List<adjEntry> &feasible,
 654         bool heuristic)
 655 {
 656         const CombinatorialEmbedding &Gamma = UPR.getEmbedding();
 657
 658         OGDF_ASSERT(Gamma.rightFace(adj) == f);
 659
 660         adjEntry start = adj, run = adj;
 661         if (f == Gamma.externalFace()) {
 662                 bool stop = false;
 663
 664                 if (adj->theNode() == adj->theEdge()->source()) {
 665                         /*
 666                          *adj->theEdge() is on the right path of f, so walk ccw
 667                          *all edges between adj->theEdge() and the super sink t_hat on the right path are feasible.
 668                          */
 669                         do {
 670                                 if (run->theEdge()->target() == UPR.getSuperSink())
 671                                         stop = true;
 672                                 if (run != start)
 673                                         feasible.pushBack(run->twin());
 674                                 run = run->faceCycleSucc();
 675                         } while (!stop);
 676
 677                         //dynamic lock; all edges between super source and adj->theEdge() of the corredponding right path muss be locked
 678                         if (!heuristic) {
 679                                 run = start;
 680                                 stop = false;
 681                                 do {
 682                                         if (run->theEdge()->source() == UPR.getSuperSource())
 683                                                 stop = true;
 684                                         locked[run->theEdge()] = true;
 685                                         run = run->faceCyclePred();
 686                                 } while (!stop);
 687                         }
 688                 }
 689
 690                 else {
 691                         /*
 692                         *currentEdge is on the left path of f, so walk cw
 693                         *All edges between adj->theEdge() and the super sink t_hat on the left path are feasible.
 694                         */
 695                         do {
 696                                 if (run->theEdge()->target()== UPR.getSuperSink())
 697                                         stop = true;
 698                                 if (run != start)
 699                                         feasible.pushBack(run->twin());
 700                                 run = run->faceCyclePred();
 701                         } while (!stop);
 702
 703                         //dynamic lock; all edges between super source and adj->theEdge() of the corredponding left path muss be locked
 704                         if (!heuristic) {
 705                                 run = start;
 706                                 stop = false;
 707                                 do {
 708                                         if (run->theEdge()->source() == UPR.getSuperSource())
 709                                                 stop = true;
 710                                         locked[run->theEdge()] = true;
 711                                         run = run->faceCycleSucc();
 712                                 } while (!stop);
 713                         }
 714                 }
 715         }
 716
 717         // internal face
 718         else {
 719                 bool stop = false;
 720
 721                 if (adj->theNode() == adj->theEdge()->source()) {
 722                 /*
 723                  *adj->theEdge() is on the left path of f; walk cw to the source-witch of f.
 724                  *All edges traversing by this walk are feasible.
 725                  */
 726                         do {
 727                                 if (run->theEdge()->source() == run->faceCycleSucc()->theEdge()->source()) //reach source-switch of f
 728                                         stop = true;
 729                                 if (run != start)
 730                                         feasible.pushBack(run->twin());
 731                                 run = run->faceCycleSucc();
 732                         } while (!stop);
 733
 734                         //dynamic lock; all edges between source-switch and adj->theEdge() of the corredponding left path muss be locked
 735                         if (!heuristic) {
 736                                 run = start;
 737                                 stop = false;
 738                                 do {
 739                                         locked[run->theEdge()] = true;
 740                                         if (run->theEdge()->source() == run->faceCyclePred()->theEdge()->source()) //reach source-switch of f
 741                                                 stop = true;
 742                                         run = run->faceCyclePred();
 743                                 } while (!stop);
 744                         }
 745                 }
 746
 747                 else {
 748                         /*
 749                         *adj->theEdge() is on the right path of f; walk ccw to the source-witch of f.
 750                         *All edges traversing by this walk are feasible.
 751                         */
 752                         do {
 753                                 if (run->theEdge()->source() == run->faceCyclePred()->theEdge()->source()) //reach source-switch of f
 754                                         stop = true;
 755                                 if (run != start)
 756                                         feasible.pushBack(run->twin());
 757                                 run = run->faceCyclePred();
 758                         } while (!stop);
 759
 760                         //dynamic lock; all edges between source-switch and adj->theEdge() of the corredponding right path muss be locked
 761                         if (!heuristic) {
 762                                 run = start;
 763                                 stop = false;
 764                                 do {
 765                                         locked[run->theEdge()] = true;
 766                                         if (run->theEdge()->source() == run->faceCycleSucc()->theEdge()->source()) //reach source-switch of f
 767                                                 stop = true;
 768                                         run = run->faceCycleSucc();
 769                                 } while (!stop);
 770                         }
 771                 }
 772         }
 773 }
 774
 775
 776 void FixedEmbeddingUpwardEdgeInserter::markUp(
 777         const Graph &G,
 778         node v,
 779         //NodeArray<bool> &markedNodes,
 780         EdgeArray<bool> &markedEdges )
 781 {
 782         // traversing G from v
 783         Queue<node> nodesToDo;
 784         nodesToDo.append(v);
 785         NodeArray<bool> inQueue(G, false);
 786         while(!nodesToDo.empty()) {
 787                 node w = nodesToDo.pop();
 788                 List<edge> outEdges;
 789                 G.outEdges(w, outEdges);
 790                 ListIterator <edge> it;
 791                 for (it = outEdges.begin(); it.valid(); ++it) {
 792                         edge e = *it;
 793                         if (!inQueue[e->target()]) { // put the next node in queue if it is not already in queue
 794                                 nodesToDo.append( e->target() );
 795                                 inQueue[e->target()] = true;
 796                         }
 797                         markedEdges[e] = true;  // mark edge
 798                 }
 799         }
 800 }
 801
 802
 803 void FixedEmbeddingUpwardEdgeInserter::markDown(
 804         const Graph &G,
 805         node v,
 806         //NodeArray<bool> &markedNodes,
 807         EdgeArray<bool> &markedEdges)
 808 {
 809         // mark the subgraph, i.e all nodes and edges, which dominate node v
 810         Queue<node> nodesToDo;
 811         nodesToDo.append(v);
 812         NodeArray<bool> inQueue(G, false);
 813         while(!nodesToDo.empty()) {
 814                 node w = nodesToDo.pop();
 815                 List<edge> inEdges;
 816                 G.inEdges(w, inEdges);
 817                 ListIterator <edge> it;
 818                 for (it = inEdges.begin(); it.valid(); ++it) {
 819                         edge e = *it;
 820                         if (!inQueue[e->source()]) {
 821                                 nodesToDo.append(e->source() ); // put the next node in queue if it is not already in queue
 822                                 inQueue[e->source()] = true;
 823                         }
 824                         markedEdges[e] = true;  // mark the edge
 825                 }
 826         }
 827 }
 828
 829
 830
 831 } // namespace
 832