ext/OGDF/src/planarity/PlanarSubgraphPQTree.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 PlanarSubgraphPQTree.
  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 #include <ogdf/internal/planarity/PlanarSubgraphPQTree.h>
  47
  48 namespace ogdf{
  49
  50 // Replaces the pertinent subtree by a P-node with leaves as children
  51 // corresponding to the incoming edges of the node v. These edges
  52 // are to be specified by their keys stored in leafKeys.
  53 void PlanarSubgraphPQTree::
  54 ReplaceRoot(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys)
  55 {
  56         if (m_pertinentRoot->status() == PQNodeRoot::FULL)
  57                 ReplaceFullRoot(leafKeys);
  58         else
  59                 ReplacePartialRoot(leafKeys);
  60 }
  61
  62 // Initializes a PQTree by a set of leaves that will korrespond to
  63 // the set of Keys stored in leafKeys.
  64 int PlanarSubgraphPQTree::
  65 Initialize(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys)
  66 {
  67         SListIterator<PlanarLeafKey<whaInfo*>* >  it;
  68
  69         SListPure<PQLeafKey<edge,whaInfo*,bool>*> castLeafKeys;
  70         for (it = leafKeys.begin(); it.valid(); ++it)
  71                 castLeafKeys.pushBack((PQLeafKey<edge,whaInfo*,bool>*) *it);
  72
  73         return PQTree<edge,whaInfo*,bool>::Initialize(castLeafKeys);
  74 }
  75
  76
  77 // Reduction reduced a set of leaves determined by their keys stored
  78 // in leafKeys. Integer redNumber is for debugging only.
  79 bool PlanarSubgraphPQTree::Reduction(
  80         SListPure<PlanarLeafKey<whaInfo*>*>   &leafKeys,
  81         SList<PQLeafKey<edge,whaInfo*,bool>*> &eliminatedKeys)
  82 {
  83         SListPure<PQLeafKey<edge,whaInfo*,bool>*> castLeafKeys;
  84
  85         SListIterator<PlanarLeafKey<whaInfo*>* >  it;
  86         for (it = leafKeys.begin(); it.valid(); ++it)
  87         {
  88                 castLeafKeys.pushBack((PQLeafKey<edge,whaInfo*,bool>*) *it);
  89         }
  90
  91         determineMinRemoveSequence(castLeafKeys,eliminatedKeys);
  92         removeEliminatedLeaves(eliminatedKeys);
  93
  94         SListIterator<PQLeafKey<edge,whaInfo*,bool>* >  itn = castLeafKeys.begin();
  95         SListIterator<PQLeafKey<edge,whaInfo*,bool>* >  itp = itn++;
  96         for (; itn.valid();)
  97         {
  98                 if ((*itn)->nodePointer()->status()== PQNodeRoot::WHA_DELETE)
  99                 {
 100                         itn++;
 101                         castLeafKeys.delSucc(itp);
 102                 }
 103                 else
 104                         itp = itn++;
 105         }
 106
 107         if ((*castLeafKeys.begin())->nodePointer()->status() == PQNodeRoot::WHA_DELETE)
 108                 castLeafKeys.popFront();
 109
 110
 111         return Reduce(castLeafKeys);
 112 }
 113
 114
 115
 116 // Function ReplaceFullRoot either replaces the full root
 117 // or one full child of a partial root of a pertinent subtree
 118 // by a single P-node  with leaves corresponding the keys stored in leafKeys.
 119 void PlanarSubgraphPQTree::
 120 ReplaceFullRoot(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys)
 121 {
 122
 123         PQLeaf<edge,whaInfo*,bool>          *leafPtr     = 0; // dummy
 124         PQInternalNode<edge,whaInfo*,bool>      *nodePtr     = 0; // dummy
 125         PQNode<edge,whaInfo*,bool>                  *currentNode = 0; // dummy
 126         SListIterator<PlanarLeafKey<whaInfo*>* >  it;
 127
 128         if (!leafKeys.empty() && leafKeys.front() == leafKeys.back())
 129         {
 130                 //ReplaceFullRoot: replace pertinent root by a single leaf
 131                 leafPtr = OGDF_NEW PQLeaf<edge,whaInfo*,bool>(m_identificationNumber++,
 132                         PQNodeRoot::EMPTY,(PQLeafKey<edge,whaInfo*,bool>*)leafKeys.front());
 133                 exchangeNodes(m_pertinentRoot,(PQNode<edge,whaInfo*,bool>*) leafPtr);
 134                 if (m_pertinentRoot == m_root)
 135                         m_root = (PQNode<edge,whaInfo*,bool>*) leafPtr;
 136         }
 137         else if (!leafKeys.empty()) // at least two leaves
 138         {
 139                 //replace pertinent root by a $P$-node
 140                 if ((m_pertinentRoot->type() == PQNodeRoot::PNode) ||
 141                         (m_pertinentRoot->type() == PQNodeRoot::QNode))
 142                 {
 143                         nodePtr = (PQInternalNode<edge,whaInfo*,bool>*)m_pertinentRoot;
 144                         nodePtr->type(PQNodeRoot::PNode);
 145                         nodePtr->status(PQNodeRoot::PERTROOT);
 146                         nodePtr->childCount(0);
 147                         while (!fullChildren(m_pertinentRoot)->empty())
 148                         {
 149                                 currentNode = fullChildren(m_pertinentRoot)->popFrontRet();
 150                                 removeChildFromSiblings(currentNode);
 151                         }
 152                 }
 153                 else if (m_pertinentRoot->type() == PQNodeRoot::leaf)
 154                 {
 155                         nodePtr = OGDF_NEW PQInternalNode<edge,whaInfo*,bool>(m_identificationNumber++,
 156                                                                                                                  PQNodeRoot::PNode,PQNodeRoot::EMPTY);
 157                         exchangeNodes(m_pertinentRoot,nodePtr);
 158                 }
 159                 SListPure<PQLeafKey<edge,whaInfo*,bool>*> castLeafKeys;
 160                 for (it = leafKeys.begin(); it.valid(); ++it)
 161                         castLeafKeys.pushBack((PQLeafKey<edge,whaInfo*,bool>*) *it);
 162                 addNewLeavesToTree(nodePtr,castLeafKeys);
 163         }
 164
 165 }
 166
 167
 168 // Function ReplacePartialRoot replaces all full nodes by a single P-node
 169 // with leaves corresponding the keys stored in leafKeys.
 170 void PlanarSubgraphPQTree::
 171         ReplacePartialRoot(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys)
 172
 173 {
 174         PQNode<edge,whaInfo*,bool>  *currentNode = NULL;
 175
 176         m_pertinentRoot->childCount(m_pertinentRoot->childCount() + 1 -
 177                 fullChildren(m_pertinentRoot)->size());
 178
 179         while (fullChildren(m_pertinentRoot)->size() > 1)
 180         {
 181                 currentNode = fullChildren(m_pertinentRoot)->popFrontRet();
 182                 removeChildFromSiblings(currentNode);
 183         }
 184
 185         currentNode = fullChildren(m_pertinentRoot)->popFrontRet();
 186
 187         currentNode->parent(m_pertinentRoot);
 188         m_pertinentRoot = currentNode;
 189         ReplaceFullRoot(leafKeys);
 190
 191 }
 192
 193
 194 /**
 195 The function removeEliminatedLeaves handles the difficult task of
 196 cleaning up after every reduction.
 197
 198 After a reduction is complete, different kind of garbage has to be
 199 handled.
 200 \begin{itemize}
 201 \item Pertinent leaves that are not in the maximal pertinent sequence.
 202         from the $PQ$-tree in order to get it reducable have to be deleted.
 203 \item The memory of some pertinent nodes, that have only pertinent leaves not beeing
 204         in the maximal pertinent sequence in their frontier has to be freed.
 205 \item Pertinent nodes that have only one child left after the removal
 206         of pertinent leaves not beeing in the maximal pertinent sequence
 207         have to be deleted.
 208 \item The memory of all full nodes has to be freed, since the complete
 209         pertinent subtree is replaced by a $P$-node after the reduction.
 210 \item Nodes, that have been removed during the call of the function [[Reduce]]
 211         of the base class template [[PQTree]] from the $PQ$-tree have to be
 212         kept but marked as nonexisting.
 213 \end{itemize}.
 214 */
 215
 216 /**************************************************************************************
 217                                                         removeEliminatedLeaves
 218 ***************************************************************************************/
 219
 220 void PlanarSubgraphPQTree::
 221 removeEliminatedLeaves(SList<PQLeafKey<edge,whaInfo*,bool>*> &eliminatedKeys)
 222 {
 223         PQNode<edge,whaInfo*,bool>*  nodePtr = 0;
 224         PQNode<edge,whaInfo*,bool>*  parent  = 0;
 225         PQNode<edge,whaInfo*,bool>*  sibling = 0;
 226
 227         SListIterator<PQLeafKey<edge,whaInfo*,bool>*> it;
 228         for (it = eliminatedKeys.begin(); it.valid(); it++)
 229         {
 230                 nodePtr = (*it)->nodePointer();
 231                 parent = nodePtr->parent();
 232                 sibling = nodePtr->getNextSib(NULL);
 233
 234                 removeNodeFromTree(parent,nodePtr);
 235                 checkIfOnlyChild(sibling,parent);
 236                 if (parent->status() == PQNodeRoot::TO_BE_DELETED)
 237                 {
 238                         parent->status(PQNodeRoot::WHA_DELETE);
 239                 }
 240                 nodePtr->status(PQNodeRoot::WHA_DELETE);
 241         }
 242 }
 243
 244
 245
 246 }