ext/OGDF/src/decomposition/TricComp.cpp

   1 /*
   2  * $Revision: 2552 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements Hopcroft/Tarjan algorithm for finding the
  11  * triconnected components of a biconnected multi-graph
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #include "TricComp.h"
  46 #include <ogdf/basic/GraphCopy.h>
  47 #include <ogdf/basic/simple_graph_alg.h>
  48 #include <ogdf/basic/NodeSet.h>
  49
  50 //#define TRIC_COMP_OUTPUT
  51
  52
  53 namespace ogdf {
  54
  55
  56 //----------------------------------------------------------
  57 //                      Destructor
  58 //
  59 //  deletes GraphCopy
  60 //----------------------------------------------------------
  61
  62 TricComp::~TricComp()
  63 {
  64         delete m_pGC;
  65 }
  66
  67
  68 //----------------------------------------------------------
  69 //                      Constructor
  70 //
  71 //  Divides G into triconnected components.
  72 //----------------------------------------------------------
  73
  74 TricComp::TricComp (const Graph& G) :
  75         m_ESTACK(G.numberOfEdges())
  76 {
  77         m_pGC = new GraphCopySimple(G);
  78         GraphCopySimple &GC = *m_pGC;
  79
  80         const int n = GC.numberOfNodes();
  81         const int m = GC.numberOfEdges();
  82
  83 #ifdef TRIC_COMP_OUTPUT
  84         cout << "Dividing G into triconnected components.\n" << endl;
  85         cout << "n = " << n << ", m = " << m << endl << endl;
  86 #endif
  87
  88         m_component = Array<CompStruct>(3*m-6);
  89         m_numComp = 0;
  90
  91         // special cases
  92         OGDF_ASSERT(n >= 2);
  93         OGDF_ASSERT_IF(dlExtendedChecking, isBiconnected(G));
  94
  95         if (n <= 2) {
  96                 OGDF_ASSERT(m >= 3);
  97                 CompStruct &C = newComp();
  98                 edge e;
  99                 forall_edges(e,GC)
 100                         C << e;
 101                 C.m_type = bond;
 102                 return;
 103         }
 104
 105         m_TYPE.init(GC,unseen);
 106         splitMultiEdges();
 107
 108         // initialize arrays
 109         m_NUMBER.init(GC,0); m_LOWPT1.init(GC);
 110         m_LOWPT2.init(GC);   m_FATHER.init(GC,0);
 111         m_ND    .init(GC);   m_DEGREE.init(GC);
 112         m_TREE_ARC.init(GC,0);
 113         m_NODEAT = Array<node>(1,n);
 114
 115         m_numCount = 0;
 116         m_start = GC.firstNode();
 117         DFS1(GC,m_start,0);
 118
 119         edge e;
 120         forall_edges(e,GC) {
 121                 bool up = (m_NUMBER[e->target()] - m_NUMBER[e->source()] > 0);
 122                 if ((up && m_TYPE[e] == frond) || (!up && m_TYPE[e] == tree))
 123                         GC.reverseEdge(e);
 124         }
 125
 126 #ifdef TRIC_COMP_OUTPUT
 127         cout << "\nnode\tNUMBER\tFATHER\tLOWPT1\tLOWPT2\tND" << endl;
 128         node v;
 129         forall_nodes(v,GC) {
 130                 cout << GC.original(v) << ":  \t" << m_NUMBER[v] << "   \t";
 131                 if (m_FATHER[v] == 0) cout << "nil \t";
 132                 else cout << GC.original(m_FATHER[v]) << "   \t";
 133                 cout << m_LOWPT1[v] << "   \t" << m_LOWPT2[v] << "   \t" << m_ND[v] << endl;
 134         }
 135 #endif
 136
 137         m_A.init(GC);
 138         m_IN_ADJ.init(GC,0);
 139         buildAcceptableAdjStruct(GC);
 140
 141 #ifdef TRIC_COMP_OUTPUT
 142         cout << "\nadjaceny lists:" << endl;
 143         forall_nodes(v,GC) {
 144                 cout << v << "\t";
 145                 ListConstIterator<edge> itE;
 146                 for(itE = m_A[v].begin(); itE.valid(); ++itE) {
 147                         printOs(*itE);
 148                 }
 149                 cout << endl;
 150         }
 151 #endif
 152
 153         DFS2(GC);
 154
 155 #ifdef TRIC_COMP_OUTPUT
 156         cout << "\nnode\tNEWNUM\tLOWPT1\tLOWPT2\tHIGHPT" << endl;
 157         forall_nodes(v,GC) {
 158                 cout << GC.original(v) << ":  \t" << m_NEWNUM[v] << "   \t";
 159                 cout << m_LOWPT1[v] << "   \t" << m_LOWPT2[v] << "   \t";
 160                 ListConstIterator<int> itH;
 161                 for(itH = m_HIGHPT[v].begin(); itH.valid(); ++itH)
 162                         cout << *itH << " ";
 163                 cout << endl;
 164         }
 165
 166         cout << "\nedges starting a path:" << endl;
 167         forall_edges(e,GC) {
 168                 if (m_START[e]) {
 169                         printOs(e);
 170                 }
 171         }
 172 #endif
 173
 174
 175         m_TSTACK_h = new int[2*m+1];
 176         m_TSTACK_a = new int[2*m+1];
 177         m_TSTACK_b = new int[2*m+1];
 178         m_TSTACK_a[m_top = 0] = -1; // start with EOS
 179
 180         pathSearch(G,m_start);
 181
 182         // last split component
 183         CompStruct &C = newComp();
 184         while(!m_ESTACK.empty()) {
 185                 C << m_ESTACK.pop();
 186         }
 187         C.m_type = (C.m_edges.size() > 4) ? triconnected : polygon;
 188
 189 #ifdef TRIC_COMP_OUTPUT
 190         printStacks();
 191 #endif
 192
 193         delete [] m_TSTACK_h;
 194         delete [] m_TSTACK_a;
 195         delete [] m_TSTACK_b;
 196
 197         // free resources
 198         m_NUMBER.init(); m_LOWPT1.init();
 199         m_LOWPT2.init(); m_FATHER.init();
 200         m_ND    .init(); m_TYPE  .init();
 201         m_A     .init(); m_NEWNUM.init();
 202         m_HIGHPT.init(); m_START .init();
 203         m_DEGREE.init(); m_TREE_ARC.init();
 204         m_IN_ADJ.init(); m_IN_HIGH.init();
 205         m_NODEAT.init();
 206         m_ESTACK.clear();
 207
 208         assembleTriconnectedComponents();
 209
 210         // Caution: checkComp() assumes that the graph is simple!
 211         //OGDF_ASSERT(checkComp());
 212
 213 #ifdef TRIC_COMP_OUTPUT
 214         cout << "\n\nTriconnected components:\n";
 215         for (int i = 0; i < m_numComp; i++) {
 216                 const List<edge> &L = m_component[i].m_edges;
 217                 if (L.size() == 0) continue;
 218                 cout << "[" << i << "] ";
 219                 switch(m_component[i].m_type) {
 220                 case bond: cout << "bond "; break;
 221                 case polygon: cout << "polygon "; break;
 222                 case triconnected: cout << "triconnected "; break;
 223                 }
 224
 225                 ListConstIterator<edge> itE;
 226                 for(itE = L.begin(); itE.valid(); ++itE)
 227                         printOs(*itE);
 228                 cout << "\n";
 229         }
 230 #endif
 231 }
 232
 233
 234 //----------------------------------------------------------
 235 //                      Constructor
 236 //
 237 // Tests G for triconnectivity and returns a cut vertex in
 238 // s1 or a separation pair in (s1,s2).
 239 //----------------------------------------------------------
 240
 241 TricComp::TricComp(const Graph &G, bool &isTric, node &s1, node &s2)
 242 {
 243         m_pGC = new GraphCopySimple(G);
 244         GraphCopySimple &GC = *m_pGC;
 245
 246         const int n = GC.numberOfNodes();
 247         const int m = GC.numberOfEdges();
 248
 249         s1 = s2 = 0;
 250
 251         if(n == 0) {
 252                 isTric = true; return;
 253         }
 254
 255         makeLoopFree(GC);
 256         makeParallelFreeUndirected(GC);
 257
 258         // initialize arrays
 259         m_TYPE.init(GC,unseen);
 260         m_NUMBER.init(GC,0); m_LOWPT1.init(GC);
 261         m_LOWPT2.init(GC);   m_FATHER.init(GC,0);
 262         m_ND    .init(GC);   m_DEGREE.init(GC);
 263         m_NODEAT.init(1,n);
 264
 265         m_TREE_ARC.init(GC,0); // probably not required
 266
 267         m_numCount = 0;
 268         m_start = GC.firstNode();
 269         DFS1(GC,m_start,0,s1);
 270
 271         // graph not even connected?
 272         if(m_numCount < n) {
 273                 s1 = 0; isTric = false;
 274                 return;
 275         }
 276
 277         // graph no biconnected?
 278         if(s1 != 0) {
 279                 s1 = GC.original(s1);
 280                 isTric = false; // s1 is a cut vertex
 281                 return;
 282         }
 283
 284         edge e;
 285         forall_edges(e,GC) {
 286                 bool up = (m_NUMBER[e->target()] - m_NUMBER[e->source()] > 0);
 287                 if ((up && m_TYPE[e] == frond) || (!up && m_TYPE[e] == tree))
 288                         GC.reverseEdge(e);
 289         }
 290
 291         m_A.init(GC);
 292         m_IN_ADJ.init(GC,0);
 293         buildAcceptableAdjStruct(GC);
 294
 295         DFS2(GC);
 296
 297         m_TSTACK_h = new int[m];
 298         m_TSTACK_a = new int[m];
 299         m_TSTACK_b = new int[m];
 300         m_TSTACK_a[m_top = 0] = -1; // start with EOS
 301
 302         isTric = pathSearch(G,m_start,s1,s2);
 303         if(s1) {
 304                 s1 = GC.original(s1);
 305                 s2 = GC.original(s2);
 306         }
 307
 308         delete [] m_TSTACK_h;
 309         delete [] m_TSTACK_a;
 310         delete [] m_TSTACK_b;
 311
 312         // free resources
 313         m_NUMBER.init(); m_LOWPT1.init();
 314         m_LOWPT2.init(); m_FATHER.init();
 315         m_ND    .init(); m_TYPE  .init();
 316         m_A     .init(); m_NEWNUM.init();
 317         m_HIGHPT.init(); m_START .init();
 318         m_DEGREE.init(); m_TREE_ARC.init();
 319         m_IN_ADJ.init(); m_IN_HIGH.init();
 320         m_NODEAT.init();
 321 }
 322
 323
 324 //----------------------------------------------------------
 325 //                     splitMultiEdges
 326 //
 327 //  Splits bundles of multi-edges into bonds and creates
 328 //  a new virtual edge in GC.
 329 //----------------------------------------------------------
 330
 331 void TricComp::splitMultiEdges()
 332 {
 333         GraphCopySimple &GC = *m_pGC;
 334
 335         SListPure<edge> edges;
 336         EdgeArray<int> minIndex(GC), maxIndex(GC);
 337         parallelFreeSortUndirected(GC,edges,minIndex,maxIndex);
 338
 339         SListIterator<edge> it;
 340         for (it = edges.begin(); it.valid(); ) {
 341                 edge e = *it;
 342                 int minI = minIndex[e], maxI = maxIndex[e];
 343                 ++it;
 344                 if (it.valid() && minI == minIndex[*it] && maxI == maxIndex[*it]) {
 345                         CompStruct &C = newComp(bond);
 346                         C << GC.newEdge(e->source(),e->target()) << e << *it;
 347                         m_TYPE[e] = m_TYPE[*it] = removed;
 348
 349                         for (++it; it.valid() &&
 350                                 minI == minIndex[*it] && maxI == maxIndex[*it]; ++it)
 351                         {
 352                                 C << *it;
 353                                 m_TYPE[*it] = removed;
 354                         }
 355                 }
 356         }
 357 }
 358
 359
 360
 361 //----------------------------------------------------------
 362 //                      checkComp
 363 //
 364 //  Checks if computed triconnected components are correct.
 365 //----------------------------------------------------------
 366
 367 bool TricComp::checkSepPair(edge eVirt)
 368 {
 369         GraphCopySimple G(*m_pGC);
 370
 371         G.delNode(G.copy(m_pGC->original(eVirt->source())));
 372         G.delNode(G.copy(m_pGC->original(eVirt->target())));
 373
 374         return !isConnected(G);
 375 }
 376
 377 bool TricComp::checkComp()
 378 {
 379         bool ok = true;
 380
 381         GraphCopySimple &GC = *m_pGC;
 382         GraphCopySimple GTest(GC.original());
 383
 384         if (!isLoopFree(GC)) {
 385                 ok = false;
 386                 cout << "GC contains loops!" << endl;
 387         }
 388
 389         int i;
 390         edge e;
 391         node v;
 392
 393         EdgeArray<int> count(GC,0);
 394         for (i = 0; i < m_numComp; i++) {
 395                 ListIterator<edge> itE;
 396                 for(itE = m_component[i].m_edges.begin(); itE.valid(); ++itE)
 397                         count[*itE]++;
 398         }
 399
 400         forall_edges(e,GC) {
 401                 if (GC.original(e) == 0) {
 402                         if (count[e] != 2) {
 403                                 ok = false;
 404                                 cout << "virtual edge contained " << count[e];
 405                                 printOs(e); cout << endl;
 406                         }
 407                         if (checkSepPair(e) == false) {
 408                                 ok = false;
 409                                 cout << "virtual edge"; printOs(e);
 410                                 cout << " does not correspond to a sep. pair." << endl;
 411                         }
 412
 413                 } else {
 414                         if (count[e] != 1) {
 415                                 ok = false;
 416                                 cout << "real edge contained " << count[e];
 417                                 printOs(e); cout << endl;
 418                         }
 419                 }
 420         }
 421
 422         NodeSet S(GC);
 423         NodeArray<node> map(GC);
 424
 425         for(i = 0; i < m_numComp; i++) {
 426                 CompStruct &C = m_component[i];
 427                 const List<edge> &L = C.m_edges;
 428                 if (L.size() == 0) continue;
 429
 430                 S.clear();
 431
 432                 ListConstIterator<edge> itE;
 433                 for(itE = L.begin(); itE.valid(); ++itE) {
 434                         S.insert((*itE)->source());
 435                         S.insert((*itE)->target());
 436                 }
 437
 438                 const int n = S.size();
 439
 440                 switch(C.m_type) {
 441                 case bond:
 442                         if (n != 2) {
 443                                 ok = false;
 444                                 cout << "bond [" << i << "] with " << n << " nodes!" << endl;
 445                         }
 446                         break;
 447
 448                 case polygon:
 449                         if (n < 3) {
 450                                 ok = false;
 451                                 cout << "polygon [" << i << "] with " << n << " nodes!" << endl;
 452                         }
 453
 454                         if (L.size() != n) {
 455                                 ok = false;
 456                                 cout << "polygon [" << i << "] with " << n << " vertices and " << L.size() << " edges!" << endl;
 457
 458                         } else {
 459                                 Graph Gp;
 460                                 ListConstIterator<node> itV;
 461                                 for(itV = S.nodes().begin(); itV.valid(); ++itV)
 462                                         map[*itV] = Gp.newNode();
 463                                 for(itE = L.begin(); itE.valid(); ++itE)
 464                                         Gp.newEdge(map[(*itE)->source()],map[(*itE)->target()]);
 465
 466                                 forall_nodes(v,Gp)
 467                                         if (v->degree() != 2) {
 468                                                 ok = false;
 469                                                 cout << "polygon [" << i << "] contains node with degree " << v->degree() << endl;
 470                                         }
 471                                         if (!isConnected(Gp)) {
 472                                                 ok = false;
 473                                                 cout << "polygon [" << i << "] not connected." << endl;
 474                                         }
 475                         }
 476                         break;
 477
 478                 case triconnected:
 479                         if (n < 4) {
 480                                 ok = false;
 481                                 cout << "triconnected component [" << i << "] with " << n << " nodes!" << endl;
 482                         }
 483
 484                         {
 485                         Graph Gp;
 486                         ListConstIterator<node> itV;
 487                         for(itV = S.nodes().begin(); itV.valid(); ++itV)
 488                                 map[*itV] = Gp.newNode();
 489                         for(itE = L.begin(); itE.valid(); ++itE)
 490                                 Gp.newEdge(map[(*itE)->source()],map[(*itE)->target()]);
 491
 492                         if (!isTriconnectedPrimitive(Gp)) {
 493                                 ok = false;
 494                                 cout << "component [" << i << "] not triconnected!" << endl;
 495                         }
 496                         if (!isSimple(Gp)) {
 497                                 ok = false;
 498                                 cout << "triconnected component [" << i << "] not simple!" << endl;
 499                         }
 500                         }
 501                         break;
 502
 503                 default:
 504                         ok = false;
 505                         cout << "component [" << i << "] with undefined type!" << endl;
 506                 }
 507         }
 508
 509         return ok;
 510 }
 511
 512
 513 //----------------------------------------------------------
 514 //               assembleTriconnectedComponents
 515 //
 516 //  joins bonds and polygons with common virtual edge in
 517 //  order to build the triconnected components.
 518 //----------------------------------------------------------
 519
 520 void TricComp::assembleTriconnectedComponents()
 521 {
 522         GraphCopySimple &GC = *m_pGC;
 523
 524         EdgeArray<int>       comp1(GC), comp2(GC);
 525         EdgeArray<ListIterator<edge> > item1(GC,ListIterator<edge>());
 526         EdgeArray<ListIterator<edge> > item2(GC);
 527
 528         bool *visited = new bool[m_numComp];
 529
 530         int i;
 531         for(i = 0; i < m_numComp; i++) {
 532                 visited[i] = false;
 533                 List<edge> &L = m_component[i].m_edges;
 534
 535                 ListIterator<edge> it;
 536                 for(it = L.begin(); it.valid(); ++it) {
 537                         edge e = *it;
 538                         if (!item1[e].valid()) {
 539                                 comp1[e] = i; item1[e] = it;
 540                         } else {
 541                                 comp2[e] = i; item2[e] = it;
 542                         }
 543                 }
 544         }
 545
 546         for(i = 0; i < m_numComp; i++) {
 547                 CompStruct &C1 = m_component[i];
 548                 List<edge> &L1 = C1.m_edges;
 549                 visited[i] = true;
 550
 551                 if (L1.size() == 0) continue;
 552
 553                 if (C1.m_type == polygon || C1.m_type == bond) {
 554                         ListIterator<edge> it, itNext;
 555                         for(it = L1.begin(); it.valid(); it = itNext) {
 556                                 itNext = it.succ();
 557                                 edge e  = *it;
 558
 559                                 if (GC.original(e) != 0) continue;
 560
 561                                 int j = comp1[e];
 562                                 ListIterator<edge> it2;
 563                                 if (visited[j]) {
 564                                         j = comp2[e];
 565                                         if (visited[j]) continue;
 566                                         it2 = item2[e];
 567                                 } else
 568                                         it2 = item1[e];
 569
 570                                 CompStruct &C2 = m_component[j];
 571
 572                                 if (C2.m_type != C1.m_type) continue;
 573
 574                                 visited[j] = true;
 575                                 List<edge> &L2 = C2.m_edges;
 576
 577                                 L2.del(it2);
 578                                 L1.conc(L2);
 579                                 if (!itNext.valid())
 580                                         itNext = it.succ();
 581                                 L1.del(it);
 582
 583                                 GC.delEdge(e);
 584                         }
 585                 }
 586         }
 587
 588         delete [] visited;
 589 }
 590
 591
 592
 593 //----------------------------------------------------------
 594 //                   The first dfs-search
 595 //
 596 //  computes NUMBER[v], FATHER[v], LOWPT1[v], LOWPT2[v],
 597 //           ND[v], TYPE[e], DEGREE[v]
 598 //----------------------------------------------------------
 599
 600 void TricComp::DFS1 (const Graph& G, node v, node u)
 601 {
 602         edge e;
 603
 604         m_NUMBER[v] = ++m_numCount;
 605         m_FATHER[v] = u;
 606         m_DEGREE[v] = v->degree();
 607
 608         m_LOWPT1[v] = m_LOWPT2[v] = m_NUMBER[v];
 609         m_ND[v] = 1;
 610
 611         forall_adj_edges (e,v) {
 612
 613                 if (m_TYPE[e] != unseen)
 614                         continue;
 615
 616                 node w = e->opposite(v);
 617
 618                 if (m_NUMBER[w] == 0) {
 619                         m_TYPE[e] = tree;
 620
 621                         m_TREE_ARC[w] = e;
 622
 623                         DFS1(G,w,v);
 624
 625                         if (m_LOWPT1[w] < m_LOWPT1[v]) {
 626                                 m_LOWPT2[v] = min(m_LOWPT1[v],m_LOWPT2[w]);
 627                                 m_LOWPT1[v] = m_LOWPT1[w];
 628
 629                         } else if (m_LOWPT1[w] == m_LOWPT1[v]) {
 630                                 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT2[w]);
 631
 632                         } else {
 633                                 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT1[w]);
 634                         }
 635
 636                         m_ND[v] += m_ND[w];
 637
 638                 } else {
 639
 640                         m_TYPE[e] = frond;
 641
 642                         if (m_NUMBER[w] < m_LOWPT1[v]) {
 643                                 m_LOWPT2[v] = m_LOWPT1[v];
 644                                 m_LOWPT1[v] = m_NUMBER[w];
 645
 646                         } else if (m_NUMBER[w] > m_LOWPT1[v]) {
 647                                 m_LOWPT2[v] = min(m_LOWPT2[v],m_NUMBER[w]);
 648                         }
 649                 }
 650         }
 651 }
 652
 653 void TricComp::DFS1 (const Graph& G, node v, node u, node &s1)
 654 {
 655         node firstSon = 0;
 656         edge e;
 657
 658         m_NUMBER[v] = ++m_numCount;
 659         m_FATHER[v] = u;
 660         m_DEGREE[v] = v->degree();
 661
 662         m_LOWPT1[v] = m_LOWPT2[v] = m_NUMBER[v];
 663         m_ND[v] = 1;
 664
 665         forall_adj_edges (e,v) {
 666
 667                 if (m_TYPE[e] != unseen)
 668                         continue;
 669
 670                 node w = e->opposite(v);
 671
 672                 if (m_NUMBER[w] == 0) {
 673                         m_TYPE[e] = tree;
 674                         if(firstSon == 0) firstSon = w;
 675
 676                         m_TREE_ARC[w] = e;
 677
 678                         DFS1(G,w,v,s1);
 679
 680                         // check for cut vertex
 681                         if(m_LOWPT1[w] >= m_NUMBER[v] && (w != firstSon || u != 0))
 682                                 s1 = v;
 683
 684                         if (m_LOWPT1[w] < m_LOWPT1[v]) {
 685                                 m_LOWPT2[v] = min(m_LOWPT1[v],m_LOWPT2[w]);
 686                                 m_LOWPT1[v] = m_LOWPT1[w];
 687
 688                         } else if (m_LOWPT1[w] == m_LOWPT1[v]) {
 689                                 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT2[w]);
 690
 691                         } else {
 692                                 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT1[w]);
 693                         }
 694
 695                         m_ND[v] += m_ND[w];
 696
 697                 } else {
 698
 699                         m_TYPE[e] = frond;
 700
 701                         if (m_NUMBER[w] < m_LOWPT1[v]) {
 702                                 m_LOWPT2[v] = m_LOWPT1[v];
 703                                 m_LOWPT1[v] = m_NUMBER[w];
 704
 705                         } else if (m_NUMBER[w] > m_LOWPT1[v]) {
 706                                 m_LOWPT2[v] = min(m_LOWPT2[v],m_NUMBER[w]);
 707                         }
 708                 }
 709         }
 710 }
 711
 712
 713 //----------------------------------------------------------
 714 //           Construction of ordered adjaceny lists
 715 //----------------------------------------------------------
 716
 717 void TricComp::buildAcceptableAdjStruct(const Graph& G)
 718 {
 719         edge e;
 720         int max = 3*G.numberOfNodes()+2;
 721         Array<List<edge> > BUCKET(1,max);
 722
 723         forall_edges(e,G) {
 724                 edgeType t = m_TYPE[e];
 725                 if (t == removed) continue;
 726
 727                 node w = e->target();
 728                 int phi = (t == frond) ? 3*m_NUMBER[w]+1 : (
 729                         (m_LOWPT2[w] < m_NUMBER[e->source()]) ? 3*m_LOWPT1[w] :
 730                         3*m_LOWPT1[w]+2);
 731                 BUCKET[phi].pushBack(e);
 732         }
 733
 734         for (int i = 1; i <= max; i++) {
 735                 ListConstIterator<edge> it;
 736                 for(it = BUCKET[i].begin(); it.valid(); ++it) {
 737                         e = *it;
 738                         m_IN_ADJ[e] = m_A[e->source()].pushBack(e);
 739                 }
 740         }
 741 }
 742
 743
 744 //----------------------------------------------------------
 745 //                   The second dfs-search
 746 //----------------------------------------------------------
 747
 748 void TricComp::pathFinder(const Graph& G, node v)
 749 {
 750         m_NEWNUM[v] = m_numCount - m_ND[v] + 1;
 751
 752         ListConstIterator<edge> it;
 753         for(it = m_A[v].begin(); it.valid(); ++it) {
 754                 edge e = *it;
 755                 node w = e->opposite(v);
 756
 757                 if (m_newPath) {
 758                         m_newPath = false;
 759                         m_START[e] = true;
 760                 }
 761
 762                 if (m_TYPE[e] == tree) {
 763                         pathFinder(G,w);
 764                         m_numCount--;
 765
 766                 } else {
 767                         m_IN_HIGH[e] = m_HIGHPT[w].pushBack(m_NEWNUM[v]);
 768                         m_newPath = true;
 769                 }
 770         }
 771 }
 772
 773 void TricComp::DFS2 (const Graph& G)
 774 {
 775         m_NEWNUM .init(G,0);
 776         m_HIGHPT .init(G);
 777         m_IN_HIGH.init(G,ListIterator<int>());
 778         m_START  .init(G,false);
 779
 780         m_numCount = G.numberOfNodes();
 781         m_newPath = true;
 782
 783         pathFinder(G,m_start);
 784
 785         node v;
 786         Array<int> old2new(1,G.numberOfNodes());
 787
 788         forall_nodes(v,G)
 789                 old2new[m_NUMBER[v]] = m_NEWNUM[v];
 790
 791         forall_nodes(v,G) {
 792                 m_NODEAT[m_NEWNUM[v]] = v;
 793                 m_LOWPT1[v] = old2new[m_LOWPT1[v]];
 794                 m_LOWPT2[v] = old2new[m_LOWPT2[v]];
 795         }
 796 }
 797
 798
 799 //----------------------------------------------------------
 800 //                      pathSearch()
 801 //
 802 // recognition of split components
 803 //----------------------------------------------------------
 804
 805 void TricComp::pathSearch (const Graph& G, node v)
 806 {
 807         node w;
 808         edge e;
 809         int y, vnum = m_NEWNUM[v], wnum;
 810         int a, b;
 811
 812         List<edge> &Adj = m_A[v];
 813         int outv = Adj.size();
 814
 815         ListIterator<edge> it, itNext;
 816         for(it = Adj.begin(); it.valid(); it=itNext)
 817         {
 818                 itNext = it.succ();
 819                 e = *it;
 820                 w = e->target(); wnum = m_NEWNUM[w];
 821
 822                 if (m_TYPE[e] == tree) {
 823
 824                         if (m_START[e]) {
 825                                 y = 0;
 826                                 if (m_TSTACK_a[m_top] > m_LOWPT1[w]) {
 827                                         do {
 828                                                 y = max(y,m_TSTACK_h[m_top]);
 829                                                 b = m_TSTACK_b[m_top--];
 830                                         } while (m_TSTACK_a[m_top] > m_LOWPT1[w]);
 831                                         TSTACK_push(y,m_LOWPT1[w],b);
 832                                 } else {
 833                                         TSTACK_push(wnum+m_ND[w]-1,m_LOWPT1[w],vnum);
 834                                 }
 835                                 TSTACK_pushEOS();
 836                         }
 837
 838                         pathSearch(G,w);
 839
 840                         m_ESTACK.push(m_TREE_ARC[w]);  // add (v,w) to ESTACK (can differ from e!)
 841
 842                         node x;
 843
 844                         while (vnum != 1 && ((m_TSTACK_a[m_top] == vnum) ||
 845                                 (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum)))
 846                         {
 847                                 a = m_TSTACK_a[m_top];
 848                                 b = m_TSTACK_b[m_top];
 849
 850                                 edge eVirt;
 851
 852                                 if (a == vnum && m_FATHER[m_NODEAT[b]] == m_NODEAT[a]) {
 853                                         m_top--;
 854                                 }
 855
 856                                 else {
 857                                         edge e_ab = 0;
 858
 859                                         if (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum) {
 860 #ifdef TRIC_COMP_OUTPUT
 861                                                 cout << endl << "\nfound type-2 separation pair " <<
 862                                                         m_pGC->original(v) << ", " <<
 863                                                         m_pGC->original(m_A[w].front()->target());
 864 #endif
 865
 866                                                 edge e1 = m_ESTACK.pop();
 867                                                 edge e2 = m_ESTACK.pop();
 868                                                 m_A[w].del(m_IN_ADJ[e2]);
 869
 870                                                 x = e2->target();
 871
 872                                                 eVirt = m_pGC->newEdge(v,x);
 873                                                 m_DEGREE[x]--; m_DEGREE[v]--;
 874
 875                                                 OGDF_ASSERT(e2->source() == w);
 876                                                 CompStruct &C = newComp(polygon);
 877                                                 C << e1 << e2 << eVirt;
 878
 879                                                 if (!m_ESTACK.empty()) {
 880                                                         e1 = m_ESTACK.top();
 881                                                         if (e1->source() == x && e1->target() == v) {
 882                                                                 e_ab = m_ESTACK.pop();
 883                                                                 m_A[x].del(m_IN_ADJ[e_ab]);
 884                                                                 delHigh(e_ab);
 885                                                         }
 886                                                 }
 887
 888                                         } else {
 889 #ifdef TRIC_COMP_OUTPUT
 890                                                 cout << "\nfound type-2 separation pair " <<
 891                                                         m_pGC->original(m_NODEAT[a]) << ", " <<
 892                                                         m_pGC->original(m_NODEAT[b]);
 893 #endif
 894
 895                                                 int h = m_TSTACK_h[m_top--];
 896
 897                                                 CompStruct &C = newComp();
 898                                                 while(true) {
 899                                                         edge xy = m_ESTACK.top();
 900                                                         x = xy->source(); node y = xy->target();
 901                                                         if (!(a <= m_NEWNUM[x] && m_NEWNUM[x] <= h &&
 902                                                                 a <= m_NEWNUM[y] && m_NEWNUM[y] <= h)) break;
 903
 904                                                         if ((m_NEWNUM[x] == a && m_NEWNUM[y] == b) ||
 905                                                                 (m_NEWNUM[y] == a && m_NEWNUM[x] == b))
 906                                                         {
 907                                                                 e_ab = m_ESTACK.pop();
 908                                                                 m_A[e_ab->source()].del(m_IN_ADJ[e_ab]);
 909                                                                 delHigh(e_ab);
 910
 911                                                         } else {
 912                                                                 edge eh = m_ESTACK.pop();
 913                                                                 if (it != m_IN_ADJ[eh]) {
 914                                                                         m_A[eh->source()].del(m_IN_ADJ[eh]);
 915                                                                         delHigh(eh);
 916                                                                 }
 917                                                                 C << eh;
 918                                                                 m_DEGREE[x]--; m_DEGREE[y]--;
 919                                                         }
 920                                                 }
 921
 922                                                 eVirt = m_pGC->newEdge(m_NODEAT[a],m_NODEAT[b]);
 923                                                 C.finishTricOrPoly(eVirt);
 924                                                 x = m_NODEAT[b];
 925                                         }
 926
 927                                         if (e_ab != 0) {
 928                                                 CompStruct &C = newComp(bond);
 929                                                 C << e_ab << eVirt;
 930
 931                                                 eVirt = m_pGC->newEdge(v,x);
 932                                                 C << eVirt;
 933
 934                                                 m_DEGREE[x]--; m_DEGREE[v]--;
 935                                         }
 936
 937                                         m_ESTACK.push(eVirt);
 938                                         *it = eVirt;
 939                                         m_IN_ADJ[eVirt] = it;
 940
 941                                         m_DEGREE[x]++; m_DEGREE[v]++;
 942                                         m_FATHER[x] = v;
 943                                         m_TREE_ARC[x] = eVirt;
 944                                         m_TYPE[eVirt] = tree;
 945
 946                                         w = x; wnum = m_NEWNUM[w];
 947                                 }
 948                         }
 949
 950                         if (m_LOWPT2[w] >= vnum && m_LOWPT1[w] < vnum && (m_FATHER[v] != m_start || outv >= 2))
 951                         {
 952 #ifdef TRIC_COMP_OUTPUT
 953                                 cout << "\nfound type-1 separation pair " <<
 954                                         m_pGC->original(m_NODEAT[m_LOWPT1[w]]) << ", " <<
 955                                         m_pGC->original(v);
 956 #endif
 957
 958                                 CompStruct &C = newComp();
 959                                 edge xy;
 960                                 int x;
 961                                 while (!m_ESTACK.empty()) {
 962                                         xy = m_ESTACK.top();
 963                                         x = m_NEWNUM[xy->source()];
 964                                         y = m_NEWNUM[xy->target()];
 965
 966                                         if (!((wnum <= x && x < wnum+m_ND[w]) || (wnum <= y && y < wnum+m_ND[w])))
 967                                                 break;
 968
 969                                         C << m_ESTACK.pop();
 970                                         delHigh(xy);
 971                                         m_DEGREE[m_NODEAT[x]]--; m_DEGREE[m_NODEAT[y]]--;
 972                                 }
 973
 974                                 edge eVirt = m_pGC->newEdge(v,m_NODEAT[m_LOWPT1[w]]);
 975                                 C.finishTricOrPoly(eVirt);
 976
 977                                 if ((x == vnum && y == m_LOWPT1[w]) || (y == vnum && x == m_LOWPT1[w])) {
 978                                         CompStruct &C = newComp(bond);
 979                                         edge eh = m_ESTACK.pop();
 980                                         if (m_IN_ADJ[eh] != it) {
 981                                                 m_A[eh->source()].del(m_IN_ADJ[eh]);
 982                                         }
 983                                         C << eh << eVirt;
 984                                         eVirt = m_pGC->newEdge(v,m_NODEAT[m_LOWPT1[w]]);
 985                                         C << eVirt;
 986                                         m_IN_HIGH[eVirt] = m_IN_HIGH[eh];
 987                                         m_DEGREE[v]--;
 988                                         m_DEGREE[m_NODEAT[m_LOWPT1[w]]]--;
 989                                 }
 990
 991                                 if (m_NODEAT[m_LOWPT1[w]] != m_FATHER[v]) {
 992                                         m_ESTACK.push(eVirt);
 993                                         *it = eVirt;
 994                                         m_IN_ADJ[eVirt] = it;
 995                                         if (!m_IN_HIGH[eVirt].valid() && high(m_NODEAT[m_LOWPT1[w]]) < vnum)
 996                                                 m_IN_HIGH[eVirt] = m_HIGHPT[m_NODEAT[m_LOWPT1[w]]].pushFront(vnum);
 997
 998                                         m_DEGREE[v]++;
 999                                         m_DEGREE[m_NODEAT[m_LOWPT1[w]]]++;
1000
1001                                 } else {
1002                                         Adj.del(it);
1003
1004                                         CompStruct &C = newComp(bond);
1005                                         C << eVirt;
1006                                         eVirt = m_pGC->newEdge(m_NODEAT[m_LOWPT1[w]],v);
1007                                         C << eVirt;
1008
1009                                         edge eh = m_TREE_ARC[v];
1010
1011                                         C << m_TREE_ARC[v];
1012
1013                                         m_TREE_ARC[v] = eVirt;
1014                                         m_TYPE[eVirt] = tree;
1015
1016                                         m_IN_ADJ[eVirt] = m_IN_ADJ[eh];
1017                                         *m_IN_ADJ[eh] = eVirt;
1018                                 }
1019                         }
1020
1021                         if (m_START[e]) {
1022                                 while (TSTACK_notEOS()) {
1023                                         m_top--;
1024                                 }
1025                                 m_top--;
1026                         }
1027
1028                         while (TSTACK_notEOS() &&
1029                                 m_TSTACK_b[m_top] != vnum && high(v) > m_TSTACK_h[m_top]) {
1030                                 m_top--;
1031                         }
1032
1033                         outv--;
1034
1035                 } else { // frond arc
1036                         if (m_START[e]) {
1037                                 y = 0;
1038                                 if (m_TSTACK_a[m_top] > wnum) {
1039                                         do {
1040                                                 y = max(y,m_TSTACK_h[m_top]);
1041                                                 b = m_TSTACK_b[m_top--];
1042                                         } while (m_TSTACK_a[m_top] > wnum);
1043                                         TSTACK_push(y,wnum,b);
1044                                 } else {
1045                                         TSTACK_push(vnum,wnum,vnum);
1046                                 }
1047                         }
1048
1049                         m_ESTACK.push(e);  // add (v,w) to ESTACK
1050                 }
1051         }
1052 }
1053
1054 // simplified path search for triconnectivity test
1055 bool TricComp::pathSearch (const Graph &G, node v, node &s1, node &s2)
1056 {
1057         node w;
1058         edge e;
1059         int y, vnum = m_NEWNUM[v], wnum;
1060         int a, b;
1061
1062         List<edge> &Adj = m_A[v];
1063         int outv = Adj.size();
1064
1065         ListIterator<edge> it, itNext;
1066         for(it = Adj.begin(); it.valid(); it=itNext)
1067         {
1068                 itNext = it.succ();
1069                 e = *it;
1070                 w = e->target(); wnum = m_NEWNUM[w];
1071
1072                 if (m_TYPE[e] == tree) {
1073
1074                         if (m_START[e]) {
1075                                 y = 0;
1076                                 if (m_TSTACK_a[m_top] > m_LOWPT1[w]) {
1077                                         do {
1078                                                 y = max(y,m_TSTACK_h[m_top]);
1079                                                 b = m_TSTACK_b[m_top--];
1080                                         } while (m_TSTACK_a[m_top] > m_LOWPT1[w]);
1081                                         TSTACK_push(y,m_LOWPT1[w],b);
1082                                 } else {
1083                                         TSTACK_push(wnum+m_ND[w]-1,m_LOWPT1[w],vnum);
1084                                 }
1085                                 TSTACK_pushEOS();
1086                         }
1087
1088                         if(pathSearch(G,w,s1,s2) == false)
1089                                 return false;
1090
1091                         while (vnum != 1 && ((m_TSTACK_a[m_top] == vnum) ||
1092                                 (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum)))
1093                         {
1094                                 a = m_TSTACK_a[m_top];
1095                                 b = m_TSTACK_b[m_top];
1096
1097                                 if (a == vnum && m_FATHER[m_NODEAT[b]] == m_NODEAT[a]) {
1098                                         m_top--;
1099
1100                                 } else if (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum)
1101                                 {
1102                                         s1 = v;
1103                                         s2 = m_A[w].front()->target();
1104                                         return false;
1105
1106                                 } else {
1107                                         s1 = m_NODEAT[a];
1108                                         s2 = m_NODEAT[b];
1109                                         return false;
1110                                 }
1111                         }
1112
1113                         if (m_LOWPT2[w] >= vnum && m_LOWPT1[w] < vnum && (m_FATHER[v] != m_start || outv >= 2))
1114                         {
1115                                 s1 = m_NODEAT[m_LOWPT1[w]];
1116                                 s2 = v;
1117                                 return false;
1118                         }
1119
1120                         if (m_START[e]) {
1121                                 while (TSTACK_notEOS()) {
1122                                         m_top--;
1123                                 }
1124                                 m_top--;
1125                         }
1126
1127                         while (TSTACK_notEOS() &&
1128                                 m_TSTACK_b[m_top] != vnum && high(v) > m_TSTACK_h[m_top]) {
1129                                 m_top--;
1130                         }
1131
1132                         outv--;
1133
1134                 } else { // frond arc
1135                         if (m_START[e]) {
1136                                 y = 0;
1137                                 if (m_TSTACK_a[m_top] > wnum) {
1138                                         do {
1139                                                 y = max(y,m_TSTACK_h[m_top]);
1140                                                 b = m_TSTACK_b[m_top--];
1141                                         } while (m_TSTACK_a[m_top] > wnum);
1142                                         TSTACK_push(y,wnum,b);
1143                                 } else {
1144                                         TSTACK_push(vnum,wnum,vnum);
1145                                 }
1146                         }
1147                 }
1148         }
1149
1150         return true;
1151 }
1152
1153
1154 // triconnectivity test
1155 bool isTriconnected(const Graph &G, node &s1, node &s2)
1156 {
1157         bool isTric;
1158         TricComp tric2(G,isTric,s1,s2);
1159
1160         return isTric;
1161 }
1162
1163
1164 //----------------------------------------------------------
1165 //                       debugging stuff
1166 //----------------------------------------------------------
1167
1168 void TricComp::printOs(edge e)
1169 {
1170 #ifdef TRIC_COMP_OUTPUT
1171         cout << " (" << m_pGC->original(e->source()) << "," <<
1172                 m_pGC->original(e->target()) << "," << e->index() << ")";
1173         if (m_pGC->original(e) == 0) cout << "v";
1174 #endif
1175 }
1176
1177 void TricComp::printStacks()
1178 {
1179 #ifdef TRIC_COMP_OUTPUT
1180         cout << "\n\nTSTACK:" << endl;
1181
1182         for (int i = m_top; i >= 0; i--)
1183                 cout << "(" << m_TSTACK_h[i] << "," << m_TSTACK_a[i] << "," << m_TSTACK_b[i] << ")\n";
1184
1185         cout << "\nESTACK\n";
1186         while(!m_ESTACK.empty()) {
1187                 printOs(m_ESTACK.pop()); cout << endl;
1188         }
1189 #endif
1190 }
1191
1192
1193 } // end namespace ogdf
1194