ext/OGDF/ogdf/decomposition/DynamicSkeleton.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class DynamicSkeleton.
  11  *
  12  * \author Jan Papenfu&szlig;
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  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
  26  * for details.
  27  *
  28  * \par
  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.
  33  *
  34  * \par
  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.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48
  49 #ifndef OGDF_DYNAMIC_SKELETON_H
  50 #define OGDF_DYNAMIC_SKELETON_H
  51
  52
  53 #include <ogdf/decomposition/Skeleton.h>
  54
  55
  56 namespace ogdf {
  57
  58         class DynamicSPQRTree;
  59
  60
  61 //! %Skeleton graphs of nodes in a dynamic SPQR-tree.
  62 /**
  63  * The class DynamicSkeleton maintains the skeleton \a S of a node \a vT in a dynamic SPQR-tree
  64  * \a T. We call \a T the owner tree of \a S and \a vT the corresponding tree node. Let
  65  * \a G be the original graph of \a T.
  66  *
  67  * \a S consists of an undirected multi-graph \a M. If the owner tree of \a S is
  68  * a PlanarSPQRTree, then \a M represents a combinatorial embedding.
  69  * The vertices in \a M correspond to vertices in \a G. The edges in \a M are of
  70  * two types: Real edges correspond to edges in \a G and virtual edges correspond
  71  * to tree-edges in \a T having \a vT as an endpoint.
  72  *
  73  * Let \a e in \a M be a virtual edge and \a eT be the corresponding tree-edge.
  74  * Then there exists exactly one edge \a e' in another skeleton \a S' of \a T that
  75  * corresponds to \a eT as well. We call \a e' the twin edge of \a e.
  76  */
  77 class OGDF_EXPORT DynamicSkeleton : public Skeleton
  78 {
  79         friend class DynamicSPQRTree;
  80
  81 public:
  82
  83         // constructor
  84
  85         //! Creates a skeleton \a S with owner tree \a T and corresponding node \a vT.
  86         /**
  87          * \pre \a vT is a node in \a T
  88          *
  89          * \remarks Skeletons are created by the constructor of DynamicSPQRTree
  90          *          and can be accessed with the skeleton() function of DynamicSPQRTree.
  91          */
  92         DynamicSkeleton(const DynamicSPQRTree *T, node vT);
  93
  94
  95         // destructor
  96         ~DynamicSkeleton() { }
  97
  98
  99         //! Returns the owner tree \a T.
 100         const SPQRTree &owner() const;
 101
 102         //! Returns the vertex in the original graph \a G that corresponds to \a v.
 103         /**
 104          * \pre \a v is a node in \a M.
 105          */
 106         node original (node v) const;
 107
 108         //! Returns the real edge that corresponds to skeleton edge \a e
 109         /**
 110          * If \a e is virtual edge, then 0 is returned.
 111          * \pre \a e is an edge in \a M
 112          */
 113         edge realEdge (edge e) const;
 114
 115         //! Returns true iff \a e is a virtual edge.
 116         /**
 117          * \pre \a e is an edge in \a M
 118          */
 119         bool isVirtual (edge e) const {
 120                 return !realEdge(e);
 121         }
 122
 123         //! Returns the twin edge of skeleton edge \a e.
 124         /**
 125          * If \a e is not a virtual edge, then 0 is returned.
 126          * \pre \a e is an edge in \a M
 127          */
 128         edge twinEdge (edge e) const;
 129
 130         //! Returns the tree node in T containing the twin edge of skeleton edge \a e.
 131         /**
 132          * If \a e is not a virtual edge, then 0 is returned.
 133          * \pre \a e is an edge in \a M
 134          */
 135         node twinTreeNode (edge e) const;
 136
 137         OGDF_NEW_DELETE
 138
 139 protected:
 140         const DynamicSPQRTree *m_owner;     //!< owner tree
 141         NodeArray<node>        m_origNode;  //!< corresp. original node
 142         EdgeArray<edge>        m_origEdge;  //!< corresp. original edge
 143 };
 144
 145
 146 } // end namespace ogdf
 147
 148
 149 #endif