1 /** \file 2 * \brief Declaration of class Skeleton. 3 * 4 * \author Carsten Gutwenger 5 * 6 * \par License: 7 * This file is part of the Open Graph Drawing Framework (OGDF). 8 * 9 * \par 10 * Copyright (C)<br> 11 * See README.md in the OGDF root directory for details. 12 * 13 * \par 14 * This program is free software; you can redistribute it and/or 15 * modify it under the terms of the GNU General Public License 16 * Version 2 or 3 as published by the Free Software Foundation; 17 * see the file LICENSE.txt included in the packaging of this file 18 * for details. 19 * 20 * \par 21 * This program is distributed in the hope that it will be useful, 22 * but WITHOUT ANY WARRANTY; without even the implied warranty of 23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 24 * GNU General Public License for more details. 25 * 26 * \par 27 * You should have received a copy of the GNU General Public 28 * License along with this program; if not, see 29 * http://www.gnu.org/copyleft/gpl.html 30 */ 31 32 #pragma once 33 34 #include <ogdf/basic/NodeArray.h> 35 #include <ogdf/basic/EdgeArray.h> 36 37 38 namespace ogdf { 39 40 class OGDF_EXPORT SPQRTree; 41 42 43 //! %Skeleton graphs of nodes in an SPQR-tree. 44 /** 45 * @ingroup dc-helper 46 * 47 * The class Skeleton maintains the skeleton \a S of a node \a vT in an SPQR-tree 48 * \a T. We call \a T the owner tree of \a S and \a vT the corresponding tree node. Let 49 * \a G be the original graph of \a T. 50 * 51 * \a S consists of an undirected multi-graph \a M. If the owner tree of \a S is 52 * a PlanarSPQRTree, then \a M represents a combinatorial embedding. 53 * The vertices in \a M correspond to vertices in \a G. The edges in \a M are of 54 * two types: Real edges correspond to edges in \a G and virtual edges correspond 55 * to tree-edges in \a T having \a vT as an endpoint. 56 * 57 * Let \a e in \a M be a virtual edge and \a eT be the corresponding tree-edge. 58 * Then there exists exactly one edge \a e' in another skeleton \a S' of \a T that 59 * corresponds to \a eT as well. We call \a e' the twin edge of \a e. 60 */ 61 class OGDF_EXPORT Skeleton 62 { 63 public: 64 65 // constructor 66 67 //! Creates a skeleton \a S with owner tree \a T and corresponding node \p vT. 68 /** 69 * \pre \p vT is a node in \a T 70 * 71 * \remarks Skeletons are created by the constructor of SPQRTree 72 * and can be accessed with the skeleton() function of SPQRTree. 73 */ Skeleton(node vT)74 explicit Skeleton(node vT) : m_treeNode(vT) { } 75 76 77 // destructor ~Skeleton()78 virtual ~Skeleton() { } 79 80 81 //! Returns the owner tree \a T. 82 virtual const SPQRTree &owner() const=0; 83 84 //! Returns the corresponding node in the owner tree \a T to which \a S belongs. treeNode()85 node treeNode() const { 86 return m_treeNode; 87 } 88 89 //! Returns the reference edge of \a S in \a M. 90 /** 91 * The reference edge is a real edge if \a S is the skeleton of the root node 92 * of \a T, and a virtual edge otherwise. 93 */ referenceEdge()94 edge referenceEdge() const { 95 return m_referenceEdge; 96 } 97 98 //! Returns a reference to the skeleton graph \a M. getGraph()99 const Graph &getGraph() const { 100 return m_M; 101 } 102 103 //! Returns a reference to the skeleton graph \a M. getGraph()104 Graph &getGraph() { 105 return m_M; 106 } 107 108 //! Returns the vertex in the original graph \a G that corresponds to \p v. 109 /** 110 * \pre \p v is a node in \a M. 111 */ 112 virtual node original (node v) const=0; 113 114 //! Returns true iff \p e is a virtual edge. 115 /** 116 * \pre \p e is an edge in \a M 117 */ 118 virtual bool isVirtual (edge e) const=0; 119 120 //! Returns the real edge that corresponds to skeleton edge \p e 121 /** 122 * If \p e is virtual edge, then 0 is returned. 123 * \pre \p e is an edge in \a M 124 */ 125 virtual edge realEdge (edge e) const=0; 126 127 //! Returns the twin edge of skeleton edge \p e. 128 /** 129 * If \p e is not a virtual edge, then 0 is returned. 130 * \pre \p e is an edge in \a M 131 */ 132 virtual edge twinEdge (edge e) const=0; 133 134 //! Returns the tree node in T containing the twin edge of skeleton edge \p e. 135 /** 136 * If \p e is not a virtual edge, then 0 is returned. 137 * \pre \p e is an edge in \a M 138 */ 139 virtual node twinTreeNode (edge e) const=0; 140 141 OGDF_NEW_DELETE 142 143 protected: 144 node m_treeNode; //!< corresp. tree node in owner tree 145 edge m_referenceEdge; //!< reference edge 146 Graph m_M; //!< actual skeleton graph 147 }; 148 149 } 150