ext/OGDF/src/basic/simple_graph_alg.cpp

   1 /*
   2  * $Revision: 2594 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-15 15:35:29 +0200 (So, 15. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of simple graph algorithms
  11  *
  12  * \author Carsten Gutwenger, Sebastian Leipert
  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/basic/simple_graph_alg.h>
  45 #include <ogdf/basic/SList.h>
  46 #include <ogdf/basic/Stack.h>
  47 #include <ogdf/basic/GraphCopy.h>
  48 #include <ogdf/basic/tuples.h>
  49 #include <ogdf/basic/BoundedStack.h>
  50
  51
  52 namespace ogdf {
  53
  54
  55 //---------------------------------------------------------
  56 // isLoopFree(), makeLoopFree()
  57 // testing for self-loops, removing self-loops
  58 //---------------------------------------------------------
  59 bool isLoopFree(const Graph &G)
  60 {
  61         edge e;
  62         forall_edges(e,G)
  63                 if(e->isSelfLoop()) return false;
  64
  65         return true;
  66 }
  67
  68
  69 void makeLoopFree(Graph &G)
  70 {
  71         edge e, eNext;
  72         for (e = G.firstEdge(); e; e = eNext) {
  73                 eNext = e->succ();
  74                 if (e->isSelfLoop()) G.delEdge(e);
  75         }
  76 }
  77
  78
  79 //---------------------------------------------------------
  80 // isParallelFree(), makeParallelFree()
  81 // testing for multi-edges, removing multi-edges
  82 //---------------------------------------------------------
  83
  84 void parallelFreeSort(const Graph &G, SListPure<edge> &edges)
  85 {
  86         G.allEdges(edges);
  87
  88         BucketSourceIndex bucketSrc;
  89         edges.bucketSort(0,G.maxNodeIndex(),bucketSrc);
  90
  91         BucketTargetIndex bucketTgt;
  92         edges.bucketSort(0,G.maxNodeIndex(),bucketTgt);
  93 }
  94
  95
  96 bool isParallelFree(const Graph &G)
  97 {
  98         if (G.numberOfEdges() <= 1) return true;
  99
 100         SListPure<edge> edges;
 101         parallelFreeSort(G,edges);
 102
 103         SListConstIterator<edge> it = edges.begin();
 104         edge ePrev = *it, e;
 105         for(it = ++it; it.valid(); ++it, ePrev = e) {
 106                 e = *it;
 107                 if (ePrev->source() == e->source() && ePrev->target() == e->target())
 108                         return false;
 109         }
 110
 111         return true;
 112 }
 113
 114
 115 int numParallelEdges(const Graph &G)
 116 {
 117         if (G.numberOfEdges() <= 1) return 0;
 118
 119         SListPure<edge> edges;
 120         parallelFreeSort(G,edges);
 121
 122         int num = 0;
 123         SListConstIterator<edge> it = edges.begin();
 124         edge ePrev = *it, e;
 125         for(it = ++it; it.valid(); ++it, ePrev = e) {
 126                 e = *it;
 127                 if (ePrev->source() == e->source() && ePrev->target() == e->target())
 128                         ++num;
 129         }
 130
 131         return num;
 132 }
 133
 134
 135
 136 //---------------------------------------------------------
 137 // isParallelFreeUndirected(), makeParallelFreeUndirected()
 138 // testing for (undirected) multi-edges, removing (undirected) multi-edges
 139 //---------------------------------------------------------
 140
 141 void parallelFreeSortUndirected(const Graph &G,
 142         SListPure<edge> &edges,
 143         EdgeArray<int> &minIndex,
 144         EdgeArray<int> &maxIndex)
 145 {
 146         G.allEdges(edges);
 147
 148         edge e;
 149         forall_edges(e,G) {
 150                 int srcIndex = e->source()->index(), tgtIndex = e->target()->index();
 151                 if (srcIndex <= tgtIndex) {
 152                         minIndex[e] = srcIndex; maxIndex[e] = tgtIndex;
 153                 } else {
 154                         minIndex[e] = tgtIndex; maxIndex[e] = srcIndex;
 155                 }
 156         }
 157
 158         BucketEdgeArray bucketMin(minIndex), bucketMax(maxIndex);
 159         edges.bucketSort(0,G.maxNodeIndex(),bucketMin);
 160         edges.bucketSort(0,G.maxNodeIndex(),bucketMax);
 161 }
 162
 163
 164 bool isParallelFreeUndirected(const Graph &G)
 165 {
 166         if (G.numberOfEdges() <= 1) return true;
 167
 168         SListPure<edge> edges;
 169         EdgeArray<int> minIndex(G), maxIndex(G);
 170         parallelFreeSortUndirected(G,edges,minIndex,maxIndex);
 171
 172         SListConstIterator<edge> it = edges.begin();
 173         edge ePrev = *it, e;
 174         for(it = ++it; it.valid(); ++it, ePrev = e) {
 175                 e = *it;
 176                 if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e])
 177                         return false;
 178         }
 179
 180         return true;
 181 }
 182
 183
 184 int numParallelEdgesUndirected(const Graph &G)
 185 {
 186         if (G.numberOfEdges() <= 1) return 0;
 187
 188         SListPure<edge> edges;
 189         EdgeArray<int> minIndex(G), maxIndex(G);
 190         parallelFreeSortUndirected(G,edges,minIndex,maxIndex);
 191
 192         int num = 0;
 193         SListConstIterator<edge> it = edges.begin();
 194         edge ePrev = *it, e;
 195         for(it = ++it; it.valid(); ++it, ePrev = e) {
 196                 e = *it;
 197                 if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e])
 198                         ++num;
 199         }
 200
 201         return num;
 202 }
 203
 204
 205
 206 //---------------------------------------------------------
 207 // isConnected(), makeConnected()
 208 // testing connectivity, establishing connectivity
 209 //---------------------------------------------------------
 210
 211 bool isConnected(const Graph &G)
 212 {
 213         node v = G.firstNode();
 214         if (v == 0) return true;
 215
 216         int count = 0;
 217         NodeArray<bool> visited(G,false);
 218         BoundedStack<node> S(G.numberOfNodes());
 219
 220         S.push(v);
 221         visited[v] = true;
 222         while(!S.empty()) {
 223                 v = S.pop();
 224                 ++count;
 225
 226                 adjEntry adj;
 227                 forall_adj(adj,v) {
 228                         node w = adj->twinNode();
 229                         if(!visited[w]) {
 230                                 visited[w] = true;
 231                                 S.push(w);
 232                         }
 233                 }
 234         }
 235
 236         return (count == G.numberOfNodes());
 237 }
 238
 239
 240 void makeConnected(Graph &G, List<edge> &added)
 241 {
 242         added.clear();
 243         if (G.numberOfNodes() == 0) return;
 244         NodeArray<bool> visited(G,false);
 245         BoundedStack<node> S(G.numberOfNodes());
 246
 247         node pred = 0, u;
 248         forall_nodes(u,G)
 249         {
 250                 if (visited[u]) continue;
 251
 252                 node vMinDeg = u;
 253                 int  minDeg  = u->degree();
 254
 255                 S.push(u);
 256                 visited[u] = true;
 257
 258                 while(!S.empty())
 259                 {
 260                         node v = S.pop();
 261
 262                         adjEntry adj;
 263                         forall_adj(adj,v) {
 264                                 node w = adj->twinNode();
 265                                 if(!visited[w]) {
 266                                         visited[w] = true;
 267                                         S.push(w);
 268
 269                                         int wDeg = w->degree();
 270                                         if (wDeg < minDeg) {
 271                                                 vMinDeg = w;
 272                                                 minDeg  = wDeg;
 273                                         }
 274                                 }
 275                         }
 276                 }
 277
 278                 if (pred)
 279                         added.pushBack(G.newEdge(pred,vMinDeg));
 280                 pred = vMinDeg;
 281         }
 282 }
 283
 284
 285 int connectedComponents(const Graph &G, NodeArray<int> &component)
 286 {
 287         int nComponent = 0;
 288         component.fill(-1);
 289
 290         StackPure<node> S;
 291
 292         node v;
 293         forall_nodes(v,G) {
 294                 if (component[v] != -1) continue;
 295
 296                 S.push(v);
 297                 component[v] = nComponent;
 298
 299                 while(!S.empty()) {
 300                         node w = S.pop();
 301                         edge e;
 302                         forall_adj_edges(e,w) {
 303                                 node x = e->opposite(w);
 304                                 if (component[x] == -1) {
 305                                         component[x] = nComponent;
 306                                         S.push(x);
 307                                 }
 308                         }
 309                 }
 310
 311                 ++nComponent;
 312         }
 313
 314         return nComponent;
 315 }
 316
 317 //return the isolated nodes too, is used in incremental layout
 318 int connectedIsolatedComponents(const Graph &G, List<node> &isolated,
 319                                                                 NodeArray<int> &component)
 320 {
 321         int nComponent = 0;
 322         component.fill(-1);
 323
 324         StackPure<node> S;
 325
 326         node v;
 327         forall_nodes(v,G) {
 328                 if (component[v] != -1) continue;
 329
 330                 S.push(v);
 331                 component[v] = nComponent;
 332
 333                 while(!S.empty()) {
 334                         node w = S.pop();
 335                         if (w->degree() == 0) isolated.pushBack(w);
 336                         edge e;
 337                         forall_adj_edges(e,w) {
 338                                 node x = e->opposite(w);
 339                                 if (component[x] == -1) {
 340                                         component[x] = nComponent;
 341                                         S.push(x);
 342                                 }
 343                         }
 344                 }
 345
 346                 ++nComponent;
 347         }
 348
 349         return nComponent;
 350 }//connectedIsolated
 351
 352
 353 //---------------------------------------------------------
 354 // isBiconnected(), makeBiconnected()
 355 // testing biconnectivity, establishing biconnectivity
 356 //---------------------------------------------------------
 357 static node dfsIsBicon (const Graph &G, node v, node father,
 358         NodeArray<int> &number, NodeArray<int> &lowpt, int &numCount)
 359 {
 360         node first_son = 0;
 361
 362         lowpt[v] = number[v] = ++numCount;
 363
 364         edge e;
 365         forall_adj_edges(e,v) {
 366                 node w = e->opposite(v);
 367                 if (v == w) continue; // ignore self-loops
 368
 369                 if (number[w] == 0) {
 370                         if (first_son == 0) first_son = w;
 371
 372                         node cutVertex = dfsIsBicon(G,w,v,number,lowpt,numCount);
 373                         if (cutVertex) return cutVertex;
 374
 375                         // is v cut vertex ?
 376                         if (lowpt[w] >= number[v] && (w != first_son || father != 0))
 377                                 return v;
 378
 379                         if (lowpt[w] < lowpt[v]) lowpt[v] = lowpt[w];
 380
 381                 } else {
 382
 383                         if (number[w] < lowpt[v]) lowpt[v] = number[w];
 384                 }
 385         }
 386
 387         return 0;
 388 }
 389
 390
 391 bool isBiconnected(const Graph &G, node &cutVertex)
 392 {
 393         if (G.empty()) return true;
 394
 395         NodeArray<int> number(G,0);
 396         NodeArray<int> lowpt(G);
 397         int numCount = 0;
 398
 399         cutVertex = dfsIsBicon(G,G.firstNode(),0,number,lowpt,numCount);
 400
 401         return (numCount == G.numberOfNodes() && cutVertex == 0);
 402 }
 403
 404
 405 static void dfsMakeBicon (Graph &G,
 406         node v, node father,
 407         NodeArray<int> &number,
 408         NodeArray<int> &lowpt,
 409         int &numCount,
 410         List<edge> &added)
 411 {
 412         node predSon = 0;
 413
 414         lowpt[v] = number[v] = ++numCount;
 415
 416         edge e;
 417         forall_adj_edges(e,v) {
 418                 node w = e->opposite(v);
 419                 if (v == w) continue; // ignore self-loops
 420
 421                 if (number[w] == 0) {
 422
 423                         dfsMakeBicon(G,w,v,number,lowpt,numCount,added);
 424
 425                         // is v cut vertex ?
 426                         if (lowpt[w] >= number[v]) {
 427                                 if (predSon == 0 && father != 0)
 428                                         added .pushBack(G.newEdge(w,father));
 429
 430                                 else if (predSon != 0)
 431                                         added.pushBack(G.newEdge(w,predSon));
 432                         }
 433
 434                         if (lowpt[w] < lowpt[v]) lowpt[v] = lowpt[w];
 435                         predSon = w;
 436
 437                 } else {
 438
 439                         if (number[w] < lowpt[v]) lowpt[v] = number[w];
 440                 }
 441         }
 442 }
 443
 444
 445 void makeBiconnected(Graph &G, List<edge> &added)
 446 {
 447         if (G.empty()) return;
 448
 449         makeConnected(G,added);
 450
 451         NodeArray<int> number(G,0);
 452         NodeArray<int> lowpt(G);
 453         int numCount = 0;
 454
 455         dfsMakeBicon(G,G.firstNode(),0,number,lowpt,numCount,added);
 456 }
 457
 458
 459 //---------------------------------------------------------
 460 // biconnectedComponents()
 461 // computing biconnected components
 462 //---------------------------------------------------------
 463 static void dfsBiconComp (const Graph &G,
 464         node v,
 465         node father,
 466         NodeArray<int> &number,
 467         NodeArray<int> &lowpt,
 468         StackPure<node> &called,
 469         EdgeArray<int> &component,
 470         int &nNumber,
 471         int &nComponent)
 472 {
 473         lowpt[v] = number[v] = ++nNumber;
 474         called.push(v);
 475
 476         edge e;
 477         forall_adj_edges(e,v) {
 478                 node w = e->opposite(v);
 479                 if (v == w) continue; // ignore self-loops
 480
 481                 if (number[w] == 0) {
 482
 483                         dfsBiconComp(G,w,v,number,lowpt,called,component,
 484                                 nNumber,nComponent);
 485
 486                         if (lowpt[w] < lowpt[v]) lowpt[v] = lowpt[w];
 487
 488                 } else {
 489
 490                         if (number[w] < lowpt[v]) lowpt[v] = number[w];
 491                 }
 492         }
 493
 494         if (father && (lowpt[v] == number[father])) {
 495                 node w;
 496                 do {
 497                         w = called.top(); called.pop();
 498
 499                         forall_adj_edges(e,w) {
 500                                 if (number[w] > number[e->opposite(w)])
 501                                         component[e] = nComponent;
 502                         }
 503                 } while (w != v);
 504
 505                 ++nComponent;
 506         }
 507 }
 508
 509
 510 int biconnectedComponents(const Graph &G, EdgeArray<int> &component)
 511 {
 512         if (G.empty()) return 0;
 513
 514         StackPure<node> called;
 515         NodeArray<int> number(G,0);
 516         NodeArray<int> lowpt(G);
 517         int nNumber = 0, nComponent = 0, nIsolated = 0;
 518
 519         node v;
 520         forall_nodes(v,G) {
 521                 if (number[v] == 0) {
 522                         bool isolated = true;
 523                         edge e;
 524                         forall_adj_edges(e,v)
 525                                 if (!e->isSelfLoop()) {
 526                                         isolated = false; break;
 527                                 }
 528
 529                         if (isolated)
 530                                 ++nIsolated;
 531                         else
 532                                 dfsBiconComp(G,v,0,number,lowpt,called,component,
 533                                         nNumber,nComponent);
 534                 }
 535         }
 536
 537         return nComponent + nIsolated;
 538 }
 539
 540
 541 //---------------------------------------------------------
 542 // isTriconnected()
 543 // testing triconnectivity
 544 //---------------------------------------------------------
 545 bool isTriconnectedPrimitive(const Graph &G, node &s1, node &s2)
 546 {
 547         s1 = s2 = 0;
 548
 549         if (isConnected(G) == false)
 550                 return false;
 551
 552         if (isBiconnected(G,s1) == false)
 553                 return false;
 554
 555         if (G.numberOfNodes() <= 3)
 556                 return true;
 557
 558         // make a copy of G
 559         GraphCopySimple GC(G);
 560
 561         // for each node v in G, we test if G \ v is biconnected
 562         node v;
 563         forall_nodes(v,G)
 564         {
 565                 node vC = GC.copy(v), wC;
 566
 567                 // store adjacent nodes
 568                 SListPure<node> adjacentNodes;
 569                 edge eC;
 570                 forall_adj_edges(eC,vC) {
 571                         wC = eC->opposite(vC);
 572                         // forget self-loops (vC would no longer be in GC!)
 573                         if (wC != vC)
 574                                 adjacentNodes.pushBack(wC);
 575                 }
 576
 577                 GC.delNode(vC);
 578
 579                 // test for biconnectivity
 580                 if(isBiconnected(GC,wC) == false) {
 581                         s1 = v; s2 = GC.original(wC);
 582                         return false;
 583                 }
 584
 585                 // restore deleted node with adjacent edges
 586                 vC = GC.newNode(v);
 587                 SListConstIterator<node> it;
 588                 for(it = adjacentNodes.begin(); it.valid(); ++it)
 589                         GC.newEdge(vC,*it);
 590         }
 591
 592         return true;
 593 }
 594
 595
 596 //--------------------------------------------------------------------------
 597 // triangulate()
 598 //--------------------------------------------------------------------------
 599 void triangulate(Graph &G)
 600 {
 601         OGDF_ASSERT(isSimple(G));
 602
 603         CombinatorialEmbedding E(G);
 604
 605         OGDF_ASSERT(E.consistencyCheck());
 606
 607         node v;
 608         edge e;
 609         adjEntry adj, succ, succ2, succ3;
 610         NodeArray<int> marked(E.getGraph(), 0);
 611
 612         forall_nodes(v,E.getGraph()) {
 613                 marked.init(E.getGraph(), 0);
 614
 615                 forall_adj(adj,v) {
 616                         marked[adj->twinNode()] = 1;
 617                 }
 618
 619                 // forall faces adj to v
 620                 forall_adj(adj,v) {
 621                         succ = adj->faceCycleSucc();
 622                         succ2 = succ->faceCycleSucc();
 623
 624                         if (succ->twinNode() != v && adj->twinNode() != v) {
 625                                 while (succ2->twinNode() != v) {
 626                                         if (marked[succ2->theNode()] == 1) {
 627                                                 // edge e=(x2,x4)
 628                                                 succ3 = succ2->faceCycleSucc();
 629                                                 E.splitFace(succ, succ3);
 630                                         }
 631                                         else {
 632                                                 // edge e=(v=x1,x3)
 633                                                 e = E.splitFace(adj, succ2);
 634                                                 marked[succ2->theNode()] = 1;
 635
 636                                                 // old adj is in wrong face
 637                                                 adj = e->adjSource();
 638                                         }
 639                                         succ = adj->faceCycleSucc();
 640                                         succ2 = succ->faceCycleSucc();
 641                                 }
 642                         }
 643                 }
 644         }
 645 }
 646
 647
 648 //--------------------------------------------------------------------------
 649 // isAcyclic(), isAcyclicUndirected(), makeAcyclic(), makeAcyclicByReverse()
 650 // testing acyclicity, establishing acyclicity
 651 //--------------------------------------------------------------------------
 652 void dfsIsAcyclic(const Graph &G,
 653         node v,
 654         NodeArray<int> &number,
 655         NodeArray<int> &completion,
 656         int &nNumber,
 657         int &nCompletion)
 658 {
 659         number[v] = ++nNumber;
 660
 661         edge e;
 662         forall_adj_edges(e,v) {
 663                 node w = e->target();
 664
 665                 if (number[w] == 0)
 666                         dfsIsAcyclic(G,w,number,completion,nNumber,nCompletion);
 667         }
 668
 669         completion[v] = ++nCompletion;
 670 }
 671
 672
 673 void dfsIsAcyclicUndirected(const Graph &G,
 674         node v,
 675         NodeArray<int> &number,
 676         int &nNumber,
 677         List<edge> &backedges)
 678 {
 679         number[v] = ++nNumber;
 680
 681         adjEntry adj;
 682         node w;
 683         forall_adj(adj,v) {
 684                 w = adj->twinNode();
 685                 if (number[w] == 0) {
 686                         dfsIsAcyclicUndirected(G,w,number,nNumber,backedges);
 687                 } else {
 688                         if (number[w] > number[v]) {
 689                                 backedges.pushBack(adj->theEdge());
 690                         }
 691                 }
 692         }
 693 }
 694
 695
 696 bool isAcyclic(const Graph &G, List<edge> &backedges)
 697 {
 698         backedges.clear();
 699
 700         NodeArray<int> number(G,0), completion(G);
 701         int nNumber = 0, nCompletion = 0;
 702
 703         node v;
 704         forall_nodes(v,G)
 705                 if (number[v] == 0)
 706                         dfsIsAcyclic(G,v,number,completion,nNumber,nCompletion);
 707
 708         edge e;
 709         forall_edges(e,G) {
 710                 node src = e->source(), tgt = e->target();
 711
 712                 if (number[src] >= number[tgt] && completion[src] <= completion[tgt])
 713                         backedges.pushBack(e);
 714         }
 715
 716         return backedges.empty();
 717 }
 718
 719
 720 bool isAcyclicUndirected(const Graph &G, List<edge> &backedges)
 721 {
 722         backedges.clear();
 723         int nNumber = 0;
 724         NodeArray<int> number(G,0);
 725
 726         node v;
 727         forall_nodes(v,G) {
 728                 if (number[v] == 0) {
 729                         dfsIsAcyclicUndirected(G,v,number,nNumber,backedges);
 730                 }
 731         }
 732         return backedges.empty();
 733 }
 734
 735
 736 void makeAcyclic(Graph &G)
 737 {
 738         List<edge> backedges;
 739         isAcyclic(G,backedges);
 740
 741         ListIterator<edge> it;
 742         for(it = backedges.begin(); it.valid(); ++it)
 743                 G.delEdge(*it);
 744 }
 745
 746
 747 void makeAcyclicByReverse(Graph &G)
 748 {
 749         List<edge> backedges;
 750         isAcyclic(G,backedges);
 751
 752         ListIterator<edge> it;
 753         for(it = backedges.begin(); it.valid(); ++it)
 754                 if (!(*it)->isSelfLoop()) G.reverseEdge(*it);
 755 }
 756
 757
 758 //---------------------------------------------------------
 759 // hasSingleSource(), hasSingleSink()
 760 // testing for single source/sink
 761 //---------------------------------------------------------
 762 bool hasSingleSource(const Graph& G, node &s)
 763 {
 764         node v;
 765         s = 0;
 766
 767         forall_nodes(v,G) {
 768                 if (v->indeg() == 0) {
 769                         if (s != 0) {
 770                                 s = 0;
 771                                 return false;
 772                         } else s = v;
 773                 }
 774         }
 775         return (G.empty() || s != 0);
 776 }
 777
 778
 779 bool hasSingleSink(const Graph& G, node &t)
 780 {
 781         node v;
 782         t = 0;
 783
 784         forall_nodes(v,G) {
 785                 if (v->outdeg() == 0) {
 786                         if (t != 0) {
 787                                 t = 0;
 788                                 return false;
 789                         } else t = v;
 790                 }
 791         }
 792         return (G.empty() || t != 0);
 793 }
 794
 795
 796 //---------------------------------------------------------
 797 // isStGraph()
 798 // true <=> G is st-graph, i.e., is acyclic, contains exactly one source s
 799 //   and one sink t, and the edge (s,t); returns single source s and single
 800 //   sink t if contained (otherwise they are set to 0), and edge st if
 801 //   contained (otherwise 0)
 802 //---------------------------------------------------------
 803 bool isStGraph(const Graph &G, node &s, node &t, edge &st)
 804 {
 805         st = 0;
 806
 807         hasSingleSource(G,s);
 808         hasSingleSink  (G,t);
 809
 810         if (s == 0 || t == 0 || isAcyclic(G) == false) {
 811                 s = t = 0;
 812                 return false;
 813         }
 814
 815         edge e;
 816         forall_adj_edges(e,s) {
 817                 if (e->target() == t) {
 818                         st = e;
 819                         break;
 820                 }
 821         }
 822
 823         return (st != 0);
 824 }
 825
 826
 827 //---------------------------------------------------------
 828 // topologicalNumbering()
 829 // computes a topological numbering of an acyclic graph
 830 //---------------------------------------------------------
 831
 832 void topologicalNumbering(const Graph &G, NodeArray<int> &num)
 833 {
 834         BoundedStack<node> S(G.numberOfNodes());
 835         NodeArray<int> indeg(G);
 836
 837         node v;
 838         forall_nodes(v,G)
 839                 if((indeg[v] = v->indeg()) == 0)
 840                         S.push(v);
 841
 842         int count = 0;
 843         while(!S.empty()) {
 844                 node v = S.pop();
 845                 num[v] = count++;
 846
 847                 edge e;
 848                 forall_adj_edges(e,v) {
 849                         node u = e->target();
 850                         if(u != v) {
 851                                 if(--indeg[u] == 0)
 852                                         S.push(u);
 853                         }
 854                 }
 855         }
 856 }
 857
 858
 859 //---------------------------------------------------------
 860 // strongComponents()
 861 // computes the strongly connected components
 862 //---------------------------------------------------------
 863
 864 //! Computes the strongly connected components with the algorithm of Tarjan.
 865 /**
 866  * @param G         is the input graph.
 867  * @param w         is the current node.
 868  * @param S         is the stack containing all vertices of the current
 869  *                  component during the algorithm
 870  * @param pre       is the preorder number.
 871  * @param low       is the lowest reachable preorder number (lowpoint).
 872  * @param cnt       is the counter for the dfs-number.
 873  * @param scnt      is the counter for the components.
 874  * @param component is assigned a mapping from nodes to component numbers.
 875  */
 876 void dfsStrongComponents(
 877         const Graph& G,
 878         node w,
 879         BoundedStack<node>& S,
 880         NodeArray<int>& pre,
 881         NodeArray<int>& low,
 882         int& cnt,
 883         int& scnt,
 884         NodeArray<int>& component)
 885 {
 886         S.push(w);
 887         int min = cnt;
 888         low[w] = cnt;
 889         pre[w] = cnt;
 890         cnt++;
 891         node t;
 892         edge e;
 893         forall_adj_edges(e, w) {
 894                 if (e->source() == w) {
 895                         t = e->target();
 896                         if(pre[t] == -1) {
 897                                 dfsStrongComponents(G, t, S, pre, low, cnt, scnt, component);
 898                         }
 899                         if (low[t] < low[w])
 900                                 min = low[t];
 901                 }
 902         }
 903         if (min < low[w]) {
 904                 low[w] = min;
 905                 return;
 906         }
 907         do {
 908                 t = S.pop();
 909                 component[t] = scnt;
 910                 low[t] = G.numberOfNodes();
 911         } while (t != w);
 912         scnt++;
 913 }
 914
 915 int strongComponents(const Graph& G, NodeArray<int>& component)
 916 {
 917         if (G.numberOfNodes() == 0)
 918                 return 0;
 919         if (G.numberOfNodes() == 1){
 920                 component[G.firstNode()] = 0;
 921                 return 1;
 922         }
 923         NodeArray<int> pre(G, -1);
 924         NodeArray<int> low(G, G.numberOfNodes());
 925         BoundedStack<node> S(G.numberOfNodes());
 926         int cnt = 0;
 927         int scnt = 0;
 928         node v;
 929         forall_nodes(v, G){
 930                 if (pre[v] == -1){
 931                         dfsStrongComponents(G, v, S, pre, low, cnt, scnt, component);
 932                 }
 933         }
 934         return scnt;
 935 }
 936
 937
 938 //---------------------------------------------------------
 939 // isFreeForest()
 940 // testing if graph represents a free forest
 941 //---------------------------------------------------------
 942
 943 bool isFreeForest(const Graph &G)
 944 {
 945         NodeArray<bool> visited(G,false);
 946
 947         node vFirst;
 948         forall_nodes(vFirst,G)
 949         {
 950                 if(visited[vFirst]) continue;
 951
 952                 StackPure<Tuple2<node,node> > S;
 953                 S.push(Tuple2<node,node>(vFirst,0));
 954
 955                 while(!S.empty())
 956                 {
 957                         Tuple2<node,node> t = S.pop();
 958                         node v      = t.x1();
 959                         node parent = t.x2();
 960
 961                         visited[v] = true;
 962
 963                         adjEntry adj;
 964                         forall_adj(adj,v)
 965                         {
 966                                 node w = adj->twinNode();
 967
 968                                 // skip edge to parent, but only once!
 969                                 if(w == parent) {
 970                                         parent = 0;
 971                                         continue;
 972                                 }
 973
 974                                 if(visited[w] == true)
 975                                         return false;
 976
 977                                 S.push(Tuple2<node,node>(w,v));
 978                         }
 979                 }
 980         }
 981
 982         return true;
 983 }
 984
 985
 986 //---------------------------------------------------------
 987 // isForest(), isTree()
 988 // testing if graph represents a forest/tree
 989 //---------------------------------------------------------
 990 static bool dfsIsForest (node v,
 991         NodeArray<bool> &visited,
 992         NodeArray<bool> &mark)
 993 {
 994         SListPure<node> sons;
 995
 996         visited[v] = true;
 997
 998         edge e;
 999         forall_adj_edges(e,v) {
1000                 node w = e->target();
1001                 if (w != v && !mark[w]) {
1002                         mark[w] = true;
1003                         sons.pushBack(w);
1004                 }
1005         }
1006
1007         SListIterator<node> it;
1008         for(it = sons.begin(); it.valid(); ++it)
1009                 mark[*it] = false;
1010
1011         while(!sons.empty()) {
1012                 node w = sons.front();
1013                 sons.popFront();
1014
1015                 if (visited [w] || dfsIsForest(w,visited,mark) == false)
1016                         return false;
1017         }
1018
1019         return true;
1020 }
1021
1022 bool isForest(const Graph& G, List<node> &roots)
1023 {
1024         roots.clear();
1025         if (G.empty()) return true;
1026
1027         NodeArray<bool> visited(G,false), mark(G,false);
1028
1029         node v;
1030         forall_nodes(v,G)
1031                 if (v->indeg() == 0) {
1032                         roots.pushBack(v);
1033                         if (dfsIsForest(v,visited,mark) == false)
1034                                 return false;
1035                 }
1036
1037         forall_nodes(v,G)
1038                 if (!visited[v]) return false;
1039
1040         return true;
1041 }
1042
1043
1044 bool isTree (const Graph& G, node &root)
1045 {
1046         List<node> roots;
1047
1048         if (isForest(G,roots) && roots.size() == 1) {
1049                 root = roots.front(); return true;
1050         }
1051         return false;
1052 }
1053
1054
1055
1056 } // end namespace ogdf