ext/OGDF/src/planarity/FindKuratowskis.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief implementation of the class FindKuratowskis
  11  *
  12  * \author Jens Schmidt
  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/internal/planarity/FindKuratowskis.h>
  45 #include <ogdf/basic/simple_graph_alg.h>
  46
  47
  48 namespace ogdf {
  49
  50
  51 // copy pointer of class Kuratowski
  52 void KuratowskiStructure::copyPointer(const KuratowskiStructure& orig, SListPure<WInfo>& list) {
  53         SListConstIterator<SListPure<adjEntry> > itHighOrig=orig.highestXYPaths.begin();
  54         SListIterator<SListPure<adjEntry> > itHigh=highestXYPaths.begin();
  55         SListConstIterator<SListPure<adjEntry> > itZOrig=orig.zPaths.begin();
  56         SListIterator<SListPure<adjEntry> > itZ=zPaths.begin();
  57         SListConstIterator<ExternE> itExternStartOrig=orig.externE.begin();
  58         SListIterator<ExternE> itExternStart=externE.begin();
  59         SListConstIterator<ExternE> itExternEndOrig=orig.externE.begin();
  60         SListIterator<ExternE> itExternEnd=externE.begin();
  61         SListIterator<WInfo> it;
  62         for (it=list.begin(); it.valid(); ++it) {
  63                 WInfo& info(*it);
  64                 if (info.highestXYPath!=NULL) {
  65                         // go to referenced object
  66                         while (info.highestXYPath != &(*itHighOrig)) {
  67                                 ++itHigh;
  68                                 ++itHighOrig;
  69                         }
  70                         OGDF_ASSERT(itHigh.valid() && itHighOrig.valid());
  71                         info.highestXYPath=&(*itHigh);
  72                 }
  73                 if (info.zPath!=NULL) {
  74                         // go to referenced object
  75                         while (info.zPath != &(*itZOrig)) {
  76                                 ++itZ;
  77                                 ++itZOrig;
  78                         }
  79                         OGDF_ASSERT(itZ.valid() && itZOrig.valid());
  80                         info.zPath=&(*itZ);
  81                 }
  82                 if (info.externEStart.valid()) {
  83                         // go to referenced object
  84                         while ((*info.externEStart).theNode != (*itExternStartOrig).theNode) {
  85                                 ++itExternStartOrig;
  86                                 ++itExternStart;
  87                         }
  88                         OGDF_ASSERT(itExternStartOrig.valid() && itExternStart.valid());
  89                         info.externEStart = itExternStart;
  90                 }
  91                 if (info.externEEnd.valid()) {
  92                         // go to referenced object
  93                         while ((*info.externEEnd).theNode != (*itExternEndOrig).theNode) {
  94                                 ++itExternEndOrig;
  95                                 ++itExternEnd;
  96                         }
  97                         OGDF_ASSERT(itExternEndOrig.valid() && itExternEnd.valid());
  98                         info.externEEnd = itExternEnd;
  99                 }
 100         }
 101 }
 102
 103 // copy class Kuratowski
 104 void KuratowskiStructure::copy(const KuratowskiStructure& orig) {
 105         V = orig.V;
 106         V_DFI = orig.V_DFI;
 107         R = orig.R;
 108         RReal = orig.RReal;
 109         stopX = orig.stopX;
 110         stopY = orig.stopY;
 111
 112         wNodes = orig.wNodes;
 113         highestFacePath = orig.highestFacePath;
 114         highestXYPaths = orig.highestXYPaths;
 115         externalFacePath = orig.externalFacePath;
 116         externalSubgraph = orig.externalSubgraph;
 117         pertinentSubgraph = orig.pertinentSubgraph;
 118         zPaths = orig.zPaths;
 119         externE = orig.externE;
 120         stopXStartnodes = orig.stopXStartnodes;
 121         stopYStartnodes = orig.stopYStartnodes;
 122         stopXEndnodes = orig.stopXEndnodes;
 123         stopYEndnodes = orig.stopYEndnodes;
 124
 125         // copy pointer
 126         copyPointer(orig,wNodes);
 127 }
 128
 129
 130 // clears members
 131 void KuratowskiStructure::clear()
 132 {
 133         V=R=RReal=stopX=stopY=NULL;
 134         V_DFI = 0;
 135         wNodes.clear();
 136         highestFacePath.clear();
 137         highestXYPaths.clear();
 138         externalFacePath.clear();
 139         externalSubgraph.clear();
 140         pertinentSubgraph.clear();
 141         zPaths.clear();
 142         externE.clear();
 143         stopXStartnodes.clear();
 144         stopYStartnodes.clear();
 145         stopXEndnodes.clear();
 146         stopYEndnodes.clear();
 147 }
 148
 149 // class FindKuratowski
 150 FindKuratowskis::FindKuratowskis(BoyerMyrvoldPlanar* bm) :
 151         pBM(bm),
 152         m_g(bm->m_g),
 153         m_embeddingGrade(bm->m_embeddingGrade),
 154
 155         m_bundles(bm->m_bundles),
 156
 157         // initialize Members of BoyerMyrvoldPlanar
 158         m_realVertex(bm->m_realVertex),
 159         m_dfi(bm->m_dfi),
 160         m_nodeFromDFI(bm->m_nodeFromDFI),
 161         m_link(bm->m_link),
 162         m_adjParent(bm->m_adjParent),
 163         m_leastAncestor(bm->m_leastAncestor),
 164         m_edgeType(bm->m_edgeType),
 165         m_lowPoint(bm->m_lowPoint),
 166         m_highestSubtreeDFI(bm->m_highestSubtreeDFI),
 167         m_separatedDFSChildList(bm->m_separatedDFSChildList),
 168         m_pointsToRoot(bm->m_pointsToRoot),
 169         m_visitedWithBackedge(bm->m_visitedWithBackedge),
 170         m_backedgeFlags(bm->m_backedgeFlags),
 171         m_pertinentRoots(bm->m_pertinentRoots)
 172 {
 173         OGDF_ASSERT(bm != NULL);
 174         m_nodeMarker = 0;
 175 }
 176
 177 // finds root node of the bicomp containing the stopping node stopX
 178 node FindKuratowskis::findRoot(node stopX) {
 179         int dir = CCW;
 180         while (m_realVertex[stopX]==NULL)
 181                 stopX = pBM->successorWithoutShortCircuit(stopX,dir);
 182         return stopX;
 183 }
 184
 185 // extracts highest face path (contains all highest xy-paths)
 186 void FindKuratowskis::extractHighestFacePath(
 187                                 ListPure<adjEntry>& highestFacePath,
 188                                 int marker) {
 189         adjEntry adj = pBM->beforeShortCircuitEdge(k.R,CCW);
 190         adjEntry end = pBM->beforeShortCircuitEdge(k.R,CW);
 191         node x,target;
 192         while (adj != end->twin()) {
 193                 x = adj->theNode();
 194
 195                 if (m_wasHere[x] >= marker) {
 196                         // node is already visited on facepath: pop until duplicate node found
 197                         OGDF_ASSERT(!highestFacePath.empty());
 198                         while (highestFacePath.back()->theNode()!=x) highestFacePath.popBack();
 199                         // sign cut-vertex with marker+1
 200                         m_wasHere[x] = marker+1;
 201                 } else {
 202                         highestFacePath.pushBack(adj);
 203                         // sign visited nodes with marker
 204                         m_wasHere[x] = marker;
 205                 }
 206
 207                 do {
 208                         adj = adj->cyclicSucc();
 209                         target = adj->twinNode();
 210                         if (target == k.R) m_wasHere[x] = marker+1;
 211                 } while (adj != end &&
 212                                 (m_edgeType[adj->theEdge()] == EDGE_BACK_DELETED ||
 213                                 m_dfi[target] <= m_dfi[k.R]));
 214                 adj = adj->twin();
 215         }
 216 }
 217
 218 // extract external facepath in direction CCW and split the highest facepath
 219 // in highest xy-paths. marker marks the node, highMarker is used to check,
 220 // whether the node was visited before by the highest facepath traversal.
 221 // highMarker+1 identifies the nodes that are zNodes.
 222 void FindKuratowskis::extractExternalFacePath(
 223                                 SListPure<adjEntry>& externalFacePath,
 224                                 const ListPure<adjEntry>& highestFacePath,
 225                                 int marker,
 226                                 int highMarker)
 227 {
 228         int dir = CCW;
 229         // x traverses the external facepath
 230         node x = pBM->successorWithoutShortCircuit(k.R,dir);
 231         externalFacePath.pushBack(pBM->beforeShortCircuitEdge(k.R,CCW));
 232         m_wasHere[k.R] = marker;
 233         while (x != k.R) {
 234                 // set visited sign on nodes that are both on the highest and external facepath
 235                 if (m_wasHere[x]>=highMarker) m_wasHere[x] = marker;
 236                 externalFacePath.pushBack(pBM->beforeShortCircuitEdge(x,dir));
 237                 x = pBM->successorWithoutShortCircuit(x,dir);
 238         }
 239
 240         dir = CCW;
 241         x = pBM->successorWithoutShortCircuit(k.R,dir);
 242         ListConstIterator<adjEntry> highIt = highestFacePath.begin();
 243         OGDF_ASSERT(x == (*highIt)->theNode());
 244         SListPure<adjEntry> XYPathList;
 245         SListPure<adjEntry> zList;
 246         WInfo info;
 247         adjEntry adj = pBM->beforeShortCircuitEdge(k.R,CCW);
 248         adjEntry temp;
 249         while (x != k.R) {
 250                 // go along the highest face path until next visited sign
 251                 OGDF_ASSERT(adj->theNode()==x);
 252                 if (m_wasHere[x] == marker) {
 253                         XYPathList.clear();
 254                         zList.clear();
 255                         info.w = NULL;
 256                         info.minorType = 0;
 257                         info.highestXYPath = NULL;
 258                         info.zPath = NULL;
 259                         info.pxAboveStopX = false;
 260                         info.pyAboveStopY = false;
 261                         info.externEStart = NULL;
 262                         info.externEEnd = NULL;
 263                         info.firstExternEAfterW = NULL;
 264                 }
 265
 266                 // push in wNodes-list
 267                 if (pBM->pertinent(x)) {
 268                         info.w = x;
 269                         k.wNodes.pushBack(info);
 270                 }
 271
 272                 // compute next highestXYPath
 273                 if (m_wasHere[x] == marker &&
 274                                         m_wasHere[pBM->constSuccessorWithoutShortCircuit(x,dir)] != marker) {
 275                         // traverse highFacePath to x
 276                         while ((*highIt)->theNode() != x) ++highIt;
 277                         OGDF_ASSERT(highIt.valid());
 278                         XYPathList.pushBack(adj);
 279                         OGDF_ASSERT((*highIt.succ())->theNode() !=
 280                                                 pBM->constSuccessorWithoutShortCircuit(x,dir));
 281
 282                         // traverse highFacePath to next marker
 283                         do {
 284                                 ++highIt;
 285                                 if (!highIt.valid()) break;
 286                                 temp = *highIt;
 287                                 XYPathList.pushBack(temp);
 288                                 // check, if node is z-node and push one single z-node
 289                                 if (m_wasHere[temp->theNode()]==highMarker+1 && zList.empty())
 290                                         zList.pushBack(temp);
 291                         } while (m_wasHere[temp->theNode()] != marker);
 292
 293                         // save highestXY-Path
 294                         OGDF_ASSERT(!XYPathList.empty());
 295                         k.highestXYPaths.pushBack(XYPathList);
 296                         info.highestXYPath = &k.highestXYPaths.back();
 297
 298                         // compute path from zNode to V and save it
 299                         if (!zList.empty()) {
 300                                 OGDF_ASSERT(zList.size()==1); // just one zNode for now
 301                                 temp = zList.back();
 302                                 do {
 303                                         do {
 304                                                 temp = temp->cyclicSucc();
 305                                                 OGDF_ASSERT(m_dfi[temp->twinNode()]==m_dfi[k.R] ||
 306                                                                         m_dfi[temp->twinNode()]>=m_dfi[k.RReal]);
 307                                         } while (m_edgeType[temp->theEdge()]==EDGE_BACK_DELETED);
 308                                         temp = temp->twin();
 309                                         zList.pushBack(temp);
 310                                 } while (temp->theNode() != k.R);
 311                                 k.zPaths.pushBack(zList);
 312                                 info.zPath = &k.zPaths.back();
 313                         }
 314                 }
 315
 316                 // go on
 317                 adj = pBM->beforeShortCircuitEdge(x,dir);
 318                 x = pBM->successorWithoutShortCircuit(x,dir);
 319         }
 320 }
 321
 322 // separate pertinent nodes in the lists of possible different minor-types
 323 void FindKuratowskis::splitInMinorTypes(
 324                         const SListPure<adjEntry>& externalFacePath,
 325                         int marker)
 326 {
 327         // mark nodes, which are before stopX or behind stopY in CCW-traversal and add
 328         // all extern nodes strictly between stopX and stopY to list
 329         // externE for minor E (pertinent nodes are considered because of the
 330         // position of z left or right of w)
 331         SListConstIterator<adjEntry> itExtern;
 332         SListIterator<WInfo> it = k.wNodes.begin();
 333         node x;
 334         bool between = false;
 335         SListPure<WInfo*> infoList;
 336         SListIterator<WInfo*> itList;
 337         ExternE externEdummy;
 338         // compute list of externE nodes
 339         for (itExtern=externalFacePath.begin(); itExtern.valid(); ++itExtern) {
 340                 x = (*itExtern)->theNode();
 341                 if (x==k.stopX || x==k.stopY) {
 342                         between = (between==false) ? true : false;
 343                 } else {
 344                         if (!between) {
 345                                 m_wasHere[x]=marker;
 346                         } else {
 347                                 if (pBM->externallyActive(x,k.V_DFI)) {
 348                                         externEdummy.theNode = x;
 349
 350                                         // check minor type B and save extern linkage
 351                                         if (it.valid() && (*it).w==x &&
 352                                                         !m_pertinentRoots[x].empty() &&
 353                                                         m_lowPoint[m_nodeFromDFI[-m_dfi[m_pertinentRoots[x].back()]]]
 354                                                         < k.V_DFI) {
 355                                                 WInfo& info(*it);
 356
 357                                                 // checking minor type B
 358                                                 info.minorType |= WInfo::B;
 359                                                 // mark extern node for later extraction
 360                                                 externEdummy.startnodes.pushBack(0);
 361                                                 // create externE-list
 362                                                 k.externE.pushBack(externEdummy);
 363                                                 // save extern linkage
 364                                                 info.externEStart = k.externE.rbegin();
 365                                                 info.externEEnd = k.externE.rbegin();
 366                                         } else {
 367                                                 // create externE-list
 368                                                 externEdummy.startnodes.clear();
 369                                                 k.externE.pushBack(externEdummy);
 370                                         }
 371
 372                                         // save for each wNode the first externally active successor
 373                                         // on the external face
 374                                         for (itList = infoList.begin(); itList.valid(); ++itList)
 375                                                 (*itList)->firstExternEAfterW = x;
 376                                         infoList.clear();
 377
 378
 379                                 }
 380
 381                                 // get appropriate WInfo
 382                                 if (it.valid() && (*it).w==x) {
 383                                         infoList.pushBack(&(*it));
 384                                         ++it;
 385                                 }
 386                         }
 387                 }
 388         }
 389
 390         // divide wNodes in different minor types
 391         // avoids multiple computation of the externE range
 392         itExtern = externalFacePath.begin();
 393         SListIterator<ExternE> itExternE = k.externE.begin();
 394         WInfo* oldInfo = NULL;
 395         for (it=k.wNodes.begin(); it.valid(); ++it) {
 396                 WInfo& info(*it);
 397
 398                 // checking minor type A
 399                 if (k.RReal!=k.V) info.minorType |= WInfo::A;
 400
 401                 // if a XYPath exists
 402                 if (info.highestXYPath!=NULL) {
 403                         if (m_wasHere[info.highestXYPath->front()->theNode()]==marker)
 404                                 info.pxAboveStopX = true;
 405                         if (m_wasHere[info.highestXYPath->back()->theNode()]==marker)
 406                                 info.pyAboveStopY = true;
 407
 408                         // checking minor type C
 409                         if (info.pxAboveStopX || info.pyAboveStopY)
 410                                 info.minorType |= WInfo::C;
 411
 412                         // checking minor type D
 413                         if (info.zPath!=NULL) info.minorType |= WInfo::D;
 414
 415                         // checking minor type E
 416                         if (!k.externE.empty()) {
 417                                 node t;
 418
 419                                 // compute valid range of externE-nodes in linear time
 420                                 if (oldInfo!=NULL && info.highestXYPath==oldInfo->highestXYPath) {
 421                                         // found the same highestXYPath as before
 422                                         info.externEStart = oldInfo->externEStart;
 423                                         info.externEEnd = oldInfo->externEEnd;
 424                                         if (oldInfo->minorType & WInfo::E) info.minorType |= WInfo::E;
 425                                 } else {
 426                                         // compute range of a new highestXYPath
 427                                         node px;
 428                                         if (info.pxAboveStopX) px = k.stopX;
 429                                                 else px = info.highestXYPath->front()->theNode();
 430                                         node py;
 431                                         if (info.pyAboveStopY) py = k.stopY;
 432                                                 else py = info.highestXYPath->back()->theNode();
 433                                         while ((*itExtern)->theNode() != px) ++itExtern;
 434                                         t = (*(++itExtern))->theNode();
 435                                         node start = NULL;
 436                                         node end = NULL;
 437                                         while (t != py) {
 438                                                 if (pBM->externallyActive(t,k.V_DFI)) {
 439                                                         if (start==NULL) start = t;
 440                                                         end = t;
 441                                                 }
 442                                                 t = (*(++itExtern))->theNode();
 443                                         }
 444                                         if (start != NULL) {
 445                                                 while ((*itExternE).theNode != start) ++itExternE;
 446                                                 info.externEStart = itExternE;
 447                                                 // mark node to extract external subgraph later
 448                                                 (*itExternE).startnodes.pushBack(0);
 449                                                 node temp = start;
 450                                                 while (temp != end) {
 451                                                         temp = (*++itExternE).theNode;
 452                                                         // mark node to extract external subgraph later
 453                                                         (*itExternE).startnodes.pushBack(0);
 454                                                 }
 455                                                 info.externEEnd = itExternE;
 456                                                 info.minorType |= WInfo::E;
 457                                         }
 458                                         oldInfo = &info;
 459                                 }
 460                         }
 461                 }
 462
 463                 /*
 464                 // use this to find special kuratowski-structures
 465                 if ((info.minorType & (WInfo::A|WInfo::B|WInfo::C|WInfo::D|WInfo::E)) ==
 466                         (WInfo::A|WInfo::B|WInfo::C|WInfo::D|WInfo::E)) {
 467                         char t; cin >> t;
 468                 }
 469                 */
 470         }
 471
 472         // extract the externalSubgraph of all saved externally active nodes
 473         // exclude the already extracted minor b-types
 474         #ifdef OGDF_DEBUG
 475         int visited = m_nodeMarker+1;
 476         #endif
 477         for (itExternE=k.externE.begin(); itExternE.valid(); ++itExternE) {
 478                 if ((*itExternE).startnodes.empty()) continue;
 479
 480                 ExternE& externE(*itExternE);
 481                 externE.startnodes.clear();
 482                 if (m_bundles) {
 483                         OGDF_ASSERT(m_wasHere[externE.theNode] < visited);
 484                         extractExternalSubgraphBundles(externE.theNode,k.V_DFI,
 485                                                                                 k.externalSubgraph,++m_nodeMarker);
 486                 } else {
 487                         extractExternalSubgraph(externE.theNode,k.V_DFI,externE.startnodes,
 488                                                                                                                         externE.endnodes);
 489                         SListIterator<int> itInt;
 490                         SListPure<edge> dummy;
 491                         for (itInt = externE.startnodes.begin(); itInt.valid(); ++itInt)
 492                                 externE.externalPaths.pushBack(dummy);
 493                 }
 494         }
 495 }
 496
 497 // extracts and adds external subgraph from stopnode to ancestors of the node with dfi root
 498 // to edgelist, nodeMarker is used as a visited flag. returns the endnode with lowest dfi.
 499 void FindKuratowskis::extractExternalSubgraph(
 500                         const node stop,
 501                         int root,
 502                         SListPure<int>& externalStartnodes,
 503                         SListPure<node>& externalEndnodes)
 504 {
 505         int lowpoint;
 506         ListConstIterator<node> it;
 507
 508         if (m_leastAncestor[stop] < root) {
 509                 externalStartnodes.pushBack(m_dfi[stop]);
 510                 externalEndnodes.pushBack(m_nodeFromDFI[m_leastAncestor[stop]]);
 511         }
 512
 513         // descent to external active child bicomps of stopnode
 514         node temp;
 515         for (it = m_separatedDFSChildList[stop].begin(); it.valid(); ++it) {
 516                 temp = *it;
 517                 lowpoint = m_lowPoint[temp];
 518                 if (lowpoint >= root) break;
 519
 520                 externalStartnodes.pushBack(m_dfi[temp]);
 521                 externalEndnodes.pushBack(m_nodeFromDFI[lowpoint]);
 522         }
 523 }
 524
 525 // extract and add external subgraph from stopnode to ancestors of the node with dfi root
 526 // to edgelist, nodeMarker is used as a visited flag. returns the endnode with lowest dfi.
 527 void FindKuratowskis::extractExternalSubgraphBundles(
 528                         const node stop,
 529                         int root,
 530                         SListPure<edge>& externalSubgraph,
 531                         int nodeMarker)
 532 {
 533         node v,temp;
 534         adjEntry adj;
 535
 536         #ifdef OGDF_DEBUG
 537         forall_nodes(v,m_g) OGDF_ASSERT(m_wasHere[v]!=nodeMarker);
 538         #endif
 539
 540         StackPure<node> stack; // stack for dfs-traversal
 541         ListConstIterator<node> it;
 542         stack.push(stop);
 543         while (!stack.empty()) {
 544                 v = stack.pop();
 545                 if (m_wasHere[v]==nodeMarker) continue;
 546                 // mark visited nodes
 547                 m_wasHere[v]=nodeMarker;
 548
 549                 // search for unvisited nodes and add them to stack
 550                 forall_adj(adj,v) {
 551                         temp = adj->twinNode();
 552                         if (m_edgeType[adj->theEdge()]==EDGE_BACK_DELETED) continue;
 553
 554                         // go along backedges to ancestor (ignore virtual nodes)
 555                         if (m_dfi[temp] < root && m_dfi[temp] > 0) {
 556                                 OGDF_ASSERT(m_edgeType[adj->theEdge()]==EDGE_BACK);
 557                                 externalSubgraph.pushBack(adj->theEdge());
 558                         } else if (v != stop && m_dfi[temp]>=m_dfi[v]) {
 559                                 // set flag and push unvisited nodes
 560                                 OGDF_ASSERT(m_edgeType[adj->theEdge()]==EDGE_BACK ||
 561                                                         m_edgeType[adj->theEdge()]==EDGE_DFS ||
 562                                                         m_edgeType[adj->theEdge()]==EDGE_BACK_DELETED);
 563                                 externalSubgraph.pushBack(adj->theEdge());
 564                                 if (m_wasHere[temp] != nodeMarker) stack.push(temp);
 565                         }
 566                 }
 567
 568                 // descent to external active child bicomps
 569                 for (it = m_separatedDFSChildList[v].begin(); it.valid(); ++it) {
 570                         temp = *it;
 571                         if (m_lowPoint[temp] >= root) break;
 572                         stack.push(m_nodeFromDFI[-m_dfi[temp]]);
 573                 }
 574         }
 575 }
 576
 577 // extract pertinent paths from all w-nodes to k.V to edgelist
 578 void FindKuratowskis::extractPertinentSubgraph(
 579                                 SListPure<WInfo>& W_All/*,
 580                                 const node V*/)
 581 {
 582         SListPure<edge> path;
 583         SListIterator<WInfo> it;
 584         adjEntry adj;
 585         int minDFI = -m_dfi[k.R];
 586         int maxDFI = m_highestSubtreeDFI[m_nodeFromDFI[minDFI]];
 587         int targetDFI;
 588         node target;
 589         edge e;
 590
 591         // create links from pertinent nodes to WInfo
 592         for (it = W_All.begin(); it.valid(); ++it)
 593                 m_getWInfo[(*it).w] = &(*it);
 594
 595         // add all pertinent paths to WInfo
 596         forall_adj(adj,k.V) {
 597                 if (m_edgeType[adj->theEdge()]==EDGE_BACK_DELETED) continue;
 598                 targetDFI = m_dfi[adj->twinNode()];
 599                 if (targetDFI >= minDFI && targetDFI <= maxDFI) {
 600                         // target node is in subtree of a pertinent node
 601
 602                         // delete last edge and backedgeFlags
 603                         target = adj->twinNode();
 604                         e = adj->theEdge();
 605                         path.pushFront(e);
 606                         OGDF_ASSERT(!m_backedgeFlags[target].empty());
 607                         m_backedgeFlags[target].clear();
 608                         m_edgeType[e] = EDGE_BACK_DELETED;
 609                         // delete backedge-counter on virtual root node
 610                         --m_visitedWithBackedge[m_pointsToRoot[e]];
 611                         OGDF_ASSERT(m_visitedWithBackedge[m_pointsToRoot[e]] >= 0);
 612
 613                         // go up along the DFS-path
 614                         while (m_getWInfo[target] == NULL) {
 615                                 path.pushFront(m_adjParent[target]->theEdge());
 616                                 target = m_adjParent[target]->theNode();
 617                                 if (m_realVertex[target] != NULL) {
 618                                         target = m_realVertex[target];
 619                                         m_pertinentRoots[target].clear();
 620                                 }
 621                         }
 622
 623                         // save path
 624                         m_getWInfo[target]->pertinentPaths.pushBack(path);
 625                         path.clear();
 626                 }
 627         }
 628
 629         // delete links from pertinent nodes to WInfo
 630         for (it = W_All.begin(); it.valid(); ++it)
 631                 m_getWInfo[(*it).w] = NULL;
 632 }
 633
 634
 635 // extract and add pertinent subgraph from all w-nodes to v to edgelist
 636 void FindKuratowskis::extractPertinentSubgraphBundles(
 637                                 const SListPure<WInfo>& W_All,
 638                                 const node V,
 639                                 SListPure<edge>& pertinentSubgraph,
 640                                 int nodeMarker)
 641 {
 642         node w,x;
 643         adjEntry adj;
 644         edge e;
 645
 646         #ifdef OGDF_DEBUG
 647         forall_nodes(w,m_g) OGDF_ASSERT(m_wasHere[w]!=nodeMarker);
 648         #endif
 649
 650         StackPure<node> stack; // stack for dfs-traversal
 651         SListIterator<node> it;
 652         SListConstIterator<WInfo> itt;
 653         // for all w-nodes
 654         for (itt = W_All.begin(); itt.valid(); ++itt) {
 655                 node currentWNode = (*itt).w;
 656                 stack.push(currentWNode);
 657
 658                 // until stack is empty, do dfs-traversal in bicomps and descent to
 659                 // pertinent child bicomps
 660                 while (!stack.empty()) {
 661                         w = stack.pop();
 662                         if (m_wasHere[w]==nodeMarker) continue;
 663                         // mark visited nodes
 664                         m_wasHere[w]=nodeMarker;
 665
 666                         // search for unvisited nodes and add them to stack
 667                         forall_adj(adj,w) {
 668                                 e = adj->theEdge();
 669                                 if (m_edgeType[e]==EDGE_BACK_DELETED) continue;
 670                                 x = adj->twinNode();
 671
 672                                 // go along pertinent backedges to V (ignore virtual nodes)
 673                                 if (x==V && m_edgeType[e]!=EDGE_BACK_DELETED) {
 674                                         OGDF_ASSERT(m_edgeType[e]==EDGE_BACK);
 675                                         // delete edge and delete backedgeFlags
 676                                         m_edgeType[e] = EDGE_BACK_DELETED;
 677                                         m_backedgeFlags[w].clear();
 678                                         // delete backedge-counter on virtual root node
 679                                         --m_visitedWithBackedge[m_pointsToRoot[e]];
 680                                         OGDF_ASSERT(m_visitedWithBackedge[m_pointsToRoot[e]]>=0);
 681                                         pertinentSubgraph.pushBack(e);
 682
 683                                 } else if (w != currentWNode && m_dfi[x] >= m_dfi[w]) {
 684                                         OGDF_ASSERT(m_edgeType[adj->theEdge()]==EDGE_DFS ||
 685                                                                 m_edgeType[adj->theEdge()]==EDGE_BACK ||
 686                                                                 m_edgeType[adj->theEdge()]==EDGE_BACK_DELETED);
 687                                         // set flag and push unvisited nodes
 688                                         pertinentSubgraph.pushBack(e);
 689                                         if (m_wasHere[x] != nodeMarker) stack.push(x);
 690                                 }
 691                         }
 692
 693                         // descent to pertinent child bicomps
 694                         for (it = m_pertinentRoots[w].begin(); it.valid(); ++it) {
 695                                 stack.push(*it);
 696                         }
 697                         // delete all pertinentRoots-lists, since there are no pertinent backedges any more
 698                         m_pertinentRoots[w].clear();
 699                 }
 700         }
 701 }
 702
 703 // add Kuratowski structure on current node V
 704 void FindKuratowskis::addKuratowskiStructure(
 705                                                 const node currentNode,
 706                                                 const node root,
 707                                                 const node stopx,
 708                                                 const node stopy)
 709 {
 710         OGDF_ASSERT(currentNode!=NULL && root!=NULL && stopx!=NULL && stopy!=NULL);
 711         OGDF_ASSERT(stopx!=stopy && currentNode!=stopx && currentNode!=stopy && m_dfi[root]<0);
 712         OGDF_ASSERT(!pBM->pertinent(stopx) &&
 713                                 pBM->externallyActive(stopx,m_dfi[currentNode]));
 714         OGDF_ASSERT(!pBM->pertinent(stopy) &&
 715                                 pBM->externallyActive(stopy,m_dfi[currentNode]));
 716         OGDF_ASSERT(findRoot(stopx)==root); // check root
 717         OGDF_ASSERT(pBM->wNodesExist(root,stopx,stopy));
 718         OGDF_ASSERT(isSimpleUndirected(m_g)); // Graph has to be simple
 719         OGDF_ASSERT(m_embeddingGrade > BoyerMyrvoldPlanar::doNotFind);
 720         // check, if we have found enough kuratowski structures
 721         OGDF_ASSERT(m_embeddingGrade <= 0 || allKuratowskis.size() < m_embeddingGrade);
 722
 723         // init NodeArrays in first invocation
 724         if (!m_wasHere.valid()) {
 725                 if (!m_bundles) {
 726                         OGDF_ASSERT(!m_getWInfo.valid() && m_getWInfo.graphOf()==NULL);
 727                         m_getWInfo.init(m_g,NULL);
 728                 }
 729                 OGDF_ASSERT(m_wasHere.graphOf()==NULL);
 730                 m_wasHere.init(m_g,0);
 731         }
 732
 733         // delete old KuratowskiStruture and initialize new structure
 734         k.clear();
 735         k.V = currentNode;
 736         k.V_DFI = m_dfi[currentNode];
 737         k.stopX = stopx;
 738         k.stopY = stopy;
 739         k.R = root;
 740         k.RReal = m_realVertex[k.R];
 741
 742         // flip bicomp with root R with or without reversed flipping. changes the embedding
 743         // process completely.
 744         pBM->flipBicomp(-m_dfi[k.R],++m_nodeMarker,m_wasHere,false,true);
 745         //      pBM->flipBicomp(-m_dfi[k.R],++m_nodeMarker,m_wasHere,false,false);
 746
 747         // extract highest facepath (contains all highest xy-paths)
 748         extractHighestFacePath(k.highestFacePath,++m_nodeMarker);
 749         ++m_nodeMarker;
 750
 751         // extract external facepath in direction CCW and split the highest facepath in
 752         // highest xy-paths
 753         ++m_nodeMarker;
 754         extractExternalFacePath(k.externalFacePath,k.highestFacePath,m_nodeMarker,
 755                                                                                                                         m_nodeMarker-2);
 756
 757         // extract external subgraph from stopX and stopY to ancestors of R
 758         if (m_bundles) {
 759                 extractExternalSubgraphBundles(k.stopX,k.V_DFI,k.externalSubgraph,++m_nodeMarker);
 760         } else {
 761                 extractExternalSubgraph(k.stopX,k.V_DFI,k.stopXStartnodes,k.stopXEndnodes);
 762         }
 763
 764         if (m_bundles) {
 765                 extractExternalSubgraphBundles(k.stopY,k.V_DFI,k.externalSubgraph,++m_nodeMarker);
 766         } else {
 767                 extractExternalSubgraph(k.stopY,k.V_DFI,k.stopYStartnodes,k.stopYEndnodes);
 768         }
 769
 770         // pass pertinent nodes in the lists of possible different minor-types
 771         splitInMinorTypes(k.externalFacePath,++m_nodeMarker);
 772
 773         // extract pertinent subgraphs from all w-nodes to k.V
 774         if (m_bundles) {
 775                 extractPertinentSubgraphBundles(k.wNodes,k.V,k.pertinentSubgraph,++m_nodeMarker);
 776         } else {
 777                 extractPertinentSubgraph(k.wNodes/*,k.V*/);
 778         }
 779
 780         // add Kuratowski to KuratowskisOnNode
 781         allKuratowskis.pushBack(k);
 782
 783         // reverse flipping
 784 //      pBM->flipBicomp(-m_dfi[k.R],++m_nodeMarker,m_wasHere,false,false);
 785
 786         OGDF_ASSERT(m_bundles || k.pertinentSubgraph.empty());
 787 }
 788
 789
 790 }