ext/OGDF/ogdf/decomposition/StaticSkeleton.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 StaticSkeleton.
  11  *
  12  * \author Carsten Gutwenger
  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_STATIC_SKELETON_H
  50 #define OGDF_STATIC_SKELETON_H
  51
  52
  53 #include <ogdf/decomposition/Skeleton.h>
  54
  55
  56 namespace ogdf {
  57
  58         class OGDF_EXPORT StaticSPQRTree;
  59
  60
  61 //! %Skeleton graphs of nodes in a static SPQR-tree.
  62 /**
  63  * The class StaticSkeleton maintains the skeleton \a S of a node \a vT in a static 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 StaticSkeleton : public Skeleton
  78 {
  79         friend class OGDF_EXPORT StaticSPQRTree;
  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 SPQRTree
  90          *          and can be accessed with the skeleton() function of SPQRTree.
  91          */
  92         StaticSkeleton(const StaticSPQRTree *T, node vT);
  93
  94
  95         // destructor
  96         ~StaticSkeleton() { }
  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                 return m_orig[v];
 108         }
 109
 110         //! Returns true iff \a e is a virtual edge.
 111         /**
 112          * \pre \a e is an edge in \a M
 113          */
 114         bool isVirtual (edge e) const {
 115                 return (m_real[e] == 0);
 116         }
 117
 118         //! Returns the real edge that corresponds to skeleton edge \a e
 119         /**
 120          * If \a e is virtual edge, then 0 is returned.
 121          * \pre \a e is an edge in \a M
 122          */
 123         edge realEdge (edge e) const {
 124                 return m_real[e];
 125         }
 126
 127         //! Returns the twin edge of skeleton edge \a e.
 128         /**
 129          * If \a e is not a virtual edge, then 0 is returned.
 130          * \pre \a e is an edge in \a M
 131          */
 132         edge twinEdge (edge e) const;
 133
 134         //! Returns the tree node in T containing the twin edge of skeleton edge \a e.
 135         /**
 136          * If \a e is not a virtual edge, then 0 is returned.
 137          * \pre \a e is an edge in \a M
 138          */
 139         node twinTreeNode (edge e) const;
 140
 141         //! Returns the tree edge which is associated with skeleton edge \a e.
 142         /**
 143          * If \a e is not a virtual edge, then 0 is retuned.
 144          * \pre \a e is an edge in \a M
 145          */
 146         edge treeEdge (edge e) const {
 147                 return m_treeEdge[e];
 148         }
 149
 150         OGDF_MALLOC_NEW_DELETE
 151
 152 protected:
 153         const StaticSPQRTree *m_owner;     //!< owner tree
 154         NodeArray<node>       m_orig;      //!< corresp. original node
 155         EdgeArray<edge>       m_real;      //!< corresp. original edge (0 if virtual)
 156         EdgeArray<edge>       m_treeEdge;  //!< corresp. tree edge (0 if real)
 157 };
 158
 159
 160 } // end namespace ogdf
 161
 162
 163 #endif