ext/OGDF/src/planarity/PlanarPQTree.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 PlanarPQTree.
  11  *
  12  * Implements a PQTree with added features for the planarity test.
  13  * 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/PlanarPQTree.h>
  48
  49 namespace ogdf{
  50
  51 // Overriding the function doDestruction (see basic.h)
  52 // Allows deallocation of lists of PlanarLeafKey<IndInfo*>
  53 // and PQLeafKey<edge,IndInfo*,bool> in constant time using OGDF
  54 // memory management.
  55
  56 typedef PlanarLeafKey<IndInfo*> *PtrPlanarLeafKeyI;
  57
  58 template<>
  59 inline bool doDestruction<PtrPlanarLeafKeyI>(const PtrPlanarLeafKeyI*) { return false; }
  60
  61
  62 typedef PQLeafKey<edge,IndInfo*,bool> *PtrPQLeafKeyEIB;
  63
  64 template<>
  65 inline bool doDestruction<PtrPQLeafKeyEIB>(const PtrPQLeafKeyEIB*) { return false; }
  66
  67
  68
  69 // Replaces the pertinent subtree by a P-node with leaves as children
  70 // corresponding to the incoming edges of the node v. These edges
  71 // are to be specified by their keys stored in leafKeys.
  72 void PlanarPQTree::ReplaceRoot(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
  73 {
  74         if (m_pertinentRoot->status() == PQNodeRoot::FULL)
  75                 ReplaceFullRoot(leafKeys);
  76         else
  77                 ReplacePartialRoot(leafKeys);
  78 }
  79
  80
  81
  82 // The function [[emptyAllPertinentNodes]] has to be called after a reduction
  83 // has been processed. This overloaded function first destroys all full nodes
  84 // by marking them as TO_BE_DELETED and then calling the base class function
  85 // [[emptyAllPertinentNodes]].
  86 void PlanarPQTree::emptyAllPertinentNodes()
  87 {
  88         ListIterator<PQNode<edge,IndInfo*,bool>*> it;
  89         for (it = m_pertinentNodes->begin(); it.valid(); it++)
  90         {
  91                 PQNode<edge,IndInfo*,bool>* nodePtr = (*it);
  92                 if (nodePtr->status() == PQNodeRoot::FULL)
  93                         destroyNode(nodePtr);
  94         }
  95         if (m_pertinentRoot)
  96                 m_pertinentRoot->status(PQNodeRoot::FULL);
  97
  98         PQTree<edge,IndInfo*,bool>::emptyAllPertinentNodes();
  99 }
 100
 101
 102 // Initializes a PQTree by a set of leaves that will korrespond to
 103 // the set of Keys stored in leafKeys.
 104 int PlanarPQTree::Initialize(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
 105 {
 106         SListIterator<PlanarLeafKey<IndInfo*>* >  it;
 107         SListPure<PQLeafKey<edge,IndInfo*,bool>*> castLeafKeys;
 108         for (it = leafKeys.begin(); it.valid(); ++it)
 109                 castLeafKeys.pushBack((PQLeafKey<edge,IndInfo*,bool>*) *it);
 110
 111         return PQTree<edge,IndInfo*,bool>::Initialize(castLeafKeys);
 112 }
 113
 114
 115 // Reduction reduced a set of leaves determined by their keys stored
 116 // in leafKeys. Integer redNumber is for debugging only.
 117 bool PlanarPQTree::Reduction(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
 118 {
 119         SListIterator<PlanarLeafKey<IndInfo*>* >  it;
 120         SListPure<PQLeafKey<edge,IndInfo*,bool>*> castLeafKeys;
 121         for (it = leafKeys.begin(); it.valid(); ++it)
 122                 castLeafKeys.pushBack((PQLeafKey<edge,IndInfo*,bool>*) *it);
 123
 124         return PQTree<edge,IndInfo*,bool>::Reduction(castLeafKeys);
 125 }
 126
 127
 128 // Function ReplaceFullRoot either replaces the full root
 129 // or one full child of a partial root of a pertinent subtree
 130 // by a single P-node  with leaves corresponding the keys stored in leafKeys.
 131 void PlanarPQTree::ReplaceFullRoot(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
 132 {
 133         if (!leafKeys.empty() && leafKeys.front() == leafKeys.back())
 134         {
 135                 //ReplaceFullRoot: replace pertinent root by a single leaf
 136                 PQLeaf<edge,IndInfo*,bool> *leafPtr =
 137                         OGDF_NEW PQLeaf<edge,IndInfo*,bool>(m_identificationNumber++,
 138                         PQNodeRoot::EMPTY,(PQLeafKey<edge,IndInfo*,bool>*)leafKeys.front());
 139
 140                 exchangeNodes(m_pertinentRoot,(PQNode<edge,IndInfo*,bool>*) leafPtr);
 141                 if (m_pertinentRoot == m_root)
 142                         m_root = (PQNode<edge,IndInfo*,bool>*) leafPtr;
 143                 m_pertinentRoot = 0;  // check for this emptyAllPertinentNodes
 144         }
 145
 146         else if (!leafKeys.empty()) // at least two leaves
 147         {
 148                 PQInternalNode<edge,IndInfo*,bool> *nodePtr = 0; // dummy
 149                 //replace pertinent root by a $P$-node
 150                 if ((m_pertinentRoot->type() == PQNodeRoot::PNode) ||
 151                         (m_pertinentRoot->type() == PQNodeRoot::QNode))
 152                 {
 153                         nodePtr = (PQInternalNode<edge,IndInfo*,bool>*)m_pertinentRoot;
 154                         nodePtr->type(PQNodeRoot::PNode);
 155                         nodePtr->childCount(0);
 156                         while (!fullChildren(m_pertinentRoot)->empty())
 157                                 removeChildFromSiblings(fullChildren(m_pertinentRoot)->popFrontRet());
 158                 }
 159                 else if (m_pertinentRoot->type() == PQNodeRoot::leaf)
 160                 {
 161                         nodePtr = OGDF_NEW PQInternalNode<edge,IndInfo*,bool>(m_identificationNumber++,
 162                                                                                                                  PQNodeRoot::PNode,PQNodeRoot::EMPTY);
 163                         exchangeNodes(m_pertinentRoot,nodePtr);
 164                         m_pertinentRoot = 0;  // check for this emptyAllPertinentNodes
 165                 }
 166
 167                 SListPure<PQLeafKey<edge,IndInfo*,bool>*> castLeafKeys;
 168                 SListIterator<PlanarLeafKey<IndInfo*>* >  it;
 169                 for (it = leafKeys.begin(); it.valid(); ++it)
 170                         castLeafKeys.pushBack((PQLeafKey<edge,IndInfo*,bool>*) *it);
 171                 addNewLeavesToTree(nodePtr,castLeafKeys);
 172         }
 173 }
 174
 175
 176 // Function ReplacePartialRoot replaces all full nodes by a single P-node
 177 // with leaves corresponding the keys stored in leafKeys.
 178 void PlanarPQTree::ReplacePartialRoot(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
 179 {
 180         m_pertinentRoot->childCount(m_pertinentRoot->childCount() + 1 -
 181                 fullChildren(m_pertinentRoot)->size());
 182
 183         while (fullChildren(m_pertinentRoot)->size() > 1)
 184                 removeChildFromSiblings(fullChildren(m_pertinentRoot)->popFrontRet());
 185
 186         PQNode<edge,IndInfo*,bool> *currentNode = fullChildren(m_pertinentRoot)->popFrontRet();
 187
 188         currentNode->parent(m_pertinentRoot);
 189         m_pertinentRoot = currentNode;
 190         ReplaceFullRoot(leafKeys);
 191 }
 192
 193
 194 }