1 /** \file 2 * \brief Declaration of class DynamicSkeleton. 3 * 4 * \author Jan Papenfuß 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/decomposition/Skeleton.h> 35 36 37 namespace ogdf { 38 39 class DynamicSPQRTree; 40 41 42 //! %Skeleton graphs of nodes in a dynamic SPQR-tree. 43 /** 44 * @ingroup dc-helper 45 * 46 * The class DynamicSkeleton maintains the skeleton \a S of a node \a vT in a dynamic SPQR-tree 47 * \a T. We call \a T the owner tree of \a S and \a vT the corresponding tree node. Let 48 * \a G be the original graph of \a T. 49 * 50 * \a S consists of an undirected multi-graph \a M. If the owner tree of \a S is 51 * a PlanarSPQRTree, then \a M represents a combinatorial embedding. 52 * The vertices in \a M correspond to vertices in \a G. The edges in \a M are of 53 * two types: Real edges correspond to edges in \a G and virtual edges correspond 54 * to tree-edges in \a T having \a vT as an endpoint. 55 * 56 * Let \a e in \a M be a virtual edge and \a eT be the corresponding tree-edge. 57 * Then there exists exactly one edge \a e' in another skeleton \a S' of \a T that 58 * corresponds to \a eT as well. We call \a e' the twin edge of \a e. 59 */ 60 class OGDF_EXPORT DynamicSkeleton : public Skeleton 61 { 62 friend class DynamicSPQRTree; 63 64 public: 65 66 // constructor 67 68 //! Creates a skeleton \a S with owner tree \p T and corresponding node \p vT. 69 /** 70 * \pre \p vT is a node in \p T 71 * 72 * \remarks Skeletons are created by the constructor of DynamicSPQRTree 73 * and can be accessed with the skeleton() function of DynamicSPQRTree. 74 */ 75 DynamicSkeleton(const DynamicSPQRTree *T, node vT); 76 77 78 // destructor ~DynamicSkeleton()79 ~DynamicSkeleton() { } 80 81 82 //! Returns the owner tree \a T. 83 const SPQRTree &owner() const override; 84 85 //! Returns the vertex in the original graph \a G that corresponds to \p v. 86 /** 87 * \pre \p v is a node in \a M. 88 */ 89 node original (node v) const override; 90 91 //! Returns the real edge that corresponds to skeleton edge \p e 92 /** 93 * If \p e is virtual edge, then 0 is returned. 94 * \pre \p e is an edge in \a M 95 */ 96 edge realEdge (edge e) const override; 97 98 //! Returns true iff \p e is a virtual edge. 99 /** 100 * \pre \p e is an edge in \a M 101 */ isVirtual(edge e)102 bool isVirtual (edge e) const override { 103 return !realEdge(e); 104 } 105 106 //! Returns the twin edge of skeleton edge \p e. 107 /** 108 * If \p e is not a virtual edge, then 0 is returned. 109 * \pre \p e is an edge in \a M 110 */ 111 edge twinEdge (edge e) const override; 112 113 //! Returns the tree node in T containing the twin edge of skeleton edge \p e. 114 /** 115 * If \p e is not a virtual edge, then 0 is returned. 116 * \pre \p e is an edge in \a M 117 */ 118 node twinTreeNode (edge e) const override; 119 120 OGDF_NEW_DELETE 121 122 protected: 123 const DynamicSPQRTree *m_owner; //!< owner tree 124 NodeArray<node> m_origNode; //!< corresp. original node 125 EdgeArray<edge> m_origEdge; //!< corresp. original edge 126 }; 127 128 } 129