ext/OGDF/src/augmentation/PlanarAugmentation.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 planar biconnected augmentation approximation algorithm
  11  *
  12  * \author Bernd Zey
  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/augmentation/PlanarAugmentation.h>
  45
  46 #include <ogdf/basic/simple_graph_alg.h>
  47 #include <ogdf/basic/extended_graph_alg.h>
  48 #include <ogdf/decomposition/DynamicBCTree.h>
  49
  50
  51 // for debug-outputs
  52 //#define PLANAR_AUGMENTATION_DEBUG
  53
  54 // for checking planarity directly after inserting a new edge
  55 //   and additional planarity tests after each augmentation round
  56 //#define PLANAR_AUGMENTATION_DEBUG_PLANARCHECK
  57
  58
  59 namespace ogdf {
  60
  61
  62 /********************************************************
  63  *
  64  * implementation of class PALabel
  65  *
  66  *******************************************************/
  67
  68 void PALabel::removePendant(node pendant)
  69 {
  70         if (m_pendants.size() > 0){
  71                 ListIterator<node> it = m_pendants.begin();
  72                 for (; it.valid(); ++it)
  73                         if ((*it) == pendant){
  74                                 m_pendants.del(it);
  75                                 break;
  76                         }
  77         }
  78 }
  79
  80
  81 /********************************************************
  82  *
  83  * implementation of class PlanarAugmentation
  84  *
  85  *******************************************************/
  86
  87
  88 //      ----------------------------------------------------
  89 //      doCall
  90 //
  91 //  ----------------------------------------------------
  92 void PlanarAugmentation::doCall(Graph& g, List<edge>& L)
  93 {
  94         m_nPlanarityTests = 0;
  95
  96         L.clear();
  97         m_pResult = &L;
  98
  99         m_pGraph = &g;
 100
 101         #ifdef PLANAR_AUGMENTATION_DEBUG
 102                 cout << "Graph G has no self loops = " << isLoopFree(*m_pGraph) << endl;
 103                 cout << "Graph G is planar         = " << isPlanar(*m_pGraph)<< endl;
 104                 cout << "Graph G is connected      = " << isConnected(*m_pGraph) << endl;
 105                 cout << "Graph G is biconnected    = " << isBiconnected(*m_pGraph) << endl;
 106         #endif
 107
 108         // create the bc-tree
 109         if (m_pGraph->numberOfNodes() > 1){
 110
 111                 if (!isConnected(*m_pGraph)){
 112                         if(m_pGraph->numberOfEdges() == 0){
 113                                 // one edge is required
 114                                 m_pResult->pushBack(m_pGraph->newEdge(m_pGraph->firstNode(), m_pGraph->firstNode()->succ()));
 115                         }
 116
 117                         makeConnectedByPendants();
 118                 }
 119
 120                 m_pBCTree = new DynamicBCTree(*m_pGraph);
 121
 122                 // init the m_adjNonChildren-NodeArray with all adjEntries of the bc-tree
 123                 m_adjNonChildren.init(m_pBCTree->m_B);
 124
 125                 node v;
 126                 adjEntry adj;
 127                 forall_nodes(v, m_pBCTree->bcTree()){
 128                         if (v->firstAdj() != 0){
 129                                 m_adjNonChildren[v].pushFront(v->firstAdj());
 130                                 adj = v->firstAdj()->cyclicSucc();
 131                                 while (adj != v->firstAdj()){
 132                                         m_adjNonChildren[v].pushBack(adj);
 133                                         adj = adj->cyclicSucc();
 134                                 }
 135                         }
 136                 }
 137                 m_isLabel.init(m_pBCTree->bcTree(), 0);
 138                 m_belongsTo.init(m_pBCTree->bcTree(), 0);
 139
 140                 // call main function
 141                 augment();
 142         }
 143 }
 144
 145
 146
 147 //      ----------------------------------------------------
 148 //      makeConnectedByPendants()
 149 //
 150 //              makes graph connected by inserting edges between
 151 //                nodes of pendants of the connected components
 152 //
 153 //  ----------------------------------------------------
 154 void PlanarAugmentation::makeConnectedByPendants()
 155 {
 156         DynamicBCTree bcTreeTemp(*m_pGraph, true);
 157
 158         NodeArray<int> components;
 159         components.init(*m_pGraph, 0);
 160
 161         int compCnt = connectedComponents(*m_pGraph, components);
 162
 163         List<node> getConnected;
 164
 165         Array<bool> compConnected(compCnt);
 166         for (int i=0; i<compCnt; i++){
 167                 compConnected[i] = false;
 168         }
 169
 170         node v;
 171         forall_nodes(v, *m_pGraph){
 172                 if (v->degree() == 0){
 173                         // found a seperated node that will be connected
 174                         getConnected.pushBack(v);
 175                         compConnected[components[v]] = true;
 176                 }
 177         }
 178
 179         forall_nodes(v, *m_pGraph){
 180                 if ((compConnected[components[v]] == false) && (bcTreeTemp.bcproper(v)->degree() <= 1)){
 181                         // found a node that will be connected
 182                         getConnected.pushBack(v);
 183                         compConnected[components[v]] = true;
 184                 }
 185         }
 186
 187         ListIterator<node> it = getConnected.begin();
 188         ListIterator<node> itBefore = getConnected.begin();
 189         while (it.valid()){
 190                 if (it != itBefore){
 191                         // insert edge between it and itBefore
 192                         m_pResult->pushBack(m_pGraph->newEdge(*it, *itBefore));
 193                         itBefore++;
 194                 }
 195                 it++;
 196         }
 197 }
 198
 199
 200
 201 //      ----------------------------------------------------
 202 //      augment()
 203 //
 204 //              the main augmentation function
 205 //
 206 //  ----------------------------------------------------
 207 void PlanarAugmentation::augment()
 208 {
 209         node v, rootPendant = 0;
 210
 211         // first initialize the list of pendants
 212         forall_nodes(v, m_pBCTree->bcTree()){
 213                 if (v->degree() == 1){
 214                         #ifdef PLANAR_AUGMENTATION_DEBUG
 215                                 cout << "augment(): found pendant with index " << v->index();
 216                         #endif
 217                         if (m_pBCTree->parent(v) == 0){
 218                                 rootPendant = v;
 219                                 #ifdef PLANAR_AUGMENTATION_DEBUG
 220                                         cout << " is root! (also inserted into pendants-list!)" << endl << flush;
 221                                 #endif
 222                         }
 223                         else{
 224                                 #ifdef PLANAR_AUGMENTATION_DEBUG
 225                                         cout << endl << flush;
 226                                 #endif
 227                         }
 228                         m_pendants.pushBack(v);
 229                 }
 230         }
 231
 232         if (rootPendant != 0){
 233                 // the root of the bc-tree is also a pendant
 234                 // this has to be changed
 235
 236                 node bAdjNode = rootPendant->firstAdj()->twinNode();
 237
 238                 #ifdef PLANAR_AUGMENTATION_DEBUG
 239                         cout << "augment(): changing root in bc-tree because root is a pendant!" << endl << flush;
 240                         cout << "augment(): index of old root = " << rootPendant->index() << ", new root = " << bAdjNode->index() << endl << flush;
 241                 #endif
 242
 243                 // modify the bc-tree-structure
 244                 modifyBCRoot(rootPendant, bAdjNode);
 245         }
 246
 247         // call reduceChain for all pendants
 248         if (m_pendants.size() > 1){
 249                 ListIterator<node> it = m_pendants.begin();
 250                 for (; it.valid(); ++it){
 251                         reduceChain((*it));
 252                 }
 253         }
 254
 255         // it can appear that reduceChain() inserts some edges
 256         //  in case of non-planarity (paPlanarity)
 257         // so there are new pendants and obsolete pendants
 258         //  the obsolete pendants are collected in m_pendantsToDel
 259         if (m_pendantsToDel.size() > 0){
 260                 ListIterator<node> delIt = m_pendantsToDel.begin();
 261                 for (; delIt.valid(); delIt = m_pendantsToDel.begin()){
 262                         deletePendant(*delIt);
 263                         m_pendantsToDel.del(delIt);
 264                 }
 265         }
 266
 267         #ifdef PLANAR_AUGMENTATION_DEBUG
 268                 cout << "augment(): after reduceChain() for every pendant:" << endl;
 269                 cout << "           #labels = " << m_labels.size() << endl;
 270                 cout << "           #pendants = " << m_pendants.size() << endl << endl;
 271                 cout << "STARTING MAIN LOOP:" << endl;
 272                 cout << endl << flush;
 273         #endif
 274
 275         // main loop
 276         while(!m_labels.empty()){
 277                 // foundMatching indicates if there are 2 labels that can be connected
 278                 bool foundMatching;
 279                 // labels first and second are going to be computed by findMatching
 280                 // and foundMatching=true or foundMatching=false
 281                 // first is always != 0 after findMatching(...)
 282                 pa_label first, second = 0;
 283
 284                 foundMatching = findMatching(first, second);
 285
 286                 // no matching labels were found
 287                 if (!foundMatching){
 288
 289                         // we have only one label
 290                         if (m_labels.size() == 1){
 291
 292                                 if (m_pendants.size() > 1)
 293                                         //m_labels.size() == 1 &&  m_pendants.size() > 1
 294                                         // join the pendants of this label
 295                                         joinPendants(first);
 296                                 else{
 297                                         //m_labels.size() == 1 &&  m_pendants.size() == 1
 298                                         connectInsideLabel(first);
 299                                 }
 300                         }
 301                         else{
 302                                 // m_labels.size() > 1
 303
 304                                 if (first->size() == 1){
 305                                         // m_labels.size() > 1 && first->size() == 1
 306                                         // connect the
 307                                         connectInsideLabel(first);
 308                                 }
 309                                 else{
 310                                         // m_labels.size() > 1 && first->size() > 1
 311                                         // so connect all pendants of label first
 312                                         joinPendants(first);
 313                                 }
 314                         }
 315                 }
 316                 else{
 317
 318                         // foundMatching == true
 319                         connectLabels(first, second);
 320                 }
 321
 322                 // output after each round:
 323                 #ifdef PLANAR_AUGMENTATION_DEBUG
 324                         cout << endl << "augment(): output after one round:" << endl;
 325                         cout         << "           #labels   = " << m_labels.size() << endl;
 326                         cout         << "           #pendants = " << m_pendants.size() << endl;
 327                         #ifdef PLANAR_AUGMENTATION_DEBUG_PLANARCHECK
 328                                 cout << "graph is planar == " << isPlanar(*m_pGraph) << endl;
 329                                 cout << "graph is biconnected == " << isBiconnected(*m_pGraph) << endl;
 330                         #endif
 331                         cout << endl << flush;
 332
 333                         ListIterator<pa_label> labelIt = m_labels.begin();
 334                         int pos = 1;
 335                         for (; labelIt.valid(); labelIt++){
 336                                 cout << "pos " << pos << ": ";
 337                                 if ((m_isLabel[(*labelIt)->parent()]).valid())
 338                                         cout << " OK, parent-index = " << (*labelIt)->parent()->index()
 339                                                 << ", size = " << (*labelIt)->size() << endl << flush;
 340                                 else
 341                                         cout << " ERROR, parent-index = " << (*labelIt)->parent()->index()
 342                                                 << ", size = " << (*labelIt)->size()<< endl << flush;
 343
 344                                 pos++;
 345                         }
 346                         cout << endl << flush;
 347                 #endif
 348                 // : output after each round
 349
 350         }//main loop
 351
 352         #ifdef PLANAR_AUGMENTATION_DEBUG
 353                 cout << endl << "FINISHED MAIN LOOP" << endl << endl;
 354                 cout << "# planarity tests = " << m_nPlanarityTests << endl;
 355                 #ifdef PLANAR_AUGMENTATION_DEBUG_PLANARITY
 356                         cout << "resulting Graph is biconnected = " << isBiconnected(*m_pGraph) << endl;
 357                         cout << "resulting Graph is planar = " << isPlanar(*m_pGraph) << endl;
 358                 #endif
 359                 cout << endl << flush;
 360         #endif
 361
 362         terminate();
 363 }
 364
 365
 366
 367 //      ----------------------------------------------------
 368 //      reduceChain(node p, label labelOld)
 369 //
 370 //              finds the "parent" (->label) for a pendant p of the BC-Tree
 371 //               and creates a new label or inserts the pendant to another
 372 //           label
 373 //              reduceChain can also insert edges in case of paPlanarity
 374 //
 375 //  ----------------------------------------------------
 376 void PlanarAugmentation::reduceChain(node p, pa_label labelOld)
 377 {
 378         #ifdef PLANAR_AUGMENTATION_DEBUG
 379                 cout << "reduceChain(" << p->index() << ")";
 380         #endif
 381
 382         // parent = parent of p in the BC-Tree
 383         // if p is the root, then parent == 0
 384         node parent = m_pBCTree->DynamicBCTree::parent(p);
 385
 386         // last is going to be the last cutvertex in the computation of followPath()
 387         node last;
 388         paStopCause stopCause;
 389
 390         // traverse from parent to the root of the bc-tree and check several
 391         // conditions. last is going to be the last cutvertex on this path
 392         stopCause = followPath(parent, last);
 393
 394         #ifdef PLANAR_AUGMENTATION_DEBUG
 395                 cout << ", stopCause == ";
 396                 switch(stopCause){
 397                         case paPlanarity:
 398                                 cout << "paPlanarity" << endl << flush;
 399                                 break;
 400                         case paCDegree:
 401                                 cout << "paCDegree" << endl << flush;
 402                                 break;
 403                         case paBDegree:
 404                                 cout << "paBDegree" << endl << flush;
 405                                 break;
 406                         case paRoot:
 407                                 cout << "paRoot" << endl << flush;
 408                                 break;
 409                 }
 410         #endif
 411
 412
 413         if (stopCause == paPlanarity){
 414                 node adjToCutP    = adjToCutvertex(p);
 415                 node adjToCutLast = adjToCutvertex(m_pBCTree->DynamicBCTree::parent(last), last);
 416
 417                 // computes path in bc-tree between bcproper(adjToCutP) and bcproper(adjToCutLast)
 418                 SList<node>& path = m_pBCTree->findPath(adjToCutP, adjToCutLast);
 419
 420                 #ifdef PLANAR_AUGMENTATION_DEBUG
 421                         cout << "reduceChain(): inserting edge between " << adjToCutP->index()
 422                                  << " and " << adjToCutLast->index() << endl << flush;
 423                 #endif
 424
 425                 // create new edge
 426                 edge e = m_pGraph->newEdge(adjToCutP, adjToCutLast);
 427
 428                 // insert the edge into the result-list
 429                 m_pResult->pushBack(e);
 430
 431                 // update the bc-Tree with new edge
 432                 m_pBCTree->updateInsertedEdge(e);
 433
 434                 // find the new arised pendant
 435                 node newPendant = m_pBCTree->find(p);
 436
 437                 if (newPendant != p){
 438                         // delete the old pendant
 439                         // cannot delete the pendant immediatly
 440                         // because that would affect the outer loop in augment()
 441                         m_pendantsToDel.pushBack(p);
 442                         // insert the new arised pendant
 443                         // at the front of m_pendants becuse that doesn't affect the outer loop in augment()
 444                         m_pendants.pushFront(newPendant);
 445                 }
 446
 447                 // updating m_adjNonChildren
 448                 updateAdjNonChildren(newPendant, path);
 449
 450                 // check if newPendant is the new root of the bc-tree
 451                 if (m_pBCTree->DynamicBCTree::parent(newPendant) == 0){
 452                         #ifdef PLANAR_AUGMENTATION_DEBUG
 453                                 cout << "reduceChain(): new arised pendant is the new root of the bc-tree, it has degree "
 454                                          << m_pBCTree->m_bNode_degree[newPendant] << endl << flush;
 455                         #endif
 456
 457                         node newRoot = (*(m_adjNonChildren[newPendant].begin()))->twinNode();
 458
 459                          // modify bc-tree-structure
 460                          modifyBCRoot(newPendant, newRoot);
 461                 }
 462
 463                 delete(&path);
 464
 465                 // delete label if necessary
 466                 if (labelOld != 0){
 467                         deleteLabel(labelOld);
 468                 }
 469
 470                 #ifdef PLANAR_AUGMENTATION_DEBUG
 471                         cout << "reduceChain(): calling reduceChain() with newPendant = " << newPendant->index() << endl << flush;
 472                 #endif
 473
 474                 // call reduceChain with the new arised pendant
 475                 reduceChain(newPendant);
 476         }
 477
 478         pa_label l;
 479
 480         if (stopCause == paCDegree || stopCause == paRoot){
 481
 482                 if (labelOld != 0){
 483                         if (labelOld->head() == last){
 484                                 // set the stop-cause
 485                                 labelOld->stopCause(stopCause);
 486                         }
 487                         else
 488                                 deleteLabel(labelOld);
 489                 }
 490
 491                 if (m_isLabel[last].valid()){
 492                         // l is the label that last is the head of
 493                         l = *(m_isLabel[last]);
 494                         // add the actual pendant p to l
 495                         addPendant(p, l);
 496                         // set the stop-cause
 497                         l->stopCause(stopCause);
 498                 }
 499                 else{
 500                         newLabel(last, p, stopCause);
 501                 }
 502         }
 503
 504         if (stopCause == paBDegree){
 505                 if (labelOld != 0){
 506                         if (labelOld->head() != last){
 507                                 deleteLabel(labelOld);
 508                                 newLabel(last, p, paBDegree);
 509                         }
 510                         else{
 511                                 labelOld->stopCause(paBDegree);
 512                         }
 513                 }
 514                 else{
 515                         newLabel(last, p, paBDegree);
 516                 }
 517         }
 518 } // reduceChain()
 519
 520
 521
 522 //      ----------------------------------------------------
 523 //      followPath(node v, node &last)
 524 //
 525 //              traverses the BC-Tree upwards from v
 526 //                (v is always a parent of a pendant)
 527 //              last becomes the last cutvertex before we return
 528 //
 529 //  ----------------------------------------------------
 530 paStopCause PlanarAugmentation::followPath(node v, node& last)
 531 {
 532         last = 0;
 533         node bcNode = m_pBCTree->find(v);
 534
 535         if (m_pBCTree->typeOfBNode(bcNode) == BCTree::CComp){
 536                 last = bcNode;
 537         }
 538
 539         while (bcNode != 0){
 540                 int deg = m_pBCTree->m_bNode_degree[bcNode];
 541
 542                 if (deg > 2){
 543                         if (m_pBCTree->typeOfBNode(bcNode) == BCTree::CComp){
 544                                 last = bcNode;
 545                                 return paCDegree;
 546                         }
 547                         else
 548                                 return paBDegree;
 549                 }
 550
 551                 // deg == 2 (case deg < 2 cannot occur)
 552                 if (m_pBCTree->typeOfBNode(bcNode) == BCTree::CComp){
 553                         last = bcNode;
 554                 }
 555                 else{
 556                         // bcNode is a BComp and degree is 2
 557                         if (m_pBCTree->numberOfNodes(bcNode) > 4){
 558                                 // check planarity if number of nodes > 4
 559                                 // because only than a K5- or k33-Subdivision can be included
 560
 561                                 node adjBCNode = 0;
 562
 563                                 bool found = false;
 564                                 SListIterator<adjEntry> childIt = m_adjNonChildren[bcNode].begin();
 565                                 while (!found && childIt.valid()){
 566                                         if (m_pBCTree->find((*childIt)->twinNode()) != last){
 567                                                 found = true;
 568                                                 adjBCNode = m_pBCTree->find((*childIt)->twinNode());
 569                                         }
 570                                         childIt++;
 571                                 }
 572
 573                                 // get nodes in biconnected-components graph of m_pBCTree
 574                                 node hNode = m_pBCTree->m_bNode_hRefNode[last];
 575                                 node hNode2 = m_pBCTree->m_bNode_hRefNode[adjBCNode];
 576
 577                                 // check planarity for corresponding graph-nodes of hNode and hNode2
 578                                 if (!planarityCheck(m_pBCTree->m_hNode_gNode[hNode],
 579                                                                         m_pBCTree->m_hNode_gNode[hNode2])){
 580                                         return paPlanarity;
 581                                 }
 582                         }
 583                 }
 584                 // iterate to parent node
 585                 bcNode = m_pBCTree->DynamicBCTree::parent(bcNode);
 586         }
 587         // reached the bc-tree-root
 588         return paRoot;
 589 }
 590
 591
 592
 593 //      ----------------------------------------------------
 594 //      planarityCheck(node v1, node v2)
 595 //
 596 //              checks planarity for the new edge (v1, v2)
 597 //               v1 and v2 are nodes in the original graph
 598 //
 599 //  ----------------------------------------------------
 600 bool PlanarAugmentation::planarityCheck(node v1, node v2)
 601 {
 602         // first simple tests
 603         if (v1 == v2){
 604                 return true;
 605         }
 606
 607         // check if edge (v1, v2) already exists
 608         if (v1->firstAdj()->twinNode() == v2){
 609                 return true;
 610         }
 611         adjEntry adjTest = v1->firstAdj()->cyclicSucc();
 612         while (adjTest != v1->firstAdj()){
 613                 if (v1->firstAdj()->twinNode() == v2){
 614                         return true;
 615                 }
 616                 adjTest = adjTest->cyclicSucc();
 617         }
 618
 619         // test planarity for edge (v1, v2)
 620         edge e = m_pGraph->newEdge(v1, v2);
 621
 622         m_nPlanarityTests++;
 623
 624         bool planar = planarEmbed(*m_pGraph);
 625
 626         // finally delete the edge
 627         m_pGraph->delEdge(e);
 628
 629         return planar;
 630 }
 631
 632
 633
 634 //      ----------------------------------------------------
 635 //      adjToCutvertex(node v, node cutvertex)
 636 //
 637 //              returns the vertex in the original graph that
 638 //       belongs to v (B-Component in the BC-Graph and pendant)
 639 //       and is adjacent to the cutvertex (also node of the BC-Graph)
 640 //              if cutvertex == 0 then the cutvertex of the parent of v
 641 //               is considered
 642 //
 643 //  ----------------------------------------------------
 644 node PlanarAugmentation::adjToCutvertex(node v, node cutvertex)
 645 {
 646         node nodeAdjToCutVertex;
 647
 648         if (cutvertex == 0){
 649
 650                 // set nodeAdjToCutVertex to the node in the original graph,
 651                 //  that corresponds to the parent (c-component) of v in the bc-tree
 652                 nodeAdjToCutVertex = m_pBCTree->m_hNode_gNode[m_pBCTree->m_bNode_hParNode[v]];
 653
 654                 // adj = adjEntry at the cutvertex
 655                 adjEntry adj = nodeAdjToCutVertex->firstAdj();
 656
 657                 while (m_pBCTree->DynamicBCTree::bcproper(adj->twinNode()) != v)
 658                         adj = adj->cyclicSucc();
 659
 660                 nodeAdjToCutVertex = adj->twinNode();
 661
 662         }
 663         else{
 664                 // set nodeAdjToCutVertex to the node in the original graph,
 665                 //  corresponding to the cutvertex in the bc-tree
 666                 nodeAdjToCutVertex = m_pBCTree->m_hNode_gNode[m_pBCTree->m_bNode_hRefNode[cutvertex]];
 667
 668                 // adj = adjEntry at the cutvertex
 669                 adjEntry adj = nodeAdjToCutVertex->firstAdj();
 670
 671                 bool found = false;
 672
 673                 if (m_pBCTree->bComponent(nodeAdjToCutVertex, adj->twinNode()) == v){
 674                         found = true;
 675                         nodeAdjToCutVertex = adj->twinNode();
 676                 }
 677                 else{
 678                         adj = adj->cyclicSucc();
 679                         while ((!found) && (adj != nodeAdjToCutVertex->firstAdj())){
 680                                 if (m_pBCTree->bComponent(nodeAdjToCutVertex, adj->twinNode()) == v){
 681                                         nodeAdjToCutVertex = adj->twinNode();
 682                                         found = true;
 683                                 }
 684                                 adj = adj->cyclicSucc();
 685                         }
 686                 }
 687         }
 688         return nodeAdjToCutVertex;
 689 }
 690
 691
 692
 693 //      ----------------------------------------------------
 694 //      findLastBefore(node pendant, node ancestor)
 695 //
 696 //              returns the last vertex before ancestor
 697 //                on the path from pendant to ancestor
 698 //
 699 //  ----------------------------------------------------
 700 node PlanarAugmentation::findLastBefore(node pendant, node ancestor)
 701 {
 702         node bcNode = pendant;
 703         while ((bcNode) && (m_pBCTree->DynamicBCTree::parent(bcNode) != ancestor))
 704                 bcNode = m_pBCTree->DynamicBCTree::parent(bcNode);
 705
 706         if (!bcNode){
 707                 // should never occur
 708                 return 0;
 709         }
 710
 711         return bcNode;
 712 }
 713
 714
 715
 716 //      ----------------------------------------------------
 717 //      deletePendant(node p)
 718 //
 719 //              deletes pendant p from the list of all pendants
 720 //              deletes p also from the label it belongs to
 721 //
 722 //  ----------------------------------------------------
 723 void PlanarAugmentation::deletePendant(node p, bool removeFromLabel)
 724 {
 725         ListIterator<node> mPendantsIt = m_pendants.begin();
 726
 727         bool deleted = false;
 728         while (!deleted && mPendantsIt.valid()){
 729                 ListIterator<node> itSucc = mPendantsIt.succ();
 730                 if ((*mPendantsIt) == p){
 731                         m_pendants.del(mPendantsIt);
 732                         deleted = true;
 733                 }
 734                 mPendantsIt = itSucc;
 735         }
 736
 737         if ((removeFromLabel) && (m_belongsTo[p] != 0)){
 738                 (m_belongsTo[p])->removePendant(p);
 739                 m_belongsTo[p] = 0;
 740         }
 741 }
 742
 743
 744
 745 //      ----------------------------------------------------
 746 //      removeAllPendants(label& l)
 747 //
 748 //              deletes a label
 749 //              and - if desired - removes the pendants belonging to l
 750 //
 751 //  ----------------------------------------------------
 752 void PlanarAugmentation::removeAllPendants(pa_label& l)
 753 {
 754         while (l->size() > 0){
 755                 m_belongsTo[l->getFirstPendant()] = 0;
 756                 l->removeFirstPendant();
 757         }
 758 }
 759
 760
 761
 762 //      ----------------------------------------------------
 763 //      addPendant(pa_label& l, node pendant)
 764 //
 765 //              adds a pendant p to a label l
 766 //              re-inserts also l to m_labels
 767 //
 768 //  ----------------------------------------------------
 769 void PlanarAugmentation::addPendant(node p, pa_label& l)
 770 {
 771         m_belongsTo[p] = l;
 772         l->addPendant(p);
 773
 774         node newParent = m_pBCTree->find(l->parent());
 775
 776         m_labels.del(m_isLabel[l->parent()]);
 777         m_isLabel[newParent] = insertLabel(l);
 778 }
 779
 780
 781
 782 //      ----------------------------------------------------
 783 //      joinPendants(pa_label& l)
 784 //
 785 //              connects all pendants of the label
 786 //
 787 //  ----------------------------------------------------
 788 void PlanarAugmentation::joinPendants(pa_label& l)
 789 {
 790         #ifdef PLANAR_AUGMENTATION_DEBUG
 791                 cout << "joinPendants(): l->size()==" << l->size() << endl << flush;
 792         #endif
 793
 794         node pendant1 = l->getFirstPendant();
 795         // delete pendant from m_pendants but not from the label it belongs to
 796         deletePendant(pendant1, false);
 797
 798         SList<edge> newEdges;
 799
 800         // traverse through pendant-list and connect them
 801         ListIterator<node> pendantIt = (l->m_pendants).begin();
 802         while (pendantIt.valid()){
 803
 804                 if (*pendantIt != pendant1){
 805
 806                         // delete pendant from m_pendants but not from the label it belongs to
 807                         deletePendant(*pendantIt, false);
 808
 809                         #ifdef PLANAR_AUGMENTATION_DEBUG
 810                                 cout << "joinPendants(): connectPendants: " << pendant1->index()
 811                                         << " and " << (*pendantIt)->index() << endl << flush;
 812                         #endif
 813
 814                         // connect pendants and insert edge in newEdges
 815                         newEdges.pushBack(connectPendants(pendant1, *pendantIt));
 816
 817                         // iterate pendant1
 818                         pendant1 = *pendantIt;
 819                 }
 820                 pendantIt++;
 821         }
 822
 823         // update new edges
 824         updateNewEdges(newEdges);
 825
 826         removeAllPendants(l);
 827
 828         SListIterator<edge> edgeIt = newEdges.begin();
 829         node newBlock = (m_pBCTree->DynamicBCTree::bcproper(*edgeIt));
 830         if (m_pBCTree->m_bNode_degree[newBlock] == 1){
 831                 #ifdef PLANAR_AUGMENTATION_DEBUG
 832                         cout << "joinPendants(): new block " << newBlock->index() << " has degree 1 " << endl << flush;
 833                 #endif
 834
 835                 m_belongsTo[newBlock] = l;
 836                 addPendant(newBlock, l);
 837                 m_pendants.pushBack(newBlock);
 838
 839         }
 840         else{
 841                 #ifdef PLANAR_AUGMENTATION_DEBUG
 842                         cout << "joinPendants(): new block has degree " << m_pBCTree->m_bNode_degree[newBlock] << endl << flush;
 843                 #endif
 844                 deleteLabel(l);
 845         }
 846 }
 847
 848
 849
 850 //      ----------------------------------------------------
 851 //      connectInsideLabel(label& l)
 852 //
 853 //              connects the only pendant of l with
 854 //                a computed "ancestor"
 855 //
 856 //  ----------------------------------------------------
 857 void PlanarAugmentation::connectInsideLabel(pa_label& l)
 858 {
 859         #ifdef PLANAR_AUGMENTATION_DEBUG
 860                 cout << "connectInsideLabel(): l->size() == " << l->size() << ", parent = " << l->parent()->index()
 861                          << ", head = " << l->head()->index() << endl << flush;
 862         #endif
 863
 864         node head = l->head();
 865         node pendant = l->getFirstPendant();
 866
 867         node ancestor = m_pBCTree->DynamicBCTree::parent(head);
 868
 869         node v1 = adjToCutvertex(pendant);
 870
 871         // check if head is the root of the BC-Tree
 872         if (ancestor == 0){
 873                 node wrongAncestor = findLastBefore(pendant, head);
 874
 875                 SListIterator<adjEntry> adjIt = m_adjNonChildren[head].begin();
 876                 bool found = false;
 877                 while ((!found) && (adjIt.valid())){
 878
 879                         if (m_pBCTree->find((*adjIt)->twinNode()) != wrongAncestor){
 880                                 ancestor = m_pBCTree->find((*adjIt)->twinNode());
 881                                 found = true;
 882                         }
 883                         adjIt++;
 884                 }
 885         }
 886
 887         node v2 = adjToCutvertex(ancestor, head);
 888
 889         #ifdef PLANAR_AUGMENTATION_DEBUG
 890                 cout << "connectInsideLabel(): inserting edge between " << v1->index() << " and " << v2->index() << endl << flush;
 891         #endif
 892
 893         SList<edge> newEdges;
 894         edge e = m_pGraph->newEdge(v1, v2);
 895         newEdges.pushFront(e);
 896
 897         #ifdef PLANAR_AUGMENTATION_DEBUG_PLANARCHECK
 898                 if (!isPlanar(*m_pGraph))
 899                         cout << "connectInsideLabel(): CRITICAL ERROR!!! inserted non-planar edge!!! (in connectInsideLabel())" << endl << flush;
 900         #endif
 901
 902         updateNewEdges(newEdges);
 903
 904         node newBlock = m_pBCTree->DynamicBCTree::bcproper(e);
 905
 906         // delete label l, and also the pendant
 907         deleteLabel(l);
 908
 909         if (m_pBCTree->m_bNode_degree[newBlock] == 1){
 910                 #ifdef PLANAR_AUGMENTATION_DEBUG
 911                         cout << "connectInsideLabel(): new block " << newBlock->index() << " has degree 1... calling reduceChain() ";
 912                 #endif
 913                 m_pendants.pushBack(newBlock);
 914                 if ((m_belongsTo[newBlock] != 0) && (m_belongsTo[newBlock]->size() == 1)){
 915                         reduceChain(newBlock, m_belongsTo[newBlock]);
 916                 }
 917                 else{
 918                         reduceChain(newBlock);
 919                         // it can appear that reduceChain() inserts some edges
 920                         // so there are new pendants and obsolete pendants
 921                         //  the obsolete pendants are collected in m_pendantsToDel
 922                         if (m_pendantsToDel.size() > 0){
 923                                 ListIterator<node> delIt = m_pendantsToDel.begin();
 924                                 for (; delIt.valid(); delIt = m_pendantsToDel.begin()){
 925                                         deletePendant(*delIt);
 926                                         m_pendantsToDel.del(delIt);
 927                                 }
 928                         }
 929                 }
 930         }
 931 }
 932
 933
 934
 935 //      ----------------------------------------------------
 936 //      connectPendants(node pendant1, node pendant2)
 937 //
 938 //              connects the two pendants with a new edge
 939 //
 940 //  ----------------------------------------------------
 941 edge PlanarAugmentation::connectPendants(node pendant1, node pendant2)
 942 {
 943         node v1 = adjToCutvertex(pendant1);
 944         node v2 = adjToCutvertex(pendant2);
 945
 946         #ifdef PLANAR_AUGMENTATION_DEBUG
 947                 cout << "connectPendants(): inserting edge between " << v1->index() << " and " << v2->index() << endl << flush;
 948         #endif
 949
 950         edge e = m_pGraph->newEdge(v1, v2);
 951
 952         #ifdef PLANAR_AUGMENTATION_DEBUG_PLANARCHECK
 953                 if (!(isPlanar(*m_pGraph)))
 954                         cout << "connectLabels(): CRITICAL ERROR in connectPendants: inserted edge is not planar!!!" << endl << flush;
 955         #endif
 956
 957         return e;
 958 }
 959
 960
 961
 962 //      ----------------------------------------------------
 963 //      insertLabel(pa_label l)
 964 //
 965 //              inserts a label l at the correct position in the list
 966 //
 967 //  ----------------------------------------------------
 968 ListIterator<pa_label> PlanarAugmentation::insertLabel(pa_label l)
 969 {
 970         if (m_labels.size() == 0){
 971                 return m_labels.pushFront(l);
 972         }
 973         else{
 974                 ListIterator<pa_label> it = m_labels.begin();
 975                 while (it.valid() && ((*it)->size() > l->size())){
 976                         it++;
 977                 }
 978                 if (!it.valid())
 979                         return m_labels.pushBack(l);
 980                 else
 981                         return m_labels.insert(l, it, before);
 982         }
 983 }
 984
 985
 986
 987 //      ----------------------------------------------------
 988 //      deleteLabel(pa_label& l, bool removePendants)
 989 //
 990 //              deletes a label
 991 //              and - if desired - removes the pendants belonging to l
 992 //
 993 //  ----------------------------------------------------
 994 void PlanarAugmentation::deleteLabel(pa_label& l, bool removePendants)
 995 {
 996         ListIterator<pa_label> labelIt = m_isLabel[l->parent()];
 997
 998         m_labels.del(labelIt);
 999         m_isLabel[l->parent()] = 0;
1000
1001         ListIterator<node> pendantIt = (l->m_pendants).begin();
1002         while (pendantIt.valid()){
1003                 m_belongsTo[*pendantIt] = 0;
1004                 pendantIt++;
1005         }
1006
1007         if (removePendants){
1008                 pendantIt = (l->m_pendants).begin();
1009                 while (pendantIt.valid()){
1010
1011                         ListIterator<node> mPendantsIt = m_pendants.begin();
1012
1013                         bool deleted = false;
1014                         while (!deleted && mPendantsIt.valid()){
1015                                 ListIterator<node> itSucc = mPendantsIt.succ();
1016                                 if ((*mPendantsIt) == *pendantIt){
1017                                         m_pendants.del(mPendantsIt);
1018                                         deleted = true;
1019                                 }
1020                                 mPendantsIt = itSucc;
1021                         }
1022                         pendantIt++;
1023                 }
1024         }
1025
1026         delete(l);
1027         l = 0;
1028 }
1029
1030
1031
1032 //      ----------------------------------------------------
1033 //      connectLabels(pa_label first, pa_label second);
1034 //
1035 //              connects the pendants of first with the pendants
1036 //                of second.
1037 //              first.size() >= second.size()
1038 //
1039 //  ----------------------------------------------------
1040 void PlanarAugmentation::connectLabels(pa_label first, pa_label second)
1041 {
1042         ListIterator<node> pendantIt;
1043
1044         #ifdef PLANAR_AUGMENTATION_DEBUG
1045                 cout << "connectLabels(), first->size()=="<< first->size() << " , second->size()=="
1046                         << second->size() << endl << flush;
1047
1048                 pendantIt = (first->m_pendants).begin();
1049                 cout << "connectLabels(): label first = ";
1050                 for (; pendantIt.valid(); pendantIt++){
1051                         cout << (*pendantIt)->index() << ", ";
1052                 }
1053                 pendantIt = (second->m_pendants).begin();
1054                 cout << " || " << endl << "label second = ";
1055                 for (; pendantIt.valid(); pendantIt++){
1056                         cout << (*pendantIt)->index() << ", ";
1057                 }
1058                 cout << endl << flush;
1059         #endif
1060
1061         SList<edge> newEdges;
1062         pendantIt = (second->m_pendants).begin();
1063
1064         // stores the pendants of label first that were connected
1065         // because first.size() => second.size()
1066         SList<node> getConnected;
1067         node v2;
1068         int n = 0;
1069
1070         while (pendantIt.valid()){
1071                 v2 = first->getPendant(n);
1072                 getConnected.pushBack(v2);
1073                 newEdges.pushBack(connectPendants(v2, *pendantIt));
1074
1075                 #ifdef PLANAR_AUGMENTATION_DEBUG_PLANARCHECK
1076                         if (!(isPlanar(*m_pGraph)))
1077                                 cout << "connectLabels(): CRITICAL ERROR: inserted edge is not planar!!!" << endl << flush;
1078                 #endif
1079
1080                 n++;
1081                 pendantIt++;
1082         }
1083
1084         updateNewEdges(newEdges);
1085         deleteLabel(second);
1086
1087         node newBlock = m_pBCTree->DynamicBCTree::bcproper(newEdges.front());
1088         #ifdef PLANAR_AUGMENTATION_DEBUG
1089                 cout << "connectLabels(): newBlock->index() == " << newBlock->index() << ", degree == "
1090                          << m_pBCTree->m_bNode_degree[newBlock] << endl << flush;
1091         #endif
1092
1093         SListIterator<node> pendantIt2 = getConnected.begin();
1094         while (pendantIt2.valid()){
1095
1096                 //first->removePendant(*pendantIt2);
1097                 deletePendant(*pendantIt2);
1098
1099                 pendantIt2++;
1100         }
1101
1102         if (first->size() != 0){
1103                 m_labels.del(m_isLabel[first->parent()]);
1104                 m_isLabel[m_pBCTree->find(first->parent())] = insertLabel(first);
1105
1106                 pendantIt = (first->m_pendants).begin();
1107                 for (; pendantIt.valid(); pendantIt++){
1108                         m_belongsTo[m_pBCTree->find(*pendantIt)] = first;
1109                 }
1110         }
1111         else{   // first->size() == 0
1112                 deleteLabel(first);
1113         }
1114
1115         if (m_pBCTree->m_bNode_degree[newBlock] == 1){
1116
1117                 #ifdef PLANAR_AUGMENTATION_DEBUG
1118                         cout << "connectLabels(): m_bNode_degree[" << newBlock->index() << "] == 1... calling reduceChain()" << endl << flush;
1119                 #endif
1120
1121                 m_pendants.pushBack(newBlock);
1122
1123                 if ((m_belongsTo[newBlock] != 0) && (m_belongsTo[newBlock]->size() == 1)){
1124                         reduceChain(newBlock, m_belongsTo[newBlock]);
1125                 }
1126                 else{
1127                         reduceChain(newBlock);
1128
1129                         // it can appear that reduceChain() inserts some edges
1130                         // so there are new pendants and obsolete pendants
1131                         //  the obsolete pendants are collected in m_pendantsToDel
1132                         if (m_pendantsToDel.size() > 0){
1133                                 ListIterator<node> delIt = m_pendantsToDel.begin();
1134                                 for (; delIt.valid(); delIt = m_pendantsToDel.begin()){
1135                                         deletePendant(*delIt);
1136                                         m_pendantsToDel.del(delIt);
1137                                 }
1138                         }
1139                 }
1140         }
1141         else{
1142                 #ifdef PLANAR_AUGMENTATION_DEBUG
1143                         cout << "connectLabels(): newBlock is no new pendant ! degree == " << m_pBCTree->m_bNode_degree[newBlock] << endl << flush;
1144                 #endif
1145         }
1146 }
1147
1148
1149
1150 //      ----------------------------------------------------
1151 //      newLabel(node cutvertex, node block, paStopCause whyStop)
1152 //
1153 //              creates a new label and inserts it into m_labels
1154 //
1155 //  ----------------------------------------------------
1156 pa_label PlanarAugmentation::newLabel(node cutvertex, node p, paStopCause whyStop)
1157 {
1158         pa_label l = OGDF_NEW PALabel(0, cutvertex, whyStop);
1159         l->addPendant(p);
1160         m_belongsTo[p] = l;
1161         m_isLabel[cutvertex] = m_labels.pushBack(l);
1162         return l;
1163 }
1164
1165
1166
1167 //      ----------------------------------------------------
1168 //      findMatching(pa_label& first, pa_label& second)
1169 //
1170 //              trys to find two matching labels
1171 //              first will be the label with max. size that has
1172 //                a matching label
1173 //
1174 //  ----------------------------------------------------
1175 bool PlanarAugmentation::findMatching(pa_label& first, pa_label& second)
1176 {
1177         first = m_labels.front();
1178         second = 0;
1179         pa_label l = 0;
1180
1181         ListIterator<pa_label> it = m_labels.begin();
1182         while (it.valid()){
1183                 second = *it;
1184
1185                 if (second != first){
1186                         if ( (l != 0) && (second->size() < l->size()) ){
1187                                 second = l;
1188                                 return true;
1189                         }
1190
1191                         if (l != 0){
1192
1193                                 if ( connectCondition(second, first)
1194                                         && planarityCheck(m_pBCTree->m_hNode_gNode[m_pBCTree->m_bNode_hRefNode[second->head()]],
1195                                         m_pBCTree->m_hNode_gNode[m_pBCTree->m_bNode_hRefNode[first->head()]]) )
1196                                 {
1197                                                 return true;
1198                                 }
1199                         }
1200                         else{   // l == 0
1201
1202                                 if ( planarityCheck(m_pBCTree->m_hNode_gNode[m_pBCTree->m_bNode_hRefNode[second->head()]],
1203                                                                         m_pBCTree->m_hNode_gNode[m_pBCTree->m_bNode_hRefNode[first->head()]]) ){
1204                                         if (connectCondition(second, first)){
1205                                                 return true;
1206                                         }
1207                                         l = second;
1208                                 }
1209                         }
1210                 }
1211                 it++;
1212         }
1213
1214         if (!l)
1215                 return false;
1216
1217         second = l;
1218         return true;
1219 }
1220
1221
1222
1223 //      ----------------------------------------------------
1224 //      connectCondition(pa_label a, pa_label b)
1225 //
1226 //              checks the connect-condition for label a and b
1227 //
1228 //  ----------------------------------------------------
1229 bool PlanarAugmentation::connectCondition(pa_label a, pa_label b)
1230 {
1231         bool found = false;
1232
1233         if ( (a->isBLabel()) && (b->size() == 1) ){
1234                 found = true;
1235         }
1236
1237         int deg1 = m_pBCTree->m_bNode_degree[m_pBCTree->find(a->head())] - b->size() +1;
1238         int deg2 = m_pBCTree->m_bNode_degree[m_pBCTree->find(b->head())] - b->size() +1;
1239
1240         if ((deg1 > 2) && (deg2 > 2)){
1241                 return true;
1242         }
1243         if ((deg1 > 2) || (deg2 > 2)){
1244                 if (found){
1245                         return true;
1246                 }
1247                 else
1248                         found = true;
1249         }
1250         SList<node> *path = m_pBCTree->findPathBCTree(a->head(), b->head());
1251         SListIterator<node> it = path->begin();
1252         node bcNode;
1253
1254         for (; it.valid(); it++){
1255                 bcNode = m_pBCTree->find(*it);
1256
1257                 if ((bcNode != a->parent()) && (bcNode != b->parent())){
1258                         if (m_pBCTree->m_bNode_degree[bcNode] > 2){
1259                                 if (found) {
1260                                         delete path;
1261                                         return true;
1262                                 } else
1263                                         found = true;
1264                         }
1265                         if ((m_pBCTree->typeOfBNode(bcNode) == BCTree::BComp)
1266                                 && (m_pBCTree->m_bNode_degree[bcNode] > 3))
1267                         {
1268                                 delete path;
1269                                 return true;
1270                         }
1271                 }
1272         }
1273
1274         delete path;
1275         return !found;
1276 }
1277
1278
1279
1280 //      ----------------------------------------------------
1281 //      updateAdjNonChildren()
1282 //
1283 //              update of m_adjNonChildren
1284 //              newBlock is the node all nodes on path now belong to
1285 //
1286 //  ----------------------------------------------------
1287 void PlanarAugmentation::updateAdjNonChildren(node newBlock, SList<node>& path)
1288 {
1289         SListIterator<node> pathIt = path.begin();
1290
1291         SListIterator<adjEntry> childIt = m_adjNonChildren[newBlock].begin();
1292         SListIterator<adjEntry> prevIt  = m_adjNonChildren[newBlock].begin();
1293         // first update m_adjNonChildren[newBlock] by deleting wrong adjEntries
1294         while (childIt.valid()){
1295                 if (m_pBCTree->find((*childIt)->twinNode()) == newBlock){
1296                         if (childIt == m_adjNonChildren[newBlock].begin()){
1297                                 m_adjNonChildren[newBlock].popFront();
1298                                 childIt = m_adjNonChildren[newBlock].begin();
1299                                 prevIt  = m_adjNonChildren[newBlock].begin();
1300                         }
1301                         else{
1302                                 childIt = prevIt;
1303                                 m_adjNonChildren[newBlock].delSucc(prevIt);
1304                                 childIt++;
1305                         }
1306                 }
1307                 else{
1308                         prevIt = childIt;
1309                         childIt++;
1310                 }
1311         }
1312
1313         // now run through list of all path-nodes
1314         // and update m_adjNonChildren[pathIt] if they do not belong to another bc-node
1315         // or insert adjEntries to m_adjNonChildren[newBlock]
1316         while (pathIt.valid()){
1317
1318                 if (*pathIt != newBlock){
1319                         if (*pathIt == m_pBCTree->find(*pathIt)){
1320
1321                                 childIt = m_adjNonChildren[*pathIt].begin();
1322                                 prevIt  = m_adjNonChildren[*pathIt].begin();
1323
1324                                 while (childIt.valid()){
1325                                         if (m_pBCTree->find((*childIt)->twinNode()) == (*pathIt)){
1326                                                 if (childIt == m_adjNonChildren[*pathIt].begin()){
1327                                                         m_adjNonChildren[*pathIt].popFront();
1328                                                         childIt = m_adjNonChildren[*pathIt].begin();
1329                                                         prevIt  = m_adjNonChildren[*pathIt].begin();
1330                                                 }
1331                                                 else{
1332                                                         childIt = prevIt;
1333                                                         m_adjNonChildren[*pathIt].delSucc(prevIt);
1334                                                         childIt++;
1335                                                 }
1336                                         }
1337                                         else{
1338                                                 prevIt = childIt;
1339                                                 childIt++;
1340                                         }
1341                                 }
1342                         }
1343                         else{   // (*pathIt != m_pBCTree->find(*pathIt))
1344                                 childIt = m_adjNonChildren[*pathIt].begin();
1345
1346                                 while (childIt.valid()){
1347                                         if (m_pBCTree->find((*childIt)->twinNode()) != newBlock){
1348                                                 // found a child of *pathIt, that has an adjacent bc-node
1349                                                 //  that doesn't belong to newBlock
1350                                                         m_adjNonChildren[newBlock].pushBack(*childIt);
1351                                         }
1352                                         childIt++;
1353                                 }
1354                                 m_adjNonChildren[*pathIt].clear();
1355                         }
1356                 }
1357                 pathIt++;
1358         }
1359 }
1360
1361
1362
1363 //      ----------------------------------------------------
1364 //      updateBCRoot()
1365 //
1366 //              modifys the root of the bc-tree
1367 //
1368 //  ----------------------------------------------------
1369 void PlanarAugmentation::modifyBCRoot(node oldRoot, node newRoot)
1370 {
1371         // status before updates:
1372         //   m_pBCTree->m_bNode_hRefNode[oldRoot] = 0
1373         //   m_pBCTree->m_bNode_hParNode[oldRoot] = 0
1374
1375         //   m_pBCTree->m_bNode_hRefNode[newRoot] = single isolated vertex in b-comp-graph of this c-comp
1376         //   m_pBCTree->m_bNode_hParNode[newRoot] = cutvertex in b-comp-graph corresponding to rootPendant
1377
1378         // updates:
1379         //   for the old root:
1380         m_pBCTree->m_bNode_hRefNode[oldRoot] = m_pBCTree->m_bNode_hParNode[newRoot];
1381         m_pBCTree->m_bNode_hParNode[oldRoot] = m_pBCTree->m_bNode_hRefNode[newRoot];
1382
1383         //   for the new root:
1384         // m_pBCTree->m_bNode_hRefNode[newRoot] = no update required;
1385         m_pBCTree->m_bNode_hParNode[newRoot] = 0;
1386 }
1387
1388
1389
1390 //      ----------------------------------------------------
1391 //      updateNewEdges(const SList<edge> &newEdges)
1392 //
1393 //              updates the bc-tree-structure and m_adjNonChildren,
1394 //              also adds all edges of newEdges to m_pResult
1395 //
1396 //  ----------------------------------------------------
1397 void PlanarAugmentation::updateNewEdges(const SList<edge> &newEdges)
1398 {
1399         SListConstIterator<edge> edgeIt = newEdges.begin();
1400         while (edgeIt.valid()){
1401                 m_pResult->pushBack(*edgeIt);
1402
1403                 SList<node>& path = m_pBCTree->findPath((*edgeIt)->source(), (*edgeIt)->target());
1404
1405                 m_pBCTree->updateInsertedEdge(*edgeIt);
1406                 node newBlock = m_pBCTree->DynamicBCTree::bcproper(*edgeIt);
1407
1408                 updateAdjNonChildren(newBlock, path);
1409
1410                 if ((m_pBCTree->parent(newBlock) == 0)
1411                 && (m_pBCTree->m_bNode_degree[newBlock] == 1)) {
1412                         // the new block is a pendant and also the new root of the bc-tree
1413                         node newRoot = 0;
1414                         newRoot = (*(m_adjNonChildren[newBlock].begin()))->twinNode();
1415                          modifyBCRoot(newBlock, newRoot);
1416                 } //if ((m_pBCTree->parent(newBlock) == 0) && (m_pBCTree->m_bNode_degree[newBlock] == 1))
1417
1418                 delete(&path);
1419                 edgeIt++;
1420         } // while (edgeIt.valid)
1421 }
1422
1423
1424
1425 //      ----------------------------------------------------
1426 //      terminate()
1427 //
1428 //              cleanup before finish
1429 //
1430 //  ----------------------------------------------------
1431 void PlanarAugmentation::terminate()
1432 {
1433         while (m_labels.size() > 0){
1434                 pa_label l = m_labels.popFrontRet();
1435                 delete (l);
1436         }
1437
1438         m_pendants.clear();
1439         node v;
1440         forall_nodes(v, m_pBCTree->m_B)
1441                 m_adjNonChildren[v].clear();
1442
1443         delete(m_pBCTree);
1444 }
1445
1446 } // end namespace ogdf