ext/OGDF/src/planarity/PlanRepExpansion.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 PlanRepExpansion.
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #include <ogdf/planarity/PlanRepExpansion.h>
  45 #include <ogdf/basic/simple_graph_alg.h>
  46 #include <ogdf/basic/extended_graph_alg.h>
  47 #include <ogdf/basic/CombinatorialEmbedding.h>
  48 #include <ogdf/basic/FaceSet.h>
  49 #include <ogdf/basic/NodeSet.h>
  50
  51
  52 namespace ogdf {
  53
  54 PlanRepExpansion::PlanRepExpansion(const Graph& G)
  55 {
  56         List<node> splittableNodes;
  57         node v;
  58         forall_nodes(v,G) {
  59                 if(v->degree() >= 4)
  60                         splittableNodes.pushBack(v);
  61         }
  62
  63         doInit(G,splittableNodes);
  64 }
  65
  66 PlanRepExpansion::PlanRepExpansion(const Graph& G, const List<node> &splittableNodes)
  67 {
  68         doInit(G,splittableNodes);
  69 }
  70
  71 void PlanRepExpansion::doInit(const Graph &G, const List<node> &splittableNodes)
  72 {
  73         m_pGraph = &G;
  74         m_eAuxCopy.init(G);
  75
  76         // compute connected component of G
  77         NodeArray<int> component(G);
  78         m_numCC = connectedComponents(G,component);
  79
  80         // intialize the array of lists of nodes contained in a CC
  81         m_nodesInCC.init(m_numCC);
  82
  83         node v;
  84         forall_nodes(v,G)
  85                 m_nodesInCC[component[v]].pushBack(v);
  86
  87         m_currentCC = -1;  // not yet initialized
  88
  89         m_vCopy.init(G);
  90         m_eCopy.init(G);
  91         m_vOrig.init(*this,0);
  92         m_eOrig.init(*this,0);
  93         m_vIterator.init(*this,0);
  94         m_eIterator.init(*this,0);
  95
  96         m_splittable.init(*this,false);
  97         m_splittableOrig.init(G,false);
  98         m_eNodeSplit.init(*this,0);
  99
 100         ListConstIterator<node> it;
 101         for(it = splittableNodes.begin(); it.valid(); ++it)
 102                 if((*it)->degree() >= 4)
 103                         m_splittableOrig[*it] = true;
 104 }
 105
 106
 107 void PlanRepExpansion::initCC(int i)
 108 {
 109         // delete copy / chain fields for originals of nodes in current cc
 110         // (since we remove all these copies in initByNodes(...)
 111         if (m_currentCC >= 0)
 112         {
 113                 const List<node> &origInCC = nodesInCC(i);
 114                 ListConstIterator<node> itV;
 115
 116                 for(itV = origInCC.begin(); itV.valid(); ++itV)
 117                 {
 118                         node vG = *itV;
 119
 120                         m_vCopy[vG].clear();
 121
 122                         adjEntry adj;
 123                         forall_adj(adj,vG) {
 124                                 if ((adj->index() & 1) == 0) continue;
 125                                 edge eG = adj->theEdge();
 126
 127                                 m_eCopy[eG].clear();
 128                         }
 129                 }
 130         }
 131
 132         m_currentCC = i;
 133
 134         NodeArray<node> vCopy(*m_pGraph);
 135         Graph::constructInitByNodes(*m_pGraph,m_nodesInCC[i],vCopy,m_eAuxCopy);
 136
 137         ListConstIterator<node> itV;
 138         for(itV = m_nodesInCC[i].begin(); itV.valid(); ++itV)
 139         {
 140                 node vOrig = *itV;
 141                 node v = vCopy[vOrig];
 142
 143                 m_vOrig[v] = vOrig;
 144                 m_vIterator[v] = m_vCopy[vOrig].pushBack(v);
 145                 m_splittable[v] = m_splittableOrig[vOrig];
 146
 147                 adjEntry adj;
 148                 forall_adj(adj,vOrig) {
 149                         if ((adj->index() & 1) == 0) {
 150                                 edge e = adj->theEdge();
 151                                 m_eIterator[m_eAuxCopy[e]] = m_eCopy[e].pushBack(m_eAuxCopy[e]);
 152                                 m_eOrig[m_eAuxCopy[e]] = e;
 153                         }
 154                 }
 155         }
 156
 157         m_nodeSplits.clear();
 158 }
 159
 160
 161 void PlanRepExpansion::delCopy(edge e)
 162 {
 163         edge eOrig = m_eOrig[e];
 164         OGDF_ASSERT(m_eCopy[eOrig].size() == 1);
 165         delEdge(e);
 166         m_eCopy[eOrig].clear();
 167 }
 168
 169
 170 bool PlanRepExpansion::embed()
 171 {
 172         return planarEmbed(*this);
 173 }
 174
 175
 176 void PlanRepExpansion::prepareNodeSplit(
 177         const SList<adjEntry> &partitionLeft,
 178         adjEntry &adjLeft,
 179         adjEntry &adjRight)
 180 {
 181         OGDF_ASSERT(!partitionLeft.empty());
 182         OGDF_ASSERT(partitionLeft.front()->theNode()->degree() > partitionLeft.size());
 183
 184         SListConstIterator<adjEntry> it = partitionLeft.begin();
 185         adjEntry adj = *it;
 186         adjLeft = adj;
 187
 188         for(++it; it.valid(); ++it) {
 189                 moveAdjAfter(*it,adj);
 190                 adj = *it;
 191         }
 192
 193         adjRight = adj->cyclicSucc();
 194 }
 195
 196
 197 void PlanRepExpansion::insertEdgePath(
 198         edge eOrig,
 199         nodeSplit ns,
 200         node vStart,
 201         node vEnd,
 202         List<Crossing> &eip,
 203         edge eSrc,
 204         edge eTgt)
 205 {
 206         OGDF_ASSERT((eOrig != 0 && ns == 0) || (eOrig == 0 && ns != 0));
 207
 208         if(eOrig)
 209                 m_eCopy[eOrig].clear();
 210         else
 211                 ns->m_path.clear();
 212
 213         if(eSrc != 0) {
 214                 if(eOrig) {
 215                         m_eIterator[eSrc] = m_eCopy[eOrig].pushBack(eSrc);
 216                         m_eOrig    [eSrc] = eOrig;
 217                 } else {
 218                         m_eIterator [eSrc] = ns->m_path.pushBack(eSrc);
 219                         m_eNodeSplit[eSrc] = ns;
 220                 }
 221         }
 222
 223         node v = vStart;
 224         ListConstIterator<Crossing> it;
 225         for(it = eip.begin(); it.valid(); ++it)
 226         {
 227                 adjEntry adj = (*it).m_adj;
 228                 if(adj == 0) {
 229                         adjEntry adjLeft, adjRight;
 230                         prepareNodeSplit((*it).m_partitionLeft, adjLeft, adjRight);
 231
 232                         node w = splitNode(adjLeft,adjRight);
 233                         edge eNew = adjLeft->cyclicPred()->theEdge();
 234
 235                         m_vIterator [w] = m_vCopy[m_vOrig[adjLeft->theNode()]].pushBack(w);
 236                         m_splittable[w] = true;
 237                         m_vOrig     [w] = m_vOrig[adjLeft->theNode()];
 238
 239                         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
 240                         (*itNS).m_nsIterator = itNS;
 241                         m_eIterator[eNew] = (*itNS).m_path.pushBack(eNew);
 242                         m_eNodeSplit[eNew] = &(*itNS);
 243
 244                         adj = adjRight->cyclicPred();
 245                 }
 246
 247                 node u = split(adj->theEdge())->source();
 248                 edge eNew = newEdge(v,u);
 249
 250                 if(eOrig) {
 251                         m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
 252                         m_eOrig    [eNew] = eOrig;
 253                 } else {
 254                         m_eIterator [eNew] = ns->m_path.pushBack(eNew);
 255                         m_eNodeSplit[eNew] = ns;
 256                 }
 257
 258                 v = u;
 259         }
 260
 261         edge eNew = newEdge(v,vEnd);
 262         if(eOrig) {
 263                 m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
 264                 m_eOrig    [eNew] = eOrig;
 265         } else {
 266                 m_eIterator [eNew] = ns->m_path.pushBack(eNew);
 267                 m_eNodeSplit[eNew] = ns;
 268         }
 269
 270         if(eTgt != 0) {
 271                 if(eOrig) {
 272                         m_eIterator[eTgt] = m_eCopy[eOrig].pushBack(eTgt);
 273                         m_eOrig    [eTgt] = eOrig;
 274                 } else {
 275                         m_eIterator [eTgt] = ns->m_path.pushBack(eTgt);
 276                         m_eNodeSplit[eTgt] = ns;
 277                 }
 278         }
 279 }
 280
 281
 282 void PlanRepExpansion::insertEdgePathEmbedded(
 283         edge eOrig,
 284         nodeSplit ns,
 285         CombinatorialEmbedding &E,
 286         const List<Tuple2<adjEntry,adjEntry> > &crossedEdges)
 287 {
 288         OGDF_ASSERT((eOrig != 0 && ns == 0) || (eOrig == 0 && ns != 0));
 289
 290         if(eOrig)
 291                 m_eCopy[eOrig].clear();
 292         else
 293                 ns->m_path.clear();
 294
 295         adjEntry adjSrc, adjTgt;
 296         ListConstIterator<Tuple2<adjEntry,adjEntry> > it = crossedEdges.begin();
 297         ListConstIterator<Tuple2<adjEntry,adjEntry> > itLast = crossedEdges.rbegin();
 298
 299         // iterate over all adjacency entries in crossedEdges except for first
 300         // and last
 301         adjSrc = (*it).x1();
 302         for(++it; it != itLast; ++it)
 303         {
 304                 adjEntry adj  = (*it).x1();
 305                 adjEntry adj2 = (*it).x2();
 306
 307                 if(adj2 != 0) {
 308                         OGDF_ASSERT(adj->theNode() == adj2->theNode());
 309                         OGDF_ASSERT(E.rightFace(adjSrc) == E.rightFace(adj->twin()));
 310                         node w = E.splitNode(adj,adj2);
 311                         edge eNew = adj->cyclicPred()->theEdge();
 312
 313                         m_vIterator [w] = m_vCopy[m_vOrig[adj->theNode()]].pushBack(w);
 314                         m_splittable[w] = true;
 315                         m_vOrig     [w] = m_vOrig[adj->theNode()];
 316
 317                         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
 318                         (*itNS).m_nsIterator = itNS;
 319                         m_eIterator[eNew] = (*itNS).m_path.pushBack(eNew);
 320                         m_eNodeSplit[eNew] = &(*itNS);
 321
 322                         adj = adj2->cyclicPred();
 323                 }
 324
 325                 // split edge
 326                 node u = E.split(adj->theEdge())->source();
 327
 328                 // determine target adjacency entry and source adjacency entry
 329                 // in the next iteration step
 330                 adjTgt = u->firstAdj();
 331                 adjEntry adjSrcNext = adjTgt->succ();
 332
 333                 if (adjTgt != adj->twin())
 334                         swap(adjTgt,adjSrcNext);
 335
 336                 OGDF_ASSERT(adjTgt == adj->twin());
 337
 338                 // insert a new edge into the face
 339                 edge eNew = E.splitFace(adjSrc,adjTgt);
 340
 341                 if(eOrig) {
 342                         m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
 343                         m_eOrig    [eNew] = eOrig;
 344                 } else {
 345                         m_eIterator [eNew] = ns->m_path.pushBack(eNew);
 346                         m_eNodeSplit[eNew] = ns;
 347                 }
 348
 349                 adjSrc = adjSrcNext;
 350         }
 351
 352         // insert last edge
 353         edge eNew = E.splitFace(adjSrc,(*it).x1());
 354
 355         if(eOrig) {
 356                 m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
 357                 m_eOrig    [eNew] = eOrig;
 358         } else {
 359                 m_eIterator [eNew] = ns->m_path.pushBack(eNew);
 360                 m_eNodeSplit[eNew] = ns;
 361         }
 362 }
 363
 364
 365 void PlanRepExpansion::removeEdgePathEmbedded(
 366         CombinatorialEmbedding &E,
 367         edge eOrig,
 368         nodeSplit ns,
 369         FaceSetPure &newFaces,
 370         NodeSetPure &mergedNodes,
 371         node &oldSrc,
 372         node &oldTgt)
 373 {
 374         OGDF_ASSERT((eOrig != 0 && ns == 0) || (eOrig == 0 && ns != 0));
 375
 376         const List<edge> &path = (eOrig) ? m_eCopy[eOrig] : ns->m_path;
 377         ListConstIterator<edge> it = path.begin();
 378
 379         oldSrc = path.front()->source();
 380         oldTgt = path.back()->target();
 381
 382         newFaces.insert(E.joinFaces(*it));
 383
 384         for(++it; it.valid(); ++it)
 385         {
 386                 edge e = *it;
 387                 node u = e->source();
 388
 389                 newFaces.remove(E.rightFace(e->adjSource()));
 390                 newFaces.remove(E.rightFace(e->adjTarget()));
 391
 392                 newFaces.insert(E.joinFaces(e));
 393
 394                 edge eIn = u->firstAdj()->theEdge();
 395                 edge eOut = u->lastAdj()->theEdge();
 396                 if (eIn->target() != u)
 397                         swap(eIn,eOut);
 398
 399                 E.unsplit(eIn,eOut);
 400
 401                 u = eIn->source();
 402                 node v = eIn->target();
 403
 404                 node vOrig = m_vOrig[v];
 405                 if(vOrig != 0 && m_vOrig[u] == vOrig) {
 406                         m_vCopy[vOrig].del(m_vIterator[v]);
 407                         ListIterator<NodeSplit> itNS = m_eNodeSplit[eIn]->m_nsIterator;
 408                         m_nodeSplits.del(itNS);
 409
 410                         E.contract(eIn);
 411
 412                         if(mergedNodes.isMember(v))
 413                                 mergedNodes.remove(v);
 414                         mergedNodes.insert(u);
 415
 416                         if(oldSrc == v) oldSrc = u;
 417                         if(oldTgt == v) oldTgt = u;
 418                 }
 419         }
 420
 421         if(eOrig)
 422                 m_eCopy[eOrig].clear();
 423         else
 424                 ns->m_path.clear();
 425 }
 426
 427
 428 void PlanRepExpansion::removeEdgePath(
 429         edge eOrig,
 430         nodeSplit ns,
 431         node &oldSrc,
 432         node &oldTgt)
 433 {
 434         OGDF_ASSERT((eOrig != 0 && ns == 0) || (eOrig == 0 && ns != 0));
 435
 436         const List<edge> &path = (eOrig) ? m_eCopy[eOrig] : ns->m_path;
 437         ListConstIterator<edge> it = path.begin();
 438
 439         oldSrc = path.front()->source();
 440         oldTgt = path.back()->target();
 441
 442         delEdge(*it);
 443
 444         for(++it; it.valid(); ++it)
 445         {
 446                 edge e = *it;
 447                 node u = e->source();
 448
 449                 delEdge(e);
 450
 451                 edge eIn = u->firstAdj()->theEdge();
 452                 edge eOut = u->lastAdj()->theEdge();
 453                 if (eIn->target() != u)
 454                         swap(eIn,eOut);
 455
 456                 unsplit(eIn,eOut);
 457
 458                 u = eIn->source();
 459                 node v = eIn->target();
 460
 461                 node vOrig = m_vOrig[v];
 462                 if(vOrig != 0 && m_vOrig[u] == vOrig) {
 463                         m_vCopy[vOrig].del(m_vIterator[v]);
 464                         ListIterator<NodeSplit> itNS = m_eNodeSplit[eIn]->m_nsIterator;
 465                         m_nodeSplits.del(itNS);
 466
 467                         contract(eIn);
 468
 469                         if(oldSrc == v) oldSrc = u;
 470                         if(oldTgt == v) oldTgt = u;
 471                 }
 472         }
 473
 474         if(eOrig)
 475                 m_eCopy[eOrig].clear();
 476         else
 477                 ns->m_path.clear();
 478 }
 479
 480
 481 void PlanRepExpansion::contractSplit(nodeSplit ns, CombinatorialEmbedding &E)
 482 {
 483         OGDF_ASSERT(ns->m_path.size() == 1);
 484
 485         edge e     = ns->m_path.front();
 486         node v     = e->target();
 487         node vOrig = m_vOrig[v];
 488
 489         m_vCopy[vOrig].del(m_vIterator[v]);
 490         ListIterator<NodeSplit> itNS = ns->m_nsIterator;
 491         m_nodeSplits.del(itNS);
 492
 493         E.contract(e);
 494 }
 495
 496
 497 void PlanRepExpansion::contractSplit(nodeSplit ns)
 498 {
 499         OGDF_ASSERT(ns->m_path.size() == 1);
 500
 501         edge e     = ns->m_path.front();
 502         node v     = e->target();
 503         node vOrig = m_vOrig[v];
 504
 505         m_vCopy[vOrig].del(m_vIterator[v]);
 506         ListIterator<NodeSplit> itNS = ns->m_nsIterator;
 507         m_nodeSplits.del(itNS);
 508
 509         contract(e);
 510 }
 511
 512
 513 int PlanRepExpansion::computeNumberOfCrossings() const
 514 {
 515         int cr = 0;
 516
 517         node v;
 518         forall_nodes(v,*this)
 519                 if(m_vOrig[v] == 0)
 520                         ++cr;
 521
 522         return cr;
 523 }
 524
 525
 526 edge PlanRepExpansion::split(edge e)
 527 {
 528         edge eNew  = Graph::split(e);
 529         edge eOrig = m_eOrig[e];
 530         NodeSplit *ns = m_eNodeSplit[e];
 531
 532         if ((m_eOrig[eNew] = eOrig) != 0) {
 533                 m_eIterator[eNew] = m_eCopy[eOrig].insert(eNew,m_eIterator[e],after);
 534
 535         } else if ((m_eNodeSplit[eNew] = ns) != 0) {
 536                 m_eIterator[eNew] = ns->m_path.insert(eNew,m_eIterator[e],after);
 537         }
 538
 539         return eNew;
 540 }
 541
 542
 543 void PlanRepExpansion::unsplit(edge eIn, edge eOut)
 544 {
 545         edge eOrig = m_eOrig[eOut];
 546         NodeSplit *ns = m_eNodeSplit[eOut];
 547
 548         // update chain of eOrig if eOrig exists
 549         if (eOrig != 0) {
 550                 m_eCopy[eOrig].del(m_eIterator[eOut]);
 551
 552         } else if (ns != 0) {
 553                 ns->m_path.del(m_eIterator[eOut]);
 554         }
 555
 556         Graph::unsplit(eIn,eOut);
 557 }
 558
 559
 560 edge PlanRepExpansion::unsplitExpandNode(
 561         node u,
 562         edge eContract,
 563         edge eExpand,
 564         CombinatorialEmbedding &E)
 565 {
 566         NodeSplit *ns = m_eNodeSplit[eContract];
 567         List<edge> &path = ns->m_path;
 568
 569         NodeSplit *nsExp    = m_eNodeSplit[eExpand];
 570         edge       eOrigExp = m_eOrig[eExpand];
 571         List<edge> &pathExp = (nsExp != 0) ? nsExp->m_path : m_eCopy[eOrigExp];
 572
 573         if((eExpand->target() == u && eContract->source() != u) ||
 574                 (eExpand->source() == u && eContract->target() != u))
 575         {
 576                 // reverse path of eContract
 577                 ListConstIterator<edge> it;
 578                 for(it = path.begin(); it.valid(); ++it) {
 579                         E.reverseEdge(*it);
 580                 }
 581                 path.reverse();
 582         }
 583
 584         // remove u from list of copy nodes of its original
 585         m_vCopy[m_vOrig[u]].del(m_vIterator[u]);
 586
 587         // unsplit u and enlarge edge path of eOrigExp
 588         edge eRet;
 589         if(eExpand->target() == u) {
 590                 eRet = eExpand;
 591                 E.unsplit(eExpand,eContract);
 592
 593                 ListConstIterator<edge> it;
 594                 for(it = path.begin(); it.valid(); ++it) {
 595                         m_eNodeSplit[*it] = nsExp;
 596                         m_eOrig     [*it] = eOrigExp;
 597                 }
 598
 599                 pathExp.conc(path);
 600
 601         } else {
 602                 eRet = eContract;
 603                 E.unsplit(eContract,eExpand);
 604
 605                 ListConstIterator<edge> it;
 606                 for(it = path.begin(); it.valid(); ++it) {
 607                         m_eNodeSplit[*it] = nsExp;
 608                         m_eOrig     [*it] = eOrigExp;
 609                 }
 610
 611                 pathExp.concFront(path);
 612         }
 613
 614         m_nodeSplits.del(ns->m_nsIterator);
 615         return eRet;
 616 }
 617
 618
 619 edge PlanRepExpansion::unsplitExpandNode(
 620         node u,
 621         edge eContract,
 622         edge eExpand)
 623 {
 624         NodeSplit *ns = m_eNodeSplit[eContract];
 625         List<edge> &path = ns->m_path;
 626
 627         NodeSplit *nsExp    = m_eNodeSplit[eExpand];
 628         edge       eOrigExp = m_eOrig[eExpand];
 629         List<edge> &pathExp = (nsExp != 0) ? nsExp->m_path : m_eCopy[eOrigExp];
 630
 631         if((eExpand->target() == u && eContract->source() != u) ||
 632                 (eExpand->source() == u && eContract->target() != u))
 633         {
 634                 // reverse path of eContract
 635                 ListConstIterator<edge> it;
 636                 for(it = path.begin(); it.valid(); ++it) {
 637                         reverseEdge(*it);
 638                 }
 639                 path.reverse();
 640         }
 641
 642         // remove u from list of copy nodes of its original
 643         m_vCopy[m_vOrig[u]].del(m_vIterator[u]);
 644
 645         // unsplit u and enlarge edge path of eOrigExp
 646         edge eRet;
 647         if(eExpand->target() == u) {
 648                 eRet = eExpand;
 649                 unsplit(eExpand,eContract);
 650
 651                 ListConstIterator<edge> it;
 652                 for(it = path.begin(); it.valid(); ++it) {
 653                         m_eNodeSplit[*it] = nsExp;
 654                         m_eOrig     [*it] = eOrigExp;
 655                 }
 656
 657                 pathExp.conc(path);
 658
 659         } else {
 660                 eRet = eContract;
 661                 unsplit(eContract,eExpand);
 662
 663                 ListConstIterator<edge> it;
 664                 for(it = path.begin(); it.valid(); ++it) {
 665                         m_eNodeSplit[*it] = nsExp;
 666                         m_eOrig     [*it] = eOrigExp;
 667                 }
 668
 669                 pathExp.concFront(path);
 670         }
 671
 672         m_nodeSplits.del(ns->m_nsIterator);
 673         return eRet;
 674 }
 675
 676
 677 edge PlanRepExpansion::enlargeSplit(
 678         node v,
 679         edge e)
 680 {
 681         node vOrig = m_vOrig[v];
 682         edge eOrig = m_eOrig[e];
 683
 684         edge eNew = split(e);
 685         node u = e->target();
 686
 687         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
 688         nodeSplit ns = &(*itNS);
 689         ns->m_nsIterator = itNS;
 690
 691         m_vOrig     [u] = vOrig;
 692         m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
 693         m_splittable[u] = true;
 694
 695         List<edge> &path = m_eCopy[eOrig];
 696         if(v == path.front()->source()) {
 697                 ListIterator<edge> it, itNext;
 698                 for(it = path.begin(); *it != eNew; it = itNext) {
 699                         itNext = it.succ();
 700
 701                         path.moveToBack(it, ns->m_path);
 702                         m_eOrig[*it] = 0;
 703                         m_eNodeSplit[*it] = ns;
 704                 }
 705
 706         } else {
 707                 ListIterator<edge> it, itNext;
 708                 for(it = m_eIterator[eNew]; it.valid(); it = itNext) {
 709                         itNext = it.succ();
 710
 711                         path.moveToBack(it, ns->m_path);
 712                         m_eOrig[*it] = 0;
 713                         m_eNodeSplit[*it] = ns;
 714                 }
 715         }
 716
 717         return eNew;
 718 }
 719
 720
 721 edge PlanRepExpansion::enlargeSplit(
 722         node v,
 723         edge e,
 724         CombinatorialEmbedding &E)
 725 {
 726         node vOrig = m_vOrig[v];
 727         edge eOrig = m_eOrig[e];
 728
 729         edge eNew = E.split(e);
 730         node u = e->target();
 731
 732         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
 733         nodeSplit ns = &(*itNS);
 734         ns->m_nsIterator = itNS;
 735
 736         m_vOrig     [u] = vOrig;
 737         m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
 738         m_splittable[u] = true;
 739
 740         List<edge> &path = m_eCopy[eOrig];
 741         if(v == path.front()->source()) {
 742                 ListIterator<edge> it, itNext;
 743                 for(it = path.begin(); *it != eNew; it = itNext) {
 744                         itNext = it.succ();
 745
 746                         path.moveToBack(it, ns->m_path);
 747                         m_eOrig[*it] = 0;
 748                         m_eNodeSplit[*it] = ns;
 749                 }
 750
 751         } else {
 752                 ListIterator<edge> it, itNext;
 753                 for(it = m_eIterator[eNew]; it.valid(); it = itNext) {
 754                         itNext = it.succ();
 755
 756                         path.moveToBack(it, ns->m_path);
 757                         m_eOrig[*it] = 0;
 758                         m_eNodeSplit[*it] = ns;
 759                 }
 760         }
 761
 762         return eNew;
 763 }
 764
 765
 766 edge PlanRepExpansion::splitNodeSplit(edge e)
 767 {
 768         nodeSplit ns = m_eNodeSplit[e];
 769         node vOrig = m_vOrig[ns->source()];
 770
 771         edge eNew = split(e);
 772         node u = e->target();
 773
 774         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
 775         nodeSplit nsNew = &(*itNS);
 776         nsNew->m_nsIterator = itNS;
 777
 778         m_vOrig     [u] = vOrig;
 779         m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
 780         m_splittable[u] = true;
 781
 782         List<edge> &path = ns->m_path;
 783         path.split(m_eIterator[eNew], path, nsNew->m_path);
 784
 785         ListIterator<edge> it;
 786         for(it = nsNew->m_path.begin(); it.valid(); ++it) {
 787                 m_eNodeSplit[*it] = nsNew;
 788         }
 789
 790         return eNew;
 791 }
 792
 793
 794 edge PlanRepExpansion::splitNodeSplit(
 795         edge e,
 796         CombinatorialEmbedding &E)
 797 {
 798         nodeSplit ns = m_eNodeSplit[e];
 799         node vOrig = m_vOrig[ns->source()];
 800
 801         edge eNew = E.split(e);
 802         node u = e->target();
 803
 804         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
 805         nodeSplit nsNew = &(*itNS);
 806         nsNew->m_nsIterator = itNS;
 807
 808         m_vOrig     [u] = vOrig;
 809         m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
 810         m_splittable[u] = true;
 811
 812         List<edge> &path = ns->m_path;
 813         path.split(m_eIterator[eNew], path, nsNew->m_path);
 814
 815         ListIterator<edge> it;
 816         for(it = nsNew->m_path.begin(); it.valid(); ++it) {
 817                 m_eNodeSplit[*it] = nsNew;
 818         }
 819
 820         return eNew;
 821 }
 822
 823
 824 void PlanRepExpansion::removeSelfLoop(
 825         edge e,
 826         CombinatorialEmbedding &E)
 827 {
 828         node      u     = e->source();
 829         nodeSplit ns    = m_eNodeSplit[e];
 830         edge      eOrig = m_eOrig[e];
 831
 832         List<edge> &path = (eOrig != 0) ? m_eCopy[eOrig] : ns->m_path;
 833         path.del(m_eIterator[e]);
 834
 835         E.joinFaces(e);
 836
 837         edge eIn  = u->firstAdj()->theEdge();
 838         edge eOut = u->lastAdj ()->theEdge();
 839         if(eIn->target() != u) swap(eIn,eOut);
 840
 841         OGDF_ASSERT(ns == m_eNodeSplit[eOut] && eOrig == m_eOrig[eOut]);
 842
 843         E.unsplit(eIn,eOut);
 844 }
 845
 846
 847 void PlanRepExpansion::removeSelfLoop(edge e)
 848 {
 849         node      u     = e->source();
 850         nodeSplit ns    = m_eNodeSplit[e];
 851         edge      eOrig = m_eOrig[e];
 852
 853         List<edge> &path = (eOrig != 0) ? m_eCopy[eOrig] : ns->m_path;
 854         path.del(m_eIterator[e]);
 855
 856         delEdge(e);
 857
 858         edge eIn  = u->firstAdj()->theEdge();
 859         edge eOut = u->lastAdj ()->theEdge();
 860         if(eIn->target() != u) swap(eIn,eOut);
 861
 862         OGDF_ASSERT(ns == m_eNodeSplit[eOut] && eOrig == m_eOrig[eOut]);
 863
 864         unsplit(eIn,eOut);
 865 }
 866
 867
 868 bool PlanRepExpansion::consistencyCheck() const
 869 {
 870         if(Graph::consistencyCheck() == false)
 871                 return false;
 872
 873         if(isLoopFree(*this) == false)
 874                 return false;
 875
 876         edge eOrig;
 877         forall_edges(eOrig,*m_pGraph) {
 878                 const List<edge> &path = m_eCopy[eOrig];
 879                 ListConstIterator<edge> it;
 880                 for(it = path.begin(); it.valid(); ++it) {
 881                         edge e = *it;
 882                         if(it != path.begin()) {
 883                                 if(e->source()->degree() != 4)
 884                                         return false;
 885                                 if(e->source() != (*it.pred())->target())
 886                                         return false;
 887                         }
 888                 }
 889         }
 890
 891         node vOrig;
 892         forall_nodes(vOrig,*m_pGraph) {
 893                 const List<node> &nodes = m_vCopy[vOrig];
 894
 895                 if(nodes.size() == 1)
 896                         if(m_splittable[nodes.front()] != m_splittableOrig[vOrig])
 897                                 return false;
 898
 899                 if(nodes.size() <= 1) continue;
 900
 901                 if(m_splittableOrig[vOrig] == false)
 902                         return false;
 903
 904                 ListConstIterator<node> it;
 905                 for(it = nodes.begin(); it.valid(); ++it) {
 906                         node v = *it;
 907                         if(v->degree() < 2)
 908                                 return false;
 909                 }
 910         }
 911
 912         EdgeArray<const NodeSplit *> nso(*this,0);
 913
 914         ListConstIterator<NodeSplit> it;
 915         for(it = m_nodeSplits.begin(); it.valid(); ++it) {
 916                 const NodeSplit &ns = *it;
 917
 918                 if(ns.m_path.size() == 0)
 919                         continue;
 920
 921                 node v = ns.source();
 922                 node w = ns.target();
 923
 924                 node vOrig = m_vOrig[v];
 925                 if(vOrig == 0 || vOrig != m_vOrig[w])
 926                         return false;
 927
 928                 if(m_splittable[v] == false || m_splittable[w] == false)
 929                         return false;
 930
 931                 const List<edge> &path = ns.m_path;
 932                 ListConstIterator<edge> itE;
 933                 for(itE = path.begin(); itE.valid(); ++itE) {
 934                         edge e = *itE;
 935                         nso[e] = &ns;
 936                         if(itE != path.begin()) {
 937                                 if(e->source()->degree() != 4)
 938                                         return false;
 939                                 if(e->source() != (*itE.pred())->target())
 940                                         return false;
 941                         }
 942                 }
 943         }
 944
 945         edge e;
 946         forall_edges(e,*this) {
 947                 if(nso[e] != m_eNodeSplit[e])
 948                         return false;
 949         }
 950
 951         return true;
 952 }
 953
 954
 955 List<edge> &PlanRepExpansion::setOrigs(edge e, edge &eOrig, nodeSplit &ns)
 956 {
 957         eOrig = m_eOrig[e];
 958         ns    = m_eNodeSplit[e];
 959         return (eOrig != 0) ? m_eCopy[eOrig] : ns->m_path;
 960 }
 961
 962
 963 PlanRepExpansion::nodeSplit PlanRepExpansion::convertDummy(
 964         node u,
 965         node vOrig,
 966         PlanRepExpansion::nodeSplit ns_0)
 967 {
 968         OGDF_ASSERT(u->indeg() == 2 && u->outdeg() == 2 && m_vOrig[u] == 0);
 969
 970         m_vOrig     [u] = vOrig;
 971         m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
 972         m_splittable[u] = true;
 973
 974         edge ec[2], eOrig[2];
 975         PlanRepExpansion::nodeSplit nsplit[2];
 976         int i = 0;
 977         edge e;
 978         forall_adj_edges(e,u)
 979                 if(e->source() == u) {
 980                         ec    [i] = e;
 981                         eOrig [i] = m_eOrig[e];
 982                         nsplit[i] = m_eNodeSplit[e];
 983                         ++i;
 984                 }
 985
 986         List<edge> &path_0 = (eOrig[0] != 0) ? m_eCopy[eOrig[0]] : nsplit[0]->m_path;
 987         if(m_vOrig[path_0.front()->source()] == vOrig)
 988                 path_0.split(m_eIterator[ec[0]], ns_0->m_path, path_0);
 989         else
 990                 path_0.split(m_eIterator[ec[0]], path_0, ns_0->m_path);
 991
 992         ListConstIterator<edge> itE;
 993         for(itE = ns_0->m_path.begin(); itE.valid(); ++itE) {
 994                 m_eNodeSplit[*itE] = ns_0;
 995                 m_eOrig     [*itE] = 0;
 996         }
 997
 998         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
 999         nodeSplit ns_1 = &(*itNS);
1000         ns_1->m_nsIterator = itNS;
1001
1002         List<edge> &path_1 = (eOrig[1] != 0) ? m_eCopy[eOrig[1]] : nsplit[1]->m_path;
1003         if(m_vOrig[path_1.front()->source()] == vOrig)
1004                 path_1.split(m_eIterator[ec[1]], ns_1->m_path, path_1);
1005         else
1006                 path_1.split(m_eIterator[ec[1]], path_1, ns_1->m_path);
1007
1008         for(itE = ns_1->m_path.begin(); itE.valid(); ++itE) {
1009                 m_eNodeSplit[*itE] = ns_1;
1010                 m_eOrig     [*itE] = 0;
1011         }
1012
1013         return ns_1;
1014 }
1015
1016
1017 edge PlanRepExpansion::separateDummy(
1018         adjEntry adj_1, adjEntry adj_2, node vStraight, bool isSrc)
1019 {
1020         node u = adj_1->theNode();
1021         OGDF_ASSERT(m_vOrig[u] == 0);
1022
1023         node vOrig = m_vOrig[vStraight];
1024         node v = newNode();
1025
1026         m_vOrig     [v] = vOrig;
1027         m_vIterator [v] = m_vCopy[vOrig].pushBack(v);
1028         m_splittable[v] = true;
1029
1030         if(adj_1->theEdge()->target() == u)
1031                 moveTarget(adj_1->theEdge(),v);
1032         else
1033                 moveSource(adj_1->theEdge(),v);
1034
1035         if(adj_2->theEdge()->target() == u)
1036                 moveTarget(adj_2->theEdge(),v);
1037         else
1038                 moveSource(adj_2->theEdge(),v);
1039
1040         edge eNew = (isSrc) ? newEdge(v,u) : newEdge(u,v);
1041
1042         ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
1043         nodeSplit nsNew = &(*itNS);
1044         nsNew->m_nsIterator = itNS;
1045
1046         edge       eOrig = m_eOrig[adj_1->theEdge()];
1047         NodeSplit *ns    = m_eNodeSplit[adj_1->theEdge()];
1048         List<edge> &path = (eOrig != 0) ? m_eCopy[eOrig] : ns->m_path;
1049
1050         if(vStraight == path.front()->source()) {
1051                 ListIterator<edge> it, itNext;
1052                 for(it = path.begin(); (*it)->source() != v; it = itNext) {
1053                         itNext = it.succ();
1054                         path.moveToBack(it, nsNew->m_path);
1055                         m_eOrig     [*it] = 0;
1056                         m_eNodeSplit[*it] = nsNew;
1057                 }
1058
1059         } else {
1060                 ListIterator<edge> it, itPrev;
1061                 for(it = path.rbegin(); (*it)->target() != v; it = itPrev) {
1062                         itPrev = it.pred();
1063                         path.moveToFront(it, nsNew->m_path);
1064                         m_eOrig     [*it] = 0;
1065                         m_eNodeSplit[*it] = nsNew;
1066                 }
1067         }
1068
1069         return eNew;
1070
1071         //edge       eOrig = m_eOrig[adjStraight->theEdge()];
1072         //NodeSplit *ns    = m_eNodeSplit[adjStraight->theEdge()];
1073
1074         //Array<adjEntry> adjA(2), adjB(2);
1075         //int i = 0, j = 0;
1076
1077         //adjEntry adj;
1078         //forall_adj(adj,u) {
1079         //      edge e = adj->theEdge();
1080         //      if(m_eOrig[e] == eOrig && m_eNodeSplit[e] == ns)
1081         //              adjA[i++] = adj;
1082         //      else
1083         //              adjB[j++] = adj;
1084         //}
1085
1086         //OGDF_ASSERT(i == 2 && j == 2);
1087
1088         //// resolve split on adjB
1089         //edge eB = adjB[0]->theEdge();
1090         //node vB = adjB[1]->twinNode();
1091
1092         //edge eOrigB;
1093         //NodeSplit *nsB;
1094         //List<edge> &pathB = (m_eOrig[eB] != 0) ? m_eCopy[m_eOrig[eB]] : m_eNodeSplit[eB]->m_path;
1095
1096         //if(eB->target() == u)
1097         //      moveTarget(eB,vB);
1098         //else
1099         //      moveSource(eB,vB);
1100
1101         //edge eB2 = adjB[1]->theEdge();
1102         //pathB.del(m_eIterator[eB2]);
1103         //delEdge(eB2);
1104
1105         //// split path at u
1106         //node vOrig = m_vOrig[vStraight];
1107
1108         //m_vOrig     [u] = vOrig;
1109         //m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
1110         //m_splittable[u] = true;
1111
1112         //ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
1113         //nodeSplit nsNew = &(*itNS);
1114         //nsNew->m_nsIterator = itNS;
1115
1116         //List<edge> &pathA = (eOrig != 0) ? m_eCopy[eOrig] : ns->m_path;
1117         //if(vStraight == pathA.front()->source()) {
1118         //      ListIterator<edge> it, itNext;
1119         //      for(it = pathA.begin(); (*it)->source() != u; it = itNext) {
1120         //              itNext = it.succ();
1121         //              pathA.moveToBack(it, nsNew->m_path);
1122         //              m_eOrig     [*it] = 0;
1123         //              m_eNodeSplit[*it] = nsNew;
1124         //      }
1125
1126         //} else {
1127         //      ListIterator<edge> it, itPrev;
1128         //      for(it = pathA.rbegin(); (*it)->target() != u; it = itPrev) {
1129         //              itPrev = it.pred();
1130         //              pathA.moveToFront(it, nsNew->m_path);
1131         //              m_eOrig     [*it] = 0;
1132         //              m_eNodeSplit[*it] = nsNew;
1133         //      }
1134         //}
1135 }
1136
1137
1138 int PlanRepExpansion::numberOfSplittedNodes() const
1139 {
1140         int num = 0;
1141
1142         node vOrig;
1143         forall_nodes(vOrig,*m_pGraph)
1144                 if(m_vCopy[vOrig].size() >= 2)
1145                         ++num;
1146
1147         return num;
1148 }
1149
1150
1151 bool PlanRepExpansion::isPseudoCrossing(node v) const
1152 {
1153         if(m_vOrig[v] != 0)
1154                 return false;
1155
1156         adjEntry adj_1 = v->firstAdj();
1157         adjEntry adj_2 = adj_1->succ();
1158         adjEntry adj_3 = adj_2->succ();
1159
1160         edge eOrig = m_eOrig[adj_2->theEdge()];
1161         nodeSplit ns = m_eNodeSplit[adj_2->theEdge()];
1162
1163         if(m_eNodeSplit[adj_1->theEdge()] == ns && m_eOrig[adj_1->theEdge()] == eOrig)
1164                 return true;
1165
1166         if(m_eNodeSplit[adj_3->theEdge()] == ns && m_eOrig[adj_3->theEdge()] == eOrig)
1167                 return true;
1168
1169         return false;
1170 }
1171
1172
1173 void PlanRepExpansion::resolvePseudoCrossing(node v)
1174 {
1175         OGDF_ASSERT(isPseudoCrossing(v));
1176
1177         edge eIn[2];
1178         int i = 0;
1179         edge e;
1180         forall_adj_edges(e,v) {
1181                 if(e->target() == v)
1182                         eIn[i++] = e;
1183         }
1184         OGDF_ASSERT(i == 2);
1185
1186         for(i = 0; i < 2; ++i) {
1187                 edge e = eIn[i];
1188
1189                 ListIterator<edge> it = m_eIterator[e];
1190                 List<edge> &path = (m_eOrig[e] != 0) ? m_eCopy[m_eOrig[e]] : m_eNodeSplit[e]->m_path;
1191
1192                 edge eNext = *(it.succ());
1193                 moveSource(eNext, e->source());
1194                 path.del(it);
1195                 delEdge(e);
1196         }
1197 }
1198
1199
1200
1201 } // end namespace ogdf