6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of ClusterPQContainer.
12 * Stores information for a biconnected component
13 * of a cluster for embedding the cluster in the
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_CLUSTER_PQ_CONTAINER_H
54 #define OGDF_CLUSTER_PQ_CONTAINER_H
56 #include <ogdf/cluster/CconnectClusterPlanarEmbed.h>
57 #include <ogdf/internal/planarity/EmbedPQTree.h>
58 #include <ogdf/basic/NodeArray.h>
59 #include <ogdf/basic/EdgeArray.h>
64 class ClusterPQContainer
{
66 friend class CconnectClusterPlanarEmbed
;
70 // incoming edge of v: an edge e = (v,w) with number(v) < number(w)
73 // Stores for every node v the keys corresponding to the incoming edges of v
74 NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > >* m_inLeaves
;
76 // Stores for every node v the keys corresponding to the outgoing edges of v
77 NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > >* m_outLeaves
;
79 // Stores for every node v the sequence of incoming edges of v according
81 NodeArray
<SListPure
<edge
> >* m_frontier
;
83 // Stores for every node v the nodes corresponding to the
84 // opposed sink indicators found in the frontier of v.
85 NodeArray
<SListPure
<node
> >* m_opposed
;
87 // Stores for every node v the nodes corresponding to the
88 // non opposed sink indicators found in the frontier of v.
89 NodeArray
<SListPure
<node
> >* m_nonOpposed
;
91 // Table to acces for every edge its corresponding key in the PQTree
92 EdgeArray
<PlanarLeafKey
<IndInfo
*>*>* m_edge2Key
;
94 // Stores for every node its st-number
95 NodeArray
<int> *m_numbering
;
97 // Stores for every st-number the node
98 Array
<node
> *m_tableNumber2Node
;
102 // the subgraph that contains the biconnected component
103 // NOT THE COPY OF THE BICONNECTED COMPONENT THAT WAS CONSTRUCTED
104 // DURING PLANARITY TESTING. THIS HAS BEEN DELETED.
106 // corresponding PQTree
108 // The leaf correpsonding to the edge (s,t).
109 PlanarLeafKey
<IndInfo
*> *m_stEdgeLeaf
;
113 ClusterPQContainer():
114 m_inLeaves(0),m_outLeaves(0),m_frontier(0),
115 m_opposed(0),m_nonOpposed(0),m_edge2Key(0),
116 m_numbering(0),m_tableNumber2Node(0),
117 m_superSink(0),m_subGraph(0),m_T(0), m_stEdgeLeaf(0) { }
119 ~ClusterPQContainer() { }
121 void init(Graph
*subGraph
){
122 m_subGraph
= subGraph
;
124 = OGDF_NEW NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > >(*subGraph
);
127 = OGDF_NEW NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > >(*subGraph
);
130 = OGDF_NEW NodeArray
<SListPure
<edge
> >(*subGraph
);
133 = OGDF_NEW NodeArray
<SListPure
<node
> >(*subGraph
);
136 = OGDF_NEW NodeArray
<SListPure
<node
> >(*subGraph
);
139 = OGDF_NEW EdgeArray
<PlanarLeafKey
<IndInfo
*>*>(*subGraph
);
142 = OGDF_NEW NodeArray
<int >(*subGraph
);
145 = OGDF_NEW Array
<node
>(subGraph
->numberOfNodes()+1);
155 forall_nodes(v
,*m_subGraph
)
157 while (!(*m_outLeaves
)[v
].empty())
159 PlanarLeafKey
<IndInfo
*>* L
= (*m_outLeaves
)[v
].popFrontRet();
175 m_T
->emptyAllPertinentNodes();
180 if (m_tableNumber2Node
)
181 delete m_tableNumber2Node
;