ext/OGDF/src/planarity/VariableEmbeddingInserter2.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 Implementation of class VariableEmbeddingInserter2
  11  *
  12  * \author Carsten Gutwenger<br>Jan Papenfu&szlig;
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #include <ogdf/planarity/VariableEmbeddingInserter2.h>
  45 #include <ogdf/decomposition/DynamicSPQRForest.h>
  46 #include <ogdf/basic/extended_graph_alg.h>
  47
  48
  49 namespace ogdf {
  50
  51 //---------------------------------------------------------
  52 //                     BCandSPQRtrees
  53 //---------------------------------------------------------
  54
  55 class BCandSPQRtrees {
  56
  57 private:
  58
  59         PlanRep*                   m_pPG;
  60         DynamicSPQRForest          m_dynamicSPQRForest;
  61
  62         bool                       m_forbidCrossingGens;
  63         const EdgeArray<int>*      m_costOrig;
  64         EdgeArray<int>             m_cost;
  65         EdgeArray<Graph::EdgeType> m_typeOf;
  66
  67 public:
  68
  69         BCandSPQRtrees (PlanRep* pPG, bool forbidCrossingGens, const EdgeArray<int>* costOrig);
  70         DynamicSPQRForest& dynamicSPQRForest () { return m_dynamicSPQRForest; }
  71         void insertEdgePath (edge eOrig, const SList<adjEntry>& crossedEdges);
  72
  73         void cost (edge e, int c) { m_cost[e] = c; }
  74         int cost (edge e) const { return m_cost[e]; }
  75         void typeOf (edge e, Graph::EdgeType et) { m_typeOf[e] = et; }
  76         Graph::EdgeType typeOf (edge e) const { return m_typeOf[e]; }
  77
  78 };
  79
  80 BCandSPQRtrees::BCandSPQRtrees (PlanRep* pPG, bool forbidCrossingGens, const EdgeArray<int>* costOrig) : m_pPG(pPG), m_dynamicSPQRForest(*pPG), m_forbidCrossingGens(forbidCrossingGens), m_costOrig(costOrig)
  81 {
  82         const Graph& H = m_dynamicSPQRForest.auxiliaryGraph();
  83         m_cost.init(H);
  84         m_typeOf.init(H);
  85         edge f;
  86         forall_edges (f,H) {
  87                 edge e = m_dynamicSPQRForest.original(f);
  88                 m_typeOf[f] = m_forbidCrossingGens ? m_pPG->typeOf(e) : Graph::association;
  89                 if (m_costOrig) {
  90                         edge eOrig = m_pPG->original(e);
  91                         m_cost[f] = eOrig ? (*m_costOrig)[eOrig] : 0;
  92                 }
  93                 else m_cost[f] = 1;
  94         }
  95 }
  96
  97 void BCandSPQRtrees::insertEdgePath (edge eOrig, const SList<adjEntry>& crossedEdges)
  98 {
  99         SList<edge> ti;
 100         SList<node> tj;
 101         SListConstIterator<adjEntry> kt;
 102         for (kt=crossedEdges.begin(); kt.valid(); ++kt) {
 103                 ti.pushBack((*kt)->theEdge());
 104                 tj.pushBack((*kt)->theEdge()->target());
 105         }
 106
 107         m_pPG->insertEdgePath(eOrig,crossedEdges);
 108
 109         Graph::EdgeType typeOfEOrig = m_forbidCrossingGens ? m_pPG->typeOrig(eOrig) : Graph::association;
 110         int costOfEOrig = m_costOrig ? eOrig ? (*m_costOrig)[eOrig] : 0 : 1;
 111
 112         node v = m_pPG->copy(eOrig->source());
 113         SListConstIterator<edge> it = ti.begin();
 114         SListConstIterator<node> jt = tj.begin();
 115         for (kt=crossedEdges.begin(); it.valid(); ++it, ++jt, ++kt) {
 116                 edge e = *it;
 117                 node u = e->target();
 118                 adjEntry a;
 119                 for (a=u->firstAdj(); a->theEdge()->target()!=*jt; a=a->succ());
 120                 edge f = a->theEdge();
 121                 m_dynamicSPQRForest.updateInsertedNode(e,f);
 122                 e = m_dynamicSPQRForest.rep(e);
 123                 f = m_dynamicSPQRForest.rep(f);
 124                 m_typeOf[f] = m_typeOf[e];
 125                 m_cost[f] = m_cost[e];
 126                 for (a=u->firstAdj(); a->theEdge()->source()!=v; a=a->succ());
 127                 f = a->theEdge();
 128                 m_dynamicSPQRForest.updateInsertedEdge(f);
 129                 f = m_dynamicSPQRForest.rep(f);
 130                 m_typeOf[f] = typeOfEOrig;
 131                 m_cost[f] = costOfEOrig;
 132                 v = u;
 133         }
 134         node u = m_pPG->copy(eOrig->target());
 135         adjEntry a;
 136         for (a=v->firstAdj(); a->theEdge()->target()!=u; a=a->succ());
 137         edge f = a->theEdge();
 138         m_dynamicSPQRForest.updateInsertedEdge(f);
 139         f = m_dynamicSPQRForest.rep(f);
 140         m_typeOf[f] = typeOfEOrig;
 141         m_cost[f] = costOfEOrig;
 142 }
 143
 144
 145
 146 //-------------------------------------------------------------------
 147 // ExpandedGraph2 represents the (partially) expanded graph with
 148 // its augmented dual
 149 //-------------------------------------------------------------------
 150
 151 class ExpandedGraph2
 152 {
 153         BCandSPQRtrees &m_BC;
 154
 155         NodeArray<node> m_GtoExp;
 156         List<node>      m_nodesG;
 157         Graph           m_exp;   // expanded graph
 158         ConstCombinatorialEmbedding m_E;
 159         AdjEntryArray<adjEntry> m_expToG;
 160         edge            m_eS, m_eT; // (virtual) edges in exp representing s and t (if any)
 161
 162         Graph           m_dual;  // augmented dual graph of exp
 163         EdgeArray<adjEntry> m_primalEdge;
 164         EdgeArray<bool>     m_primalIsGen; // true iff corresponding primal edge is a generalization
 165
 166         node            m_vS, m_vT; // augmented nodes in dual representing s and t
 167
 168 public:
 169         ExpandedGraph2(BCandSPQRtrees &BC);
 170
 171         void expand(node v, node vPred, node vSucc);
 172
 173         void constructDual(node s, node t, GraphCopy &GC, const EdgeArray<bool> *forbiddenEdgeOrig);
 174         void constructDualForbidCrossingGens(node s, node t);
 175
 176         void findShortestPath(Graph::EdgeType eType, List<adjEntry> &L);
 177         void findWeightedShortestPath(Graph::EdgeType eType,
 178                 List<adjEntry> &L);
 179
 180         int costDual(edge eDual) const {
 181                 adjEntry adjExp = m_primalEdge[eDual];
 182                 return (adjExp == 0) ? 0 : m_BC.cost(m_expToG[adjExp]->theEdge());
 183         }
 184
 185         // avoid automatic creation of assignment operator
 186         ExpandedGraph2 &operator=(const ExpandedGraph2 &);
 187
 188 private:
 189         edge insertEdge(node vG, node wG, edge eG);
 190         void expandSkeleton(node v, edge e1, edge e2);
 191 };
 192
 193
 194 ExpandedGraph2::ExpandedGraph2(BCandSPQRtrees &BC) : m_BC(BC),
 195         m_GtoExp(BC.dynamicSPQRForest().auxiliaryGraph(),0), m_expToG(m_exp,0),
 196         m_primalEdge(m_dual,0), m_primalIsGen(m_dual,false)
 197 {
 198 }
 199
 200
 201 //-------------------------------------------------------------------
 202 // build expanded graph (by expanding skeleton(v), nodes vPred and
 203 // vSucc are the predecessor and successor tree nodes of v on the
 204 // path from v1 to v2
 205 //-------------------------------------------------------------------
 206
 207 void ExpandedGraph2::expand(node v, node vPred, node vSucc)
 208 {
 209         m_exp.clear();
 210         while (!m_nodesG.empty())
 211                 m_GtoExp[m_nodesG.popBackRet()] = 0;
 212
 213         edge eInS = 0;
 214         if (vPred != 0) {
 215                 eInS = m_BC.dynamicSPQRForest().virtualEdge(vPred,v);
 216                 m_eS = insertEdge(eInS->source(),eInS->target(),0);
 217         }
 218         edge eOutS = 0;
 219         if (vSucc != 0) {
 220                 eOutS = m_BC.dynamicSPQRForest().virtualEdge(vSucc,v);
 221                 m_eT = insertEdge(eOutS->source(),eOutS->target(),0);
 222         }
 223
 224         expandSkeleton(v, eInS, eOutS);
 225
 226         planarEmbed(m_exp);
 227         m_E.init(m_exp);
 228 }
 229
 230
 231 //-------------------------------------------------------------------
 232 // expand one skeleton (recursive construction)
 233 //-------------------------------------------------------------------
 234
 235 void ExpandedGraph2::expandSkeleton(node v, edge e1, edge e2)
 236 {
 237         ListConstIterator<edge> i;
 238         for(i = m_BC.dynamicSPQRForest().hEdgesSPQR(v).begin(); i.valid(); ++i)
 239         {
 240                 edge et = m_BC.dynamicSPQRForest().twinEdge(*i);
 241
 242                 if (et == 0) insertEdge((*i)->source(),(*i)->target(),*i);
 243
 244                 // do not expand virtual edges corresponding to tree edges e1 or e2
 245                 else if (*i != e1 && *i != e2)
 246                         expandSkeleton(m_BC.dynamicSPQRForest().spqrproper(et),et,0);
 247         }
 248 }
 249
 250
 251 //-------------------------------------------------------------------
 252 // insert edge in exp (from a node corresponding to vG in G to a node
 253 // corresponding to wG)
 254 //-------------------------------------------------------------------
 255
 256 edge ExpandedGraph2::insertEdge(node vG, node wG, edge eG)
 257 {
 258         node &rVG = m_GtoExp[vG];
 259         node &rWG = m_GtoExp[wG];
 260
 261         if (rVG == 0) {
 262                 rVG = m_exp.newNode();
 263                 m_nodesG.pushBack(vG);
 264         }
 265         if (rWG == 0) {
 266                 rWG = m_exp.newNode();
 267                 m_nodesG.pushBack(wG);
 268         }
 269
 270         edge e1 = m_exp.newEdge(rVG,rWG);
 271
 272         if(eG != 0) {
 273                 m_expToG[e1->adjSource()] = eG->adjSource();
 274                 m_expToG[e1->adjTarget()] = eG->adjTarget();
 275         } else {
 276                 m_expToG[e1->adjSource()] = 0;
 277                 m_expToG[e1->adjTarget()] = 0;
 278         }
 279
 280         return e1;
 281 }
 282
 283
 284 //-------------------------------------------------------------------
 285 // construct augmented dual of exp
 286 //-------------------------------------------------------------------
 287
 288 void ExpandedGraph2::constructDual(node s, node t,
 289         GraphCopy &GC, const EdgeArray<bool> *forbiddenEdgeOrig)
 290 {
 291         m_dual.clear();
 292
 293         FaceArray<node> faceNode(m_E);
 294
 295         // constructs nodes (for faces in exp)
 296         face f;
 297         forall_faces(f,m_E) {
 298                 faceNode[f] = m_dual.newNode();
 299         }
 300
 301         // construct dual edges (for primal edges in exp)
 302         node v;
 303         forall_nodes(v,m_exp)
 304         {
 305                 adjEntry adj;
 306                 forall_adj(adj,v)
 307                 {
 308                         // cannot cross edges that does not correspond to real edges
 309                         adjEntry adjG = m_expToG[adj];
 310                         if(adjG == 0)
 311                                 continue;
 312
 313                         // Do not insert edges into dual if crossing the original edge
 314                         // is forbidden
 315                         if(forbiddenEdgeOrig &&
 316                                 (*forbiddenEdgeOrig)[GC.original(m_BC.dynamicSPQRForest().original(m_expToG[adj]->theEdge()))] == true)
 317                                 continue;
 318
 319                         node vLeft  = faceNode[m_E.leftFace (adj)];
 320                         node vRight = faceNode[m_E.rightFace(adj)];
 321
 322                         m_primalEdge[m_dual.newEdge(vLeft,vRight)] = adj;
 323                 }
 324         }
 325
 326         // augment dual by m_vS and m_vT
 327         m_vS = m_dual.newNode();
 328         if (m_GtoExp[s] != 0)
 329         {
 330                 adjEntry adj;
 331                 forall_adj(adj,m_GtoExp[s])
 332                         m_dual.newEdge(m_vS,faceNode[m_E.rightFace(adj)]);
 333         }
 334         else
 335         {
 336                 m_dual.newEdge(m_vS,faceNode[m_E.rightFace(m_eS->adjSource())]);
 337                 m_dual.newEdge(m_vS,faceNode[m_E.rightFace(m_eS->adjTarget())]);
 338         }
 339
 340         m_vT = m_dual.newNode();
 341         if (m_GtoExp[t] != 0)
 342         {
 343                 adjEntry adj;
 344                 forall_adj(adj,m_GtoExp[t])
 345                         m_dual.newEdge(faceNode[m_E.rightFace(adj)], m_vT);
 346         }
 347         else
 348         {
 349                 m_dual.newEdge(faceNode[m_E.rightFace(m_eT->adjSource())], m_vT);
 350                 m_dual.newEdge(faceNode[m_E.rightFace(m_eT->adjTarget())], m_vT);
 351         }
 352 }
 353
 354
 355 void ExpandedGraph2::constructDualForbidCrossingGens(node s, node t)
 356 {
 357         m_dual.clear();
 358
 359         FaceArray<node> faceNode(m_E);
 360
 361         // constructs nodes (for faces in exp)
 362         face f;
 363         forall_faces(f,m_E) {
 364                 faceNode[f] = m_dual.newNode();
 365         }
 366
 367         edge eDual;
 368         // construct dual edges (for primal edges in exp)
 369         node v;
 370         forall_nodes(v,m_exp)
 371         {
 372                 adjEntry adj;
 373                 forall_adj(adj,v)
 374                 {
 375                         // cannot cross edges that does not correspond to real edges
 376                         adjEntry adjG = m_expToG[adj];
 377                         if(adjG == 0)
 378                                 continue;
 379
 380                         node vLeft  = faceNode[m_E.leftFace (adj)];
 381                         node vRight = faceNode[m_E.rightFace(adj)];
 382
 383                         edge e = m_dual.newEdge(vLeft,vRight);
 384                         m_primalEdge[e] = adj;
 385
 386                         // mark dual edges corresponding to generalizations
 387                         if (adjG && m_BC.typeOf(adjG->theEdge()) == Graph::generalization)
 388                                 m_primalIsGen[e] = true;
 389
 390                         OGDF_ASSERT(m_primalEdge[e] == 0 || m_expToG[m_primalEdge[e]] != 0);
 391                 }
 392         }
 393
 394         // augment dual by m_vS and m_vT
 395         m_vS = m_dual.newNode();
 396         if (m_GtoExp[s] != 0)
 397         {
 398                 adjEntry adj;
 399                 forall_adj(adj,m_GtoExp[s]) {
 400                         eDual = m_dual.newEdge(m_vS,faceNode[m_E.rightFace(adj)]);
 401                         OGDF_ASSERT(m_primalEdge[eDual] == 0 || m_expToG[m_primalEdge[eDual]] != 0);
 402                 }
 403         }
 404         else
 405         {
 406                 eDual = m_dual.newEdge(m_vS,faceNode[m_E.rightFace(m_eS->adjSource())]);
 407                 OGDF_ASSERT(m_primalEdge[eDual] == 0 || m_expToG[m_primalEdge[eDual]] != 0);
 408
 409                 eDual = m_dual.newEdge(m_vS,faceNode[m_E.rightFace(m_eS->adjTarget())]);
 410                 OGDF_ASSERT(m_primalEdge[eDual] == 0 || m_expToG[m_primalEdge[eDual]] != 0);
 411         }
 412
 413         m_vT = m_dual.newNode();
 414         if (m_GtoExp[t] != 0)
 415         {
 416                 adjEntry adj;
 417                 forall_adj(adj,m_GtoExp[t]) {
 418                         eDual = m_dual.newEdge(faceNode[m_E.rightFace(adj)], m_vT);
 419                         OGDF_ASSERT(m_primalEdge[eDual] == 0 || m_expToG[m_primalEdge[eDual]] != 0);
 420                 }
 421         }
 422         else
 423         {
 424                 eDual = m_dual.newEdge(faceNode[m_E.rightFace(m_eT->adjSource())], m_vT);
 425                 OGDF_ASSERT(m_primalEdge[eDual] == 0 || m_expToG[m_primalEdge[eDual]] != 0);
 426
 427                 eDual = m_dual.newEdge(faceNode[m_E.rightFace(m_eT->adjTarget())], m_vT);
 428                 OGDF_ASSERT(m_primalEdge[eDual] == 0 || m_expToG[m_primalEdge[eDual]] != 0);
 429         }
 430 }
 431
 432
 433 //-------------------------------------------------------------------
 434 // find shortest path in dual from m_vS to m_vT; output this path
 435 // in L by omitting first and last edge, and translating edges to G
 436 //-------------------------------------------------------------------
 437
 438 void ExpandedGraph2::findShortestPath(Graph::EdgeType eType, List<adjEntry> &L)
 439 {
 440         NodeArray<edge> spPred(m_dual,0); // predecessor in shortest path tree
 441         List<edge> queue; // candidate edges
 442
 443         // start with all edges leaving from m_vS
 444         edge e;
 445         forall_adj_edges(e,m_vS)
 446                 queue.pushBack(e);
 447
 448         for( ; ; ) {
 449                 edge eCand = queue.popFrontRet(); // next candidate from front of queue
 450                 node v = eCand->target();
 451
 452                 // hit an unvisited node ?
 453                 if (spPred[v] == 0) {
 454                         spPred[v] = eCand;
 455
 456                         // if it is m_vT, we have found the shortest path
 457                         if (v == m_vT) {
 458                                 // build path from shortest path tree
 459                                 while(v != m_vS) {
 460                                         adjEntry adjExp = m_primalEdge[spPred[v]];
 461                                         if (adjExp != 0) // == nil for first and last edge
 462                                                 L.pushFront(m_expToG[adjExp]);
 463                                         v = spPred[v]->source();
 464                                 }
 465                                 return;
 466                         }
 467
 468                         // append next candidates to end of queue
 469                         forall_adj_edges(e,v) {
 470                                 if(v == e->source() &&
 471                                         (eType != Graph::generalization || m_primalIsGen[e] == false))
 472                                 {
 473                                         queue.pushBack(e);
 474                                 }
 475                         }
 476                 }
 477         }
 478 }
 479
 480
 481 //-------------------------------------------------------------------
 482 // find weighted shortest path in dual from m_vS to m_vT; output this path
 483 // in L by omitting first and last edge, and translating edges to G
 484 //-------------------------------------------------------------------
 485
 486 void ExpandedGraph2::findWeightedShortestPath(Graph::EdgeType eType,
 487         List<adjEntry> &L)
 488 {
 489         int maxCost = 0;
 490         edge eDual;
 491         forall_edges(eDual,m_dual) {
 492                 int c = costDual(eDual);
 493                 if (c > maxCost) maxCost = c;
 494         }
 495
 496         ++maxCost;
 497         Array<SListPure<edge> > nodesAtDist(maxCost);
 498
 499         NodeArray<edge> spPred(m_dual,0); // predecessor in shortest path tree
 500         //List<edge> queue; // candidate edges
 501
 502         // start with all edges leaving from m_vS
 503         edge e;
 504         forall_adj_edges(e,m_vS)
 505                 nodesAtDist[0].pushBack(e);
 506
 507         // actual search (using extended bfs on directed dual)
 508         int currentDist = 0;
 509         for( ; ; ) {
 510                 // next candidate edge
 511                 while(nodesAtDist[currentDist % maxCost].empty())
 512                         ++currentDist;
 513
 514                 edge eCand = nodesAtDist[currentDist % maxCost].popFrontRet();
 515                 node v = eCand->target();
 516
 517                 // leads to an unvisited node ?
 518                 if (spPred[v] == 0) {
 519                         // yes, then we set v's predecessor in search tree
 520                         spPred[v] = eCand;
 521
 522                         // have we reached t ...
 523                         if (v == m_vT) {
 524                                 // ... then search is done.
 525                                 // construct list of used edges (translated to crossed
 526                                 // adjacency entries in G)
 527                                 while(v != m_vS) {
 528                                         adjEntry adjExp = m_primalEdge[spPred[v]];
 529                                         if (adjExp != 0) // == nil for first and last edge
 530                                                 L.pushFront(m_expToG[adjExp]);
 531                                         v = spPred[v]->source();
 532                                 }
 533                                 return;
 534                         }
 535
 536                         // append next candidates to end of queue
 537                         // (all edges leaving v)
 538                         forall_adj_edges(e,v) {
 539                                 if(v == e->source() &&
 540                                         (eType != Graph::generalization || m_primalIsGen[e] == false))
 541                                 {
 542                                         int listPos = (currentDist + costDual(e)) % maxCost;
 543                                         nodesAtDist[listPos].pushBack(e);
 544                                 }
 545                         }
 546                 }
 547         }
 548 }
 549
 550
 551
 552 //---------------------------------------------------------
 553 // VEICrossingsBucket
 554 // bucket function for sorting edges by decreasing number
 555 // of crossings
 556 //---------------------------------------------------------
 557
 558 class VEICrossingsBucket : public BucketFunc<edge>
 559 {
 560         const PlanRep *m_pPG;
 561
 562 public:
 563         VEICrossingsBucket(const PlanRep *pPG) :
 564                 m_pPG(pPG) { }
 565
 566         int getBucket(const edge &e) {
 567                 return -m_pPG->chain(e).size();
 568         }
 569 };
 570
 571
 572
 573 //---------------------------------------------------------
 574 //               VariableEmbeddingInserter2
 575 //---------------------------------------------------------
 576
 577 //---------------------------------------------------------
 578 // constructor
 579 // sets default values for options
 580 //
 581 VariableEmbeddingInserter2::VariableEmbeddingInserter2()
 582 {
 583         m_rrOption = rrNone;
 584         m_percentMostCrossed = 25;
 585 }
 586
 587
 588 //---------------------------------------------------------
 589 // actual call (called by all variations of call)
 590 //   crossing of generalizations is forbidden if forbidCrossingGens = true
 591 //   edge costs are obeyed if costOrig != 0
 592 //
 593 Module::ReturnType VariableEmbeddingInserter2::doCall(
 594         PlanRep &PG,
 595         const List<edge> &origEdges,
 596         bool forbidCrossingGens,
 597         const EdgeArray<int> *costOrig,
 598         const EdgeArray<bool> *forbiddenEdgeOrig)
 599 {
 600         double T;
 601         usedTime(T);
 602
 603         ReturnType retValue = retFeasible;
 604         m_runsPostprocessing = 0;
 605
 606         if (origEdges.size() == 0)
 607                 return retOptimal;  // nothing to do
 608
 609         OGDF_ASSERT(forbidCrossingGens == false || forbiddenEdgeOrig == 0);
 610
 611         m_pPG                = &PG;
 612         m_forbidCrossingGens = forbidCrossingGens;
 613         m_costOrig           = costOrig;
 614         m_forbiddenEdgeOrig  = forbiddenEdgeOrig;
 615
 616         SListPure<edge> currentOrigEdges;
 617         ListConstIterator<edge> it;
 618
 619         if(removeReinsert() == rrIncremental) {
 620                 edge e;
 621                 forall_edges(e,PG)
 622                         currentOrigEdges.pushBack(PG.original(e));
 623
 624                 // insertion of edges
 625                 for(it = origEdges.begin(); it.valid(); ++it)
 626                 {
 627                         edge eOrig = *it;
 628                         m_typeOfCurrentEdge = m_forbidCrossingGens ? PG.typeOrig(eOrig) : Graph::association;
 629
 630                         m_pBC = new BCandSPQRtrees(m_pPG,m_forbidCrossingGens,m_costOrig);
 631                         SList<adjEntry> eip;
 632                         insert(eOrig,eip);
 633                         PG.insertEdgePath(eOrig,eip);
 634                         delete m_pBC;
 635
 636                         currentOrigEdges.pushBack(eOrig);
 637
 638                         bool improved;
 639                         do {
 640                                 ++m_runsPostprocessing;
 641                                 improved = false;
 642
 643                                 SListConstIterator<edge> itRR;
 644                                 for(itRR = currentOrigEdges.begin(); itRR.valid(); ++itRR)
 645                                 {
 646                                         edge eOrigRR = *itRR;
 647
 648                                         int pathLength;
 649                                         if(costOrig != 0)
 650                                                 pathLength = costCrossed(eOrigRR);
 651                                         else
 652                                                 pathLength = PG.chain(eOrigRR).size() - 1;
 653                                         if (pathLength == 0) continue; // cannot improve
 654
 655                                         PG.removeEdgePath(eOrigRR);
 656
 657                                         m_typeOfCurrentEdge = m_forbidCrossingGens ? PG.typeOrig(eOrigRR) : Graph::association;
 658
 659                                         m_pBC = new BCandSPQRtrees(m_pPG,m_forbidCrossingGens,m_costOrig);
 660                                         SList<adjEntry> eip;
 661                                         insert(eOrigRR,eip);
 662                                         PG.insertEdgePath(eOrigRR,eip);
 663                                         delete m_pBC;
 664
 665                                         int newPathLength = (costOrig != 0) ? costCrossed(eOrigRR) : (PG.chain(eOrigRR).size() - 1);
 666                                         OGDF_ASSERT(newPathLength <= pathLength);
 667
 668                                         if(newPathLength < pathLength)
 669                                                 improved = true;
 670                                 }
 671                         } while (improved);
 672                 }
 673         }
 674         else {
 675                 // insertion of edges
 676                 m_pBC = new BCandSPQRtrees(m_pPG,m_forbidCrossingGens,m_costOrig);
 677                 for(it = origEdges.begin(); it.valid(); ++it)
 678                 {
 679                         edge eOrig = *it;
 680                         m_typeOfCurrentEdge = m_forbidCrossingGens ? PG.typeOrig(eOrig) : Graph::association;
 681
 682                         SList<adjEntry> eip;
 683                         insert(eOrig,eip);
 684                         m_pBC->insertEdgePath(eOrig,eip);
 685
 686                 }
 687
 688                 // postprocessing (remove-reinsert heuristc)
 689                 const Graph &G = PG.original();
 690                 SListPure<edge> rrEdges;
 691
 692                 switch(removeReinsert())
 693                 {
 694                 case rrAll:
 695                 case rrMostCrossed: {
 696                                 const List<node> &origInCC = PG.nodesInCC();
 697                                 ListConstIterator<node> itV;
 698
 699                                 for(itV = origInCC.begin(); itV.valid(); ++itV) {
 700                                         node vG = *itV;
 701                                         adjEntry adj;
 702                                         forall_adj(adj,vG) {
 703                                                 if ((adj->index() & 1) == 0) continue;
 704                                                 edge eG = adj->theEdge();
 705                                                 rrEdges.pushBack(eG);
 706                                         }
 707                                 }
 708                         }
 709                         break;
 710
 711                 case rrInserted:
 712                         for(ListConstIterator<edge> it = origEdges.begin(); it.valid(); ++it)
 713                                 rrEdges.pushBack(*it);
 714                         break;
 715
 716                 default:
 717                         break;
 718                 }
 719
 720                 delete m_pBC;
 721
 722                 // marks the end of the interval of rrEdges over which we iterate
 723                 // initially set to invalid iterator which means all edges
 724                 SListConstIterator<edge> itStop;
 725
 726                 bool improved;
 727                 do {
 728                         // abort postprocessing if time limit reached
 729                         if (m_timeLimit >= 0 && m_timeLimit <= usedTime(T)) {
 730                                 retValue = retTimeoutFeasible;
 731                                 break;
 732                         }
 733
 734                         ++m_runsPostprocessing;
 735                         improved = false;
 736
 737                         if(removeReinsert() == rrMostCrossed)
 738                         {
 739                                 VEICrossingsBucket bucket(&PG);
 740                                 rrEdges.bucketSort(bucket);
 741
 742                                 const int num = int(0.01 * percentMostCrossed() * G.numberOfEdges());
 743                                 itStop = rrEdges.get(num);
 744                         }
 745
 746                         SListConstIterator<edge> it;
 747                         for(it = rrEdges.begin(); it != itStop; ++it)
 748                         {
 749                                 edge eOrig = *it;
 750
 751                                 int pathLength;
 752                                 if(costOrig != 0)
 753                                         pathLength = costCrossed(eOrig);
 754                                 else
 755                                         pathLength = PG.chain(eOrig).size() - 1;
 756                                 if (pathLength == 0) continue; // cannot improve
 757
 758                                 PG.removeEdgePath(eOrig);
 759
 760                                 m_typeOfCurrentEdge = m_forbidCrossingGens ? PG.typeOrig(eOrig) : Graph::association;
 761
 762                                 m_pBC = new BCandSPQRtrees(m_pPG,m_forbidCrossingGens,m_costOrig);
 763                                 SList<adjEntry> eip;
 764                                 insert(eOrig,eip);
 765                                 PG.insertEdgePath(eOrig,eip);
 766                                 delete m_pBC;
 767
 768                                 // we cannot find a shortest path that is longer than before!
 769                                 int newPathLength = (costOrig != 0) ? costCrossed(eOrig) : (PG.chain(eOrig).size() - 1);
 770                                 OGDF_ASSERT(newPathLength <= pathLength);
 771
 772                                 if(newPathLength < pathLength)
 773                                         improved = true;
 774                         }
 775                 } while (improved);
 776         }
 777
 778 #ifdef OGDF_DEBUG
 779         bool isPlanar =
 780 #endif
 781                 planarEmbed(PG);
 782
 783         OGDF_ASSERT(isPlanar);
 784
 785         PG.removePseudoCrossings();
 786         OGDF_ASSERT(PG.representsCombEmbedding());
 787         OGDF_ASSERT(forbidCrossingGens == false || checkCrossingGens(static_cast<const PlanRepUML&>(PG)) == true);
 788
 789         return retValue;
 790 }
 791
 792
 793 edge VariableEmbeddingInserter2::crossedEdge(adjEntry adj) const
 794 {
 795         edge e = adj->theEdge();
 796
 797         adj = adj->cyclicSucc();
 798         while(adj->theEdge() == e)
 799                 adj = adj->cyclicSucc();
 800
 801         return adj->theEdge();
 802 }
 803
 804
 805 int VariableEmbeddingInserter2::costCrossed(edge eOrig) const
 806 {
 807         int c = 0;
 808
 809         const List<edge> &L = m_pPG->chain(eOrig);
 810
 811         ListConstIterator<edge> it = L.begin();
 812         for(++it; it.valid(); ++it) {
 813                 c += (*m_costOrig)[m_pPG->original(crossedEdge((*it)->adjSource()))];
 814         }
 815
 816         return c;
 817 }
 818
 819
 820 //-------------------------------------------------------------------
 821 // find optimal edge insertion path from s to t in connected
 822 // graph G
 823 //-------------------------------------------------------------------
 824
 825 void VariableEmbeddingInserter2::insert (edge eOrig, SList<adjEntry>& eip)
 826 {
 827         eip.clear();
 828         node s = m_pPG->copy(eOrig->source());
 829         node t = m_pPG->copy(eOrig->target());
 830
 831         // find path from s to t in BC-tree
 832         // call of blockInsert() is done when we have found the path
 833         // if no path is found, s and t are in different connected components
 834         // and thus an empty edge insertion path is correct!
 835         DynamicSPQRForest& dSPQRF = m_pBC->dynamicSPQRForest();
 836         SList<node>& path = dSPQRF.findPath(s,t);
 837         if (!path.empty()) {
 838                 SListIterator<node> it=path.begin();
 839                 node repS = dSPQRF.repVertex(s,*it);
 840                 for (SListIterator<node> jt=it; it.valid(); ++it) {
 841                         node repT = (++jt).valid() ? dSPQRF.cutVertex(*jt,*it) : dSPQRF.repVertex(t,*it);
 842
 843                         // less than 3 nodes requires no crossings (cannot build SPQR-tree
 844                         // for a graph with less than 3 nodes!)
 845                         if (dSPQRF.numberOfNodes(*it)>3) {
 846                                 List<adjEntry> L;
 847                                 blockInsert(repS,repT,L); // call biconnected case
 848
 849                                 // transform crossed edges to edges in G
 850                                 for (ListConstIterator<adjEntry> kt=L.begin(); kt.valid(); ++kt) {
 851                                         edge e = (*kt)->theEdge();
 852                                         eip.pushBack(e->adjSource()==*kt ? dSPQRF.original(e)->adjSource()
 853                                                 : dSPQRF.original(e)->adjTarget());
 854                                 }
 855                         }
 856                         if (jt.valid()) repS = dSPQRF.cutVertex(*it,*jt);
 857                 }
 858         }
 859         delete &path;
 860 }
 861
 862
 863 //-------------------------------------------------------------------
 864 // find optimal edge insertion path from s to t for biconnected
 865 // graph G (OptimalBlockInserter)
 866 //-------------------------------------------------------------------
 867
 868 void VariableEmbeddingInserter2::blockInsert(node s, node t, List<adjEntry> &L)
 869 {
 870         L.clear();
 871
 872         // find path in SPQR-tree from an allocation node of s
 873         // to an allocation node of t
 874         SList<node>& path = m_pBC->dynamicSPQRForest().findPathSPQR(s,t);
 875
 876         // call build_subpath for every R-node building the list L of crossed edges
 877         ExpandedGraph2 Exp(*m_pBC);
 878
 879         node vPred = 0;
 880         path.pushBack(0);
 881         SListConstIterator<node> it;
 882         for(it = path.begin(); *it; ++it)
 883         {
 884                 node v = *it;
 885                 node vSucc = *it.succ();
 886
 887                 if (m_pBC->dynamicSPQRForest().typeOfTNode(v) == DynamicSPQRForest::RComp)
 888                         buildSubpath(v, vPred, vSucc, L, Exp, s, t);
 889
 890                 vPred = v;
 891         }
 892
 893         delete &path;
 894 }
 895
 896
 897 //-------------------------------------------------------------------
 898 // find the shortest path from represent. of s to represent. of t in
 899 // the dual of the (partially) expanded skeleton of v
 900 //-------------------------------------------------------------------
 901
 902 void VariableEmbeddingInserter2::buildSubpath(
 903         node v,
 904         node vPred,
 905         node vSucc,
 906         List<adjEntry> &L,
 907         ExpandedGraph2 &Exp,
 908         node s,
 909         node t)
 910 {
 911         // build expanded graph Exp
 912         Exp.expand(v,vPred,vSucc);
 913
 914         // construct augmented dual of expanded graph
 915         if(m_forbidCrossingGens)
 916                 Exp.constructDualForbidCrossingGens(s,t);
 917         else
 918                 Exp.constructDual(s,t,*m_pPG,m_forbiddenEdgeOrig);
 919
 920         // find shortest path in augmented dual
 921         List<adjEntry> subpath;
 922         if(m_costOrig != 0)
 923                 Exp.findWeightedShortestPath(m_typeOfCurrentEdge,subpath);
 924         else
 925                 Exp.findShortestPath(m_typeOfCurrentEdge,subpath);
 926
 927         L.conc(subpath);
 928 }
 929
 930
 931 } // end namespace ogdf