6 * $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of the class EmbedPQTree.
12 * \author Sebastian Leipert
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
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
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.
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.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
49 #ifndef OGDF_EMBED_PQTREE_H
50 #define OGDF_EMBED_PQTREE_H
52 #include <ogdf/basic/Graph.h>
53 #include <ogdf/basic/SList.h>
54 #include <ogdf/internal/planarity/PQTree.h>
55 #include <ogdf/internal/planarity/PlanarLeafKey.h>
56 #include <ogdf/internal/planarity/EmbedIndicator.h>
60 typedef PQBasicKey
<edge
,IndInfo
*,bool> *PtrPQBasicKeyEIB
;
63 inline bool doDestruction
<PtrPQBasicKeyEIB
>(const PtrPQBasicKeyEIB
*) { return false; }
66 typedef PlanarLeafKey
<IndInfo
*> *PtrPlanarLeafKeyI
;
69 inline bool doDestruction
<PtrPlanarLeafKeyI
>(const PtrPlanarLeafKeyI
*) { return false; }
72 class EmbedPQTree
: public PQTree
<edge
,IndInfo
*,bool>
76 EmbedPQTree() : PQTree
<edge
,IndInfo
*,bool>() { }
78 virtual ~EmbedPQTree() { }
80 virtual void emptyAllPertinentNodes();
82 virtual void clientDefinedEmptyNode(PQNode
<edge
,IndInfo
*,bool>* nodePtr
);
84 virtual int Initialize(SListPure
<PlanarLeafKey
<IndInfo
*>*> &leafKeys
);
87 SListPure
<PlanarLeafKey
<IndInfo
*>*> &leafKeys
,
88 SListPure
<edge
> &frontier
,
89 SListPure
<node
> &opposed
,
90 SListPure
<node
> &nonOpposed
,
93 virtual bool Reduction(SListPure
<PlanarLeafKey
<IndInfo
*>*> &leafKeys
);
95 PQNode
<edge
,IndInfo
*,bool>* scanSibLeft(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const {
96 return clientSibLeft(nodePtr
);
99 PQNode
<edge
,IndInfo
*,bool>* scanSibRight(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const {
100 return clientSibRight(nodePtr
);
103 PQNode
<edge
,IndInfo
*,bool>* scanLeftEndmost(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const {
104 return clientLeftEndmost(nodePtr
);
107 PQNode
<edge
,IndInfo
*,bool>* scanRightEndmost(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const {
108 return clientRightEndmost(nodePtr
);
111 PQNode
<edge
,IndInfo
*,bool>* scanNextSib(
112 PQNode
<edge
,IndInfo
*,bool> *nodePtr
,
113 PQNode
<edge
,IndInfo
*,bool> *other
) {
114 return clientNextSib(nodePtr
,other
);
117 virtual void getFront(
118 PQNode
<edge
,IndInfo
*,bool>* nodePtr
,
119 SListPure
<PQBasicKey
<edge
,IndInfo
*,bool>*> &leafKeys
);
123 virtual PQNode
<edge
,IndInfo
*,bool>*
124 clientSibLeft(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const;
126 virtual PQNode
<edge
,IndInfo
*,bool>*
127 clientSibRight(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const;
129 virtual PQNode
<edge
,IndInfo
*,bool>*
130 clientLeftEndmost(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const;
132 virtual PQNode
<edge
,IndInfo
*,bool>*
133 clientRightEndmost(PQNode
<edge
,IndInfo
*,bool> *nodePtr
) const;
135 virtual PQNode
<edge
,IndInfo
*,bool>*
136 clientNextSib(PQNode
<edge
,IndInfo
*,bool> *nodePtr
,
137 PQNode
<edge
,IndInfo
*,bool> *other
) const;
139 clientPrintStatus(PQNode
<edge
,IndInfo
*,bool> *nodePtr
);
142 PQNode
<edge
,IndInfo
*,bool>* nodePtr
,
143 SListPure
<PQBasicKey
<edge
,IndInfo
*,bool>*> &leafKeys
);
147 void ReplaceFullRoot(
148 SListPure
<PlanarLeafKey
<IndInfo
*>*> &leafKeys
,
149 SListPure
<PQBasicKey
<edge
,IndInfo
*,bool>*> &frontier
,
151 bool addIndicator
= false,
152 PQNode
<edge
,IndInfo
*,bool> *opposite
= 0);
154 void ReplacePartialRoot(
155 SListPure
<PlanarLeafKey
<IndInfo
*>*> &leafKeys
,
156 SListPure
<PQBasicKey
<edge
,IndInfo
*,bool>*> &frontier
,