6 * $Date: 2012-07-04 12:19:10 +0200 (Wed, 04 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class StaticPlanarSPQRTree.
12 * \author Carsten Gutwenger
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 ***************************************************************/
47 // disable wrong warnings (VS compiler bug regarding virtual base classes)
48 #pragma warning(disable:4250)
52 #ifndef OGDF_STATIC_PLANAR_SPQR_TREE_H
53 #define OGDF_STATIC_PLANAR_SPQR_TREE_H
56 #include <ogdf/decomposition/StaticSPQRTree.h>
57 #include <ogdf/decomposition/PlanarSPQRTree.h>
63 template<class A
, class B
> class Tuple2
;
66 //---------------------------------------------------------
67 // StaticPlanarSPQRTree
68 // extension of class StaticSPQRTree for support of embedded graphs
69 //---------------------------------------------------------
71 //! SPQR-trees of planar graphs.
73 * The class StaticPlanarSPQRTree maintains the triconnected components of a
74 * planar biconnected graph G and represents all possible embeddings
75 * of G. Each skeleton graph is embedded.
77 * The current embeddings of the skeletons define an embedding of G.
78 * There are two basic operations for obtaining another embedding
79 * of G: reverse(v), which flips the skeleton of an R-node v
80 * around its poles, and swap(v,e_1,e_2), which exchanges the
81 * positions of the edges e_1 and e_2 in the skeleton of a P-node v.
84 class OGDF_EXPORT StaticPlanarSPQRTree
: public StaticSPQRTree
, public PlanarSPQRTree
90 //! Creates an SPQR tree \a T for planar graph \a G rooted at the first edge of \a G.
92 * If \a isEmbedded is set to true, \a G must represent a combinatorial
93 * embedding, i.e., the counter-clockwise order of the adjacency entries
94 * around each vertex defines an embedding.
95 * \pre \a G is planar and biconnected and contains at least 3 nodes,
96 * or \a G has exactly 2 nodes and at least 3 edges.
98 StaticPlanarSPQRTree(const Graph
&G
, bool isEmbedded
= false) :
101 PlanarSPQRTree::init(isEmbedded
);
104 //! Creates an SPQR tree \a T for planar graph \a G rooted at edge \a e.
106 * If \a isEmbedded is set to true, \a G must represent a combinatorial
107 * embedding, i.e., the counter-clockwise order of the adjacency entries
108 * around each vertex defines an embedding.
109 * \pre \a e is an edge in \a G, and \a G is planar and biconnected and
110 * contains at least 3 nodes, or \a G has exactly 2 nodes and at least 3
113 StaticPlanarSPQRTree(const Graph
&G
, edge e
, bool isEmbedded
= false) :
116 PlanarSPQRTree::init(isEmbedded
);
121 } // end namespace ogdf