ext/OGDF/ogdf/decomposition/SPQRTree.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 SPQRTree
  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_SPQR_TREE_H
  50 #define OGDF_SPQR_TREE_H
  51
  52
  53 #include <ogdf/decomposition/Skeleton.h>
  54 #include <ogdf/decomposition/PertinentGraph.h>
  55 #include <ogdf/basic/SList.h>
  56
  57
  58 namespace ogdf {
  59
  60 //---------------------------------------------------------
  61 // SPQRTree
  62 // SPQR-tree data structure
  63 //---------------------------------------------------------
  64
  65 /**
  66  * \brief Linear-time implementation of static SPQR-trees.
  67  *
  68  * The class SPQRTree maintains the arrangement of the triconnected
  69  * components of a biconnected multi-graph \a G [Hopcroft, Tarjan 1973]
  70  * as a so-called SPQR tree \a T [Di Battista, Tamassia, 1996]. We
  71  * call \a G the original graph of \a T.
  72  *
  73  * Each node of the tree has an associated type (represented by
  74  * SPQRTree::NodeType), which is either SNode, PNode, or
  75  * RNode, and a skeleton (represented by the class Skeleton).
  76  * The skeletons of the nodes of \a T are in one-to-one
  77  * correspondence to the triconnected components of \a G, i.e.,
  78  * S-nodes correspond to polygons, P-nodes to bonds, and
  79  * R-nodes to triconnected graphs.
  80  *
  81  * In our representation of SPQR-trees, Q-nodes are omitted. Instead,
  82  * the skeleton S of a node \a v in \a T contains two types of edges:
  83  * real edges, which correspond to edges in \a G, and virtual edges, which
  84  * correspond to edges in \a T having \a v as an endpoint.
  85  * There is a special edge \a er in G at which \a T is rooted, i.e., the
  86  * root node of \a T is the node whose skeleton contains the real edge
  87  * corresponding to \a er.
  88  *
  89  * The reference edge of the skeleton of the root node is \a er, the
  90  * reference edge of the skeleton \a S of a non-root node \a v is the virtual
  91  * edge in \a S that corresponds to the tree edge (parent(\a v),\a v).
  92  */
  93
  94 class OGDF_EXPORT SPQRTree
  95 {
  96 public:
  97
  98         //! The type of a tree node in T.
  99         enum NodeType { SNode, PNode, RNode };
 100
 101
 102         // destructor
 103
 104         virtual ~SPQRTree() { }
 105
 106
 107         //
 108         // a) Access operations
 109         //
 110
 111         //! Returns a reference to the original graph \a G.
 112         virtual const Graph &originalGraph() const=0;
 113
 114         //! Returns a reference to the tree \a T.
 115         virtual const Graph &tree() const=0;
 116
 117         //! Returns the edge of \a G at which \a T is rooted.
 118         virtual edge rootEdge() const=0;
 119
 120         //! Returns the root node of \a T.
 121         virtual node rootNode() const=0;
 122
 123         //! Returns the number of S-nodes in \a T.
 124         virtual int numberOfSNodes() const=0;
 125
 126         //! Returns the number of P-nodes in \a T.
 127         virtual int numberOfPNodes() const=0;
 128
 129         //! Returns the number of R-nodes in \a T.
 130         virtual int numberOfRNodes() const=0;
 131
 132         /**
 133          * \brief Returns the type of node \a v.
 134          * \pre \a v is a node in \a T
 135          */
 136         virtual NodeType typeOf(node v) const=0;
 137
 138         //! Returns the list of all nodes with type \a t.
 139         virtual List<node> nodesOfType(NodeType t) const=0;
 140
 141         /**
 142          * \brief Returns the skeleton of node \a v.
 143          * \pre \a v is a node in \a T
 144          */
 145         virtual Skeleton &skeleton(node v) const=0;
 146
 147         /**
 148          * \brief Returns the skeleton that contains the real edge \a e.
 149          * \pre \a e is an edge in \a G
 150          */
 151         virtual const Skeleton &skeletonOfReal(edge e) const=0;
 152
 153         /**
 154          * \brief Returns the skeleton edge that corresponds to the real edge \a e.
 155          * \pre \a e is an edge in \a G
 156          */
 157         virtual edge copyOfReal(edge e) const=0;
 158
 159         /**
 160          * \brief Returns the pertinent graph of tree node \a v in \a Gp.
 161          * \pre \a v is a node in \a T
 162          */
 163         void pertinentGraph(node v, PertinentGraph &Gp) const
 164         {
 165                 if (m_cpV == 0) m_cpV = OGDF_NEW NodeArray<node>(originalGraph(),0);
 166                 NodeArray<node> &cpV = *m_cpV;
 167
 168                 Gp.init(v);
 169                 cpRec(v,Gp);
 170
 171                 const Skeleton &S = skeleton(v);
 172
 173                 edge e = Gp.m_skRefEdge = S.referenceEdge();
 174                 if (e != 0) e = Gp.m_P.newEdge(cpV[S.original(e->source())],cpV[S.original(e->target())]);
 175                 Gp.m_vEdge = e;
 176
 177                 while (!m_cpVAdded.empty()) cpV[m_cpVAdded.popFrontRet()] = 0;
 178         }
 179
 180
 181         //
 182         // b) Update operations
 183         //
 184
 185         /**
 186          * \brief Roots \a T at edge \a e and returns the new root node of \a T.
 187          * \pre \a e is an edge in \a G
 188          */
 189         virtual node rootTreeAt(edge e) =0;
 190
 191         /**
 192          * \brief Roots \a T at node \a v and returns \a v.
 193          * \pre \a v is a node in \a T
 194          */
 195         virtual node rootTreeAt(node v) =0;
 196
 197
 198         void directSkEdge(node vT, edge e, node src)
 199         {
 200                 OGDF_ASSERT(e != 0 && (src == e->source() || src == e->target()))
 201
 202                 if(e->source() != src) skeleton(vT).getGraph().reverseEdge(e);
 203         }
 204
 205         void replaceSkEdgeByPeak(node vT, edge e)
 206         {
 207                 Graph &M = skeleton(vT).getGraph();
 208                 M.reverseEdge(M.split(e));
 209         }
 210
 211
 212 protected:
 213
 214         /**
 215          * \brief Recursively performs the task of adding edges (and nodes)
 216          * to the pertinent graph \a Gp for each involved skeleton graph.
 217          */
 218         virtual void cpRec(node v, PertinentGraph &Gp) const=0;
 219
 220         //! Add an edge to \a Gp corresponding to \a eOrig.
 221         edge cpAddEdge(edge eOrig, PertinentGraph &Gp) const
 222         {
 223                 edge eP = Gp.m_P.newEdge(cpAddNode(eOrig->source(),Gp),cpAddNode(eOrig->target(),Gp));
 224                 Gp.m_origE[eP] = eOrig;
 225                 return eP;
 226         }
 227
 228         //! Add a node to \a Gp corresponding to \a vOrig if required.
 229         node cpAddNode(node vOrig, PertinentGraph &Gp) const
 230         {
 231                 node &vP = (*m_cpV)[vOrig];
 232                 if (vP == 0) {
 233                         m_cpVAdded.pushBack(vOrig);
 234                         Gp.m_origV[vP = Gp.m_P.newNode()] = vOrig;
 235                 }
 236                 return vP;
 237         }
 238
 239
 240         // auxiliary members used for computing pertinent graphs
 241         mutable NodeArray<node> *m_cpV;       //!< node in pertinent graph corresponding to an original node (auxiliary member)
 242         mutable SList<node>      m_cpVAdded;  //!< list of added nodes (auxiliary member)
 243
 244 }; // class SPQRTree
 245
 246
 247 } // end namespace ogdf
 248
 249
 250 #endif