6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class PertinentGraph.
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 ***************************************************************/
49 #ifndef OGDF_PERTINENT_GRAPH_H
50 #define OGDF_PERTINENT_GRAPH_H
55 class OGDF_EXPORT SPQRTree
;
58 //---------------------------------------------------------
60 // pertinent graph of a node in an SPQR-tree
61 //---------------------------------------------------------
62 //! Pertinent graphs of nodes in an SPQR-tree.
64 * The class PertinentGraph represents the pertinent graph \a G(\a vT)
65 * of a node \a vT in an SPQR-tree \a T with original graph \a G.
67 * The expansion graph E(\a e) of a virtual skeleton edge \a e is the skeleton graph
68 * of the twin \a e' of \a e without \a e', where each virtual edge \a eV again is
69 * replaced by its expansion graph E(\a eV). The pertinent graph \a G(\a vT) of a tree
70 * node \a vT is obtained from the skeleton \a S of \a vT, where each edge except for
71 * the reference edge of \a S is replaced by its expansion graph. Hence, if \a vT
72 * is not the root node of \a T, all but one edge in \a G(\a vT) correspond to real
73 * edges, otherwise all edges correspond to real edges.
75 * If \a P is the pertinent graph of a PlanarSPQRTree, the underlying graph
76 * represents the combinatorial embedding which is implied by the embeddings
77 * of the skeletons of \a T.
80 class OGDF_EXPORT PertinentGraph
82 friend class OGDF_EXPORT SPQRTree
;
87 // Remark: Pertinent graphs are created by the pertinentGraph()
88 // function of SPQRTree.
90 //! Creates an empty instance of type PertinentGraph.
92 * \remarks Pertinent graphs are created by the pertinentGraph()
93 * function of SPQRTree.
95 PertinentGraph() : m_vT(0) { }
97 //! Initialization of a pertinent graph of tree node \a vT.
101 m_vEdge
= m_skRefEdge
= 0;
107 //! Returns the tree node \a vT in \a T whose pertinent graph is this one.
108 node
treeNode() const {
112 //! Returns a reference to \a G(\a vT).
113 const Graph
&getGraph() const {
117 //! Returns a reference to \a G(\a vT).
122 //! Returns the edge in \a G(\a vT) corresponding to the reference edge in skeleton of \a vT.
124 * If \a vT is the root of \a T, then 0 is returned.
126 edge
referenceEdge() const {
130 //! Returns the reference edge in skeleton of \a vT.
132 * Notice that this edge may differ from the current reference edge in skeleton
133 * of \a vT if \a T has been rerooted after the construction of \a P.
135 edge
skeletonReferenceEdge() const {
139 //! Returns the vertex in \a G that corresponds to \a v.
141 * \pre \a v is a node in \a G(\a vT)
143 node
original(node v
) const {
147 //! Returns the edge in \a G that corresponds to \a e.
149 * If \a e is the reference edge, then 0 is returned.
150 * \pre \a e is an edge in \a G(\a vT)
152 edge
original(edge e
) const {
157 node m_vT
; //!< corresponding tree node
158 Graph m_P
; //!< actual graph
159 edge m_vEdge
; //!< reference edge (in \a m_P)
160 edge m_skRefEdge
; //!< reference edge (in skeleton(\a m_vT))
162 NodeArray
<node
> m_origV
; //!< corresp. original node
163 EdgeArray
<edge
> m_origE
; //!< corresp. original edge
168 } // end namespace ogdf