ext/OGDF/src/cluster/ClusterGraph.cpp

   1 /*
   2  * $Revision: 2573 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-10 18:48:33 +0200 (Di, 10. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements the class ClusterGraph, providing
  11  * extra functionality for clustered graphs.
  12  * A clustered graph C=(G,T) consists of an undirected graph G
  13  * and a rooted tree T in which the leaves of T correspond
  14  * to the vertices of G=(V,E).
  15  *
  16  * \author Sebastian Leipert, Karsten Klein
  17  *
  18  * \par License:
  19  * This file is part of the Open Graph Drawing Framework (OGDF).
  20  *
  21  * \par
  22  * Copyright (C)<br>
  23  * See README.txt in the root directory of the OGDF installation for details.
  24  *
  25  * \par
  26  * This program is free software; you can redistribute it and/or
  27  * modify it under the terms of the GNU General Public License
  28  * Version 2 or 3 as published by the Free Software Foundation;
  29  * see the file LICENSE.txt included in the packaging of this file
  30  * for details.
  31  *
  32  * \par
  33  * This program is distributed in the hope that it will be useful,
  34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  36  * GNU General Public License for more details.
  37  *
  38  * \par
  39  * You should have received a copy of the GNU General Public
  40  * License along with this program; if not, write to the Free
  41  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  42  * Boston, MA 02110-1301, USA.
  43  *
  44  * \see  http://www.gnu.org/copyleft/gpl.html
  45  ***************************************************************/
  46
  47
  48 #include <ogdf/cluster/ClusterGraph.h>
  49 #include <ogdf/cluster/ClusterArray.h>
  50 #include <ogdf/cluster/ClusterGraphObserver.h>
  51
  52 #include <limits.h>
  53 #include <ctype.h>
  54 #include <string.h>
  55
  56 #include <ogdf/basic/String.h>
  57 #include <ogdf/basic/AdjEntryArray.h>
  58
  59 #include <ogdf/fileformats/GmlParser.h>
  60
  61
  62 namespace ogdf {
  63
  64 #define MIN_CLUSTER_TABLE_SIZE (1 << 4)
  65
  66 //---------------------------------------------------------
  67 //node search in cluster hierarchy
  68 //---------------------------------------------------------
  69 void ClusterElement::getClusterInducedNodes(List<node> &clusterNodes) {
  70
  71         ListConstIterator<node> nit;
  72         for (nit=m_entries.begin(); nit.valid(); ++nit) {
  73                 clusterNodes.pushBack(*nit);
  74         }
  75         ListConstIterator<cluster> cit;
  76         for (cit=m_children.begin(); cit.valid(); ++cit) {
  77                 (*cit)->getClusterInducedNodes(clusterNodes);
  78         }
  79 }
  80
  81 void ClusterElement::getClusterNodes(List<node> &clusterNodes) {
  82
  83         clusterNodes.clear();
  84         getClusterInducedNodes(clusterNodes);
  85 }
  86
  87 void ClusterElement::getClusterInducedNodes(NodeArray<bool> &clusterNode, int& num) {
  88
  89         ListConstIterator<node> nit;
  90         for (nit=m_entries.begin(); nit.valid(); ++nit) {
  91                 clusterNode[*nit] = true;
  92                 num++;
  93         }
  94         ListConstIterator<cluster> cit;
  95         for (cit=m_children.begin(); cit.valid(); ++cit) {
  96                 (*cit)->getClusterInducedNodes(clusterNode, num);
  97         }
  98 }
  99
 100 int ClusterElement::getClusterNodes(NodeArray<bool> &clusterNode)
 101 {
 102         int num = 0;
 103         getClusterInducedNodes(clusterNode, num);
 104
 105         return num;
 106 }
 107
 108
 109 //---------------------------------------------------------
 110 // Construction
 111 //---------------------------------------------------------
 112
 113 ClusterGraph::ClusterGraph()
 114 {
 115         m_clusterIdCount = 0;
 116         m_postOrderStart = 0;
 117         m_rootCluster    = 0;
 118
 119         m_allowEmptyClusters = true;
 120         m_updateDepth   = false;
 121         m_depthUpToDate = false;
 122
 123         m_nClusters = 0;
 124         m_lcaNumber = 0;
 125         m_clusterArrayTableSize = MIN_CLUSTER_TABLE_SIZE;
 126         m_adjAvailable = false;
 127         m_lcaNumber = 0;
 128         m_lcaSearch = 0;
 129         m_vAncestor = 0;
 130         m_wAncestor = 0;
 131         //m_clusterDepth.init(*this, 0);
 132 }
 133
 134
 135
 136 // Construction of a new cluster graph. All nodes
 137 // are children of the root cluster
 138 ClusterGraph::ClusterGraph(const Graph &G) : GraphObserver(&G), m_pGraph(&G)
 139 {
 140         m_clusterIdCount = 0;
 141         m_postOrderStart = 0;
 142         m_rootCluster    = 0;
 143
 144         m_allowEmptyClusters = true;
 145         m_updateDepth   = false;
 146         m_depthUpToDate = false;
 147
 148         m_nClusters = 0;
 149         m_lcaNumber = 0;
 150         m_clusterArrayTableSize = G.nextPower2(MIN_CLUSTER_TABLE_SIZE, G.nodeArrayTableSize());
 151         //m_clusterDepth.init(*this, 0);
 152         initGraph(G);
 153 }
 154
 155
 156 ClusterGraph::ClusterGraph(const ClusterGraph &C) :
 157         GraphObserver(&(C.getGraph())),
 158         m_lcaSearch(0),
 159         m_vAncestor(0),
 160         m_wAncestor(0)
 161 {
 162         m_clusterIdCount = 0;
 163         m_postOrderStart = 0;
 164         m_rootCluster    = 0;
 165
 166         m_allowEmptyClusters = true;
 167         m_updateDepth   = false;
 168         m_depthUpToDate = false;
 169
 170         m_nClusters = 0;
 171         m_lcaNumber = 0;
 172
 173         m_clusterArrayTableSize = C.m_clusterArrayTableSize;
 174         shallowCopy(C);
 175 }
 176
 177
 178 ClusterGraph::ClusterGraph(
 179         const ClusterGraph &C,
 180         Graph &G,
 181         ClusterArray<cluster> &originalClusterTable,
 182         NodeArray<node> &originalNodeTable)
 183 :
 184         GraphObserver(&G),
 185         m_lcaSearch(0),
 186         m_vAncestor(0),
 187         m_wAncestor(0)
 188 {
 189         m_clusterIdCount = 0;
 190         m_postOrderStart = 0;
 191         m_rootCluster    = 0;
 192
 193         m_allowEmptyClusters = true;
 194         m_updateDepth   = false;
 195         m_depthUpToDate = false;
 196
 197         m_nClusters = 0;
 198         m_lcaNumber = 0;
 199
 200         m_clusterArrayTableSize = C.m_clusterArrayTableSize;
 201         deepCopy(C,G,originalClusterTable,originalNodeTable);
 202 }
 203
 204
 205 ClusterGraph::ClusterGraph(
 206         const ClusterGraph &C,
 207         Graph &G,
 208         ClusterArray<cluster> &originalClusterTable,
 209         NodeArray<node> &originalNodeTable,
 210         EdgeArray<edge> &edgeCopy)
 211 :
 212         GraphObserver(&G),
 213         m_lcaSearch(0),
 214         m_vAncestor(0),
 215         m_wAncestor(0)
 216 {
 217         m_clusterIdCount = 0;
 218         m_postOrderStart = 0;
 219         m_rootCluster    = 0;
 220
 221         m_allowEmptyClusters = true;
 222         m_updateDepth   = false;
 223         m_depthUpToDate = false;
 224
 225         m_nClusters = 0;
 226         m_lcaNumber = 0;
 227
 228         m_clusterArrayTableSize = C.m_clusterArrayTableSize;
 229         deepCopy(C, G, originalClusterTable, originalNodeTable, edgeCopy);
 230 }
 231
 232
 233 ClusterGraph::ClusterGraph(const ClusterGraph &C,Graph &G) :
 234         GraphObserver(&G),
 235         m_lcaSearch(0),
 236         m_vAncestor(0),
 237         m_wAncestor(0)
 238 {
 239         m_clusterIdCount = 0;
 240         m_postOrderStart = 0;
 241         m_rootCluster    = 0;
 242
 243         m_allowEmptyClusters = true;
 244         m_updateDepth   = false;
 245         m_depthUpToDate = false;
 246
 247         m_nClusters = 0;
 248         m_lcaNumber = 0;
 249
 250         m_clusterArrayTableSize = C.m_clusterArrayTableSize;
 251         deepCopy(C,G);
 252 }
 253
 254
 255 ClusterGraph::~ClusterGraph()
 256 {
 257         for(ListIterator<ClusterArrayBase*> it = m_regClusterArrays.begin();
 258                 it.valid(); ++it)
 259         {
 260                 (*it)->disconnect();
 261         }
 262
 263         clear();
 264 }
 265
 266
 267 // Construction of a new cluster graph. All nodes
 268 // are children of the root cluster
 269 void ClusterGraph::init(const Graph &G)
 270 {
 271         clear();
 272         m_clusterIdCount = 0;
 273         m_postOrderStart = 0;
 274         m_pGraph = &G;
 275
 276         m_nClusters = 0;
 277         m_lcaNumber = 0;
 278         m_clusterArrayTableSize = G.nextPower2(MIN_CLUSTER_TABLE_SIZE, G.nodeArrayTableSize());
 279         //m_clusterDepth.init(*this, 0);
 280         initGraph(G);
 281 }
 282
 283
 284
 285 //---------------------------------------------------------
 286 // =
 287 //---------------------------------------------------------
 288
 289 ClusterGraph &ClusterGraph::operator=(const ClusterGraph &C)
 290 {
 291         clear(); shallowCopy(C);
 292         m_clusterArrayTableSize = C.m_clusterArrayTableSize;
 293         reinitArrays();
 294
 295         OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
 296         return *this;
 297 }
 298
 299
 300 //---------------------------------------------------------
 301 // copy,initGraph
 302 //---------------------------------------------------------
 303
 304 // Copy Function
 305 void ClusterGraph::shallowCopy(const ClusterGraph &C)
 306 {
 307         const Graph &G = C;
 308         m_pGraph = &G;
 309
 310         m_nClusters = 0;
 311
 312         //m_clusterDepth.init(*this, 0);
 313
 314         initGraph(G);
 315
 316         m_updateDepth = C.m_updateDepth;
 317         m_depthUpToDate = C.m_depthUpToDate;
 318
 319         // Construct cluster tree
 320         ClusterArray<cluster> originalClusterTable(C);
 321         cluster c = 0;
 322         forall_clusters(c,C)
 323         {
 324                 if (c == C.m_rootCluster)
 325                 {
 326                         originalClusterTable[c] = m_rootCluster;
 327                         //does not really need to be assigned HERE in for
 328                         m_rootCluster->depth() = 1;
 329                         OGDF_ASSERT(C.rootCluster()->depth() == 1)
 330                         continue;
 331                 }
 332                 originalClusterTable[c] = newCluster();
 333                 originalClusterTable[c]->depth() = c->depth();
 334         }
 335         forall_clusters(c,C)
 336         {
 337
 338                 if (c == C.m_rootCluster)
 339                         continue;
 340                 originalClusterTable[c]->m_parent = originalClusterTable[c->m_parent];
 341                 originalClusterTable[c->m_parent]->m_children.pushBack(originalClusterTable[c]);
 342                 originalClusterTable[c]->m_it = originalClusterTable[c->m_parent]->m_children.rbegin();
 343         }
 344
 345         node v;
 346         forall_nodes(v,G)
 347                 reassignNode(v,originalClusterTable[C.clusterOf(v)]);
 348
 349         copyLCA(C);
 350 }
 351
 352
 353
 354 // Initialize the graph
 355 void ClusterGraph::initGraph(const Graph &G)
 356 {
 357
 358         reregister(&G); //will in some constructors cause double registration
 359
 360         m_lcaNumber = 0;
 361         m_lcaSearch = 0;
 362         m_vAncestor = 0;
 363         m_wAncestor = 0;
 364
 365         //if (G.empty())
 366         //      return;
 367
 368         m_adjAvailable = false;
 369
 370         //assign already existing nodes, new nodes are assigned
 371         //over nodeadded
 372         List<node> allNodes;
 373         G.allNodes(allNodes);
 374
 375         //clusterIdcount may be zero in case of constructor call,
 376         //but can be != zero if readgraphwin is used
 377         //root cluster should always get id 0
 378         #ifdef OGDF_DEBUG
 379         m_rootCluster = OGDF_NEW ClusterElement(this, 0);//m_clusterIdCount++);
 380         #else
 381         m_rootCluster = OGDF_NEW ClusterElement(0);//m_clusterIdCount++);
 382         #endif
 383
 384         OGDF_ASSERT(m_nClusters == 0)
 385
 386         m_clusterIdCount++;
 387         m_rootCluster->depth() = 1;
 388         m_rootCluster->init(allNodes);
 389         m_nodeMap.init(G,m_rootCluster);
 390         m_itMap.init(G,0);
 391         ListIterator<node> it;
 392         for (it = m_rootCluster->m_entries.begin(); it.valid(); it++)
 393                 m_itMap[*it] = it;
 394
 395         m_nClusters++;
 396         m_clusters.pushBack(m_rootCluster);
 397 }
 398
 399
 400 void ClusterGraph::reinitGraph(const Graph &G)
 401         {
 402                 m_pGraph = &G;
 403
 404                 OGDF_ASSERT_IF(dlConsistencyChecks, G.consistencyCheck());
 405
 406                 m_clusterArrayTableSize = G.nextPower2(MIN_CLUSTER_TABLE_SIZE, G.nodeArrayTableSize());
 407
 408                 if (numberOfClusters() != 0)
 409                 {
 410                         clear();
 411                 }//if
 412                 initGraph(G); //already constructs root cluster, reassign
 413         }
 414
 415
 416 void ClusterGraph::reinitArrays()
 417 {
 418         ListIterator<ClusterArrayBase*> itCluster = m_regClusterArrays.begin();
 419         for(; itCluster.valid(); ++itCluster)
 420                 (*itCluster)->reinit(m_clusterArrayTableSize);
 421 }
 422
 423
 424
 425 // Copy Function
 426 void ClusterGraph::deepCopy(const ClusterGraph &C,Graph &G)
 427 {
 428
 429         const Graph &cG = C;    // original graph
 430
 431         ClusterArray<cluster> originalClusterTable(C);
 432         NodeArray<node> originalNodeTable(cG);
 433         EdgeArray<edge> edgeCopy(cG);
 434
 435         deepCopy(C,G,originalClusterTable, originalNodeTable, edgeCopy);
 436 }
 437
 438 void ClusterGraph::deepCopy(const ClusterGraph &C,Graph &G,
 439                                                         ClusterArray<cluster> &originalClusterTable,
 440                                                         NodeArray<node> &originalNodeTable)
 441 {
 442
 443         const Graph &cG = C;    // original graph
 444
 445         EdgeArray<edge> edgeCopy(cG);
 446
 447         deepCopy(C,G,originalClusterTable, originalNodeTable, edgeCopy);
 448 }
 449
 450 void ClusterGraph::deepCopy(const ClusterGraph &C,Graph &G,
 451                                                         ClusterArray<cluster> &originalClusterTable,
 452                                                         NodeArray<node> &originalNodeTable,
 453                                                         EdgeArray<edge> &edgeCopy)
 454 {
 455         G.clear();
 456
 457         const Graph &cG = C;    // original graph
 458
 459         m_pGraph = &G;
 460
 461         m_nClusters = 0;
 462
 463         initGraph(G); //arrays have already to be initialized for newnode
 464
 465         m_updateDepth = C.m_updateDepth;
 466         m_depthUpToDate = C.m_depthUpToDate;
 467
 468         NodeArray<node> orig(G);
 469         node v;
 470         edge e;
 471
 472         forall_nodes(v,cG)
 473         {
 474                 node w = G.newNode();
 475                 orig[w] = v;
 476                 originalNodeTable[v] = w;
 477         }
 478         forall_edges(e,cG)
 479         {
 480                 edge eNew = G.newEdge(originalNodeTable[e->adjSource()->theNode()],
 481                                         originalNodeTable[e->adjTarget()->theNode()]);
 482                 edgeCopy[e] = eNew;
 483         }//foralledges
 484
 485         //m_clusterDepth.init(*this, 0);
 486
 487
 488         // Construct cluster tree
 489         cluster c = 0;
 490         forall_clusters(c,C)
 491         {
 492                 if (c == C.m_rootCluster)
 493                 {
 494                         originalClusterTable[c] = m_rootCluster;
 495                         //does not really need to be assigned HERE in for
 496                         m_rootCluster->depth() = 1;
 497                         OGDF_ASSERT(c->depth() == 1)
 498                         continue;
 499                 }
 500                 originalClusterTable[c] = newCluster();
 501                 originalClusterTable[c]->depth() = c->depth();
 502         }
 503         forall_clusters(c,C)
 504         {
 505
 506                 if (c == C.m_rootCluster)
 507                         continue;
 508                 originalClusterTable[c]->m_parent = originalClusterTable[c->m_parent];
 509                 originalClusterTable[c->m_parent]->m_children.pushBack(originalClusterTable[c]);
 510                 originalClusterTable[c]->m_it = originalClusterTable[c->m_parent]->m_children.rbegin();
 511         }
 512
 513         forall_nodes(v,G)
 514                 reassignNode(v,originalClusterTable[C.clusterOf(orig[v])]);
 515
 516         //ClusterArray<cluster>* ca = ;
 517         copyLCA(C, &originalClusterTable);
 518 }
 519
 520 //*********************************************************
 521 //cluster search
 522
 523 //We search for the lowest common cluster of a set of nodes.
 524 //We first compute the common path of two nodes, then update path if root
 525 //path from other nodes hits it .
 526 //We always stop if we encounter root cluster.
 527 cluster ClusterGraph::commonCluster(SList<node>& nodes)
 528 {
 529         //worst case running time #nodes x clustertreeheight-1
 530         //always <= complete tree run
 531         //we could even use pathcompression...
 532         //at any time, we stop if root is encountered as lowest
 533         //common cluster of a node subset
 534
 535
 536         if (nodes.empty()) return 0;
 537
 538         //For simplicity, we use cluster arrays
 539         ClusterArray<int> commonPathHit(*this, 0); //count for clusters path hits
 540         int runs = 0; //number of nodes already considered
 541         cluster pathCluster;
 542         SListIterator<node> sIt = nodes.begin();
 543         node v1 = (*sIt);
 544         if (nodes.size() == 1) return clusterOf(v1);
 545         sIt++;
 546         node v2 = (*sIt);
 547
 548         cluster lowestCommon = commonCluster(v1, v2);
 549         commonPathHit[lowestCommon] = 2;
 550         pathCluster = lowestCommon;
 551         while (pathCluster->parent())
 552         {
 553                 pathCluster = pathCluster->parent();
 554                 commonPathHit[pathCluster] = 2;
 555         }
 556         runs = 2;
 557         //we save direct lca access, it also lies on a runs hit path from root
 558         while ((runs < nodes.size()) && (lowestCommon != m_rootCluster))
 559         {
 560                 sIt++;
 561                 node v = (*sIt);
 562                 pathCluster = clusterOf(v);
 563                 while (commonPathHit[pathCluster] == 0)
 564                 {
 565                         if (pathCluster->parent()) pathCluster = pathCluster->parent();
 566                         else return m_rootCluster; //can never happen
 567                 }//while
 568                 //assign new (maybe same) lowest common
 569                 if (commonPathHit[pathCluster] == runs) lowestCommon = pathCluster;
 570                 commonPathHit[pathCluster] = commonPathHit[pathCluster]+1;
 571                 if (pathCluster == m_rootCluster) return m_rootCluster;
 572                 //update hits in path to root
 573                 while (pathCluster->parent())
 574                 {
 575                         pathCluster = pathCluster->parent();
 576                         commonPathHit[pathCluster] = commonPathHit[pathCluster]+1;
 577                 }
 578
 579                 runs++;
 580         }
 581         return lowestCommon;
 582
 583
 584 }//commoncluster
 585
 586 //lowest common cluster of v,w
 587 cluster ClusterGraph::commonCluster(node v, node w) const
 588 {
 589         cluster c1, c2;
 590         return commonClusterLastAncestors(v, w, c1, c2);
 591 }//commonCluster
 592
 593 //lowest common cluster of v,w and its ancestors
 594 cluster ClusterGraph::commonClusterLastAncestors(node v,
 595                                                                                                  node w,
 596                                                                                                  cluster& c1,
 597                                                                                                  cluster& c2) const
 598 {
 599         List<cluster> e;
 600         return commonClusterAncestorsPath(v, w, c1, c2, e);
 601 }//commonClusterLastAncestors
 602 //lowest common cluster and path between v and w containing it
 603 //note that eL is directed from v to w
 604 cluster ClusterGraph::commonClusterPath(node v,
 605                                                                                 node w,
 606                                                                                 List<cluster>& eL) const
 607 {
 608         cluster c1, c2;
 609         return commonClusterAncestorsPath(v, w, c1, c2, eL);
 610 }//commonClusterLastAncestors
 611
 612 //note that eL is directed from v to w
 613 cluster ClusterGraph::commonClusterAncestorsPath(node v,
 614                                                                                                  node w,
 615                                                                                                  cluster& c1,
 616                                                                                                  cluster& c2,
 617                                                                                                  List<cluster>& eL) const
 618 {
 619         OGDF_ASSERT(v->graphOf() == m_pGraph)
 620         OGDF_ASSERT(w->graphOf() == m_pGraph)
 621
 622         cluster cv = clusterOf(v);
 623         cluster cw = clusterOf(w);
 624
 625
 626         //clusters from v and w to common
 627         List<cluster> vList;
 628         List<cluster> wList;
 629
 630         //CASE1 no search necessary
 631         //if both nodes are in the same cluster, we return this cluster
 632         //and have to check if c1 == c2 to have a (v,w) representation edge
 633         if (cv == cw)
 634         {
 635                 c1 = c2 = cv;
 636                 eL.pushBack(c1);
 637                 return cv;
 638         }
 639
 640         if (m_lcaNumber == INT_MAX - 1) m_lcaNumber = 0;
 641         else m_lcaNumber++;
 642         if (!m_lcaSearch)
 643         {
 644                 m_lcaSearch = OGDF_NEW ClusterArray<int>(*this, -1);
 645                 m_vAncestor = OGDF_NEW ClusterArray<cluster>(*this, 0);
 646                 m_wAncestor = OGDF_NEW ClusterArray<cluster>(*this, 0);
 647         }
 648
 649         //CASE2: one of the nodes hangs at root: save root as ancestor
 650         //any other case: save cluster of node as ancestor, too, to check this
 651         //case:: common = xCluster != yCluster
 652         //(*m_vAncestor)[rootCluster()] = rootCluster();
 653         //(*m_wAncestor)[rootCluster()] = rootCluster();
 654         (*m_vAncestor)[cv] = 0;
 655         (*m_wAncestor)[cw] = 0;
 656
 657         //we rely on the fact all nodes are in the rootcluster or
 658         //that parent is initialized to zero to terminate
 659
 660         //we start with different clusters due to CASE1
 661         //save the ancestor information
 662         (*m_lcaSearch)[cw] = m_lcaNumber; //not really necessary, we won't return
 663         (*m_lcaSearch)[cv] = m_lcaNumber;
 664         vList.pushBack(cv);
 665         wList.pushBack(cw);
 666
 667         //we break and return if we find a common node
 668         //before we reach the rootcluster
 669         do
 670         {
 671                 if (cv->parent()) //root reached?
 672                 {
 673                         (*m_vAncestor)[cv->parent()] = cv;
 674                         cv = cv->parent();
 675                         //was cv visited on path from w
 676                         if ((*m_lcaSearch)[cv] == m_lcaNumber)
 677                         {
 678                                 c1 = (*m_vAncestor)[cv];
 679                                 c2 = (*m_wAncestor)[cv];
 680                                 //setup list
 681                                 ListIterator<cluster> itC = vList.begin();
 682
 683                                 while (itC.valid())
 684                                 {
 685                                         eL.pushBack(*itC);
 686                                         itC++;
 687                                 }
 688                                 itC = wList.rbegin();
 689                                 while (itC.valid() && ((*itC) != cv))
 690                                         itC--;
 691                                 while (itC.valid())
 692                                 {
 693                                         eL.pushBack(*itC);
 694                                         itC--;
 695                                 }
 696
 697                                 return cv;
 698                         }
 699                         vList.pushBack(cv);
 700                         (*m_lcaSearch)[cv] = m_lcaNumber;
 701                 }//if not root reached on cvpath
 702
 703                 if (cw->parent())
 704                 {
 705                         (*m_wAncestor)[cw->parent()] = cw;
 706                         cw = cw->parent();
 707                         //was cw visited on path from v
 708                         if ((*m_lcaSearch)[cw] == m_lcaNumber)
 709                         {
 710                                 c1 = (*m_vAncestor)[cw];
 711                                 c2 = (*m_wAncestor)[cw];
 712                                 //setup list
 713                                 ListIterator<cluster> itC = vList.begin();
 714                                 while (itC.valid() && ((*itC) != cw))
 715                                 {
 716                                         eL.pushBack(*itC);
 717                                         itC++;
 718                                 }
 719
 720                                 eL.pushBack(cw);
 721
 722                                 itC = wList.rbegin();
 723                                 while (itC.valid())
 724                                 {
 725                                         eL.pushBack(*itC);
 726                                         itC--;
 727                                 }
 728
 729                                 return cw;
 730                         }
 731                         wList.pushBack(cw);
 732                         (*m_lcaSearch)[cw] = m_lcaNumber;
 733
 734                 }//if not root reached on cwpath
 735         }       while ( cv->parent() || cw->parent() );
 736
 737         //v,w should be at least together in the rootcluster
 738         c1 = (*m_vAncestor)[rootCluster()];
 739         c2 = (*m_wAncestor)[rootCluster()];
 740         return rootCluster();
 741
 742 }//commonclusterlastAncestors
 743
 744 void ClusterGraph::copyLCA(
 745         const ClusterGraph &C,
 746         ClusterArray<cluster>* clusterCopy)
 747 {
 748         if (m_lcaSearch)
 749         {
 750                 delete m_lcaSearch;
 751                 delete m_vAncestor;
 752                 delete m_wAncestor;
 753         }//if
 754         if (C.m_lcaSearch)
 755         {
 756                 //otherwise, initialization won't work
 757                 m_clusterArrayTableSize = C.m_clusterArrayTableSize;
 758
 759                 m_lcaSearch = OGDF_NEW ClusterArray<int>(*this, -1);//(*C.m_lcaSearch);
 760
 761                 m_vAncestor = OGDF_NEW ClusterArray<cluster>(*this, 0); //*C.m_vAncestor);
 762                 //m_vAncestor->init(*this, 0),
 763                 m_wAncestor = OGDF_NEW ClusterArray<cluster>(*this, 0);//*C.m_wAncestor);
 764                 //setting of clusters is not necessary!
 765                 //(*m_v/wAncestor)[(*clusterCopy)[c]]= (*(C.m_v/wAncestor))[c];
 766         }//if
 767 }//copylca
 768
 769 //---------------------------------------------------------
 770 // check the graph for empty clusters
 771 //---------------------------------------------------------
 772 //we never set rootcluster to be one of the empty clusters!!
 773 void ClusterGraph::emptyClusters(SList<cluster>& emptyCluster,
 774                                                                  SList<cluster>* checkCluster)
 775 {
 776         emptyCluster.clear();
 777         cluster cc;
 778         //for all nodes = #nodes
 779         if (checkCluster)
 780         {
 781                 SListIterator<cluster> it = checkCluster->begin();
 782
 783                 while (it.valid())
 784                 {
 785                         if ((*it)->cCount() + (*it)->nCount() == 0)
 786                                 if ((*it) != rootCluster()) //we dont add rootcluster
 787                                         emptyCluster.pushBack((*it));
 788                         it++;
 789                 }//while
 790         }//if checkcluster given
 791         else
 792         {
 793                 forall_clusters(cc, *this)
 794                 {
 795                         if (cc->cCount() + cc->nCount() == 0)
 796                                 if (cc != rootCluster()) //we dont add rootcluster
 797                                         emptyCluster.pushBack(cc);
 798                 }//forallclusters
 799         }//else checkcluster
 800         //other clusters can get empty, too, if we delete these
 801         ClusterArray<int> delCount(*this, 0);
 802         SList<cluster> emptyParent;
 803         SListIterator<cluster> itC = emptyCluster.begin();
 804         while (itC.valid())
 805         {
 806                 //count deleted children
 807                 cluster runc = (*itC)->parent();
 808                 if (runc)  //is always the case as long as root was not inserted to list
 809                 {
 810                         delCount[runc]++;
 811                         while ((runc->nCount() == 0) && (runc->cCount() == delCount[runc]))
 812                         {
 813                                 if (runc == rootCluster()) break;
 814                                 emptyParent.pushBack(runc);
 815                                 runc = runc->parent();
 816                                 delCount[runc]++;
 817                         }//while parent emptied
 818                 }//if not runc = root->parent
 819
 820                 itC++;
 821         }//while empty leaves
 822
 823         emptyCluster.conc(emptyParent);
 824         //for reinsertion, start at emptycluster's back
 825
 826 }//emptyClusters
 827
 828 //---------------------------------------------------------
 829 // newCluster, delCluster, createCluster
 830 //---------------------------------------------------------
 831
 832 // Inserts a new cluster prescribing its parent
 833 cluster ClusterGraph::newCluster(cluster parent, int id)
 834 {
 835         OGDF_ASSERT(parent);
 836         cluster c;
 837         if (id > 0)
 838                 c = newCluster(id);
 839         else
 840                 c = newCluster();
 841         parent->m_children.pushBack(c);
 842         c->m_it = parent->m_children.rbegin();
 843         c->m_parent = parent;
 844         c->depth() = parent->depth() + 1;
 845
 846         return c;
 847 }
 848
 849 //Insert a new cluster with given ID, precondition: id not used
 850 //has to be updated in the same way as newcluster()
 851 cluster ClusterGraph::newCluster(int id)
 852 {
 853         m_nClusters++;
 854         m_adjAvailable = false;
 855         m_postOrderStart = 0;
 856         if (id >= m_clusterIdCount) m_clusterIdCount = id+1;
 857         if (m_clusterIdCount >= m_clusterArrayTableSize)
 858         {
 859                 m_clusterArrayTableSize =
 860                         m_pGraph->nextPower2(m_clusterArrayTableSize, id);
 861                 for(ListIterator<ClusterArrayBase*> it = m_regClusterArrays.begin();
 862                         it.valid(); ++it)
 863                 {
 864                         (*it)->enlargeTable(m_clusterArrayTableSize);
 865                 }
 866         }
 867         #ifdef OGDF_DEBUG
 868         cluster c = OGDF_NEW ClusterElement(this,id);
 869         #else
 870         cluster c = OGDF_NEW ClusterElement(id);
 871         #endif
 872         m_clusters.pushBack(c);
 873         // notify observers
 874         for(ListIterator<ClusterGraphObserver*> it = m_regObservers.begin();
 875                         it.valid(); ++it) (*it)->clusterAdded(c);
 876         return c;
 877 }
 878
 879 // Inserts a new cluster
 880 //has to be updated in the same way as newcluster(id)
 881 cluster ClusterGraph::newCluster()
 882 {
 883         m_nClusters++;
 884         m_adjAvailable = false;
 885         m_postOrderStart = 0;
 886         if (m_clusterIdCount == m_clusterArrayTableSize)
 887         {
 888                 m_clusterArrayTableSize <<= 1;
 889                 for(ListIterator<ClusterArrayBase*> it = m_regClusterArrays.begin();
 890                         it.valid(); ++it)
 891                 {
 892                         (*it)->enlargeTable(m_clusterArrayTableSize);
 893                 }
 894         }
 895         #ifdef OGDF_DEBUG
 896         cluster c = OGDF_NEW ClusterElement(this,m_clusterIdCount++);
 897         #else
 898         cluster c = OGDF_NEW ClusterElement(m_clusterIdCount++);
 899         #endif
 900         m_clusters.pushBack(c);
 901         // notify observers
 902         for(ListIterator<ClusterGraphObserver*> it = m_regObservers.begin();
 903                         it.valid(); ++it) (*it)->clusterAdded(c);
 904         return c;
 905 }
 906
 907 cluster ClusterGraph::createEmptyCluster(const cluster parent, int clusterId)
 908 {
 909         //if no id given, use next free id
 910         if (clusterId < 0) clusterId = m_clusterIdCount;
 911         //create the new cluster
 912         cluster cnew;
 913         if (parent)
 914                 cnew = newCluster(parent, clusterId);
 915         else
 916                 cnew = newCluster(m_rootCluster, clusterId);
 917         return cnew;
 918 }//createemptycluster
 919
 920 cluster ClusterGraph::createCluster(SList<node>& nodes, const cluster parent)
 921 {
 922         cluster c;
 923         if (m_allowEmptyClusters)
 924         {
 925                 c = doCreateCluster(nodes, parent);
 926                 return c;
 927         }
 928         else
 929         {
 930                 SList<cluster> emptyCluster;
 931
 932                 c = doCreateCluster(nodes, emptyCluster, parent);
 933
 934                 SListIterator<cluster> sIt = emptyCluster.begin();
 935                 while (sIt.valid())
 936                 {
 937                         delCluster((*sIt));
 938
 939                         //root cluster can never be empty, as we deleted a node
 940                         sIt++;
 941                 }//While
 942         }
 943         return c;
 944 }
 945
 946 cluster ClusterGraph::doCreateCluster(SList<node>& nodes,
 947                 const cluster parent,
 948                 int clusterId)
 949 {
 950
 951         if (nodes.empty()) return 0;
 952
 953         //if no id given, use next free id
 954         if (clusterId < 0) clusterId = m_clusterIdCount;
 955         //create the new cluster
 956         cluster cnew;
 957         if (parent)
 958                 cnew = newCluster(parent, clusterId);
 959         else
 960                 cnew = newCluster(m_rootCluster, clusterId);
 961
 962         //insert nodes in new cluster
 963         SListIterator<node> it = nodes.begin();
 964         while (it.valid())
 965         {
 966                 reassignNode((*it), cnew);
 967                 it++;
 968         }//while
 969
 970         return cnew;
 971 }//createcluster
 972
 973 cluster ClusterGraph::doCreateCluster(SList<node>& nodes,
 974                 SList<cluster>& emptyCluster,
 975                 const cluster parent,
 976                 int clusterId)
 977 {
 978         // Even if m_allowEmptyClusters is set we check if a cluster
 979         // looses all of its nodes and has
 980         // no more entries and childs. This can be used for special cluster
 981         // object handling or for deletion if m_allowEmptyClusters is not set
 982         // if it is not the new parent, it can be deleted
 983         // running time max(#cluster, length(nodelist))
 984         // TODO: Parameter, der dies auslaesst, da hohe Laufzeit
 985         // hier macht das nur Sinn, wenn es schneller ist als forallclusters,
 986         // sonst koennte man es ja auch aussen testen, aber bisher ist es nicht
 987         // schneller implementiert
 988         // Vorgehen: hash auf cluster index, falls nicht gesetzt, in liste einfuegen
 989         // und als checkcluster an emptycluster uebergeben
 990
 991         if (nodes.empty()) return 0;
 992
 993         //if no id given, use next free id
 994         if (clusterId < 0) clusterId = m_clusterIdCount;
 995         //create the new cluster
 996         cluster cnew;
 997         if (parent)
 998                 cnew = newCluster(parent, clusterId);
 999         else
1000                 cnew = newCluster(m_rootCluster, clusterId);
1001
1002         //insert nodes in new cluster
1003         SListIterator<node> it = nodes.begin();
1004         while (it.valid())
1005         {
1006                 reassignNode((*it), cnew);
1007                 it++;
1008         }//while
1009
1010         //should be: only for changed clusters (see comment above)
1011         //it is important to save the cluster in an order
1012         //that allows deletion as well as reinsertion
1013         emptyClusters(emptyCluster);
1014         //for reinsertion, start at emptycluster's back
1015
1016         return cnew;
1017 }//createcluster
1018
1019 // Deletes cluster c
1020 // All subclusters become children of parent cluster
1021 // Precondition: c is not the root cluster
1022 // updating of cluster depth information pumps running time
1023 // up to worst case O(#C)
1024 void ClusterGraph::delCluster(cluster c)
1025 {
1026         OGDF_ASSERT(c != 0 && c->graphOf() == this && c != m_rootCluster)
1027
1028         // notify observers
1029         for(ListIterator<ClusterGraphObserver*> it = m_regObservers.begin();
1030                         it.valid(); ++it) (*it)->clusterDeleted(c);
1031
1032         --m_nClusters;
1033         m_adjAvailable = false;
1034
1035         c->m_parent->m_children.del(c->m_it);
1036         c->m_it = 0;
1037
1038         while (!c->m_children.empty())
1039         {
1040                 cluster trace = c->m_children.popFrontRet();
1041                 trace->m_parent =  c->m_parent;
1042                 trace->m_parent->m_children.pushBack(trace);
1043                 trace->m_it = trace->m_parent->m_children.rbegin();
1044
1045                 //only recompute depth if option set and it makes sense
1046                 if (m_updateDepth && m_depthUpToDate)
1047                 {
1048                         //update depth for all children in subtree
1049                         OGDF_ASSERT(trace->depth() == trace->parent()->depth()+2)
1050                         pullUpSubTree(trace);
1051                         //could just set depth-1 here
1052                         //trace->depth() = trace->parent()->depth()+1;
1053
1054                 }///if depth update
1055                 else m_depthUpToDate = false;
1056         }
1057         while (!c->m_entries.empty())
1058         {
1059                 node v = c->m_entries.popFrontRet();
1060                 m_nodeMap[v] = 0;
1061                 reassignNode(v,c->m_parent);
1062         }
1063
1064         m_clusters.del(c);
1065 }
1066
1067 //pulls up depth of subtree located at c by one
1068 //precondition: depth is consistent
1069 //we dont ask for depthuptodate since the caller needs
1070 //to know for himself if he wants the tree to be pulled
1071 //for any special purpose
1072 void ClusterGraph::pullUpSubTree(cluster c)
1073 {
1074         c->depth() = c->depth() - 1;
1075         ListConstIterator<cluster> it = c->getChildren().begin();
1076         while (it.valid())
1077         {
1078                 pullUpSubTree(*it);
1079                 it++;
1080         }
1081
1082 }
1083
1084 //---------------------------------------------------------
1085 // clear, clearClusterTree
1086 //---------------------------------------------------------
1087
1088 void ClusterGraph::clear()
1089 {
1090         //split condition
1091         if (m_lcaSearch)
1092         {
1093                 delete m_lcaSearch;
1094                 delete m_vAncestor;
1095                 delete m_wAncestor;
1096         }
1097         if (m_nClusters != 0)
1098         {
1099                 clearClusterTree(m_rootCluster);
1100                 m_clusters.del(m_rootCluster);
1101         }
1102         //no clusters, so we can restart at 0
1103         m_clusterIdCount = 0;
1104         m_nClusters = 0;
1105 }
1106
1107
1108 // Removes the Clustering of a Tree and frees the allocated memory
1109 void ClusterGraph::clearClusterTree(cluster c)
1110 {
1111         cluster trace = 0;
1112         cluster parent = c->parent();
1113         m_postOrderStart = 0;
1114         m_adjAvailable = false;
1115
1116         List<cluster>  children = c->getChildren();
1117         List<node>     attached;
1118
1119         while (!children.empty())
1120         {
1121                 trace = children.popFrontRet();
1122                 clearClusterTree(trace,attached);
1123         }
1124
1125         if (parent != 0)
1126         {
1127                 ListIterator<node> it;
1128                 for (it = attached.begin();it.valid();it++)
1129                 {
1130                         m_nodeMap[(*it)] = parent;
1131                         parent->m_entries.pushBack((*it));
1132                         m_itMap[(*it)] = parent->m_entries.rbegin();
1133                 }
1134                 m_clusters.del(c);
1135         }
1136         else if (c == m_rootCluster)
1137         {
1138                 ListIterator<node> it;
1139                 for (it = attached.begin();it.valid();it++)
1140                 {
1141                         m_nodeMap[(*it)] = m_rootCluster;
1142                         m_rootCluster->m_entries.pushBack((*it));
1143                         m_itMap[(*it)] = m_rootCluster->m_entries.rbegin();
1144                 }
1145                 m_rootCluster->m_children.clear();
1146         }
1147 }
1148
1149 void ClusterGraph::clearClusterTree(cluster c,List<node> &attached)
1150 {
1151         cluster trace;
1152         List<cluster>  children = c->getChildren();
1153         attached.conc(c->m_entries);
1154         m_adjAvailable = false;
1155
1156         while (!children.empty())
1157         {
1158                 trace = children.popFrontRet();
1159                 clearClusterTree(trace,attached);
1160         }
1161         m_clusters.del(c);
1162 }
1163
1164 //don't delete root cluster
1165 void ClusterGraph::semiClear()
1166 {
1167         //split condition
1168         if (m_lcaSearch)
1169         {
1170                 delete m_lcaSearch;
1171                 delete m_vAncestor;
1172                 delete m_wAncestor;
1173         }
1174         if (m_nClusters != 0)
1175         {
1176                 //clear the cluster structure under root cluster
1177                 clearClusterTree(m_rootCluster);
1178                 //now delete all rootcluster entries
1179                 while (!m_rootCluster->m_entries.empty())
1180                 {
1181                         node v = m_rootCluster->m_entries.popFrontRet();
1182                         m_nodeMap[v] = 0;
1183                 }
1184         }
1185         //no child clusters, so we can restart at 1
1186         m_clusterIdCount = 1;
1187         m_nClusters = 1;
1188 }
1189
1190 //reassign cluster depth for clusters in subtree rooted at c
1191 void ClusterGraph::computeSubTreeDepth(cluster c) const
1192 {
1193         if (c == rootCluster()) m_depthUpToDate = true;
1194         if (!(c->parent())) c->depth() = 1;
1195         else c->depth() = c->parent()->depth() + 1;
1196         ListConstIterator<cluster> it = c->getChildren().begin();
1197         while (it.valid())
1198         {
1199                 computeSubTreeDepth(*it);
1200                 it++;
1201         }
1202
1203 }
1204
1205 //move cluster from old parent to an other
1206 void ClusterGraph::moveCluster(cluster c, cluster newParent)
1207 {
1208         if (c == rootCluster()) return;
1209         if ((c == 0) || (newParent == 0)) return; //no cheap tricks
1210         if (c->parent() == newParent) return;     //no work to do
1211
1212         cluster oldParent = c->parent();
1213         //we dont move root
1214         OGDF_ASSERT(oldParent)
1215
1216         //check if we move to a descendant
1217         cluster crun = newParent->parent();
1218         bool descendant = false;
1219         while (crun)
1220         {
1221                 if (crun == c)
1222                 {
1223                         descendant = true;
1224                         break;
1225                 }
1226                 crun = crun->parent();
1227         }//while running upwards
1228
1229         //do not allow to move empty clusters to descendants
1230         if (descendant && (c->nCount() == 0))
1231                 return;
1232
1233         // save postorder for old parent
1234         bool newOrder = false;
1235         if (!m_postOrderStart)
1236         {
1237                 newOrder = true;
1238         }
1239
1240         //temporarily only recompute postorder for all clusters
1241
1242         oldParent->m_children.del(c->m_it);
1243         newParent->m_children.pushBack(c);
1244         c->m_it = newParent->m_children.rbegin();
1245         c->m_parent = newParent;
1246
1247         //update the cluster depth information in the subtree
1248         //If moved to descendant, recompute
1249         //depth for parent (including all brother trees)
1250         if (descendant)
1251         {
1252                 //how do we move:
1253                 //only entries with c? => may be empty
1254                 //we currently dont allow this, because it makes
1255                 //no sense, you could just delete the cluster or move
1256                 //the children
1257                 //move all children to oldparent
1258
1259                 while (!c->m_children.empty())
1260                 {
1261                         cluster child = c->m_children.popFrontRet();
1262                         child->m_parent =  oldParent;
1263                         child->m_parent->m_children.pushBack(child);
1264                         child->m_it = child->m_parent->m_children.rbegin();
1265                         //child++;
1266                 }
1267
1268                 //recompute depth only if option set AND it makes sense at that point
1269                 if (m_updateDepth && m_depthUpToDate)
1270                         computeSubTreeDepth(oldParent);
1271                 else m_depthUpToDate = false;
1272         }//moved to descendant
1273         else
1274         {
1275                 if (m_updateDepth && m_depthUpToDate)
1276                         computeSubTreeDepth(c);
1277                 else m_depthUpToDate = false;
1278         }
1279
1280         // update postorder for new parent
1281         // we only recompute postorder for all clusters
1282         // because of special cases like move to descendant...
1283         if (newOrder) postOrder();
1284         else postOrder();
1285
1286         m_adjAvailable = false;
1287
1288         //checkPostOrder();
1289 }//move cluster
1290
1291
1292 //*****************
1293 //postorder updates
1294
1295 //leftmostcluster in subtree rooted at c, has postorderpred for subtree
1296 cluster ClusterGraph::leftMostCluster(cluster c) const
1297 {
1298         cluster result = c;
1299         if (!c) return 0;
1300         while (!result->m_children.empty())
1301         {
1302                 result = result->m_children.front();
1303         }
1304         return result;
1305 }//leftMostCluster
1306
1307 //searches for predecessor of SUBTREE at c
1308 cluster ClusterGraph::postOrderPredecessor(cluster c) const
1309 {
1310         //all clusters on a path from root to leftmost cluster in tree
1311         //have no predecessor for their subtree
1312         cluster run = c;
1313         ListConstIterator<cluster> it;
1314         do
1315         {
1316                 //predecessor of clustertree is 0
1317                 if (run == m_rootCluster) return 0;
1318                 it = run->m_it;
1319                 //a child to the left is the immediate predecessor,
1320                 //otherwise we go one level up
1321                 if (it == (run->m_parent)->m_children.begin())
1322                         run = run->parent();
1323                 else return (*(it.pred()));
1324
1325         } while (run);
1326
1327         return 0;
1328 }//postorderpredecessor
1329
1330 //***************
1331 //node assignment
1332 //Assigns a node to a new cluster
1333 void ClusterGraph::assignNode(node v, cluster c)
1334 {
1335         m_adjAvailable = false;
1336         m_postOrderStart = 0;
1337         m_nodeMap[v] = c;
1338         c->m_entries.pushBack(v);
1339         m_itMap[v] = c->m_entries.rbegin();
1340 }
1341
1342
1343 //Reassigns a node to a new cluster
1344 void ClusterGraph::reassignNode(node v, cluster c)
1345 {
1346         OGDF_ASSERT(v->graphOf() == m_pGraph);
1347         OGDF_ASSERT(c->graphOf() == this);
1348
1349         unassignNode(v);
1350         m_nodeMap[v] = c;
1351         c->m_entries.pushBack(v);
1352         m_itMap[v] = c->m_entries.rbegin();
1353 }
1354
1355
1356 //Unassigns a node of cluster
1357 //Note: Nodes can already be unassigned by the nodeDeleted function.
1358 void ClusterGraph::unassignNode(node v)
1359 {
1360         m_adjAvailable = false;
1361         m_postOrderStart = 0;
1362
1363         removeNodeAssignment(v);
1364 }
1365
1366
1367 //---------------------------------------------------------
1368 // Sort clusters in post order
1369 //---------------------------------------------------------
1370
1371 // Start function for post order
1372 void ClusterGraph::postOrder() const
1373 {
1374         SListPure<cluster> L;
1375         postOrder(m_rootCluster,L);
1376         cluster c = 0;
1377         cluster prev = L.popFrontRet();
1378         prev->m_pPrev = 0;
1379         m_postOrderStart = prev;
1380         while (!L.empty())
1381         {
1382                 c = L.popFrontRet();
1383                 prev->m_pNext = c;
1384                 c->m_pPrev = prev;
1385                 prev = c;
1386         }
1387         if (c != 0)
1388                 c->m_pNext = 0;
1389         else
1390                 m_postOrderStart->m_pNext = 0;
1391 #ifdef OGDF_DEBUG
1392         forall_clusters(c, *this)
1393         {
1394                 cluster cp = leftMostCluster(c);
1395                 OGDF_ASSERT(cp->pPred() == postOrderPredecessor(c))
1396         }
1397 #endif
1398 }
1399
1400 void ClusterGraph::checkPostOrder() const
1401 {
1402         SListPure<cluster> L;
1403         postOrder(m_rootCluster,L);
1404         cluster c = 0;
1405         cluster prev = L.popFrontRet();
1406         OGDF_ASSERT(prev->m_pPrev == 0);
1407
1408         while (!L.empty())
1409         {
1410                 c = L.popFrontRet();
1411                 OGDF_ASSERT(prev->m_pNext == c)
1412                 OGDF_ASSERT(c->m_pPrev == prev)
1413                 prev = c;
1414         }
1415         if (c != 0)
1416         {
1417                 OGDF_ASSERT(c->m_pNext == 0)
1418         }
1419         else
1420         {
1421                 OGDF_ASSERT(m_postOrderStart->m_pNext == 0);
1422         }
1423 }
1424 // Recursive function for post order
1425 void ClusterGraph::postOrder(cluster c,SListPure<cluster> &L) const
1426 {
1427         ListIterator<cluster> it;
1428         for (it = c->m_children.begin(); it.valid(); it++)
1429                 postOrder((*it),L);
1430         L.pushBack(c);
1431 }
1432
1433
1434
1435
1436 //---------------------------------------------------------
1437 // Methods for debugging
1438 //---------------------------------------------------------
1439
1440
1441 // checks the consistency of the data structure
1442 // (for debugging only)
1443 bool ClusterGraph::consistencyCheck()
1444 {
1445
1446         ClusterArray<bool> visitedClusters((*this),false);
1447         NodeArray<bool> visitedNodes((*m_pGraph),false);
1448
1449
1450         cluster c = 0;
1451         forall_postOrderClusters(c,(*this))
1452         {
1453                 visitedClusters[c] = true;
1454                 ListIterator<node> itn;
1455                 for (itn = c->m_entries.begin(); itn.valid(); itn++)
1456                 {
1457                         node v = *itn;
1458                         if (m_nodeMap[v] != c)
1459                                 return false;
1460                         visitedNodes[v] = true;
1461                 }
1462         }
1463         forall_clusters(c,(*this))
1464                 if (!visitedClusters[c])
1465                         return false;
1466         node v;
1467         forall_nodes(v,(*m_pGraph))
1468                 if (!visitedNodes[v])
1469                         return false;
1470         return true;
1471 }
1472
1473
1474
1475 bool ClusterGraph::representsCombEmbedding()
1476 {
1477
1478         if (!m_adjAvailable)
1479                 return false;
1480
1481         if (!consistencyCheck())
1482                 return false;
1483
1484
1485         cluster c = 0;
1486         forall_postOrderClusters(c,(*this))
1487         {
1488
1489                 #ifdef OGDF_DEBUG
1490                 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
1491                         cout << "__________________________________________________________________"
1492                                  << endl << endl
1493                                  << "Testing cluster " << c << endl
1494                                  << "Check on AdjList of c" << endl;
1495                         adjEntry adjDD;
1496                         forall_cluster_adj(adjDD,c)
1497                                 cout << adjDD << ";  ";
1498                         cout << endl;
1499                 }
1500                 #endif
1501
1502                 if (c != m_rootCluster)
1503                 {
1504
1505                         ListIterator<adjEntry> it;
1506                         it = c->firstAdj();
1507                         adjEntry start = *it;
1508
1509                         #ifdef OGDF_DEBUG
1510                         if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
1511                                 cout << "firstAdj " << start << endl; }
1512                         #endif
1513
1514                         while (it.valid())
1515                         {
1516                                 AdjEntryArray<bool> visitedAdjEntries((*m_pGraph),false);
1517
1518                                 ListIterator<adjEntry> succ = it.succ();
1519                                 adjEntry adj = *it;
1520                                 adjEntry succAdj;
1521
1522                                 if (succ.valid())
1523                                         succAdj = *succ;
1524                                 else
1525                                         succAdj = start;  // reached the last outgoing edge
1526
1527                                 #ifdef OGDF_DEBUG
1528                                 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
1529                                         cout << "Check next " << endl;
1530                                         cout << "current in adj list of" << adj << endl;
1531                                         cout << "succ in adj list of c " << succAdj << endl;
1532                                         cout << "cyclic succ in outer face " << adj->cyclicSucc() << endl;
1533                                 }
1534                                 #endif
1535
1536
1537
1538                                 if (adj->cyclicSucc() != succAdj)
1539                                         // run along the outer face of the cluster
1540                                         // until you find the next outgoing edge
1541                                 {
1542                                         adjEntry next = adj->cyclicSucc();
1543                                         adjEntry twin = next->twin();
1544
1545                                         #ifdef OGDF_DEBUG
1546                                         if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
1547                                                 cout << "Running along the outer face ... " << endl;
1548                                                 cout << "next adj " << next << endl;
1549                                                 cout << "twin adj " << twin << endl;
1550                                         }
1551                                         #endif
1552
1553                                         if (visitedAdjEntries[twin])
1554                                                 return false;
1555                                         visitedAdjEntries[twin] = true;
1556                                         while ( next != succAdj)
1557                                         {
1558                                                 next = twin->cyclicSucc();
1559                                                 twin = next->twin();
1560                                                 #ifdef OGDF_DEBUG
1561                                                 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
1562                                                         cout << "Running along the outer face ... " << endl;
1563                                                         cout << "next adj " << next << endl;
1564                                                         cout << "twin adj " << twin << endl;
1565                                                 }
1566                                                 #endif
1567                                                 if (visitedAdjEntries[twin])
1568                                                         return false;
1569                                                 visitedAdjEntries[twin] = true;
1570                                         }
1571
1572                                 }
1573                                 // else
1574                                 // next edge is also outgoing
1575
1576                                 it = succ;
1577                         }
1578                 }
1579         }
1580
1581
1582         return true;
1583
1584 }
1585
1586
1587
1588
1589 // registers a cluster array
1590 ListIterator<ClusterArrayBase*> ClusterGraph::registerArray(
1591         ClusterArrayBase *pClusterArray) const
1592 {
1593         return m_regClusterArrays.pushBack(pClusterArray);
1594 }
1595
1596 // unregisters a cluster array
1597 void ClusterGraph::unregisterArray(ListIterator<ClusterArrayBase*> it) const
1598 {
1599         m_regClusterArrays.del(it);
1600 }
1601
1602 //! Registers a ClusterGraphObserver.
1603 ListIterator<ClusterGraphObserver*> ClusterGraph::registerObserver(ClusterGraphObserver *pObserver) const
1604 {
1605         return m_regObservers.pushBack(pObserver);
1606 }
1607
1608 //! Unregisters a ClusterGraphObserver.
1609 void ClusterGraph::unregisterObserver(ListIterator<ClusterGraphObserver*> it) const
1610 {
1611         m_regObservers.del(it);
1612 }
1613 //---------------------------------------------------------
1614 // Methods for printing
1615 //---------------------------------------------------------
1616
1617
1618 // writes graph in GML format to file fileName
1619 void ClusterGraph::writeGML(const char *fileName)
1620 {
1621         ofstream os(fileName);
1622         writeGML(os);
1623 }
1624
1625 // writes graph in GML format to output stream os
1626 void ClusterGraph::writeGML(ostream &os)
1627 {
1628         NodeArray<int>    nId(*m_pGraph);
1629         ClusterArray<int> cId(*this);
1630         int nextId = 0;
1631
1632         os << "Creator \"ogdf::ClusterGraph::writeGML\"\n";
1633         os << "graph [\n";
1634         os << "  directed 1\n";
1635
1636         node v;
1637         forall_nodes(v,*m_pGraph) {
1638                 os << "  node [\n";
1639                 os << "    id " << (nId[v] = nextId++) << "\n";
1640                 os << "  ]\n"; // node
1641         }
1642
1643         edge e;
1644         forall_edges(e,*m_pGraph) {
1645                 os << "  edge [\n";
1646                 os << "    source " << nId[e->source()] << "\n";
1647                 os << "    target " << nId[e->target()] << "\n";
1648                 os << "  ]\n"; // edge
1649         }
1650
1651         String scip = "  ";
1652         nextId = 0;
1653         writeCluster(os,nId,cId,nextId,m_rootCluster,scip);
1654
1655         os << "]\n"; // graph
1656 }
1657
1658
1659 // recursively write the cluster structure in GML
1660 void ClusterGraph::writeCluster(ostream &os,
1661                                                                 NodeArray<int> &nId,
1662                                                                 ClusterArray<int> & cId,
1663                                                                 int &nextId,
1664                                                                 cluster c,
1665                                                                 String scip)
1666 {
1667         String newScip = scip;
1668         newScip+="  ";
1669         os << scip << "cluster [\n";
1670         os << scip << "  id " << (cId[c] = nextId++) << "\n";
1671         ListIterator<cluster> it;
1672         for (it = c->m_children.begin(); it.valid(); it++)
1673                 writeCluster(os,nId,cId,nextId,*it,newScip);
1674         ListIterator<node> itn;
1675         for (itn = c->m_entries.begin(); itn.valid(); itn++)
1676                 os << scip << "  node " << nId[*itn] << "\n";
1677         os << scip << "]\n"; // cluster
1678 }
1679
1680
1681 // recursively write the cluster structure in GraphWin GML
1682 void ClusterGraph::writeGraphWinCluster(ostream &os,
1683                                                                 NodeArray<int> &nId,
1684                                                                 NodeArray<String> &nStr,
1685                                                                 ClusterArray<int> & cId,
1686                                                                 ClusterArray<String> & cStr,
1687                                                                 int &nextId,
1688                                                                 cluster c,
1689                                                                 String scip)
1690 {
1691         String newScip = scip;
1692         newScip+="  ";
1693         if (c == m_rootCluster)
1694                 os << scip << "rootcluster [\n";
1695         else
1696         {
1697                 os << scip << "cluster [\n";
1698 //              os << scip << "  id " << (cId[c] = nextId++) << "\n";
1699                 os << scip << "  id " << c->index() << "\n";
1700                 char newLabel[124];
1701 //              sprintf(newLabel,"C%d",cId[c]);
1702                 ogdf::sprintf(newLabel,124,"C%d",c->index());
1703                 cStr[c] = newLabel;
1704                 os << scip << "  label \"" << cStr[c] << "\"\n";
1705
1706         }
1707         ListIterator<cluster> it;
1708         for (it = c->m_children.begin(); it.valid(); it++)
1709                 writeGraphWinCluster(os,nId,nStr,cId,cStr,nextId,*it,newScip);
1710         ListIterator<node> itn;
1711         for (itn = c->m_entries.begin(); itn.valid(); itn++)
1712                 os << scip << "  vertex \"v" << nId[*itn] << "\"\n";
1713         os << scip << "]\n"; // cluster
1714 }
1715
1716
1717 //++++++++++++++++++++++++++++++++++++++++++++
1718 //reading graph,  cluster structure
1719 bool ClusterGraph::readClusterGML(const char* fileName,
1720                                                                 Graph& G)
1721 {
1722         ifstream is(fileName);
1723         if (!is)
1724                 return false; // couldn't open file
1725
1726         return readClusterGML(is, G);
1727 }
1728
1729 bool ClusterGraph::readClusterGML(istream& is,
1730                                                                 Graph& G)
1731 {
1732         bool result;
1733         GmlParser gml(is);
1734         if (gml.error())
1735                 return false;
1736
1737         result = gml.read(G);
1738
1739         if (!result) return false;
1740
1741         return gml.readCluster(G, *this);
1742 }
1743
1744
1745 // read Cluster Graph from OGML file
1746 //bool ClusterGraph::readClusterGraphOGML(const char* fileName,
1747 //                                                                                               ClusterGraph& CG,
1748 //                                                                                               Graph& G)
1749 //{
1750 //      ifstream is(fileName);
1751 //      // not able to open file
1752 //      if (!is) return false;
1753 //
1754 //      OgmlParser *op = new OgmlParser();
1755 //      // build graph
1756 //      // method read contains the validation
1757 //      if (!op->read(fileName, G, CG, *this)){
1758 //              delete(op);
1759 //              cerr << "ERROR occured while reading. Aborting." << endl << flush;
1760 //              return false;
1761 //      }
1762 //
1763 //      delete(op);
1764 //      return true;
1765 //};
1766
1767
1768 } // end namespace ogdf
1769
1770 //****************************************************************
1771 ostream &operator<<(ostream &os, ogdf::cluster c)
1772 {
1773         if (c) os << c->index(); else os << "nil";
1774         return os;
1775 }