ext/OGDF/src/planarity/EmbedPQTree.cpp

   1 /*
   2  * $Revision: 2599 $
   3  *
   4  * last checkin:
   5  *   $Author: chimani $
   6  *   $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of the class EmbedPQTree.
  11  *
  12  * Implements a PQTree with added features for the planar
  13  * embedding algorithm. Used by BoothLueker.
  14  *
  15  * \author Sebastian Leipert
  16  *
  17  * \par License:
  18  * This file is part of the Open Graph Drawing Framework (OGDF).
  19  *
  20  * \par
  21  * Copyright (C)<br>
  22  * See README.txt in the root directory of the OGDF installation for details.
  23  *
  24  * \par
  25  * This program is free software; you can redistribute it and/or
  26  * modify it under the terms of the GNU General Public License
  27  * Version 2 or 3 as published by the Free Software Foundation;
  28  * see the file LICENSE.txt included in the packaging of this file
  29  * for details.
  30  *
  31  * \par
  32  * This program is distributed in the hope that it will be useful,
  33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35  * GNU General Public License for more details.
  36  *
  37  * \par
  38  * You should have received a copy of the GNU General Public
  39  * License along with this program; if not, write to the Free
  40  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  41  * Boston, MA 02110-1301, USA.
  42  *
  43  * \see  http://www.gnu.org/copyleft/gpl.html
  44  ***************************************************************/
  45
  46
  47 #include <ogdf/internal/planarity/EmbedPQTree.h>
  48
  49 namespace ogdf{
  50
  51 // Overriding the function doDestruction (see basic.h)
  52 // Allows deallocation of lists of PQLeafKey<edge,IndInfo*,bool>
  53 // in constant time using OGDF memory management.
  54
  55
  56 typedef PQLeafKey<edge,IndInfo*,bool> *PtrPQLeafKeyEIB;
  57
  58 template<>
  59 inline bool doDestruction<PtrPQLeafKeyEIB>(const PtrPQLeafKeyEIB*) { return false;  }
  60
  61
  62
  63 // Replaces the pertinent subtree by a P-node with leaves as children
  64 // corresponding to the incoming edges of the node v. These edges
  65 // are to be specified by their keys stored in leafKeys.
  66 // The function returns the frontier of the pertinent subtree and
  67 // the direction indicators found within the pertinent leaves.
  68 // The direction indicators are returned in two list:
  69 // opposed: containing the keys of indicators pointing into reverse
  70 // frontier scanning direction (thus their corsponding list has to be
  71 // reversed.
  72 // nonOpposed: containing the keys of indicators pointing into
  73 // frontier scanning direction (thus their corsponding list do not need
  74 // reversed in the first place)
  75
  76 void EmbedPQTree::ReplaceRoot(
  77         SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys,
  78         SListPure<edge> &frontier,
  79         SListPure<node> &opposed,
  80         SListPure<node> &nonOpposed,
  81         node v)
  82 {
  83         SListPure<PQBasicKey<edge,IndInfo*,bool>*> nodeFrontier;
  84
  85         if (leafKeys.empty() && m_pertinentRoot == m_root)
  86         {
  87                 front(m_pertinentRoot,nodeFrontier);
  88                 m_pertinentRoot = 0;  // check for this emptyAllPertinentNodes
  89
  90         } else {
  91                 if (m_pertinentRoot->status() == PQNodeRoot::FULL)
  92                         ReplaceFullRoot(leafKeys,nodeFrontier,v);
  93                 else
  94                         ReplacePartialRoot(leafKeys,nodeFrontier,v);
  95         }
  96
  97         // Check the frontier and get the direction indicators.
  98         while (!nodeFrontier.empty())
  99         {
 100                 PQBasicKey<edge,IndInfo*,bool>* entry = nodeFrontier.popFrontRet();
 101                 if (entry->userStructKey()) // is a regular leaf
 102                         frontier.pushBack(entry->userStructKey());
 103
 104                 else if (entry->userStructInfo()) {
 105                         if (entry->userStructInfo()->changeDir)
 106                                 opposed.pushBack(entry->userStructInfo()->v);
 107                         else
 108                                 nonOpposed.pushBack(entry->userStructInfo()->v);
 109                 }
 110         }
 111 }
 112
 113
 114 // The function [[emptyAllPertinentNodes]] has to be called after a reduction
 115 // has been processed. This overloaded function first destroys all full nodes
 116 // by marking them as TO_BE_DELETED and then calling the base class function
 117 // [[emptyAllPertinentNodes]].
 118 void EmbedPQTree::emptyAllPertinentNodes()
 119 {
 120         ListIterator<PQNode<edge,IndInfo*,bool>*> it;
 121
 122         for (it = m_pertinentNodes->begin(); it.valid(); it++)
 123         {
 124                 PQNode<edge,IndInfo*,bool>* nodePtr = (*it);
 125                 if (nodePtr->status() == PQNodeRoot::FULL)
 126                         destroyNode(nodePtr);
 127         }
 128         if (m_pertinentRoot) // Node was kept in the tree. Do not free it.
 129                 m_pertinentRoot->status(PQNodeRoot::FULL);
 130
 131         PQTree<edge,IndInfo*,bool>::emptyAllPertinentNodes();
 132 }
 133
 134
 135
 136 void EmbedPQTree::clientDefinedEmptyNode(PQNode<edge,IndInfo*,bool>* nodePtr)
 137 {
 138         if (nodePtr->status() == PQNodeRoot::INDICATOR)
 139                 delete nodePtr;
 140         else
 141                 PQTree<edge,IndInfo*,bool>::clientDefinedEmptyNode(nodePtr);
 142 }
 143
 144
 145
 146 // Initializes a PQTree by a set of leaves that will korrespond to
 147 // the set of Keys stored in leafKeys.
 148 int EmbedPQTree::Initialize(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
 149 {
 150         SListIterator<PlanarLeafKey<IndInfo*>* > it;
 151
 152         SListPure<PQLeafKey<edge,IndInfo*,bool>*> castLeafKeys;
 153         for (it = leafKeys.begin(); it.valid(); ++it)
 154                 castLeafKeys.pushBack((PQLeafKey<edge,IndInfo*,bool>*) *it);
 155
 156         return PQTree<edge,IndInfo*,bool>::Initialize(castLeafKeys);
 157 }
 158
 159
 160 // Reduction reduced a set of leaves determined by their keys stored
 161 // in leafKeys. Integer redNumber is for debugging only.
 162 bool EmbedPQTree::Reduction(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
 163 {
 164         SListIterator<PlanarLeafKey<IndInfo*>* >  it;
 165
 166         SListPure<PQLeafKey<edge,IndInfo*,bool>*> castLeafKeys;
 167         for (it = leafKeys.begin(); it.valid(); ++it)
 168                 castLeafKeys.pushBack((PQLeafKey<edge,IndInfo*,bool>*) *it);
 169
 170         return PQTree<edge,IndInfo*,bool>::Reduction(castLeafKeys);
 171 }
 172
 173
 174
 175 // Function ReplaceFullRoot either replaces the full root
 176 // or one full child of a partial root of a pertinent subtree
 177 // by a single P-node  with leaves corresponding the keys stored in leafKeys.
 178 // Furthermore it scans the frontier of the pertinent subtree, and returns it
 179 // in frontier.
 180 // If called by ReplacePartialRoot, the function ReplaceFullRoot handles
 181 // the introduction of the direction  indicator. (This must be indicated
 182 // by addIndicator.
 183 // Node v determines the node related to the pertinent leaves. It is needed
 184 // to assign the dirrection indicator to this sequence.
 185
 186 void EmbedPQTree::ReplaceFullRoot(
 187         SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys,
 188         SListPure<PQBasicKey<edge,IndInfo*,bool>*> &frontier,
 189         node v,
 190         bool addIndicator,
 191         PQNode<edge,IndInfo*,bool> *opposite)
 192 {
 193         EmbedIndicator *newInd = 0;
 194
 195         front(m_pertinentRoot,frontier);
 196         if (addIndicator)
 197         {
 198                 IndInfo *newInfo = OGDF_NEW IndInfo(v);
 199                 PQNodeKey<edge,IndInfo*,bool> *nodeInfoPtr = OGDF_NEW PQNodeKey<edge,IndInfo*,bool>(newInfo);
 200                 newInd = OGDF_NEW EmbedIndicator(m_identificationNumber++, nodeInfoPtr);
 201                 newInd->setNodeInfo(nodeInfoPtr);
 202                 nodeInfoPtr->setNodePointer(newInd);
 203         }
 204
 205         if (!leafKeys.empty() && leafKeys.front() == leafKeys.back())
 206         {
 207                 //ReplaceFullRoot: replace pertinent root by a single leaf
 208                 if (addIndicator)
 209                 {
 210                         opposite = m_pertinentRoot->getNextSib(opposite);
 211                         if (!opposite) // m_pertinentRoot is endmost child
 212                         {
 213                                 addNodeToNewParent(m_pertinentRoot->parent(), newInd, m_pertinentRoot, opposite);
 214                         }
 215                         else
 216                                 addNodeToNewParent(0,newInd,m_pertinentRoot,opposite);
 217
 218                         // Setting the sibling pointers into opposite direction of
 219                         // scanning the front allows to track swaps of the indicator
 220                         newInd->changeSiblings(m_pertinentRoot,0);
 221                         newInd->changeSiblings(opposite,0);
 222                         newInd->putSibling(m_pertinentRoot,PQNodeRoot::LEFT);
 223                         newInd->putSibling(opposite,PQNodeRoot::RIGHT);
 224                 }
 225                 PQLeaf<edge,IndInfo*,bool> *leafPtr =
 226                         OGDF_NEW PQLeaf<edge,IndInfo*,bool>(m_identificationNumber++,
 227                         PQNodeRoot::EMPTY,(PQLeafKey<edge,IndInfo*,bool>*)leafKeys.front());
 228                 exchangeNodes(m_pertinentRoot,(PQNode<edge,IndInfo*,bool>*) leafPtr);
 229                 if (m_pertinentRoot == m_root)
 230                         m_root = (PQNode<edge,IndInfo*,bool>*) leafPtr;
 231                 m_pertinentRoot = 0;  // check for this emptyAllPertinentNodes
 232         }
 233
 234         else if (!leafKeys.empty()) // at least two leaves
 235         {
 236                 //replace pertinent root by a $P$-node
 237                 if (addIndicator)
 238                 {
 239                         opposite = m_pertinentRoot->getNextSib(opposite);
 240                         if (!opposite) // m_pertinentRoot is endmost child
 241                         {
 242                                 addNodeToNewParent(m_pertinentRoot->parent(), newInd, m_pertinentRoot, opposite);
 243                         }
 244                         else
 245                                 addNodeToNewParent(0, newInd, m_pertinentRoot, opposite);
 246
 247                         // Setting the sibling pointers into opposite direction of
 248                         // scanning the front allows to track swaps of the indicator
 249                         newInd->changeSiblings(m_pertinentRoot,0);
 250                         newInd->changeSiblings(opposite,0);
 251                         newInd->putSibling(m_pertinentRoot,PQNodeRoot::LEFT);
 252                         newInd->putSibling(opposite,PQNodeRoot::RIGHT);
 253                 }
 254
 255                 PQInternalNode<edge,IndInfo*,bool> *nodePtr = 0; // dummy
 256                 if ((m_pertinentRoot->type() == PQNodeRoot::PNode) ||
 257                         (m_pertinentRoot->type() == PQNodeRoot::QNode))
 258                 {
 259                         nodePtr = (PQInternalNode<edge,IndInfo*,bool>*)m_pertinentRoot;
 260                         nodePtr->type(PQNodeRoot::PNode);
 261                         nodePtr->childCount(0);
 262                         while (!fullChildren(m_pertinentRoot)->empty())
 263                         {
 264                                 PQNode<edge,IndInfo*,bool> *currentNode =
 265                                         fullChildren(m_pertinentRoot)->popFrontRet();
 266                                 removeChildFromSiblings(currentNode);
 267                         }
 268                 }
 269                 else if (m_pertinentRoot->type() == PQNodeRoot::leaf)
 270                 {
 271                         nodePtr = OGDF_NEW PQInternalNode<edge,IndInfo*,bool>(m_identificationNumber++,
 272                                                                                                                  PQNodeRoot::PNode,PQNodeRoot::EMPTY);
 273                         exchangeNodes(m_pertinentRoot,nodePtr);
 274                         m_pertinentRoot = 0;  // check for this emptyAllPertinentNodes
 275                 }
 276
 277                 SListPure<PQLeafKey<edge,IndInfo*,bool>*> castLeafKeys;
 278                 SListIterator<PlanarLeafKey<IndInfo*>* > it;
 279                 for (it = leafKeys.begin(); it.valid(); ++it)
 280                         castLeafKeys.pushBack((PQLeafKey<edge,IndInfo*,bool>*) *it);
 281                 addNewLeavesToTree(nodePtr,castLeafKeys);
 282         }
 283 }
 284
 285
 286 // Function ReplacePartialRoot replaces all full nodes by a single P-node
 287 // with leaves corresponding the keys stored in leafKeys.
 288 // Furthermore it scans the frontier of the pertinent subtree, and returns it
 289 // in frontier.
 290 // node v determines the node related to the pertinent leaves. It is needed
 291 // to assign the dirrection indicator to this sequence.
 292
 293 void EmbedPQTree::ReplacePartialRoot(
 294         SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys,
 295         SListPure<PQBasicKey<edge,IndInfo*,bool>*> &frontier,
 296         node v)
 297 {
 298         m_pertinentRoot->childCount(m_pertinentRoot->childCount() + 1 -
 299                                                                 fullChildren(m_pertinentRoot)->size());
 300
 301         PQNode<edge,IndInfo*,bool> *predNode = 0; // dummy
 302         PQNode<edge,IndInfo*,bool> *beginSequence = 0; // marks begin consecuitve seqeunce
 303         PQNode<edge,IndInfo*,bool> *endSequence = 0; // marks end consecutive sequence
 304         PQNode<edge,IndInfo*,bool> *beginInd = 0;       // initially, marks direct sibling indicator
 305                                                                                                 // next to beginSequence not contained
 306                                                                                                 // in consectuive sequence
 307
 308         // Get beginning and end of sequence.
 309         while (fullChildren(m_pertinentRoot)->size())
 310         {
 311                 PQNode<edge,IndInfo*,bool> *currentNode = fullChildren(m_pertinentRoot)->popFrontRet();
 312                 if (!clientSibLeft(currentNode) ||
 313                         clientSibLeft(currentNode)->status() == PQNodeRoot::EMPTY)
 314                 {
 315                         if (!beginSequence)
 316                         {
 317                                 beginSequence = currentNode;
 318                                 predNode = clientSibLeft(currentNode);
 319                                 beginInd =PQTree<edge,IndInfo*,bool>::clientSibLeft(currentNode);
 320                         }
 321                         else
 322                                 endSequence = currentNode;
 323                 }
 324                 else if (!clientSibRight(currentNode) ||
 325                                  clientSibRight(currentNode)->status() == PQNodeRoot::EMPTY )
 326                 {
 327                         if (!beginSequence)
 328                         {
 329                                 beginSequence = currentNode;
 330                                 predNode = clientSibRight(currentNode);
 331                                 beginInd =PQTree<edge,IndInfo*,bool>::clientSibRight(currentNode);
 332                         }
 333                         else
 334                                 endSequence = currentNode;
 335                 }
 336         }
 337
 338         SListPure<PQBasicKey<edge,IndInfo*,bool>*> partialFrontier;
 339
 340
 341         // Now scan the sequence of full nodes. Remove all of them but the last.
 342         // Call ReplaceFullRoot on the last one.
 343         // For every full node get its frontier. Scan intermediate indicators.
 344
 345         PQNode<edge,IndInfo*,bool> *currentNode = beginSequence;
 346         while (currentNode != endSequence)
 347         {
 348                 PQNode<edge,IndInfo*,bool>* nextNode =
 349                         clientNextSib(currentNode,predNode);
 350                 front(currentNode,partialFrontier);
 351                 frontier.conc(partialFrontier);
 352
 353                 PQNode<edge,IndInfo*,bool>* currentInd  = PQTree<edge,IndInfo*,bool>::
 354                         clientNextSib(currentNode,beginInd);
 355
 356                 // Scan for intermediate direction indicators.
 357                 while (currentInd != nextNode)
 358                 {
 359                         PQNode<edge,IndInfo*,bool> *nextInd = PQTree<edge,IndInfo*,bool>::
 360                                 clientNextSib(currentInd,currentNode);
 361                         if (currentNode == currentInd->getSib(PQNodeRoot::RIGHT)) //Direction changed
 362                                 currentInd->getNodeInfo()->userStructInfo()->changeDir = true;
 363                         frontier.pushBack((PQBasicKey<edge,IndInfo*,bool>*)
 364                                                                 currentInd->getNodeInfo());
 365                         removeChildFromSiblings(currentInd);
 366                         m_pertinentNodes->pushBack(currentInd);
 367                         currentInd = nextInd;
 368                 }
 369
 370                 removeChildFromSiblings(currentNode);
 371                 currentNode = nextNode;
 372         }
 373
 374         currentNode->parent(m_pertinentRoot);
 375         m_pertinentRoot = currentNode;
 376         ReplaceFullRoot(leafKeys,partialFrontier,v,true,beginInd);
 377         frontier.conc(partialFrontier);
 378 }
 379
 380
 381
 382 // Overloads virtual function of base class PQTree
 383 // Allows ignoring the virtual direction indicators during
 384 // the template matching algorithm.
 385 PQNode<edge,IndInfo*,bool>* EmbedPQTree::clientSibLeft(
 386         PQNode<edge,IndInfo*,bool> *nodePtr) const
 387 {
 388         PQNode<edge,IndInfo*,bool> *predNode = nodePtr;
 389         nodePtr = PQTree<edge,IndInfo*,bool>::clientSibLeft(predNode);
 390         while (nodePtr && nodePtr->status() == PQNodeRoot::INDICATOR)
 391         {
 392                 PQNode<edge,IndInfo*,bool> *holdSib = predNode;
 393                 predNode = nodePtr;
 394                 nodePtr  = predNode->getNextSib(holdSib);
 395         }
 396
 397         return nodePtr;
 398 }
 399
 400
 401 // Overloads virtual function of base class PQTree
 402 // Allows ignoring the virtual direction indicators during
 403 // the template matching algorithm.
 404 PQNode<edge,IndInfo*,bool>* EmbedPQTree::clientSibRight(
 405         PQNode<edge,IndInfo*,bool> *nodePtr) const
 406 {
 407         PQNode<edge,IndInfo*,bool> *predNode = nodePtr;
 408         nodePtr = PQTree<edge,IndInfo*,bool>::clientSibRight(predNode);
 409         while (nodePtr && nodePtr->status() == PQNodeRoot::INDICATOR)
 410         {
 411                 PQNode<edge,IndInfo*,bool> *holdSib = predNode;
 412                 predNode = nodePtr;
 413                 nodePtr = predNode->getNextSib(holdSib);
 414         }
 415
 416         return nodePtr;
 417 }
 418
 419
 420 // Overloads virtual function of base class PQTree
 421 // Allows ignoring the virtual direction indicators during
 422 // the template matching algorithm.
 423 PQNode<edge,IndInfo*,bool>* EmbedPQTree::clientLeftEndmost(
 424         PQNode<edge,IndInfo*,bool> *nodePtr) const
 425 {
 426         PQNode<edge,IndInfo*,bool> *left = PQTree<edge,IndInfo*,bool>::clientLeftEndmost(nodePtr);
 427
 428         if (!left || left->status() != PQNodeRoot::INDICATOR)
 429                 return left;
 430         else
 431                 return clientNextSib(left,NULL);
 432 }
 433
 434
 435 // Overloads virtual function of base class PQTree
 436 // Allows ignoring the virtual direction indicators during
 437 // the template matching algorithm.
 438 PQNode<edge,IndInfo*,bool>* EmbedPQTree::clientRightEndmost(
 439         PQNode<edge,IndInfo*,bool> *nodePtr) const
 440 {
 441         PQNode<edge,IndInfo*,bool> *right = PQTree<edge,IndInfo*,bool>::clientRightEndmost(nodePtr);
 442
 443         if (!right || right->status() != PQNodeRoot::INDICATOR)
 444                 return right;
 445         else
 446                 return clientNextSib(right,NULL);
 447 }
 448
 449
 450 // Overloads virtual function of base class PQTree
 451 // Allows ignoring the virtual direction indicators during
 452 // the template matching algorithm.
 453 PQNode<edge,IndInfo*,bool>* EmbedPQTree::clientNextSib(
 454         PQNode<edge,IndInfo*,bool> *nodePtr,
 455         PQNode<edge,IndInfo*,bool> *other) const
 456 {
 457         PQNode<edge,IndInfo*,bool> *left = clientSibLeft(nodePtr);
 458         if (left  != other) return left;
 459
 460         PQNode<edge,IndInfo*,bool> *right = clientSibRight(nodePtr);
 461         if (right != other) return right;
 462
 463         return 0;
 464 }
 465
 466
 467 // Overloads virtual function of base class PQTree
 468 // Allows to print debug information on the direction indicators
 469 const char* EmbedPQTree::clientPrintStatus(PQNode<edge,IndInfo*,bool> *nodePtr)
 470 {
 471         if (nodePtr->status() == PQNodeRoot::INDICATOR)
 472                 return "INDICATOR";
 473         else
 474                 return PQTree<edge,IndInfo*,bool>::clientPrintStatus(nodePtr);
 475 }
 476
 477
 478 // The function front scans the frontier of nodePtr. It returns the keys
 479 // of the leaves found in the frontier of nodePtr in a SListPure.
 480 // These keys include keys of direction indicators detected in the frontier.
 481 //
 482 // CAREFUL: Funktion marks all full nodes for destruction.
 483 //                      Only to be used in connection with replaceRoot.
 484 //
 485 void EmbedPQTree::front(
 486         PQNode<edge,IndInfo*,bool>* nodePtr,
 487         SListPure<PQBasicKey<edge,IndInfo*,bool>*> &keys)
 488 {
 489         Stack<PQNode<edge,IndInfo*,bool>*> S;
 490         S.push(nodePtr);
 491
 492         while (!S.empty())
 493         {
 494                 PQNode<edge,IndInfo*,bool> *checkNode = S.pop();
 495
 496                 if (checkNode->type() == PQNodeRoot::leaf)
 497                         keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) checkNode->getKey());
 498                 else
 499                 {
 500                         PQNode<edge,IndInfo*,bool>* firstSon = 0;
 501                         if (checkNode->type() == PQNodeRoot::PNode)
 502                         {
 503                                 firstSon = checkNode->referenceChild();
 504                         }
 505                         else if (checkNode->type() == PQNodeRoot::QNode)
 506                         {
 507                                 firstSon = checkNode->getEndmost(PQNodeRoot::RIGHT);
 508                                 // By this, we make sure that we start on the left side
 509                                 // since the left endmost child will be on top of the stack
 510                         }
 511
 512                         if (firstSon->status() == PQNodeRoot::INDICATOR)
 513                         {
 514                                 keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) firstSon->getNodeInfo());
 515                                 m_pertinentNodes->pushBack(firstSon);
 516                                 destroyNode(firstSon);
 517                         }
 518                         else
 519                                 S.push(firstSon);
 520
 521                         PQNode<edge,IndInfo*,bool> *nextSon = firstSon->getNextSib(0);
 522                         PQNode<edge,IndInfo*,bool> *oldSib = firstSon;
 523                         while (nextSon && nextSon != firstSon)
 524                         {
 525                                 if (nextSon->status() == PQNodeRoot::INDICATOR)
 526                                 {
 527                                         // Direction indicators point with their left sibling pointer
 528                                         // in the direction of their sequence. If an indicator is scanned
 529                                         // from the opposite direction, coming from its right sibling
 530                                         // the corresponding sequence must be reversed.
 531                                         if (oldSib == nextSon->getSib(PQNodeRoot::LEFT)) //Direction changed
 532                                                 nextSon->getNodeInfo()->userStructInfo()->changeDir = true;
 533                                         keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) nextSon->getNodeInfo());
 534                                         m_pertinentNodes->pushBack(nextSon);
 535                                 }
 536                                 else
 537                                         S.push(nextSon);
 538
 539                                 PQNode<edge,IndInfo*,bool> *holdSib = nextSon->getNextSib(oldSib);
 540                                 oldSib = nextSon;
 541                                 nextSon = holdSib;
 542                         }
 543                 }
 544         }
 545 }
 546
 547
 548
 549 // The function front scans the frontier of nodePtr. It returns the keys
 550 // of the leaves found in the frontier of nodePtr in a SListPure.
 551 // These keys include keys of direction indicators detected in the frontier.
 552 //
 553 // No direction is assigned to the direction indicators.
 554 //
 555 void EmbedPQTree::getFront(
 556         PQNode<edge,IndInfo*,bool>* nodePtr,
 557         SListPure<PQBasicKey<edge,IndInfo*,bool>*> &keys)
 558 {
 559         Stack<PQNode<edge,IndInfo*,bool>*> S;
 560         S.push(nodePtr);
 561
 562         while (!S.empty())
 563         {
 564                 PQNode<edge,IndInfo*,bool> *checkNode = S.pop();
 565
 566                 if (checkNode->type() == PQNodeRoot::leaf)
 567                         keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) checkNode->getKey());
 568                 else
 569                 {
 570                         PQNode<edge,IndInfo*,bool>* firstSon  = 0;
 571                         if (checkNode->type() == PQNodeRoot::PNode)
 572                         {
 573                                 firstSon = checkNode->referenceChild();
 574                         }
 575                         else if (checkNode->type() == PQNodeRoot::QNode)
 576                         {
 577                                 firstSon = checkNode->getEndmost(PQNodeRoot::RIGHT);
 578                                 // By this, we make sure that we start on the left side
 579                                 // since the left endmost child will be on top of the stack
 580                         }
 581
 582                         if (firstSon->status() == PQNodeRoot::INDICATOR)
 583                         {
 584                                 keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) firstSon->getNodeInfo());
 585                         }
 586                         else
 587                                 S.push(firstSon);
 588
 589                         PQNode<edge,IndInfo*,bool> *nextSon = firstSon->getNextSib(0);
 590                         PQNode<edge,IndInfo*,bool> *oldSib = firstSon;
 591                         while (nextSon && nextSon != firstSon)
 592                         {
 593                                 if (nextSon->status() == PQNodeRoot::INDICATOR)
 594                                         keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) nextSon->getNodeInfo());
 595                                 else
 596                                         S.push(nextSon);
 597
 598                                 PQNode<edge,IndInfo*,bool> *holdSib = nextSon->getNextSib(oldSib);
 599                                 oldSib = nextSon;
 600                                 nextSon = holdSib;
 601                         }
 602                 }
 603         }
 604 }
 605
 606
 607
 608 }