ext/OGDF/ogdf/decomposition/DynamicSPQRForest.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 DynamicSPQRForest
  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 #ifndef OGDF_DYNAMIC_SPQR_FOREST_H
  49 #define OGDF_DYNAMIC_SPQR_FOREST_H
  50
  51 #include <ogdf/decomposition/DynamicBCTree.h>
  52 #include <ogdf/decomposition/SPQRTree.h>
  53
  54 namespace ogdf {
  55
  56 /**
  57  * \brief Dynamic SPQR-forest.
  58  *
  59  * This class is an extension of DynamicBCTree.\n
  60  * It provides a set of SPQR-trees for each B-component of a BC-tree.
  61  * These SPQR-trees are dynamic, i.e. there are member functions for
  62  * dynamic updates (edge insertion and node insertion).
  63  */
  64 class OGDF_EXPORT DynamicSPQRForest : public DynamicBCTree {
  65
  66 public:
  67
  68 /** \enum TNodeType
  69  * \brief Enumeration type for characterizing the SPQR-tree-vertices.
  70  */
  71 /** \var TNodeType ogdf::DynamicSPQRForest::SComp
  72  * denotes a vertex representing an S-component.
  73  */
  74 /** \var TNodeType ogdf::DynamicSPQRForest::PComp
  75  * denotes a vertex representing a P-component.
  76  */
  77 /** \var TNodeType ogdf::DynamicSPQRForest::RComp
  78  * denotes a vertex representing an R-component.
  79  */
  80         enum TNodeType {
  81                 SComp = SPQRTree::SNode,
  82                 PComp = SPQRTree::PNode,
  83                 RComp = SPQRTree::RNode
  84         };
  85
  86 protected:
  87
  88 /**
  89  * \brief A \e Graph structure containing all SPQR-trees.
  90  */
  91         mutable Graph m_T;
  92
  93 /** @{
  94  * \brief The root vertices of the SPQR-trees.
  95  *
  96  * For each vertex of the BC-tree representing a B-component, this
  97  * array contains the root vertex of the respective SPQR-tree, or
  98  * \e NULL, if the SPQR-tree does not exist.
  99  */
 100         mutable NodeArray<node> m_bNode_SPQR;
 101 /**
 102  * \brief The numbers of S-components.
 103  *
 104  * For each vertex of the BC-tree representing a B-component,
 105  * this array contains the number of S-components of the respective
 106  * SPQR-tree. If the SPQR-tree does not exist, then the array member
 107  * is undefined.
 108  */
 109         mutable NodeArray<int> m_bNode_numS;
 110 /**
 111  * \brief The numbers of P-components.
 112  *
 113  * For each vertex of the BC-tree representing a B-component,
 114  * this array contains the number of P-components of the respective
 115  * SPQR-tree. If the SPQR-tree does not exist, then the array member
 116  * is undefined.
 117  */
 118         mutable NodeArray<int> m_bNode_numP;
 119 /**
 120  * \brief The numbers of R-components.
 121  *
 122  * For each vertex of the BC-tree representing a B-component,
 123  * this array contains the number of R-components of the respective
 124  * SPQR-tree. If the SPQR-tree does not exist, then the array member
 125  * is undefined.
 126  */
 127         mutable NodeArray<int> m_bNode_numR;
 128
 129 /** @} @{
 130  * \brief The types of the SPQR-tree-vertices.
 131  */
 132         mutable NodeArray<TNodeType> m_tNode_type;
 133 /**
 134  * \brief The owners of the SPQR-tree-vertices in the UNION/FIND
 135  * structure.
 136  */
 137         mutable NodeArray<node> m_tNode_owner;
 138 /**
 139  * \brief The virtual edges leading to the parents of the
 140  * SPQR-tree-vertices.
 141  */
 142         mutable NodeArray<edge> m_tNode_hRefEdge;
 143 /**
 144  * \brief Lists of real and virtual edges belonging to
 145  * SPQR-tree-vertices.
 146  */
 147         mutable NodeArray<List<edge> > m_tNode_hEdges;
 148
 149 /** @} @{
 150  * \brief The positions of real and virtual edges in their
 151  * \e m_tNode_hEdges lists.
 152  */
 153         mutable EdgeArray<ListIterator<edge> > m_hEdge_position;
 154 /**
 155  * \brief The SPQR-tree-vertices which the real and virtual edges
 156  * are belonging to.
 157  */
 158         mutable EdgeArray<node> m_hEdge_tNode;
 159 /**
 160  * \brief The partners of virtual edges (\e NULL if real).
 161  */
 162         mutable EdgeArray<edge> m_hEdge_twinEdge;
 163
 164 /** @} @{
 165  * \brief Auxiliary array used by \e createSPQR().
 166  */
 167         mutable NodeArray<node> m_htogc;
 168 /**
 169  * \brief Auxiliary array used by \e findNCASPQR()
 170  */
 171         mutable NodeArray<bool> m_tNode_isMarked;
 172
 173 /** @}
 174  * \brief Initialization.
 175  */
 176         void init ();
 177 /**
 178  * \brief creates the SPQR-tree for a given B-component of the
 179  * BC-tree.
 180  *
 181  * An SPQR-tree belonging to a B-component of the BC-tree is only
 182  * created on demand, i.e. this member function is only called by
 183  * findSPQRTree() and - under certain circumstances - by
 184  * updateInsertedEdge().
 185  * \param vB is a vertex of the BC-tree representing a B-component.
 186  * \pre \a vB has to be the proper representative of its B-component,
 187  * i.e. it has to be the root vertex of its respective
 188  * UNION/FIND-tree.
 189  * \pre The B-component represented by \a vB must contain at least
 190  * 3 edges.
 191  */
 192         void createSPQR (node vB) const;
 193
 194 /** @{
 195  * \brief unites two SPQR-tree-vertices (UNION part of UNION/FIND).
 196  * \param vB is a vertex of the BC-tree representing a B-component.
 197  * \param sT is a vertex of the SPQR-tree belonging to \a vB.
 198  * \param tT is a vertex of the SPQR-tree belonging to \a vB.
 199  * \pre \a vB has to be the proper representative of its B-component,
 200  * i.e. it has to be the root vertex of its respective
 201  * UNION/FIND-tree.
 202  * \pre \a sT and \a tT have to be proper representatives of their
 203  * triconnected components, i.e. they have to be the root vertices of
 204  * their respective UNION/FIND-trees.
 205  * \return the proper representative of the united SPQR-tree-vertex.
 206  */
 207         node uniteSPQR (node vB, node sT, node tT);
 208 /**
 209  * \brief finds the proper representative of an SPQR-tree-vertex (FIND
 210  * part of UNION/FIND).
 211  * \param vT is any vertex of \e m_T.
 212  * \return the owner of \a vT properly representing a triconnected
 213  * component, i.e. the root of the UNION/FIND-tree of \a vT.
 214  */
 215         node findSPQR (node vT) const;
 216
 217 /** @} @{
 218  * \brief finds the nearest common ancestor of \a sT and \a tT.
 219  * \param sT is a vertex of an SPQR-tree.
 220  * \param tT is a vertex of an SPQR-tree.
 221  * \pre \a sT and \a tT must belong to the same SPQR-tree.
 222  * \pre \a sT and \a tT have to be proper representatives of their
 223  * triconnected components, i.e. they have to be the root vertices of
 224  * their respective UNION/FIND-trees.
 225  * \return the proper representative of the nearest common ancestor of
 226  * \a sT and \a tT.
 227  */
 228         node findNCASPQR (node sT, node tT) const;
 229 /**
 230  * \brief finds the shortest path between the two sets of
 231  * SPQR-tree-vertices which \a sH and \a tH are belonging to.
 232  * \param sH is a vertex of \e m_H.
 233  * \param tH is a vertex of \e m_H.
 234  * \param rT <b>is a reference!</b> It is set to the very vertex of
 235  * the found path which is nearest to the root vertex of the SPQR-tree.
 236  * \pre \a sH and \a tH must belong to the same B-component, i.e. to
 237  * the same SPQR-tree. This SPQR-tree must exist!
 238  * \return the path in the SPQR-tree as a linear list of vertices.
 239  * \post <b>The SList<node> instance is created by this function and
 240  * has to be destructed by the caller!</b>
 241  */
 242         SList<node>& findPathSPQR (node sH, node tH, node& rT) const;
 243
 244 /** @} @{
 245  * \brief updates an SPQR-tree after a new edge has been inserted into
 246  * the original graph.
 247  * \param vB is a BC-tree-vertex representing a B-component. The
 248  * SPQR-tree, which is to be updated is identified by it.
 249  * \param eG is a new edge in the original graph.
 250  * \pre \a vB has to be the proper representative of its B-component,
 251  * i.e. it has to be the root vertex of its respective
 252  * UNION/FIND-tree.
 253  * \pre Both the source and the target vertices of \a eG must belong
 254  * to the same B-component represented by \a vB.
 255  * \return the new edge of the original graph.
 256  */
 257         edge updateInsertedEdgeSPQR (node vB, edge eG);
 258 /**
 259  * \brief updates an SPQR-tree after a new vertex has been inserted
 260  * into the original graph by splitting an edge into \a eG and \a fG.
 261  * \param vB is a BC-tree-vertex representing a B-component. The
 262  * SPQR-tree, which is to be updated is identified by it.
 263  * \param eG is the incoming edge of the newly inserted vertex which
 264  * has been generated by a Graph::split() operation.
 265  * \param fG is the outgoing edge of the newly inserted vertex which
 266  * has been generated by a Graph::split() operation.
 267  * \pre The split edge must belong to the B-component which is
 268  * represented by \a vB.
 269  * \return the new vertex of the original graph.
 270  */
 271         node updateInsertedNodeSPQR (node vB, edge eG, edge fG);
 272
 273 public:
 274
 275 /** @} @{
 276  * \brief A constructor.
 277  *
 278  * This constructor does only create the dynamic BC-tree rooted at the first
 279  * edge of \a G. The data structure is prepared for dealing with SPQR-trees,
 280  * but they will only be created on demand. Cf. member functions findPathSPQR()
 281  * and updateInsertedEdge().
 282  * \param G is the original graph.
 283  */
 284         DynamicSPQRForest (Graph& G) : DynamicBCTree(G) { init(); }
 285
 286 /** @} @{
 287  * \brief finds the proper representative of the SPQR-tree-vertex which
 288  * a given real or virtual edge is belonging to.
 289  *
 290  * This member function has to be used carefully (see <b>Precondition</b>)!
 291  * \param eH is an edge of \e m_H.
 292  * \pre The respective SPQR-tree belonging to the B-component represented by
 293  * the BC-tree-vertex bcproper(\a eH) must exist! Notice, that this condition
 294  * is fulfilled, if \a eH is a member of a list gained by the hEdgesSPQR()
 295  * member function, because that member function needs an SPQR-tree-vertex as
 296  * parameter, which might have been found (and eventually created) by the
 297  * findPathSPQR() member function.
 298  * \return the proper representative of the SPQR-tree-vertex which \a eH
 299  * is belonging to.
 300  */
 301         node spqrproper (edge eH) const { return m_hEdge_tNode[eH] = findSPQR(m_hEdge_tNode[eH]); }
 302 /**
 303  * \brief returns the twin edge of a given edge of \e m_H, if it is
 304  * virtual, or \e NULL, if it is real.
 305  * \param eH is an edge of \e m_H.
 306  * \return the twin edge of \a eH, if it is virtual, or \e NULL, if it
 307  * is real.
 308  */
 309         edge twinEdge (edge eH) const { return m_hEdge_twinEdge[eH]; }
 310
 311 /** @} @{
 312  * \brief returns the type of the triconnected component represented by
 313  * a given SPQR-tree-vertex.
 314  * \param vT is a vertex of an SPQR-tree.
 315  * \pre \a vT has to be the proper representative of its triconnected
 316  * component, i.e. it has to be the root vertex of its respective
 317  * UNION/FIND-tree. This condition is particularly fulfilled if \a vT
 318  * is a member of a list gained by the findPathSPQR() member function.
 319  * \return the type of the triconnected component represented by \a vT.
 320  */
 321         TNodeType typeOfTNode (node vT) const { return m_tNode_type[vT]; }
 322 /**
 323  * \brief returns a linear list of the edges in \e m_H belonging to
 324  * the triconnected component represented by a given SPQR-tree-vertex.
 325  * \param vT is a vertex of an SPQR-tree.
 326  * \pre \a vT has to be the proper representative of its triconnected
 327  * component, i.e. it has to be the root vertex of its respective
 328  * UNION/FIND-tree. This condition is particularly fulfilled if \a vT
 329  * is a member of a list gained by the findPathSPQR() member function.
 330  * \return a linear list of the edges in \e m_H belonging to the
 331  * triconnected component represented by \a vT.
 332  */
 333         const List<edge>& hEdgesSPQR (node vT) const { return m_tNode_hEdges[vT]; }
 334 /**
 335  * \brief finds the shortest path between the two sets of
 336  * SPQR-tree-vertices which \a sH and \a tH are belonging to.
 337  * \param sH is a vertex of \e m_H.
 338  * \param tH is a vertex of \e m_H.
 339  * \pre \a sH and \a tH must belong to the same B-component, i.e. to
 340  * the same SPQR-tree. This SPQR-tree does not need to exist. If it
 341  * it does not exist, it will be created.
 342  * \return the path in the SPQR-tree as a linear list of vertices.
 343  * \post <b>The SList<node> instance is created by this function and
 344  * has to be destructed by the caller!</b>
 345  */
 346         SList<node>& findPathSPQR (node sH, node tH) const;
 347 /**
 348  * \brief returns the virtual edge which leads from one vertex of an
 349  * SPQR-tree to another one.
 350  * \param vT is a vertex of an SPQR-tree.
 351  * \param wT is a vertex of an SPQR-tree.
 352  * \pre \a vT and \a wT must belong to the same SPQR-tree and must be
 353  * adjacent.
 354  * \pre \a vT and \a wT have to be proper representatives of their
 355  * triconnected components, i.e. they have to be the root vertices of
 356  * their respective UNION/FIND-trees. This condition is particularly
 357  * fulfilled if \a vT and \a wT are members of a list gained by the
 358  * findPathSPQR() member function.
 359  * \return the virtual edge in \e m_H which belongs to \a wT and
 360  * leads to \a vT.
 361  */
 362         edge virtualEdge (node vT, node wT) const;
 363
 364 /** @} @{
 365  * \brief updates the whole data structure after a new edge has been
 366  * inserted into the original graph.
 367  *
 368  * This member function generally updates both BC- and SPQR-trees. If
 369  * any SPQR-tree of the B-components of the insertion path through
 370  * the BC-tree exists, the SPQR-tree data structure of the resulting
 371  * B-component will be valid afterwards. If none of the SPQR-trees
 372  * does exist in advance, then only the BC-tree is updated and no
 373  * SPQR-tree is created.
 374  * \param eG is a new edge in the original graph.
 375  * \return the new edge of the original graph.
 376  */
 377         edge updateInsertedEdge (edge eG);
 378 /**
 379  * \brief updates the whole data structure after a new vertex has been
 380  * inserted into the original graph by splitting an edge into \a eG
 381  * and \a fG.
 382  *
 383  * This member function updates the BC-tree at first. If the SPQR-tree
 384  * of the B-component which the split edge is belonging to does exist,
 385  * then it is updated, too. If it does not exist, it is not created.
 386  * \param eG is the incoming edge of the newly inserted vertex which
 387  * has been generated by a Graph::split() operation.
 388  * \param fG is the outgoing edge of the newly inserted vertex which
 389  * has been generated by a Graph::split() operation.
 390  * \return the new vertex of the original graph.
 391  */
 392         node updateInsertedNode (edge eG, edge fG);
 393
 394 /** @}
 395  */
 396 };
 397
 398 }
 399
 400 #endif