ext/OGDF/ogdf/decomposition/StaticSPQRTree.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 StaticSPQRTree
  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_SPQR_TREE_H
  50 #define OGDF_STATIC_SPQR_TREE_H
  51
  52
  53 #include <ogdf/decomposition/SPQRTree.h>
  54 #include <ogdf/decomposition/StaticSkeleton.h>
  55
  56
  57 namespace ogdf {
  58
  59         class TricComp;
  60
  61 //---------------------------------------------------------
  62 // StaticSPQRTree
  63 // SPQR-tree data structure (static environment)
  64 //---------------------------------------------------------
  65
  66 /**
  67  * \brief Linear-time implementation of static SPQR-trees.
  68  *
  69  * The class StaticSPQRTree maintains the arrangement of the triconnected
  70  * components of a biconnected multi-graph \a G [Hopcroft, Tarjan 1973]
  71  * as a so-called SPQR tree \a T [Fi Battista, Tamassia, 1996]. We
  72  * call \a G the original graph of \a T.
  73  * The class StaticSPQRTree supports only the statical construction
  74  * of an SPQR-tree for a given graph \a G, dynamic updates are
  75  * not supported.
  76  *
  77  * Each node of the tree has an associated type (represented by
  78  * SPQRTree::NodeType), which is either SNode, PNode, or
  79  * RNode, and a skeleton (represented by the class StaticSkeleton).
  80  * The skeletons of the nodes of \a T are in one-to-one
  81  * correspondence to the triconnected components of \a G, i.e.,
  82  * S-nodes correspond to polygons, P-nodes to bonds, and
  83  * R-nodes to triconnected graphs.
  84  *
  85  * In our representation of SPQR-trees, Q-nodes are omitted. Instead,
  86  * the skeleton S of a node \a v in \a T contains two types of edges:
  87  * real edges, which correspond to edges in \a G, and virtual edges, which
  88  * correspond to edges in \a T having \a v as an endpoint.
  89  * There is a special edge \a er in G at which \a T is rooted, i.e., the
  90  * root node of \a T is the node whose skeleton contains the real edge
  91  * corresponding to \a er.
  92  *
  93  * The reference edge of the skeleton of the root node is \a er, the
  94  * reference edge of the skeleton \a S of a non-root node \a v is the virtual
  95  * edge in \a S that corresponds to the tree edge (parent(\a v),\a v).
  96  */
  97
  98 class OGDF_EXPORT StaticSPQRTree : public virtual SPQRTree
  99 {
 100 public:
 101
 102         friend class StaticSkeleton;
 103
 104
 105         // constructors
 106
 107         /**
 108          * \brief Creates an SPQR tree \a T for graph \a G rooted at the first edge of \a G.
 109          * \pre \a G is biconnected and contains at least 3 nodes,
 110          *      or \a G has exactly 2 nodes and at least 3 edges.
 111          */
 112         StaticSPQRTree(const Graph &G) : m_skOf(G), m_copyOf(G) { m_pGraph = &G; init(G.firstEdge()); }
 113
 114         /**
 115          * \brief Creates an SPQR tree \a T for graph \a G rooted at the edge \a e.
 116          * \pre \a e is in \a G, \a G is biconnected and contains at least 3 nodes,
 117          *      or \a G has exactly 2 nodes and at least 3 edges.
 118          */
 119         StaticSPQRTree(const Graph &G, edge e) : m_skOf(G), m_copyOf(G) { m_pGraph = &G; init(e); }
 120
 121         /**
 122          * \brief Creates an SPQR tree \a T for graph \a G rooted at the first edge of \a G.
 123          * \pre \a G is biconnected and contains at least 3 nodes,
 124          *      or \a G has exactly 2 nodes and at least 3 edges.
 125          */
 126         StaticSPQRTree(const Graph &G, TricComp &tricComp) : m_skOf(G), m_copyOf(G) { m_pGraph = &G; init(G.firstEdge(),tricComp); }
 127
 128
 129         // destructor
 130
 131         ~StaticSPQRTree();
 132
 133
 134         //
 135         // a) Access operations
 136         //
 137
 138         //! Returns a reference to the original graph \a G.
 139         const Graph &originalGraph() const { return *m_pGraph; }
 140
 141         //! Returns a reference to the tree \a T.
 142         const Graph &tree() const { return m_tree; }
 143
 144         //! Returns the edge of \a G at which \a T is rooted.
 145         edge rootEdge() const { return m_rootEdge; }
 146
 147         //! Returns the root node of \a T.
 148         node rootNode() const { return m_rootNode; }
 149
 150         //! Returns the number of S-nodes in \a T.
 151         int numberOfSNodes() const { return m_numS; }
 152
 153         //! Returns the number of P-nodes in \a T.
 154         int numberOfPNodes() const { return m_numP; }
 155
 156         //! Returns the number of R-nodes in \a T.
 157         int numberOfRNodes() const { return m_numR; }
 158
 159         /**
 160          * \brief Returns the type of node \a v.
 161          * \pre \a v is a node in \a T
 162          */
 163         NodeType typeOf(node v) const { return m_type[v]; }
 164
 165         //! Returns the list of all nodes with type \a t.
 166         List<node> nodesOfType(NodeType t) const;
 167
 168         /**
 169          * \brief Returns the skeleton of node \a v.
 170          * \pre \a v is a node in \a T
 171          */
 172         Skeleton &skeleton(node v) const { return *m_sk[v]; }
 173
 174         /**
 175          * \brief Returns the edge in skeleton of source(\a e) that corresponds to tree edge \a e.
 176          * \pre \a e is an edge in \a T
 177          */
 178         edge skeletonEdgeSrc(edge e) const { return m_skEdgeSrc[e]; }
 179
 180         /**
 181          * \brief Returns the edge in skeleton of target(\a e) that corresponds to tree edge \a e.
 182          * \pre \a e is an edge in \a T
 183          */
 184         edge skeletonEdgeTgt(edge e) const { return m_skEdgeTgt[e]; }
 185
 186         /**
 187          * \brief Returns the skeleton that contains the real edge \a e.
 188          * \pre \a e is an edge in \a G
 189          */
 190         const Skeleton &skeletonOfReal(edge e) const { return *m_skOf[e]; }
 191
 192         /**
 193          * \brief Returns the skeleton edge that corresponds to the real edge \a e.
 194          * \pre \a e is an edge in \a G
 195          */
 196         edge copyOfReal(edge e) const { return m_copyOf[e]; }
 197
 198
 199         //
 200         // b) Update operations
 201         //
 202
 203         /**
 204          * \brief Roots \a T at edge \a e and returns the new root node of \a T.
 205          * \pre \a e is an edge in \a G
 206          */
 207         node rootTreeAt(edge e);
 208
 209         /**
 210          * \brief Roots \a T at node \a v and returns \a v.
 211          * \pre \a v is a node in \a T
 212          */
 213         node rootTreeAt(node v);
 214
 215
 216 protected:
 217
 218         //! Initialization (called by constructor).
 219         void init(edge e);
 220
 221         //! Initialization (called by constructor).
 222         void init(edge eRef, TricComp &tricComp);
 223
 224         //! Recursively performs rooting of tree.
 225         void rootRec(node v, edge ef);
 226
 227         /**
 228          * \brief Recursively performs the task of adding edges (and nodes)
 229          * to the pertinent graph \a Gp for each involved skeleton graph.
 230          */
 231         void cpRec(node v, PertinentGraph &Gp) const
 232         {
 233                 edge e;
 234                 const Skeleton &S = skeleton(v);
 235
 236                 forall_edges(e,S.getGraph()) {
 237                         edge eOrig = S.realEdge(e);
 238                         if (eOrig != 0) cpAddEdge(eOrig,Gp);
 239                 }
 240
 241                 forall_adj_edges(e,v) {
 242                         node w = e->target();
 243                         if (w != v) cpRec(w,Gp);
 244                 }
 245         }
 246
 247
 248         const Graph *m_pGraph;  //!< pointer to original graph
 249         Graph        m_tree;    //!< underlying tree graph
 250
 251         edge m_rootEdge;  //!< edge of \a G at which \a T is rooted
 252         node m_rootNode;  //!< root node of \a T
 253
 254         int m_numS;  //!< number of S-nodes
 255         int m_numP;  //!< number of P-nodes
 256         int m_numR;  //!< number of R-nodes
 257
 258         NodeArray<NodeType> m_type;  //!< type of nodes in \a T
 259
 260         NodeArray<StaticSkeleton *> m_sk;         //!< pointer to skeleton of a node in \a T
 261         EdgeArray<edge>             m_skEdgeSrc;  //!< corresponding edge in skeleton(source(\a e))
 262         EdgeArray<edge>             m_skEdgeTgt;  //!< corresponding edge in skeleton(target(\a e))
 263
 264         EdgeArray<StaticSkeleton *> m_skOf;    //!< skeleton containing real edge \a e
 265         EdgeArray<edge>             m_copyOf;  //!< skeleton edge corresponding to real edge \a e
 266
 267 }; // class StaticSPQRTree
 268
 269
 270 } // end namespace ogdf
 271
 272
 273 #endif