6 * $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class PlanarSubgraphPQTree.
12 * Datastructure used by the planarization module FastPlanarSubgraph.
13 * Derived class of MaxSequencePQTree. Implements an Interface
14 * of MaxSequencePQTree for the planarization module FastPlanarSubgraph.
16 * \author Sebastian Leipert
19 * This file is part of the Open Graph Drawing Framework (OGDF).
23 * See README.txt in the root directory of the OGDF installation for details.
26 * This program is free software; you can redistribute it and/or
27 * modify it under the terms of the GNU General Public License
28 * Version 2 or 3 as published by the Free Software Foundation;
29 * see the file LICENSE.txt included in the packaging of this file
33 * This program is distributed in the hope that it will be useful,
34 * but WITHOUT ANY WARRANTY; without even the implied warranty of
35 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
36 * GNU General Public License for more details.
39 * You should have received a copy of the GNU General Public
40 * License along with this program; if not, write to the Free
41 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
42 * Boston, MA 02110-1301, USA.
44 * \see http://www.gnu.org/copyleft/gpl.html
45 ***************************************************************/
53 #ifndef OGDF_PLANAR_SUBGRAPH_PQTREE_H
54 #define OGDF_PLANAR_SUBGRAPH_PQTREE_H
58 #include <ogdf/basic/Graph.h>
59 #include <ogdf/basic/SList.h>
60 #include <ogdf/internal/planarity/PQTree.h>
61 #include <ogdf/internal/planarity/PlanarLeafKey.h>
62 #include <ogdf/internal/planarity/MaxSequencePQTree.h>
66 // Overriding the function doDestruction (see basic.h)
67 // Allows deallocation of lists of PlanarLeafKey<whaInfo*>
68 // and PQLeafKey<edge,IndInfo*,bool> in constant time using OGDF
72 typedef PQLeafKey
<edge
,whaInfo
*,bool> *PtrPQLeafKeyEWB
;
75 inline bool doDestruction
<PtrPQLeafKeyEWB
>(const PtrPQLeafKeyEWB
*) { return false; }
77 typedef PlanarLeafKey
<whaInfo
*> *PtrPlanarLeafKeyW
;
80 inline bool doDestruction
<PtrPlanarLeafKeyW
>(const PtrPlanarLeafKeyW
*) { return false; }
84 class PlanarSubgraphPQTree
: public MaxSequencePQTree
<edge
,bool> {
88 PlanarSubgraphPQTree() : MaxSequencePQTree
<edge
,bool>() { }
90 virtual ~PlanarSubgraphPQTree() { }
92 //! Initializes a new PQ-tree with a set of leaves.
93 virtual int Initialize(SListPure
<PlanarLeafKey
<whaInfo
*>*> &leafKeys
);
95 //! Replaces the pertinent subtree by a set of new leaves.
96 void ReplaceRoot(SListPure
<PlanarLeafKey
<whaInfo
*>*> &leafKeys
);
98 //! Reduces a set of leaves.
99 virtual bool Reduction(
100 SListPure
<PlanarLeafKey
<whaInfo
*>*> &leafKeys
,
101 SList
<PQLeafKey
<edge
,whaInfo
*,bool>*> &eliminatedKeys
);
105 //! Replaces a pertinet subtree by a set of new leaves if the root is full.
106 void ReplaceFullRoot(SListPure
<PlanarLeafKey
<whaInfo
*>*> &leafKeys
);
108 //! Replaces a pertinet subtree by a set of new leaves if the root is partial.
109 void ReplacePartialRoot(SListPure
<PlanarLeafKey
<whaInfo
*>*> &leafKeys
);
111 //! Removes the leaves that have been marked for elimination from the PQ-tree.
112 void removeEliminatedLeaves(SList
<PQLeafKey
<edge
,whaInfo
*,bool>*> &eliminatedKeys
);