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