ext/OGDF/src/planarity/ExtractKuratowskis.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 ExtractKuratowskis
  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/planarity/ExtractKuratowskis.h>
  45
  46
  47 namespace ogdf {
  48
  49 // reinitializes backtracking. all paths will be traversed again. startedges are
  50 // either startInclude or not startExclude, all startedges have to contain the flag
  51 // startFlag
  52 void DynamicBacktrack::init(
  53                                 const node start,
  54                                 const node end,
  55                                 const bool less,
  56                                 const int flag,
  57                                 const int startFlag = 0,
  58                                 const edge startInclude = NULL,
  59                                 const edge startExlude = NULL)
  60 {
  61         OGDF_ASSERT(start!=NULL && end!=NULL);
  62         this->start = start;
  63         this->end = end;
  64         this->less = less;
  65         this->flag = flag;
  66
  67         // init stack
  68         stack.clear();
  69         adjEntry adj;
  70         if (startInclude == NULL) {
  71                 forall_adj(adj,start) {
  72                         if (((m_flags[adj->theEdge()] & startFlag) == startFlag) &&
  73                                         adj->theEdge() != startExlude) {
  74                                 stack.push(NULL);
  75                                 stack.push(adj);
  76                         }
  77                 }
  78         } else {
  79                 forall_adj(adj,start) {
  80                         if (adj->theEdge() == startInclude &&
  81                                 (m_flags[adj->theEdge()] & startFlag) == startFlag) {
  82                                 stack.push(NULL);
  83                                 stack.push(adj);
  84                         }
  85                 }
  86         }
  87
  88         // init array parent
  89         if (!stack.empty()) {
  90                 m_parent.fill(NULL);
  91                 m_parent[start] = stack.top();
  92         }
  93 }
  94
  95 // returns the next possible path from start to endnode, if exists.
  96 // endnode returns the last traversed node.
  97 bool DynamicBacktrack::addNextPath(SListPure<edge>& list, node& endnode) {
  98         adjEntry adj;
  99         node v = NULL;
 100         node temp;
 101
 102         while (!stack.empty()) {
 103                 // backtrack
 104                 adj = stack.pop();
 105
 106                 // return from a child node: delete parent
 107                 if (adj==NULL) {
 108                         // go to parent and delete visited flag
 109                         temp = v;
 110                         v = m_parent[temp]->theNode();
 111                         m_parent[temp] = NULL;
 112                         continue;
 113                 }
 114
 115                 // get and mark node
 116                 v = adj->twinNode();
 117                 m_parent[v] = adj;
 118
 119                 // path found
 120                 if ((less && m_dfi[v]<m_dfi[end]) || (!less && v==end))
 121                 {
 122                         // extract path
 123                         endnode = v;
 124                         list.clear();
 125                         list.pushBack(adj->theEdge());
 126                         while(adj->theNode() != start) {
 127                                 adj = m_parent[adj->theNode()];
 128                                 list.pushBack(adj->theEdge());
 129                         }
 130
 131                         // in a following call of this method we'll have to reconstruct the actual
 132                         // state, therefore delete the last NULLs and visited flags on stack
 133                         while (!stack.empty() && stack.top()==NULL) {
 134                                 stack.pop();
 135                                 temp = v;
 136                                 v = m_parent[temp]->theNode();
 137                                 m_parent[temp] = NULL;
 138                         }
 139
 140                         // return bool, if path found
 141                         return true;
 142                 }
 143
 144                 // push all possible child-nodes
 145                 forall_adj(adj,v) {
 146                         // if edge is signed and target node was not visited before
 147                         if ((m_flags[adj->theEdge()] & flag) && (m_parent[adj->twinNode()]==NULL)) {
 148                                 stack.push(NULL);
 149                                 stack.push(adj);
 150                         }
 151                 }
 152         }
 153         return false;
 154 }
 155
 156 // returns the next possible path from start to endnode, if exists.
 157 // endnode returns the last traversed node. all paths avoid "exclude"-nodes, except if
 158 // on an edge with flag "exceptOnEdge". only the part of the path, that doesn't
 159 // contain "exclude"-nodes is finally added. Here also the startedges computed in init()
 160 // are considered to match these conditions.
 161 bool DynamicBacktrack::addNextPathExclude(
 162                                 SListPure<edge>& list,
 163                                 node& endnode,
 164                                 const NodeArray<int>& nodeflags,
 165                                 int exclude,
 166                                 int exceptOnEdge) {
 167         adjEntry adj;
 168         node v = NULL;
 169         node temp;
 170
 171         while (!stack.empty()) {
 172                 // backtrack
 173                 adj = stack.pop();
 174
 175                 // return from a child node: delete parent
 176                 if (adj==NULL) {
 177                         // go to parent and delete visited flag
 178                         temp = v;
 179                         v = m_parent[temp]->theNode();
 180                         m_parent[temp] = NULL;
 181                         continue;
 182                 }
 183
 184                 // get and mark node
 185                 v = adj->twinNode();
 186
 187                 // check if startedges computed in init() match th conditions
 188                 if (nodeflags[v]==exclude && !(m_flags[adj->theEdge()] & exceptOnEdge)) {
 189                         OGDF_ASSERT(stack.top()==NULL);
 190                         stack.pop();
 191                         continue;
 192                 }
 193                 m_parent[v] = adj;
 194
 195                 // path found
 196                 if ((less && m_dfi[v] < m_dfi[end]) || (!less && v==end))
 197                 {
 198                         // extract path vice versa until the startnode or an exclude-node is found
 199                         endnode = v;
 200                         list.clear();
 201                         OGDF_ASSERT(nodeflags[v] != exclude);
 202                         list.pushBack(adj->theEdge());
 203                         while (adj->theNode() != start && nodeflags[adj->theNode()] != exclude) {
 204                                 adj = m_parent[adj->theNode()];
 205                                 list.pushBack(adj->theEdge());
 206                         }
 207
 208                         // in a following call of this method we'll have to reconstruct the actual
 209                         // state, therefore delete the last NULLs and visited flags on stack
 210                         while (!stack.empty() && stack.top()==NULL) {
 211                                 stack.pop();
 212                                 temp = v;
 213                                 v = m_parent[temp]->theNode();
 214                                 m_parent[temp] = NULL;
 215                         }
 216
 217                         // return bool, if path found
 218                         return true;
 219                 }
 220
 221                 // push all possible child-nodes
 222                 forall_adj(adj,v) {
 223                         node x = adj->twinNode();
 224                         edge e = adj->theEdge();
 225                         // if edge is signed and target node was not visited before
 226                         if ((m_flags[e] & flag) && m_parent[x]==NULL)
 227                         {
 228                                 // don't allow exclude-nodes, if not on an except-edge
 229                                 if ((nodeflags[x] != exclude) || (m_flags[e] & exceptOnEdge))
 230                                 {
 231                                         stack.push(NULL);
 232                                         stack.push(adj);
 233                                 }
 234                         }
 235                 }
 236         }
 237         return false;
 238 }
 239
 240 // class ExtractKuratowski
 241 ExtractKuratowskis::ExtractKuratowskis(BoyerMyrvoldPlanar& bm) :
 242         BMP(bm),
 243         m_g(bm.m_g),
 244         m_embeddingGrade(bm.m_embeddingGrade),
 245         m_avoidE2Minors(bm.m_avoidE2Minors),
 246
 247         m_wasHere(m_g,0),
 248
 249         // initialize Members of BoyerMyrvoldPlanar
 250         m_dfi(bm.m_dfi),
 251         m_nodeFromDFI(bm.m_nodeFromDFI),
 252         m_adjParent(bm.m_adjParent)
 253 {
 254         OGDF_ASSERT(m_embeddingGrade == BoyerMyrvoldPlanar::doFindUnlimited ||
 255                                 m_embeddingGrade > 0);
 256         // if only structures are limited, subdivisions must not be limited
 257         if (bm.m_limitStructures) m_embeddingGrade = BoyerMyrvoldPlanar::doFindUnlimited;
 258         m_nodeMarker = 0;
 259
 260         // flip Graph and merge virtual with real nodes, if not already done
 261         bm.flipBicomp(1,-1,m_wasHere,true,true);
 262 }
 263
 264 // returns the type of Kuratowski subdivision in list (none, K33 or K5)
 265 int ExtractKuratowskis::whichKuratowski(
 266                                         const Graph& m_g,
 267                                         const NodeArray<int>& /*m_dfi*/,
 268                                         const SListPure<edge>& list) {
 269         OGDF_ASSERT(!list.empty());
 270         EdgeArray<int> edgenumber(m_g,0);
 271
 272         // count edges
 273         SListConstIterator<edge> it;
 274         for (it = list.begin(); it.valid(); ++it) {
 275                 edge e = *it;
 276                 if (edgenumber[e] == 1) {
 277                         return ExtractKuratowskis::none;
 278                 }
 279                 edgenumber[e] = 1;
 280         }
 281
 282         return whichKuratowskiArray(m_g,/*m_dfi,*/edgenumber);
 283 }
 284
 285 // returns the type of Kuratowski subdivision in list (none, K33 or K5)
 286 // the edgenumber has to be 1 for used edges, otherwise 0
 287 int ExtractKuratowskis::whichKuratowskiArray(
 288                                         const Graph& m_g,
 289                                         //const NodeArray<int>& /* m_dfi */,
 290                                         EdgeArray<int>& edgenumber)
 291 {
 292         edge e,ed;
 293         node v;
 294         NodeArray<int> nodenumber(m_g,0);
 295         int K33Partition[6] = {0,-1,-1,-1,-1,-1};
 296         bool K33Links[6][6] = {{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},
 297                                                         {0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}};
 298
 299         node K33Nodes[6];
 300         node K5Nodes[5];
 301
 302         #ifdef OGDF_DEBUG
 303         forall_edges(e,m_g) OGDF_ASSERT(edgenumber[e] == 0 || edgenumber[e] == 1);
 304         #endif
 305
 306         // count incident nodes
 307         SListConstIterator<edge> it;
 308         int allEdges = 0;
 309         forall_edges(e,m_g) {
 310                 if (edgenumber[e] == 1) {
 311                         ++allEdges;
 312                         ++nodenumber[e->source()];
 313                         ++nodenumber[e->target()];
 314                 }
 315         }
 316         if (allEdges < 9) {
 317                 return ExtractKuratowskis::none;
 318         }
 319
 320         int degree3nodes = 0;
 321         int degree4nodes = 0;
 322         forall_nodes(v,m_g) {
 323                 if (nodenumber[v] > 4 || nodenumber[v] == 1) {
 324                         return ExtractKuratowskis::none;
 325                 }
 326                 if (nodenumber[v]==3) {
 327                         K33Nodes[degree3nodes] = v;
 328                         ++degree3nodes;
 329                 } else if (nodenumber[v]==4) {
 330                         K5Nodes[degree4nodes] = v;
 331                         ++degree4nodes;
 332                 }
 333         }
 334
 335         // check on K3,3
 336         int paths = 0;
 337         if (degree3nodes == 6) {
 338                 if (degree4nodes > 0) {
 339                         return ExtractKuratowskis::none;
 340                 }
 341                 for (int i=0; i<6; ++i) {
 342                         forall_adj_edges(e,K33Nodes[i]) {
 343                                 if (edgenumber[e] > 0) { // not visited
 344                                         edgenumber[e] = -2; // visited
 345                                         v = e->opposite(K33Nodes[i]);
 346                                         // traverse nodedegree-2 path until degree-3 node found
 347                                         while (nodenumber[v] != 3) {
 348                                                 nodenumber[v] = -2; // visited
 349                                                 forall_adj_edges(ed,v) if (edgenumber[ed] > 0) break;
 350                                                 OGDF_ASSERT(edgenumber[ed] > 0);
 351                                                 edgenumber[ed] = -2; // visited
 352                                                 v = ed->opposite(v);
 353                                         }
 354                                         int ii;
 355                                         for (ii=0; ii<6; ++ii) if (K33Nodes[ii]==v) break;
 356                                         OGDF_ASSERT(ii>=0 && ii<=5);
 357                                         if (K33Partition[i] != K33Partition[ii]) {
 358                                                 ++paths;
 359                                                 if (K33Partition[ii]==-1) K33Partition[ii] = !K33Partition[i];
 360                                                 if (!K33Links[i][ii]) {
 361                                                         K33Links[i][ii] = true;
 362                                                 } else {
 363                                                         return ExtractKuratowskis::none;
 364                                                 }
 365                                         } else {
 366                                                 return ExtractKuratowskis::none;
 367                                         }
 368                                 }
 369                         }
 370                 }
 371                 if (paths==9) {
 372                         return ExtractKuratowskis::K33;
 373                 } else {
 374                         return ExtractKuratowskis::none;
 375                 }
 376         } else if (degree4nodes == 5) {
 377                 // check on K5
 378                 if (degree3nodes > 0) {
 379                         return ExtractKuratowskis::none;
 380                 }
 381                 for (int i=0; i<5; ++i) {
 382                         forall_adj_edges(e,K5Nodes[i]) {
 383                                 if (edgenumber[e] > 0) { // not visited
 384                                         edgenumber[e] = -2; // visited
 385                                         v = e->opposite(K5Nodes[i]);
 386                                         // traverse nodedegree-2 path until degree-4 node found
 387                                         while (nodenumber[v] != 4) {
 388                                                 nodenumber[v] = -2; // visited
 389                                                 forall_adj_edges(ed,v) if (edgenumber[ed] > 0) break;
 390                                                 if (edgenumber[ed] <= 0) break;
 391                                                 edgenumber[ed] = -2; // visited
 392                                                 v = ed->opposite(v);
 393                                         }
 394                                         if (nodenumber[v] == 4) ++paths;
 395                                 }
 396                         }
 397                 }
 398                 if (paths==10) {
 399                         return ExtractKuratowskis::K5;
 400                 } else {
 401                         return ExtractKuratowskis::none;
 402                 }
 403         } else {
 404                 return ExtractKuratowskis::none;
 405         }
 406 }
 407
 408 // returns true, if kuratowski EdgeArray isn't already contained in output
 409 bool ExtractKuratowskis::isANewKuratowski(
 410                 //const Graph& g,
 411                 const EdgeArray<int>& test,
 412                 const SList<KuratowskiWrapper>& output)
 413 {
 414         SListConstIterator<KuratowskiWrapper> itW;
 415         SListConstIterator<edge> it;
 416         for (itW = output.begin(); itW.valid(); ++itW) {
 417                 bool differentEdgeFound = false;
 418                 for (it = (*itW).edgeList.begin(); it.valid(); ++it) {
 419                         if (!test[*it]) {
 420                                 differentEdgeFound = true;
 421                                 break;
 422                         }
 423                 }
 424                 if (!differentEdgeFound) {
 425                         cerr << "\nERROR: Kuratowski is already in list as subdivisiontype "
 426                                 << (*itW).subdivisionType << "\n";
 427                         return false;
 428                 }
 429         }
 430         return true;
 431 }
 432
 433 // returns true, if kuratowski edgelist isn't already contained in output
 434 bool ExtractKuratowskis::isANewKuratowski(
 435                 const Graph& g,
 436                 const SListPure<edge>& kuratowski,
 437                 const SList<KuratowskiWrapper>& output)
 438 {
 439         EdgeArray<int> test(g,0);
 440         SListConstIterator<edge> it;
 441         for (it = kuratowski.begin(); it.valid(); ++it) test[*it] = 1;
 442         return isANewKuratowski(/*g,*/test,output);
 443 }
 444
 445 // returns adjEntry of the edge between node high and that node
 446 // with the lowest DFI not less than the DFI of low
 447 inline adjEntry ExtractKuratowskis::adjToLowestNodeBelow(node high, int low) {
 448         adjEntry adj;
 449         int result = 0;
 450         int temp;
 451         adjEntry resultAdj = NULL;
 452         forall_adj(adj,high) {
 453                 temp = m_dfi[adj->twinNode()];
 454                 if (temp >= low && (result==0 || temp < result)) {
 455                         result = temp;
 456                         resultAdj = adj->twin();
 457                 }
 458         }
 459         if (result==0) {
 460                 return NULL;
 461         } else return resultAdj;
 462 }
 463
 464 // add DFS-path from node bottom to node top to edgelist
 465 // each virtual node has to be merged
 466 inline void ExtractKuratowskis::addDFSPath(
 467                                                 SListPure<edge>& list,
 468                                                 node bottom,
 469                                                 node top) {
 470         if (bottom == top) return;
 471         adjEntry adj = m_adjParent[bottom];
 472         list.pushBack(adj->theEdge());
 473         while (adj->theNode() != top) {
 474                 adj = m_adjParent[adj->theNode()];
 475                 list.pushBack(adj->theEdge());
 476         }
 477 }
 478
 479 // the same as above but list is reversed
 480 inline void ExtractKuratowskis::addDFSPathReverse(
 481                                                 SListPure<edge>& list,
 482                                                 node bottom,
 483                                                 node top) {
 484         if (bottom == top) return;
 485         adjEntry adj = m_adjParent[bottom];
 486         list.pushFront(adj->theEdge());
 487         while (adj->theNode() != top) {
 488                 adj = m_adjParent[adj->theNode()];
 489                 list.pushFront(adj->theEdge());
 490         }
 491 }
 492
 493 // separate list1 from edges already contained in list2
 494 inline void ExtractKuratowskis::truncateEdgelist(
 495                                         SListPure<edge>& list1,
 496                                         const SListPure<edge>& list2)
 497 {
 498         SListConstIterator<edge> it = list2.begin();
 499         while (!list1.empty() && it.valid() && list1.front() == *it) {
 500                 list1.popFront();
 501                 ++it;
 502         }
 503 }
 504
 505 // extracts a type A minor.
 506 // each virtual node has to be merged into its real counterpart.
 507 void ExtractKuratowskis::extractMinorA(
 508                                 SList<KuratowskiWrapper>& output,
 509                                 const KuratowskiStructure& k,
 510                                 //const WInfo& info,
 511                                 const SListPure<edge>& pathX,
 512                                 const node endnodeX,
 513                                 const SListPure<edge>& pathY,
 514                                 const node endnodeY,
 515                                 const SListPure<edge>& pathW)
 516 {
 517         OGDF_ASSERT(k.RReal != k.V);
 518         // check, if we have found enough subdivisions
 519         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
 520                                 output.size() >= m_embeddingGrade)
 521                 return;
 522
 523         KuratowskiWrapper A;
 524
 525         // add all external face edges
 526         addExternalFacePath(A.edgeList,k.externalFacePath);
 527
 528         // add the path from v to u, this is only possible after computation of pathX and pathY
 529         if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
 530                 addDFSPath(A.edgeList,k.V,endnodeX);
 531         } else addDFSPath(A.edgeList,k.V,endnodeY);
 532
 533         // copy other paths to subdivision
 534         SListConstIterator<edge> it;
 535         for(it = pathX.begin(); it.valid(); ++it) A.edgeList.pushBack(*it);
 536         for(it = pathY.begin(); it.valid(); ++it) A.edgeList.pushBack(*it);
 537         for(it = pathW.begin(); it.valid(); ++it) A.edgeList.pushBack(*it);
 538         OGDF_ASSERT(whichKuratowski(m_g,m_dfi,A.edgeList) == ExtractKuratowskis::K33);
 539         OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,A.edgeList,output));
 540         A.subdivisionType = KuratowskiWrapper::A;
 541         A.V = k.V;
 542         output.pushBack(A);
 543 }
 544
 545 // extracts a type B minor.
 546 // each virtual node has to be merged into its real counterpart.
 547 void ExtractKuratowskis::extractMinorB(
 548                                 SList<KuratowskiWrapper>& output,
 549                                 //NodeArray<int>& nodeflags,
 550                                 //const int nodemarker,
 551                                 const KuratowskiStructure& k,
 552                                 const WInfo& info,
 553                                 const SListPure<edge>& pathX,
 554                                 const node endnodeX,
 555                                 const SListPure<edge>& pathY,
 556                                 const node endnodeY,
 557                                 const SListPure<edge>& pathW)
 558 {
 559         // check, if we have found enough subdivisions
 560         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
 561                                 output.size() >= m_embeddingGrade)
 562                 return;
 563
 564         KuratowskiWrapper B;
 565
 566         // find ExternE-struct suitable for wNode
 567         SListIterator<ExternE> itExternW;
 568         for (itExternW = info.externEStart; (*itExternW).theNode != info.w; ++itExternW)
 569                 ;
 570         OGDF_ASSERT(itExternW.valid() && (*itExternW).theNode == info.w);
 571         ExternE& externE(*itExternW);
 572         OGDF_ASSERT(externE.theNode == pathW.front()->source() ||
 573                                 externE.theNode == pathW.front()->target());
 574
 575         // check, if a external path sharing the first pathW-edge exists
 576         SListIterator<int> itStart;
 577         SListIterator<node> itEnd = externE.endnodes.begin();
 578         SListIterator<SListPure<edge> > itPath = externE.externalPaths.begin();
 579         SListIterator<edge> itEdge;
 580         for (itStart = externE.startnodes.begin(); itStart.valid(); ++itStart) {
 581                 if (*itStart != m_dfi[pathW.front()->opposite(info.w)]) {
 582                         ++itEnd;
 583                         ++itPath;
 584                         continue;
 585                 }
 586
 587                 // if path was preprocessed, copy path
 588                 node endnodeWExtern = *itEnd;
 589                 if (!(*itPath).empty()) {
 590                         B.edgeList = (*itPath);
 591                 } else {
 592                         // else traverse external Path starting with z. forbid edges starting at W,
 593                         // that are different from the edge w->z.
 594                         adjEntry adj = adjToLowestNodeBelow(endnodeWExtern,*itStart);
 595                         B.edgeList.pushFront(adj->theEdge());
 596                         addDFSPathReverse(B.edgeList,adj->theNode(),info.w);
 597
 598                         // copy list
 599                         *itPath = B.edgeList;
 600                 }
 601
 602                 // truncate pathZ from edges already contained in pathW
 603                 OGDF_ASSERT(B.edgeList.front() == pathW.front());
 604                 truncateEdgelist(B.edgeList,pathW);
 605
 606                 // add external face edges
 607                 addExternalFacePath(B.edgeList,k.externalFacePath);
 608
 609                 // compute dfi-minimum and maximum of all three paths to node Ancestor u
 610                 // add the dfs-path from minimum to maximum
 611                 node min,max;
 612                 if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
 613                         min = endnodeX;
 614                         max = endnodeY;
 615                 } else {
 616                         min = endnodeY;
 617                         max = endnodeX;
 618                 }
 619                 if (m_dfi[endnodeWExtern] < m_dfi[min]) {
 620                         min = endnodeWExtern;
 621                 } else {
 622                         if (m_dfi[endnodeWExtern] > m_dfi[max]) max = endnodeWExtern;
 623                 }
 624                 addDFSPath(B.edgeList,max,min);
 625
 626                 // copy other paths to subdivision
 627                 SListConstIterator<edge> it;
 628                 for (it = pathX.begin(); it.valid(); ++it) B.edgeList.pushBack(*it);
 629                 for (it = pathY.begin(); it.valid(); ++it) B.edgeList.pushBack(*it);
 630                 for (it = pathW.begin(); it.valid(); ++it) B.edgeList.pushBack(*it);
 631                 OGDF_ASSERT(whichKuratowski(m_g,m_dfi,B.edgeList) == ExtractKuratowskis::K33);
 632                 OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,B.edgeList,output));
 633                 if (info.minorType & WInfo::A) {
 634                         B.subdivisionType = KuratowskiWrapper::AB;
 635                 } else B.subdivisionType = KuratowskiWrapper::B;
 636                 B.V = k.V;
 637                 output.pushBack(B);
 638                 B.edgeList.clear();
 639
 640 //              break;
 641         }
 642 }
 643
 644 // extracts a type B minor.
 645 // each virtual node has to be merged into its real counterpart.
 646 void ExtractKuratowskis::extractMinorBBundles(
 647                                 SList<KuratowskiWrapper>& output,
 648                                 NodeArray<int>& nodeflags,
 649                                 const int nodemarker,
 650                                 const KuratowskiStructure& k,
 651                                 EdgeArray<int>& flags,
 652                                 const WInfo& info,
 653                                 const SListPure<edge>& pathX,
 654                                 const node endnodeX,
 655                                 const SListPure<edge>& pathY,
 656                                 const node endnodeY,
 657                                 const SListPure<edge>& pathW)
 658 {
 659         KuratowskiWrapper B;
 660         OGDF_ASSERT(flags[pathW.back()] & DynamicBacktrack::pertinentPath);
 661
 662         // check, if pertinent pathW (w->u) traverses node z
 663         if (!(flags[pathW.back()] & DynamicBacktrack::externalPath)) return;
 664
 665         // mark single pathW in flags, so that pathW and the externalPath
 666         // don't interfere later
 667         SListConstIterator<edge> itE;
 668         for (itE = pathW.begin(); itE.valid(); ++itE) {
 669                 flags[*itE] |= DynamicBacktrack::singlePath;
 670                 nodeflags[(*itE)->source()] = nodemarker;
 671                 nodeflags[(*itE)->target()] = nodemarker;
 672         }
 673
 674         // traverse all possible external Paths out of z. forbid edges starting at W,
 675         // that are different from the edge w->z
 676         node endnodeWExtern;
 677         DynamicBacktrack backtrackExtern(m_g,m_dfi,flags);
 678         backtrackExtern.init(info.w,k.V,true,DynamicBacktrack::externalPath,
 679                                                 DynamicBacktrack::externalPath,pathW.back(),NULL);
 680         while (backtrackExtern.addNextPathExclude(B.edgeList,endnodeWExtern,nodeflags,
 681                                                                                 nodemarker,DynamicBacktrack::singlePath)) {
 682                 // check, if we have found enough subdivisions
 683                 if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
 684                                         output.size() >= m_embeddingGrade)
 685                         break;
 686
 687                 // add external face edges
 688                 addExternalFacePath(B.edgeList,k.externalFacePath);
 689
 690                 // compute dfi-minimum and maximum of all three paths to node Ancestor u
 691                 // add the dfs-path from minimum to maximum
 692                 node min,max;
 693                 if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
 694                         min = endnodeX;
 695                         max = endnodeY;
 696                 } else {
 697                         min = endnodeY;
 698                         max = endnodeX;
 699                 }
 700                 if (m_dfi[endnodeWExtern] < m_dfi[min]) min = endnodeWExtern;
 701                         else if (m_dfi[endnodeWExtern] > m_dfi[max]) max = endnodeWExtern;
 702                 addDFSPath(B.edgeList,max,min);
 703
 704                 // copy other paths to subdivision
 705                 SListConstIterator<edge> it;
 706                 for (it = pathX.begin(); it.valid(); ++it) B.edgeList.pushBack(*it);
 707                 for (it = pathY.begin(); it.valid(); ++it) B.edgeList.pushBack(*it);
 708                 for (it = pathW.begin(); it.valid(); ++it) B.edgeList.pushBack(*it);
 709                 OGDF_ASSERT(whichKuratowski(m_g,m_dfi,B.edgeList) == ExtractKuratowskis::K33);
 710                 OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,B.edgeList,output));
 711                 if (info.minorType & WInfo::A) {
 712                         B.subdivisionType = KuratowskiWrapper::AB;
 713                 } else B.subdivisionType = KuratowskiWrapper::B;
 714                 B.V = k.V;
 715                 output.pushBack(B);
 716                 B.edgeList.clear();
 717         }
 718
 719         // delete marked single pathW
 720         for (itE = pathW.begin(); itE.valid(); ++itE) {
 721                 flags[*itE] &= ~DynamicBacktrack::singlePath;
 722         }
 723 }
 724
 725 // extracts a type C minor.
 726 // each virtual node has to be merged into its real counterpart.
 727 void ExtractKuratowskis::extractMinorC(
 728                                 SList<KuratowskiWrapper>& output,
 729                                 const KuratowskiStructure& k,
 730                                 const WInfo& info,
 731                                 const SListPure<edge>& pathX,
 732                                 const node endnodeX,
 733                                 const SListPure<edge>& pathY,
 734                                 const node endnodeY,
 735                                 const SListPure<edge>& pathW)
 736 {
 737         // check, if we have found enough subdivisions
 738         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
 739                                 output.size() >= m_embeddingGrade)
 740                 return;
 741
 742         KuratowskiWrapper C;
 743         SListPure<edge> tempC;
 744
 745         // the case, that px is above stopX
 746         OGDF_ASSERT(info.pxAboveStopX || info.pyAboveStopY);
 747         SListConstIterator<adjEntry> itE;
 748
 749         // add the path from v to u, this is only possible after computation
 750         // of pathX and pathY
 751         if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
 752                 addDFSPath(tempC,k.V,endnodeX);
 753         } else addDFSPath(tempC,k.V,endnodeY);
 754
 755         // add highestFacePath of wNode
 756         OGDF_ASSERT(info.highestXYPath->size() >= 2);
 757         for (itE=info.highestXYPath->begin().succ(); itE.valid(); ++itE) {
 758                 tempC.pushBack((*itE)->theEdge());
 759         }
 760
 761         // the case, that px is above stopX
 762         if (info.pxAboveStopX) {
 763                 C.edgeList = tempC;
 764
 765                 // add the external face path edges except the path from py/stopY to R
 766                 node end;
 767                 if (info.pyAboveStopY) {
 768                         end = info.highestXYPath->back()->theNode();
 769                 } else end = k.stopY;
 770                 for (itE=k.externalFacePath.begin(); itE.valid(); ++itE) {
 771                         C.edgeList.pushBack((*itE)->theEdge());
 772                         if ((*itE)->theNode() == end) break;
 773                 }
 774
 775                 // copy other paths to subdivision
 776                 SListConstIterator<edge> it;
 777                 for (it = pathX.begin(); it.valid(); ++it) C.edgeList.pushBack(*it);
 778                 for (it = pathY.begin(); it.valid(); ++it) C.edgeList.pushBack(*it);
 779                 for (it = pathW.begin(); it.valid(); ++it) C.edgeList.pushBack(*it);
 780                 OGDF_ASSERT(whichKuratowski(m_g,m_dfi,C.edgeList) == ExtractKuratowskis::K33);
 781                 OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,C.edgeList,output));
 782                 if (info.minorType & WInfo::A) {
 783                         C.subdivisionType = KuratowskiWrapper::AC;
 784                 } else C.subdivisionType = KuratowskiWrapper::C;
 785                 C.V = k.V;
 786                 output.pushBack(C);
 787                 C.edgeList.clear();
 788         }
 789
 790         // the case, that py is above stopY
 791         if (info.pyAboveStopY) {
 792                 // check, if we have found enough subdivisions
 793                 if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
 794                                         output.size() >= m_embeddingGrade)
 795                         return;
 796
 797                 C.edgeList = tempC;
 798
 799                 // add the external face path edges except the path from px/stopX to R
 800                 node start;
 801                 if (info.pxAboveStopX) {
 802                         start = info.highestXYPath->front()->theNode();
 803                 } else start = k.stopX;
 804                 bool after = false;
 805                 for (itE=k.externalFacePath.begin(); itE.valid(); ++itE) {
 806                         if (after) {
 807                                 C.edgeList.pushBack((*itE)->theEdge());
 808                         } else if ((*itE)->theNode() == start) after = true;
 809                 }
 810
 811                 // copy other paths to subdivision
 812                 SListConstIterator<edge> it;
 813                 for (it = pathX.begin(); it.valid(); ++it) C.edgeList.pushBack(*it);
 814                 for (it = pathY.begin(); it.valid(); ++it) C.edgeList.pushBack(*it);
 815                 for (it = pathW.begin(); it.valid(); ++it) C.edgeList.pushBack(*it);
 816                 OGDF_ASSERT(whichKuratowski(m_g,m_dfi,C.edgeList) == ExtractKuratowskis::K33);
 817                 OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,C.edgeList,output));
 818                 if (info.minorType & WInfo::A) {
 819                         C.subdivisionType = KuratowskiWrapper::AC;
 820                 } else C.subdivisionType = KuratowskiWrapper::C;
 821                 C.V = k.V;
 822                 output.pushBack(C);
 823         }
 824 }
 825
 826 // extracts a type D minor.
 827 // each virtual node has to be merged into its real counterpart.
 828 void ExtractKuratowskis::extractMinorD(
 829                                 SList<KuratowskiWrapper>& output,
 830                                 const KuratowskiStructure& k,
 831                                 const WInfo& info,
 832                                 const SListPure<edge>& pathX,
 833                                 const node endnodeX,
 834                                 const SListPure<edge>& pathY,
 835                                 const node endnodeY,
 836                                 const SListPure<edge>& pathW)
 837 {
 838         // check, if we have found enough subdivisions
 839         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
 840                                 output.size() >= m_embeddingGrade)
 841                 return;
 842
 843         KuratowskiWrapper D;
 844
 845         // add the path from v to u, this is only possible after computation of pathX and pathY
 846         if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
 847                 addDFSPath(D.edgeList,k.V,endnodeX);
 848         } else addDFSPath(D.edgeList,k.V,endnodeY);
 849
 850         // add the external face path edges except the part from R to the nearest of
 851         // the two nodes stopX and px resp. the part to stopY/py
 852         node start;
 853         if (info.pxAboveStopX) {
 854                 start = info.highestXYPath->front()->theNode();
 855         } else start = k.stopX;
 856         node end;
 857         if (info.pyAboveStopY) {
 858                 end = info.highestXYPath->back()->theNode();
 859         } else end = k.stopY;
 860         node temp;
 861         SListConstIterator<adjEntry> itE;
 862         bool between = false;
 863         for (itE=k.externalFacePath.begin(); itE.valid(); ++itE) {
 864                 temp = (*itE)->theNode();
 865                 if (between) D.edgeList.pushBack((*itE)->theEdge());
 866                 if (temp == start) {
 867                         between = true;
 868                 } else if (temp == end) between = false;
 869         }
 870
 871         // add highestFacePath of wNode
 872         OGDF_ASSERT(info.highestXYPath->size() >= 2);
 873         for (itE=info.highestXYPath->begin().succ(); itE.valid(); ++itE) {
 874                 D.edgeList.pushBack((*itE)->theEdge());
 875         }
 876
 877         // add path from first zNode to R
 878         OGDF_ASSERT(!info.zPath->empty());
 879         for (itE=info.zPath->begin().succ(); itE.valid(); ++itE) {
 880                 D.edgeList.pushBack((*itE)->theEdge());
 881         }
 882
 883         // copy other paths to subdivision
 884         SListConstIterator<edge> it;
 885         for (it = pathX.begin(); it.valid(); ++it) D.edgeList.pushBack(*it);
 886         for (it = pathY.begin(); it.valid(); ++it) D.edgeList.pushBack(*it);
 887         for (it = pathW.begin(); it.valid(); ++it) D.edgeList.pushBack(*it);
 888         OGDF_ASSERT(whichKuratowski(m_g,m_dfi,D.edgeList) == ExtractKuratowskis::K33);
 889         OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,D.edgeList,output));
 890                 if (info.minorType & WInfo::A) {
 891                         D.subdivisionType = KuratowskiWrapper::AD;
 892                 } else D.subdivisionType = KuratowskiWrapper::D;
 893         D.V = k.V;
 894         output.pushBack(D);
 895 }
 896
 897 // extracts a subtype E1 minor.
 898 // each virtual node has to be merged into its real counterpart.
 899 void ExtractKuratowskis::extractMinorE1(
 900                                 SList<KuratowskiWrapper>& output,
 901                                 int before,
 902                                 //const node z,
 903                                 const node px,
 904                                 const node py,
 905                                 const KuratowskiStructure& k,
 906                                 const WInfo& info,
 907                                 const SListPure<edge>& pathX,
 908                                 const node endnodeX,
 909                                 const SListPure<edge>& pathY,
 910                                 const node endnodeY,
 911                                 const SListPure<edge>& pathW,
 912                                 const SListPure<edge>& pathZ,
 913                                 const node endnodeZ)
 914 {
 915         // check, if we have found enough subdivisions
 916         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
 917                                 output.size() >= m_embeddingGrade)
 918                 return;
 919
 920         OGDF_ASSERT(before == -1 || before == 1);
 921         KuratowskiWrapper E1;
 922         SListConstIterator<edge> itE;
 923
 924         // add highestFacePath of wNode
 925         SListConstIterator<adjEntry> it;
 926         for (it=info.highestXYPath->begin().succ(); it.valid(); ++it)
 927                 E1.edgeList.pushBack((*it)->theEdge());
 928
 929         if (before == -1) {
 930                 // z is before w on external face path
 931
 932                 // add pathY
 933                 for (itE = pathY.begin(); itE.valid(); ++itE) E1.edgeList.pushBack(*itE);
 934
 935                 // add the path from v to u, this is only possible after computation of
 936                 // pathX and pathY
 937                 if (m_dfi[endnodeZ] < m_dfi[endnodeY]) {
 938                         addDFSPath(E1.edgeList,k.V,endnodeZ);
 939                 } else addDFSPath(E1.edgeList,k.V,endnodeY);
 940
 941                 // add the external face path edges except the part from stopY/py to R
 942                 node stop;
 943                 if (info.pyAboveStopY) {
 944                         stop = py;
 945                 } else stop = k.stopY;
 946                 for (it=k.externalFacePath.begin(); it.valid(); ++it) {
 947                         E1.edgeList.pushBack((*it)->theEdge());
 948                         if ((*it)->theNode() == stop) break;
 949                 }
 950         } else {
 951                 // z is after w on external face path
 952
 953                 // if minor A occurs, add the dfs-path from node RReal to V, that isn't anymore
 954                 // involved because of removing pathY
 955                 if (k.RReal != k.V) addDFSPath(E1.edgeList,k.RReal,k.V);
 956
 957                 // add pathX
 958                 for (itE = pathX.begin(); itE.valid(); ++itE) E1.edgeList.pushBack(*itE);
 959
 960                 // add the path from v to u, this is only possible after computation of
 961                 // pathX and pathY
 962                 if (m_dfi[endnodeZ] < m_dfi[endnodeX]) {
 963                         addDFSPath(E1.edgeList,k.V,endnodeZ);
 964                 } else addDFSPath(E1.edgeList,k.V,endnodeX);
 965
 966                 // add the external face path edges except the part from stopX/px to R
 967                 node start;
 968                 if (info.pxAboveStopX) {
 969                         start = px;
 970                 } else start = k.stopX;
 971                 bool after = false;
 972                 for (it=k.externalFacePath.begin(); it.valid(); ++it) {
 973                         if (after) {
 974                                 E1.edgeList.pushBack((*it)->theEdge());
 975                         } else if ((*it)->theNode() == start) after = true;
 976                 }
 977         }
 978
 979         // add pathW and pathZ
 980         for (itE = pathW.begin(); itE.valid(); ++itE) E1.edgeList.pushBack(*itE);
 981         for (itE = pathZ.begin(); itE.valid(); ++itE) E1.edgeList.pushBack(*itE);
 982         // push this subdivision to kuratowskilist
 983         OGDF_ASSERT(whichKuratowski(m_g,m_dfi,E1.edgeList) == ExtractKuratowskis::K33);
 984         OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,E1.edgeList,output));
 985         if (info.minorType & WInfo::A) {
 986                 E1.subdivisionType = KuratowskiWrapper::AE1;
 987         } else E1.subdivisionType = KuratowskiWrapper::E1;
 988         E1.V = k.V;
 989         output.pushBack(E1);
 990 }
 991
 992 // extracts a subtype E2 minor.
 993 // each virtual node has to be merged into its real counterpart.
 994 void ExtractKuratowskis::extractMinorE2(
 995                                 SList<KuratowskiWrapper>& output,
 996                                 /*int before,
 997                                 const node z,
 998                                 const node px,
 999                                 const node py,*/
1000                                 const KuratowskiStructure& k,
1001                                 const WInfo& info,
1002                                 const SListPure<edge>& pathX,
1003                                 const node endnodeX,
1004                                 const SListPure<edge>& pathY,
1005                                 const node endnodeY,
1006                                 //const SListPure<edge>& pathW,
1007                                 const SListPure<edge>& pathZ/*,
1008                                 const node endnodeZ*/
1009                                 )
1010 {
1011         OGDF_ASSERT(!m_avoidE2Minors);
1012
1013         // check, if we have found enough subdivisions
1014         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1015                                 output.size() >= m_embeddingGrade)
1016                 return;
1017
1018         KuratowskiWrapper E2;
1019
1020         // add the path from v to u
1021         if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
1022                 addDFSPath(E2.edgeList,k.V,endnodeX);
1023         } else addDFSPath(E2.edgeList,k.V,endnodeY);
1024
1025         // add the external face path edges
1026         SListConstIterator<adjEntry> it;
1027         for (it=k.externalFacePath.begin(); it.valid(); ++it)
1028                 E2.edgeList.pushBack((*it)->theEdge());
1029
1030         // add pathX, pathY and pathZ
1031         SListConstIterator<edge> itE;
1032         for (itE = pathX.begin(); itE.valid(); ++itE) E2.edgeList.pushBack(*itE);
1033         for (itE = pathY.begin(); itE.valid(); ++itE) E2.edgeList.pushBack(*itE);
1034         for (itE = pathZ.begin(); itE.valid(); ++itE) E2.edgeList.pushBack(*itE);
1035         // push this subdivision to kuratowskilist
1036         OGDF_ASSERT(whichKuratowski(m_g,m_dfi,E2.edgeList) == ExtractKuratowskis::K33);
1037         OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,E2.edgeList,output));
1038         if (info.minorType & WInfo::A) {
1039                 E2.subdivisionType = KuratowskiWrapper::AE2;
1040         } else E2.subdivisionType = KuratowskiWrapper::E2;
1041         E2.V = k.V;
1042         output.pushBack(E2);
1043 }
1044
1045 // extracts a subtype E3 minor.
1046 // each virtual node has to be merged into its real counterpart.
1047 void ExtractKuratowskis::extractMinorE3(
1048                                 SList<KuratowskiWrapper>& output,
1049                                 int before,
1050                                 const node z,
1051                                 const node px,
1052                                 const node py,
1053                                 const KuratowskiStructure& k,
1054                                 const WInfo& info,
1055                                 const SListPure<edge>& pathX,
1056                                 const node endnodeX,
1057                                 const SListPure<edge>& pathY,
1058                                 const node endnodeY,
1059                                 const SListPure<edge>& pathW,
1060                                 const SListPure<edge>& pathZ,
1061                                 const node endnodeZ)
1062 {
1063         // check, if we have found enough subdivisions
1064         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1065                                 output.size() >= m_embeddingGrade)
1066                 return;
1067
1068         KuratowskiWrapper E3;
1069         OGDF_ASSERT(endnodeX != endnodeY);
1070
1071         // add pathZ
1072         SListConstIterator<edge> itE;
1073         for (itE = pathZ.begin(); itE.valid(); ++itE) E3.edgeList.pushBack(*itE);
1074
1075         // add highestFacePath px <-> py
1076         SListConstIterator<adjEntry> it;
1077         for (it=info.highestXYPath->begin().succ(); it.valid(); ++it)
1078                 E3.edgeList.pushBack((*it)->theEdge());
1079
1080         // check, if endnodeX or endnodeY is descendant
1081         if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
1082                 OGDF_ASSERT(m_dfi[endnodeZ] < m_dfi[endnodeY]);
1083
1084                 // add the path from v to u
1085                 if (m_dfi[endnodeX] < m_dfi[endnodeZ]) {
1086                         addDFSPath(E3.edgeList,k.V,endnodeX);
1087                 } else addDFSPath(E3.edgeList,k.V,endnodeZ);
1088
1089                 // add the external face path edges except max(px,stopX)<->min(z,w) and v<->nearest(py,stopY)
1090                 node temp,start1,end1,start2;
1091                 if (info.pxAboveStopX) {
1092                         start1 = k.stopX;
1093                 } else start1 = px;
1094                 if (before<=0) {
1095                         end1 = z;
1096                 } else end1 = info.w;
1097                 if (info.pyAboveStopY) {
1098                         start2 = py;
1099                 } else start2 = k.stopY;
1100                 bool between = false;
1101                 for (it=k.externalFacePath.begin(); it.valid(); ++it) {
1102                         temp = (*it)->theNode();
1103                         if (!between) E3.edgeList.pushBack((*it)->theEdge());
1104                         if (temp == start1) between = true;
1105                                 else if (temp == start2) break;
1106                                 else if (temp == end1) between = false;
1107                 }
1108         } else {
1109                 OGDF_ASSERT(m_dfi[endnodeZ] < m_dfi[endnodeX]);
1110
1111                 // add the path from v to u
1112                 if (m_dfi[endnodeY] < m_dfi[endnodeZ]) {
1113                         addDFSPath(E3.edgeList,k.V,endnodeY);
1114                 } else addDFSPath(E3.edgeList,k.V,endnodeZ);
1115
1116                 // add the external face path edges except v<->min(px,stopX) and max(w,z)<->nearest(py,stopY)
1117                 node temp,end1,start2,end2;
1118                 if (info.pxAboveStopX) {
1119                         end1 = px;
1120                 } else end1 = k.stopX;
1121                 if (before>0) {
1122                         start2 = z;
1123                 } else start2 = info.w;
1124                 if (info.pyAboveStopY) {
1125                         end2 = k.stopY;
1126                 } else end2 = py;
1127                 bool between = true;
1128                 for (it=k.externalFacePath.begin(); it.valid(); ++it) {
1129                         temp = (*it)->theNode();
1130                         if (!between) E3.edgeList.pushBack((*it)->theEdge());
1131                         if (temp == end1) between = false;
1132                                 else if (temp == start2) between = true;
1133                                 else if (temp == end2) between = false;
1134                 }
1135         }
1136
1137         // add pathX, pathY and pathW
1138         for (itE = pathX.begin(); itE.valid(); ++itE) E3.edgeList.pushBack(*itE);
1139         for (itE = pathY.begin(); itE.valid(); ++itE) E3.edgeList.pushBack(*itE);
1140         for (itE = pathW.begin(); itE.valid(); ++itE) E3.edgeList.pushBack(*itE);
1141         // push this subdivision to kuratowskilist
1142         OGDF_ASSERT(whichKuratowski(m_g,m_dfi,E3.edgeList) == ExtractKuratowskis::K33);
1143         OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,E3.edgeList,output));
1144         if (info.minorType & WInfo::A) {
1145                 E3.subdivisionType = KuratowskiWrapper::AE3;
1146         } else E3.subdivisionType = KuratowskiWrapper::E3;
1147         E3.V = k.V;
1148         output.pushBack(E3);
1149 }
1150
1151 // extracts a subtype E4 minor.
1152 // each virtual node has to be merged into its real counterpart.
1153 void ExtractKuratowskis::extractMinorE4(
1154                                 SList<KuratowskiWrapper>& output,
1155                                 int before,
1156                                 const node z,
1157                                 const node px,
1158                                 const node py,
1159                                 const KuratowskiStructure& k,
1160                                 const WInfo& info,
1161                                 const SListPure<edge>& pathX,
1162                                 const node endnodeX,
1163                                 const SListPure<edge>& pathY,
1164                                 const node endnodeY,
1165                                 const SListPure<edge>& pathW,
1166                                 const SListPure<edge>& pathZ,
1167                                 const node endnodeZ)
1168 {
1169         // check, if we have found enough subdivisions
1170         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1171                                 output.size() >= m_embeddingGrade)
1172                 return;
1173
1174         KuratowskiWrapper E4;
1175         SListPure<edge> tempE4;
1176         OGDF_ASSERT((px != k.stopX && !info.pxAboveStopX) ||
1177                                 (py != k.stopY && !info.pyAboveStopY));
1178
1179         // add pathZ
1180         SListConstIterator<edge> itE;
1181         for (itE = pathZ.begin(); itE.valid(); ++itE) tempE4.pushBack(*itE);
1182
1183         // add highestFacePath px <-> py
1184         SListConstIterator<adjEntry> it;
1185         for (it = info.highestXYPath->begin().succ(); it.valid(); ++it)
1186                 tempE4.pushBack((*it)->theEdge());
1187
1188         // compute dfi-minimum and maximum of all three paths to node Ancestor u
1189         // add the dfs-path from minimum to maximum
1190         node min,max;
1191         if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
1192                 min = endnodeX;
1193                 max = endnodeY;
1194         } else {
1195                 min = endnodeY;
1196                 max = endnodeX;
1197         }
1198         if (m_dfi[endnodeZ] < m_dfi[min]) min = endnodeZ;
1199                 else if (m_dfi[endnodeZ] > m_dfi[max]) max = endnodeZ;
1200         addDFSPath(tempE4,max,min);
1201
1202         if (px != k.stopX && !info.pxAboveStopX) {
1203                 E4.edgeList = tempE4;
1204
1205                 // add the external face path edges except max(w,z)<->min(py,stopY)
1206                 node temp,start,end;
1207                 if (before<=0) {
1208                         start = info.w;
1209                 } else start = z;
1210                 if (info.pyAboveStopY) {
1211                         end = k.stopY;
1212                 } else end = py;
1213                 bool between = false;
1214                 for (it=k.externalFacePath.begin(); it.valid(); ++it) {
1215                         temp = (*it)->theNode();
1216                         if (!between) E4.edgeList.pushBack((*it)->theEdge());
1217                         if (temp == start) between = true;
1218                                 else if (temp == end) between = false;
1219                 }
1220
1221                 // add pathX, pathY and pathW
1222                 for (itE = pathX.begin(); itE.valid(); ++itE) E4.edgeList.pushBack(*itE);
1223                 for (itE = pathY.begin(); itE.valid(); ++itE) E4.edgeList.pushBack(*itE);
1224                 for (itE = pathW.begin(); itE.valid(); ++itE) E4.edgeList.pushBack(*itE);
1225                 // push this subdivision to kuratowski-list
1226                 OGDF_ASSERT(whichKuratowski(m_g,m_dfi,E4.edgeList) == ExtractKuratowskis::K33);
1227                 OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,E4.edgeList,output));
1228                 if (info.minorType & WInfo::A) {
1229                         E4.subdivisionType = KuratowskiWrapper::AE4;
1230                 } else E4.subdivisionType = KuratowskiWrapper::E4;
1231                 E4.V = k.V;
1232                 output.pushBack(E4);
1233         }
1234
1235         if (py != k.stopY && !info.pyAboveStopY) {
1236                 // check, if we have found enough subdivisions
1237                 if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1238                                         output.size() >= m_embeddingGrade)
1239                         return;
1240
1241                 E4.edgeList = tempE4;
1242
1243                 // add the external face path edges except max(px,stopX)<->min(w,z)
1244                 node temp,start,end;
1245                 if (info.pxAboveStopX) {
1246                         start = k.stopX;
1247                 } else start = px;
1248                 if (before <= 0) {
1249                         end = z;
1250                 } else end = info.w;
1251
1252                 bool between = false;
1253                 for (it=k.externalFacePath.begin(); it.valid(); ++it) {
1254                         temp = (*it)->theNode();
1255                         if (!between) E4.edgeList.pushBack((*it)->theEdge());
1256                         if (temp == start) between = true;
1257                                 else if (temp == end) between = false;
1258                 }
1259
1260                 // add pathX, pathY and pathW
1261                 for (itE = pathX.begin(); itE.valid(); ++itE) E4.edgeList.pushBack(*itE);
1262                 for (itE = pathY.begin(); itE.valid(); ++itE) E4.edgeList.pushBack(*itE);
1263                 for (itE = pathW.begin(); itE.valid(); ++itE) E4.edgeList.pushBack(*itE);
1264                 // push this subdivision to kuratowski-list
1265                 OGDF_ASSERT(whichKuratowski(m_g,m_dfi,E4.edgeList) == ExtractKuratowskis::K33);
1266                 OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,E4.edgeList,output));
1267                 if (info.minorType & WInfo::A) {
1268                         E4.subdivisionType = KuratowskiWrapper::AE4;
1269                 } else E4.subdivisionType = KuratowskiWrapper::E4;
1270                 E4.V = k.V;
1271                 output.pushBack(E4);
1272         }
1273 }
1274
1275 // extracts a subtype E5 minor (the only minortype which represents a K5).
1276 // each virtual node has to be merged into its real counterpart.
1277 void ExtractKuratowskis::extractMinorE5(
1278                                 SList<KuratowskiWrapper>& output,
1279                                 /*int before,
1280                                 const node z,
1281                                 const node px,
1282                                 const node py,*/
1283                                 const KuratowskiStructure& k,
1284                                 const WInfo& info,
1285                                 const SListPure<edge>& pathX,
1286                                 const node endnodeX,
1287                                 const SListPure<edge>& pathY,
1288                                 const node endnodeY,
1289                                 const SListPure<edge>& pathW,
1290                                 const SListPure<edge>& pathZ,
1291                                 const node endnodeZ)
1292 {
1293         // check, if we have found enough subdivisions
1294         if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1295                                 output.size() >= m_embeddingGrade)
1296                 return;
1297
1298         KuratowskiWrapper E5;
1299         //OGDF_ASSERT(px==k.stopX && py==k.stopY && z==info.w && k.V == k.RReal);
1300         OGDF_ASSERT((endnodeX == endnodeY && m_dfi[endnodeZ] <= m_dfi[endnodeX]) ||
1301                                 (endnodeX == endnodeZ && m_dfi[endnodeY] <= m_dfi[endnodeX]) ||
1302                                 (endnodeY == endnodeZ && m_dfi[endnodeX] <= m_dfi[endnodeY]));
1303
1304         // compute dfi-minimum of all three paths to node Ancestor u and
1305         // add the dfs-path from minimum to V
1306         node min;
1307         if (m_dfi[endnodeX] < m_dfi[endnodeY]) {
1308                 min = endnodeX;
1309         } else if (m_dfi[endnodeY] < m_dfi[endnodeZ]) {
1310                 min = endnodeY;
1311         } else {
1312                 min = endnodeZ;
1313         }
1314         addDFSPath(E5.edgeList,k.V,min);
1315
1316         // add pathZ
1317         SListConstIterator<edge> itE;
1318         for (itE = pathZ.begin(); itE.valid(); ++itE) E5.edgeList.pushBack(*itE);
1319
1320         // add highestFacePath px <-> py
1321         SListConstIterator<adjEntry> it;
1322         for (it=info.highestXYPath->begin().succ(); it.valid(); ++it)
1323                 E5.edgeList.pushBack((*it)->theEdge());
1324
1325         // add the external face path edges
1326         for (it=k.externalFacePath.begin(); it.valid(); ++it) {
1327                 E5.edgeList.pushBack((*it)->theEdge());
1328         }
1329
1330         // add pathX, pathY and pathW
1331         for (itE = pathX.begin(); itE.valid(); ++itE) E5.edgeList.pushBack(*itE);
1332         for (itE = pathY.begin(); itE.valid(); ++itE) E5.edgeList.pushBack(*itE);
1333         for (itE = pathW.begin(); itE.valid(); ++itE) E5.edgeList.pushBack(*itE);
1334         // push this subdivision to kuratowski-list
1335         OGDF_ASSERT(whichKuratowski(m_g,m_dfi,E5.edgeList) == ExtractKuratowskis::K5);
1336         OGDF_ASSERT(!m_avoidE2Minors || isANewKuratowski(m_g,E5.edgeList,output));
1337         E5.subdivisionType = KuratowskiWrapper::E5;
1338         E5.V = k.V;
1339         output.pushBack(E5);
1340 }
1341
1342 // extracts a type E minor through splitting in different subtypes.
1343 // each virtual node has to be merged into its real counterpart.
1344 void ExtractKuratowskis::extractMinorE(
1345                                 SList<KuratowskiWrapper>& output,
1346                                 bool firstXPath,
1347                                 bool firstYPath,
1348                                 bool firstWPath,
1349                                 bool firstWOnHighestXY,
1350                                 const KuratowskiStructure& k,
1351                                 const WInfo& info,
1352                                 const SListPure<edge>& pathX,
1353                                 const node endnodeX,
1354                                 const SListPure<edge>& pathY,
1355                                 const node endnodeY,
1356                                 const SListPure<edge>& pathW)
1357 {
1358         // find external paths for each extern node z on the lower external face
1359         OGDF_ASSERT(info.externEStart.valid() && info.externEEnd.valid());
1360
1361         int before = -1; // -1= before, 0=equal, 1=after
1362         SListConstIterator<edge> itW;
1363         SListConstIterator<ExternE> it;
1364         node px = info.highestXYPath->front()->theNode();
1365         node py = info.highestXYPath->back()->theNode();
1366
1367         adjEntry temp;
1368         node z;
1369         SListPure<edge> pathZ;
1370         node endnodeZ;
1371         SListConstIterator<node> itZEndnode;
1372         SListConstIterator<int> itZStartnode;
1373         SListConstIterator<SListPure<edge> > itEPath;
1374
1375         // consider only the nodes between px and py
1376         for (it = info.externEStart; it.valid(); ++it) {
1377                 const ExternE& externE(*it);
1378                 z = externE.theNode;
1379
1380                 if (z == info.w) {
1381                         OGDF_ASSERT(z == pathW.front()->source() || z == pathW.front()->target());
1382                         // z = wNode
1383                         before = 0;
1384
1385                         itZStartnode = externE.startnodes.begin();
1386                         itEPath = externE.externalPaths.begin();
1387                         for (itZEndnode = externE.endnodes.begin(); itZEndnode.valid();
1388                                                                                         ++itZEndnode,++itZStartnode,++itEPath) {
1389                                 endnodeZ = *itZEndnode;
1390                                 SListPure<edge>& externalPath(const_cast<SListPure<edge>& >(*itEPath));
1391
1392                                 if (!externalPath.empty()) {
1393                                         // get preprocessed path
1394                                         pathZ = externalPath;
1395                                 } else {
1396                                         temp = adjToLowestNodeBelow(endnodeZ,*itZStartnode);
1397                                         pathZ.clear();
1398                                         pathZ.pushFront(temp->theEdge());
1399                                         addDFSPathReverse(pathZ,temp->theNode(),z);
1400
1401                                         // copy path
1402                                         externalPath = pathZ;
1403                                 }
1404
1405                                 // minortype E2 on z=wNode
1406                                 if (!m_avoidE2Minors && firstWPath && firstWOnHighestXY &&
1407                                                 m_dfi[endnodeZ] > m_dfi[endnodeX] &&
1408                                                 m_dfi[endnodeZ] > m_dfi[endnodeY]) {
1409                                                 extractMinorE2(output,/*before,z,px,py,*/k,info,pathX,
1410                                                                                 endnodeX,pathY,endnodeY,/*pathW,*/pathZ/*,endnodeZ*/);
1411                                 }
1412
1413                                 // truncate pathZ from edges already contained in pathW
1414                                 truncateEdgelist(pathZ,pathW);
1415
1416                                 // minortype E3 on z=wNode
1417                                 if (endnodeX != endnodeY &&
1418                                                 (m_dfi[endnodeX] > m_dfi[endnodeZ] || m_dfi[endnodeY] > m_dfi[endnodeZ])) {
1419                                         extractMinorE3(output,before,z,px,py,k,info,pathX,
1420                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1421                                 }
1422                                 // minortype E4 on z=wNode
1423                                 if ((px != k.stopX && !info.pxAboveStopX) ||
1424                                                 (py != k.stopY && !info.pyAboveStopY)) {
1425                                         extractMinorE4(output,before,z,px,py,k,info,pathX,
1426                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1427                                 }
1428
1429                                 // minortype E5 (K5)
1430                                 if (px == k.stopX && py == k.stopY && k.V == k.RReal &&
1431                                                 ((endnodeX == endnodeY && m_dfi[endnodeZ] <= m_dfi[endnodeX]) ||
1432                                                  (endnodeX == endnodeZ && m_dfi[endnodeY] <= m_dfi[endnodeX]) ||
1433                                                  (endnodeY == endnodeZ && m_dfi[endnodeX] <= m_dfi[endnodeY]))) {
1434                                         // check, if pathZ shares no edge with pathW
1435                                         if (*itZStartnode != m_dfi[pathW.front()->opposite(z)]) {
1436                                                 extractMinorE5(output,/*before,z,px,py,*/k,info,pathX,
1437                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1438                                         }
1439                                 }
1440                         }
1441                 } else {
1442                         // z != wNode, check position of node z
1443                         if (z == info.firstExternEAfterW) before = 1;
1444                         OGDF_ASSERT(before != 0);
1445                         OGDF_ASSERT(z != pathW.front()->source() && z != pathW.front()->target());
1446
1447                         itZStartnode = externE.startnodes.begin();
1448                         for (itZEndnode = externE.endnodes.begin(); itZEndnode.valid();
1449                                                                                                          ++itZEndnode,++itZStartnode) {
1450                                 endnodeZ = *itZEndnode;
1451
1452                                 temp = adjToLowestNodeBelow(endnodeZ,*itZStartnode);
1453                                 pathZ.clear();
1454                                 pathZ.pushFront(temp->theEdge());
1455                                 addDFSPathReverse(pathZ,temp->theNode(),z);
1456
1457                                 // split in minorE-subtypes
1458
1459                                 // minortype E1
1460                                 if ((before == -1 && firstXPath) || (before == 1 && firstYPath)) {
1461                                         extractMinorE1(output,before,/*z,*/px,py,k,info,pathX,
1462                                                                 endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1463                                 }
1464                                 // minortype E2
1465                                 if (!m_avoidE2Minors && firstWPath && firstWOnHighestXY
1466                                                                 && m_dfi[endnodeZ] > m_dfi[endnodeX]
1467                                                                 && m_dfi[endnodeZ] > m_dfi[endnodeY]) {
1468                                         extractMinorE2(output,/*before,z,px,py,*/k,info,pathX,
1469                                                                         endnodeX,pathY,endnodeY,/*pathW,*/pathZ/*,endnodeZ*/);
1470                                 }
1471                                 // minortype E3
1472                                 if (endnodeX != endnodeY && (m_dfi[endnodeX] > m_dfi[endnodeZ] ||
1473                                                                                         m_dfi[endnodeY] > m_dfi[endnodeZ])) {
1474                                         extractMinorE3(output,before,z,px,py,k,info,pathX,
1475                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1476                                 }
1477                                 // minortype E4
1478                                 if ((px != k.stopX && !info.pxAboveStopX) ||
1479                                                                         (py != k.stopY && !info.pyAboveStopY)) {
1480                                         extractMinorE4(output,before,z,px,py,k,info,pathX,
1481                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1482                                 }
1483                         }
1484                 }
1485
1486                 // check if last node was reached
1487                 if (it == info.externEEnd) break;
1488         }
1489 }
1490
1491 // extracts a type E minor through splitting in different subtypes.
1492 // each virtual node has to be merged into its real counterpart.
1493 void ExtractKuratowskis::extractMinorEBundles(
1494                                 SList<KuratowskiWrapper>& output,
1495                                 bool firstXPath,
1496                                 bool firstYPath,
1497                                 bool firstWPath,
1498                                 bool firstWOnHighestXY,
1499                                 NodeArray<int>& nodeflags,
1500                                 const int nodemarker,
1501                                 const KuratowskiStructure& k,
1502                                 EdgeArray<int>& flags,
1503                                 const WInfo& info,
1504                                 const SListPure<edge>& pathX,
1505                                 const node endnodeX,
1506                                 const SListPure<edge>& pathY,
1507                                 const node endnodeY,
1508                                 const SListPure<edge>& pathW)
1509 {
1510         // perform backtracking for each extern node z on the lower external face
1511         OGDF_ASSERT(info.externEStart.valid() && info.externEEnd.valid());
1512         SListPure<edge> pathZ;
1513         node z;
1514         node endnodeZ;
1515         int before = -1; // -1= before, 0=equal to wNode, 1=after
1516         SListConstIterator<edge> itW;
1517         SListConstIterator<ExternE> it;
1518         node px = info.highestXYPath->front()->theNode();
1519         node py = info.highestXYPath->back()->theNode();
1520         DynamicBacktrack backtrackZ(m_g,m_dfi,flags);
1521
1522         // mark all nodes of the single pathW in flags, so that pathW and
1523         // the externalPath don't interfere later
1524         for (itW = pathW.begin(); itW.valid(); ++itW) {
1525                 flags[*itW] |= DynamicBacktrack::singlePath;
1526                 nodeflags[(*itW)->source()] = nodemarker;
1527                 nodeflags[(*itW)->target()] = nodemarker;
1528         }
1529
1530         // consider only the nodes between px and py
1531         for (it = info.externEStart; it.valid(); ++it) {
1532                 z = (*it).theNode;
1533
1534                 if (z == info.w) {
1535                         OGDF_ASSERT(z == pathW.back()->source() || z == pathW.back()->target());
1536                         // z = wNode
1537                         before = 0;
1538
1539                         // minortype E2 on z=wNode
1540                         // on the first pathW: consider all pathsZ
1541                         if (!m_avoidE2Minors && firstWPath && firstWOnHighestXY) {
1542                                 backtrackZ.init(z,k.V,true,DynamicBacktrack::externalPath,
1543                                                                 DynamicBacktrack::externalPath,NULL,NULL);
1544                                 while (backtrackZ.addNextPath(pathZ,endnodeZ)) {
1545                                         if (m_dfi[endnodeZ] > m_dfi[endnodeX] &&
1546                                                 m_dfi[endnodeZ] > m_dfi[endnodeY]) {
1547                                                 extractMinorE2(output,/*before,z,px,py,*/k,info,pathX,
1548                                                                                 endnodeX,pathY,endnodeY/*,pathW*/,pathZ/*,endnodeZ*/);
1549                                         }
1550                                 }
1551                         }
1552
1553                         backtrackZ.init(z,k.V,true,DynamicBacktrack::externalPath,
1554                                                         DynamicBacktrack::externalPath,NULL,NULL);
1555                         while (backtrackZ.addNextPathExclude(pathZ,endnodeZ,
1556                                                 nodeflags,nodemarker,DynamicBacktrack::singlePath)) {
1557                                 // minortype E3 on z=wNode
1558                                 if (endnodeX != endnodeY && (m_dfi[endnodeX] > m_dfi[endnodeZ] ||
1559                                                                                         m_dfi[endnodeY] > m_dfi[endnodeZ])) {
1560                                         extractMinorE3(output,before,z,px,py,k,info,pathX,
1561                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1562                                 }
1563                                 // minortype E4 on z=wNode
1564                                 if ((px != k.stopX && !info.pxAboveStopX) ||
1565                                                 (py != k.stopY && !info.pyAboveStopY)) {
1566                                         extractMinorE4(output,before,z,px,py,k,info,pathX,
1567                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1568                                 }
1569                                 // minortype E5 (K5)
1570                                 if (px == k.stopX && py == k.stopY && k.V == k.RReal &&
1571                                                 ((endnodeX == endnodeY && m_dfi[endnodeZ] <= m_dfi[endnodeX]) ||
1572                                                  (endnodeX == endnodeZ && m_dfi[endnodeY] <= m_dfi[endnodeX]) ||
1573                                                  (endnodeY == endnodeZ && m_dfi[endnodeX] <= m_dfi[endnodeY]))) {
1574                                         // instead of slower code:
1575                                         //backtrackZ.init(z,k.V,true,DynamicBacktrack::externalPath,
1576                                         //                                      DynamicBacktrack::externalPath,NULL,pathW.back());
1577                                         //while (backtrackZ.addNextPathExclude(pathZ,endnodeZ,nodeflags,nodemarker,0)) {
1578                                         if (pathZ.back() != pathW.back() &&
1579                                                 (pathZ.back()->source() == z || pathZ.back()->target() == z)) {
1580                                                 extractMinorE5(output,/*before,z,px,py,*/k,info,pathX,
1581                                                                                 endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1582                                         }
1583                                 }
1584                         }
1585                 } else {
1586                         // z != wNode, check position of node z
1587                         if (z == info.firstExternEAfterW) before = 1;
1588                         OGDF_ASSERT(before != 0);
1589                         OGDF_ASSERT(z != pathW.back()->source() && z != pathW.back()->target());
1590
1591                         backtrackZ.init(z,k.V,true,DynamicBacktrack::externalPath,
1592                                                         DynamicBacktrack::externalPath,NULL,NULL);
1593                         while (backtrackZ.addNextPath(pathZ,endnodeZ)) {
1594                                 // split in minorE-subtypes
1595
1596                                 // minortype E1
1597                                 if ((before == -1 && firstXPath) || (before == 1 && firstYPath)) {
1598                                         extractMinorE1(output,before,/*z,*/px,py,k,info,pathX,
1599                                                                 endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1600                                 }
1601                                 // minortype E2
1602                                 if (!m_avoidE2Minors && firstWPath && firstWOnHighestXY
1603                                                                 && m_dfi[endnodeZ] > m_dfi[endnodeX]
1604                                                                 && m_dfi[endnodeZ] > m_dfi[endnodeY]) {
1605                                         extractMinorE2(output,/*before,z,px,py,*/k,info,pathX,
1606                                                                         endnodeX,pathY,endnodeY,/*pathW,*/pathZ/*,endnodeZ*/);
1607                                 }
1608                                 // minortype E3
1609                                 if (endnodeX != endnodeY && (m_dfi[endnodeX] > m_dfi[endnodeZ] ||
1610                                                                                         m_dfi[endnodeY] > m_dfi[endnodeZ])) {
1611                                         extractMinorE3(output,before,z,px,py,k,info,pathX,
1612                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1613                                 }
1614                                 // minortype E4
1615                                 if ((px != k.stopX && !info.pxAboveStopX) ||
1616                                                                         (py != k.stopY && !info.pyAboveStopY)) {
1617                                         extractMinorE4(output,before,z,px,py,k,info,pathX,
1618                                                                         endnodeX,pathY,endnodeY,pathW,pathZ,endnodeZ);
1619                                 }
1620                         }
1621                 }
1622
1623                 // check if last node was reached
1624                 if (it == info.externEEnd) break;
1625
1626                 // check, if we have found enough subdivisions
1627                 if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1628                                         output.size() >= m_embeddingGrade)
1629                         break;
1630         }
1631
1632         // delete marked single pathW
1633         for (itW = pathW.begin(); itW.valid(); ++itW) {
1634                 flags[*itW] &= ~DynamicBacktrack::singlePath;
1635         }
1636 }
1637
1638 // extracts all kuratowski subdivisions and adds them to output
1639 void ExtractKuratowskis::extract(
1640                                 const SListPure<KuratowskiStructure>& allKuratowskis,
1641                                 SList<KuratowskiWrapper>& output)
1642 {
1643         SListConstIterator<KuratowskiStructure> itAll;
1644         SListConstIterator<WInfo> itInfo;
1645         SListConstIterator<edge> itS;
1646         SListConstIterator<SListPure<edge> > itL;
1647
1648         SListPure<edge> pathX,pathY;
1649         node endnodeX,endnodeY;
1650         adjEntry temp;
1651
1652         SListConstIterator<node> itXEndnode;
1653         SListConstIterator<node> itYEndnode;
1654         SListConstIterator<int> itXStartnode;
1655         SListConstIterator<int> itYStartnode;
1656
1657         // consider all different kuratowski structures
1658         for (itAll=allKuratowskis.begin(); itAll.valid(); ++itAll) {
1659                 const KuratowskiStructure& k(*itAll);
1660
1661                 // compute all possible external paths of stopX and stopY (pathX,pathY)
1662                 bool firstXPath = true;
1663                 itXStartnode = k.stopXStartnodes.begin();
1664                 for (itXEndnode = k.stopXEndnodes.begin(); itXEndnode.valid(); ++itXEndnode) {
1665                         endnodeX = *itXEndnode;
1666                         pathX.clear();
1667                         temp = adjToLowestNodeBelow(endnodeX,*(itXStartnode++));
1668                         pathX.pushBack(temp->theEdge());
1669                         addDFSPath(pathX,temp->theNode(),k.stopX);
1670
1671                         bool firstYPath = true;
1672                         itYStartnode = k.stopYStartnodes.begin();
1673                         for (itYEndnode = k.stopYEndnodes.begin(); itYEndnode.valid(); ++itYEndnode) {
1674                                 endnodeY = *itYEndnode;
1675                                 pathY.clear();
1676                                 temp = adjToLowestNodeBelow(endnodeY,*(itYStartnode++));
1677                                 pathY.pushBack(temp->theEdge());
1678                                 addDFSPath(pathY,temp->theNode(),k.stopY);
1679
1680                                 // if minor A occurs, other minortypes are possible with adding
1681                                 // the dfs-path from node RReal to V
1682                                 if (k.RReal != k.V) addDFSPath(pathY,k.RReal,k.V);
1683
1684                                 // consider all possible wNodes
1685                                 SListPure<adjEntry>* oldHighestXYPath = NULL;
1686                                 for (itInfo = k.wNodes.begin(); itInfo.valid(); ++itInfo) {
1687                                         const WInfo& info(*itInfo);
1688
1689                                         // compute all possible internal paths of this wNode
1690                                         bool firstWPath = true; // avoid multiple identical subdivisions in E2
1691                                         for (itL = info.pertinentPaths.begin(); itL.valid(); ++itL) {
1692                                                 const SListPure<edge>& pathW(*itL);
1693                                                 OGDF_ASSERT(!pathX.empty() && !pathY.empty() && !pathW.empty());
1694
1695                                                 // extract minor A
1696                                                 if (info.minorType & WInfo::A)
1697                                                         extractMinorA(output,k,/*info,*/pathX,endnodeX,pathY,
1698                                                                                 endnodeY,pathW);
1699
1700                                                 // extract minor B
1701                                                 if (info.minorType & WInfo::B) {
1702                                                         ++m_nodeMarker;
1703                                                         extractMinorB(output,/*m_wasHere,++m_nodeMarker,*/k,
1704                                                                                 info,pathX,endnodeX,pathY,endnodeY,pathW);
1705                                                 }
1706
1707                                                 // extract minor C
1708                                                 if (info.minorType & WInfo::C)
1709                                                         extractMinorC(output,k,info,pathX,endnodeX,pathY,
1710                                                                                 endnodeY,pathW);
1711
1712                                                 // extract minor D
1713                                                 if (info.minorType & WInfo::D)
1714                                                         extractMinorD(output,k,info,pathX,endnodeX,pathY,
1715                                                                                 endnodeY,pathW);
1716
1717                                                 // extract minor E including all subtypes
1718                                                 if (info.minorType & WInfo::E) {
1719                                                         extractMinorE(output,firstXPath,firstYPath,firstWPath,
1720                                                                                 oldHighestXYPath!=info.highestXYPath,k,info,
1721                                                                                 pathX,endnodeX,pathY,endnodeY,pathW);
1722                                                 }
1723
1724                                                 if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1725                                                                         output.size() >= m_embeddingGrade)
1726                                                         return;
1727                                                 firstWPath = false;
1728                                                 // break;
1729                                         }
1730                                         oldHighestXYPath = info.highestXYPath;
1731                                 }
1732                                 firstYPath = false;
1733                                 // break;
1734                         }
1735                         firstXPath = false;
1736                         // break;
1737                 }
1738         }
1739 }
1740
1741 // extracts all kuratowski subdivisions and adds them to output
1742 void ExtractKuratowskis::extractBundles(
1743                                 const SListPure<KuratowskiStructure>& allKuratowskis,
1744                                 SList<KuratowskiWrapper>& output)
1745 {
1746         SListConstIterator<KuratowskiStructure> itAll;
1747         SListConstIterator<WInfo> itInfo;
1748         SListConstIterator<edge> itS;
1749
1750         SListPure<edge> pathX,pathY,pathW;
1751         node endnodeX,endnodeY;
1752
1753         EdgeArray<int> flags(m_g,0);
1754         DynamicBacktrack backtrackX(m_g,m_dfi,flags);
1755         DynamicBacktrack backtrackY(m_g,m_dfi,flags);
1756         DynamicBacktrack backtrackW(m_g,m_dfi,flags);
1757
1758         // consider all different kuratowski structures
1759         for (itAll=allKuratowskis.begin(); itAll.valid(); ++itAll) {
1760                 const KuratowskiStructure& k(*itAll);
1761
1762                 // create pertinent and external flags
1763                 for (itS = k.pertinentSubgraph.begin(); itS.valid(); ++itS)
1764                         flags[*itS] |= DynamicBacktrack::pertinentPath;
1765                 for (itS = k.externalSubgraph.begin(); itS.valid(); ++itS)
1766                         flags[*itS] |= DynamicBacktrack::externalPath;
1767
1768                 // compute all possible external paths of stopX and stopY (pathX,pathY)
1769                 bool firstXPath = true;
1770                 backtrackX.init(k.stopX,k.V,true,DynamicBacktrack::externalPath,
1771                                                 DynamicBacktrack::externalPath,NULL,NULL);
1772                 while (backtrackX.addNextPath(pathX,endnodeX)) {
1773                         bool firstYPath = true;
1774                         backtrackY.init(k.stopY,k.V,true,DynamicBacktrack::externalPath,
1775                                                         DynamicBacktrack::externalPath,NULL,NULL);
1776                         while (backtrackY.addNextPath(pathY,endnodeY)) {
1777
1778                                 // if minor A occurs, other minortypes are possible with adding
1779                                 // the dfs-path from node RReal to V
1780                                 if (k.RReal != k.V) addDFSPath(pathY,k.RReal,k.V);
1781
1782                                 // consider all possible wNodes
1783                                 SListPure<adjEntry>* oldHighestXYPath = NULL;
1784                                 for (itInfo = k.wNodes.begin(); itInfo.valid(); ++itInfo) {
1785                                         const WInfo& info(*itInfo);
1786
1787                                         // compute all possible internal paths of this wNode
1788                                         bool firstWPath = true; // avoid multiple identical subdivisions in E2
1789                                         backtrackW.init(info.w,k.V,false,DynamicBacktrack::pertinentPath,
1790                                                                         DynamicBacktrack::pertinentPath,NULL,NULL);
1791                                         node dummy;
1792                                         while (backtrackW.addNextPath(pathW,dummy)) {
1793                                                 OGDF_ASSERT(!pathX.empty() && !pathY.empty() && !pathW.empty());
1794
1795                                                 // extract minor A
1796                                                 if (info.minorType & WInfo::A)
1797                                                         extractMinorA(output,k,/*info,*/pathX,endnodeX,pathY,
1798                                                                                 endnodeY,pathW);
1799
1800                                                 // extract minor B
1801                                                 if (info.minorType & WInfo::B)
1802                                                         extractMinorBBundles(output,m_wasHere,++m_nodeMarker,k,flags,
1803                                                                                 info,pathX,endnodeX,pathY,endnodeY,pathW);
1804
1805                                                 // extract minor C
1806                                                 if (info.minorType & WInfo::C)
1807                                                         extractMinorC(output,k,info,pathX,endnodeX,pathY,
1808                                                                                 endnodeY,pathW);
1809
1810                                                 // extract minor D
1811                                                 if (info.minorType & WInfo::D)
1812                                                         extractMinorD(output,k,info,pathX,endnodeX,pathY,
1813                                                                                 endnodeY,pathW);
1814
1815                                                 // extract minor E including all subtypes
1816                                                 if (info.minorType & WInfo::E) {
1817                                                         extractMinorEBundles(output,firstXPath,firstYPath,firstWPath,
1818                                                                                 oldHighestXYPath!=info.highestXYPath,
1819                                                                                 m_wasHere,++m_nodeMarker,k,flags,info,
1820                                                                                 pathX,endnodeX,pathY,endnodeY,pathW);
1821                                                 }
1822
1823                                                 if (m_embeddingGrade > BoyerMyrvoldPlanar::doFindUnlimited &&
1824                                                                         output.size() >= m_embeddingGrade)
1825                                                         return;
1826                                                 firstWPath = false;
1827                                                 // break;
1828                                         }
1829                                         oldHighestXYPath = info.highestXYPath;
1830                                 }
1831                                 firstYPath = false;
1832                                 // break;
1833                         }
1834                         firstXPath = false;
1835                         // break;
1836                 }
1837
1838                 // delete pertinent and external flags
1839                 for (itS = k.pertinentSubgraph.begin(); itS.valid(); ++itS)
1840                         flags[*itS] = 0;
1841                 for (itS = k.externalSubgraph.begin(); itS.valid(); ++itS)
1842                         flags[*itS] = 0;
1843         }
1844 }
1845
1846
1847 }