ext/OGDF/ogdf/decomposition/BCTree.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 BCTree
  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_BC_TREE_H
  49 #define OGDF_BC_TREE_H
  50
  51 #include <ogdf/basic/BoundedStack.h>
  52 #include <ogdf/basic/EdgeArray.h>
  53 #include <ogdf/basic/NodeArray.h>
  54 #include <ogdf/basic/SList.h>
  55
  56 namespace ogdf {
  57
  58 /**
  59  * \brief Static BC-trees.
  60  *
  61  * This class provides static BC-trees.\n
  62  * The data structure consists of three parts:
  63  * - The original graph itself (\e G) is represented by an ordinary ogdf::Graph
  64  *   structure.
  65  * - The BC-tree (\e B) is represented by an ogdf::Graph structure, each
  66  *   vertex representing a B-component or a C-component.
  67  * - The biconnected components graph (\e H), which contains a set of copies of
  68  *   the biconnected components and the cut-vertices of the original graph,
  69  *   combined but not interconnected within a single ogdf::Graph structure.
  70  */
  71 class OGDF_EXPORT BCTree {
  72
  73 public:
  74
  75 /** \enum GNodeType
  76  * \brief Enumeration type for characterizing the vertices of the original
  77  * graph.
  78  */
  79 /** \var GNodeType ogdf::BCTree::Normal
  80  * denotes an ordinary vertex, i.e. not a cut-vertex.
  81  */
  82 /** \var GNodeType ogdf::BCTree::CutVertex
  83  * denotes a cut-vertex.
  84  */
  85         enum GNodeType { Normal, CutVertex };
  86 /** \enum BNodeType
  87  * \brief Enumeration type for characterizing the BC-tree-vertices.
  88  */
  89 /** \var BNodeType ogdf::BCTree::BComp
  90  * denotes a vertex representing a B-component.
  91  */
  92 /** \var BNodeType ogdf::BCTree::CComp
  93  * denotes a vertex representing a C-component.
  94  */
  95         enum BNodeType { BComp, CComp };
  96
  97 protected:
  98
  99 /**
 100  * \brief The original graph.
 101  */
 102         Graph& m_G;
 103 /**
 104  * \brief The BC-tree.
 105  *
 106  * Each vertex is representing a biconnected component (B-component) or a
 107  * cut-vertex (C-component) of the original graph.
 108  */
 109         Graph m_B;
 110 /**
 111  * \brief The biconnected components graph.
 112  *
 113  * This graph contains copies of the the biconnected components (B-components)
 114  * and the cut-vertices (C-components) of the original graph. The copies of the
 115  * B- and C-components of the original graph are not interconnected, i.e. the
 116  * biconnected components graph is representing B-components as isolated
 117  * biconnected subgraphs and C-components as isolated single vertices. Thus the
 118  * copies of the edges and non-cut-vertices of the original graph are
 119  * unambiguous, but each cut-vertex of the original graph being common to a
 120  * C-component and several B-components appears multiple times.
 121  */
 122         mutable Graph m_H;
 123
 124 /** @{
 125  * \brief The number of B-components.
 126  */
 127         int m_numB;
 128 /**
 129  * \brief The number of C-components.
 130  */
 131         int m_numC;
 132
 133 /** @} @{
 134  * \brief Array of marks for the vertices of the original graph.
 135  *
 136  * They are needed during the generation of the BC-tree by DFS method.
 137  */
 138         NodeArray<bool> m_gNode_isMarked;
 139 /**
 140  * \brief An injective mapping vertices(\e G) -> vertices(\e H).
 141  *
 142  * For each vertex \e vG of the original graph:
 143  * - If \e vG is not a cut-vertex, then m_gNode_hNode[\e vG] is the very vertex
 144  *   of the biconnected components graph corresponding to \e vG.
 145  * - If \e vG is a cut-vertex, then m_gNode_hNode[\e vG] is the very vertex of
 146  *   the biconnected components graph representing the C-component, which \e vG
 147  *   is belonging to, as a single isolated vertex.
 148  */
 149         NodeArray<node> m_gNode_hNode;
 150 /**
 151  * \brief A bijective mapping edges(\e G) -> edges(\e H).
 152  *
 153  * For each edge \e eG of the original graph, m_gEdge_hEdge[\e eG] is the very
 154  * edge of the biconnected components graph corresponding to \e eG.
 155  */
 156         EdgeArray<edge> m_gEdge_hEdge;
 157
 158 /** @} @{
 159  * \brief Array that contains the type of each BC-tree-vertex.
 160  */
 161         NodeArray<BNodeType> m_bNode_type;
 162 /**
 163  * \brief Array of marks for the BC-tree-vertices.
 164  *
 165  * They are needed for searching for the nearest common ancestor of two
 166  * vertices of the BC-tree.
 167  */
 168         mutable NodeArray<bool> m_bNode_isMarked;
 169 /**
 170  * \brief Array that contains for each BC-tree-vertex the representant of its
 171  * parent within the subgraph in the biconnected components graph belonging to
 172  * the biconnected component represented by the respective BC-tree-vertex.
 173  *
 174  * For each vertex \e vB of the BC-tree:
 175  * - If \e vB is representing a B-component and \e vB is the root of the
 176  *   BC-tree, then m_bNode_hRefNode[\e vB] is \e NULL.
 177  * - If \e vB is representing a B-component and \e vB is not the root of the
 178  *   BC-tree, then m_bNode_hRefNode[\e vB] is the very vertex of the
 179  *   biconnected components graph which is the duplicate of the cut-vertex
 180  *   represented by the parent of \e vB <em>in the copy of the B-component
 181  *   represented by</em> \e vB.
 182  * - If \e vB is representing a C-component, then m_bNode_hRefNode[\e vB]
 183  *   is the single isolated vertex of the biconnected components graph
 184  *   corresponding to the cut-vertex which the C-component consists of,
 185  *   irrespective of whether \e vB is the root of the BC-tree or not.
 186  */
 187         NodeArray<node> m_bNode_hRefNode;
 188 /**
 189  * \brief Array that contains for each BC-tree-vertex the representant of
 190  * itself within the subgraph in the biconnected components graph belonging to
 191  * the biconnected component represented by the parent of the respective
 192  * BC-tree-vertex.
 193  *
 194  * - If \e vB is the root of the BC-tree, then m_bNode_hParNode[\e vB] is
 195  *   \e NULL.
 196  * - If \e vB is representing a B-component and \e vB is not the root of the
 197  *   BC-tree, then m_bNode_hParNode[\e vB] is the single isolated vertex
 198  *   of the biconnected components graph corresponding to the very cut-vertex,
 199  *   which the C-component represented by <em>the parent of</em> \e vB consists
 200  *   of.
 201  * - If \e vB is representing to a C-component and \e vB is not the root of the
 202  *   BC-tree, then m_bNode_hParNode[\e vB] is the very vertex of the
 203  *   biconnected components graph, which is the duplicate of the cut-vertex,
 204  *   which the C-component consists of, <em>in the copy of the B-component
 205  *   represented by the parent of</em> \e vB.
 206  */
 207         NodeArray<node> m_bNode_hParNode;
 208 /**
 209  * \brief Array that contains for each BC-tree-vertex a linear list of the
 210  * edges of the biconnected components graph belonging to the biconnected
 211  * component represented by the respective BC-tree-vertex.
 212  *
 213  * For each vertex \e vB of the BC-tree:
 214  * - If \e vB is representing a B-component, then m_bNode_hEdges[\e vB] is a
 215  *   linear list of the edges of the biconnected components graph corresponding
 216  *   to the edges of the original graph belonging to the B-component.
 217  * - If \e vB is representing a C-component, then m_bNode_hEdges[\e vB] is an
 218  *   empty list.
 219  */
 220         NodeArray<SList<edge> > m_bNode_hEdges;
 221 /**
 222  * \brief Array that contains for each BC-tree-vertex the number of vertices
 223  * belonging to the biconnected component represented by the respective
 224  * BC-tree-vertex.
 225  *
 226  * For each vertex \e vB of the BC-tree:
 227  * - If \e vB is representing a B-component, then m_bNode_numNodes[\e vB] is
 228  *   the number of vertices belonging to the B-component, cut-vertices
 229  *   inclusive.
 230  * - If \e vB is representing a C-component, then m_bNode_numNodes[\e vB] is 1.
 231  */
 232         NodeArray<int> m_bNode_numNodes;
 233
 234 /** @} @{
 235  * \brief A surjective mapping vertices(\e H) -> vertices(\e B).
 236  *
 237  * For each vertex \e vH of the biconnected components graph,
 238  * m_hNode_bNode[\e vH] is the very BC-tree-vertex representing the B- or
 239  * C-component with respect to the copy of the very block or representation
 240  * of a cut-vertex, which vH is belonging to.
 241  */
 242         mutable NodeArray<node> m_hNode_bNode;
 243 /**
 244  * \brief A surjective mapping edges(\e H) -> vertices(\e B).
 245  *
 246  * For each edge \e eH of the biconnected components graph,
 247  * m_hEdge_bNode[\e eH] is the very BC-tree-vertex representing the unambiguous
 248  * B-component, which \e eH is belonging to.
 249  */
 250         mutable EdgeArray<node> m_hEdge_bNode;
 251 /**
 252  * \brief A surjective mapping vertices(\e H) -> vertices(\e G).
 253  *
 254  * For each vertex \e vH of the biconnected components graph,
 255  * m_hNode_gNode[\e vH] is the vertex of the original graph which \e vH is
 256  * corresponding to.
 257  */
 258         NodeArray<node> m_hNode_gNode;
 259 /**
 260  * \brief A bijective mapping edges(\e H) -> edges(\e G).
 261  *
 262  * For each edge \e eH of the biconnected components graph,
 263  * m_hEdge_gEdge[\e eH] is the edge of the original graph which \e eH is
 264  * corresponding to.
 265  */
 266         EdgeArray<edge> m_hEdge_gEdge;
 267
 268 /** @} @{
 269  * \brief Temporary variable.
 270  *
 271  * It is needed for the generation of the BC-tree by DFS method. It has to be a
 272  * member of class BCTree due to recursive calls to biComp().
 273  */
 274         int m_count;
 275 /**
 276  * \brief Temporary array.
 277  *
 278  * It is needed for the generation of the BC-tree by DFS method. It has to be a
 279  * member of class BCTree due to recursive calls to biComp().
 280 */
 281         NodeArray<int> m_number;
 282 /**
 283  * \brief Temporary array.
 284  *
 285  * It is needed for the generation of the BC-tree by DFS method. It has to be a
 286  * member of class BCTree due to recursive calls to biComp().
 287  */
 288         NodeArray<int> m_lowpt;
 289 /**
 290  * \brief Temporary stack.
 291  *
 292  * It is needed for the generation of the BC-tree by DFS method. It has to be a
 293  * member of class BCTree due to recursive calls to biComp().
 294  */
 295         BoundedStack<adjEntry> m_eStack;
 296 /**
 297  * \brief Temporary array.
 298  *
 299  * It is needed for the generation of the BC-tree by DFS method. It has to be a
 300  * member of class BCTree due to recursive calls to biComp().
 301  */
 302         NodeArray<node> m_gtoh;
 303 /**
 304  * \brief Temporary list.
 305  *
 306  * It is needed for the generation of the BC-tree by DFS method. It has to be a
 307  * member of class BCTree due to recursive calls to biComp().
 308  */
 309         SList<node> m_nodes;
 310
 311 /** @}
 312  * \brief Initialization.
 313  *
 314  * initializes all data structures and generates the BC-tree and the
 315  * biconnected components graph by call to biComp().
 316  * \param vG is the vertex of the original graph which the DFS algorithm starts
 317  * with.
 318  */
 319         void init (node vG);
 320
 321 /** @}
 322  * \brief Initialization for not connected graphs
 323  *
 324  * initializes all data structures and generates a forest of BC-trees and the
 325  * biconnected components graph by call to biComp().
 326  * \param vG is the vertex of the original graph which the DFS algorithm starts
 327  * first with.
 328  */
 329         void initNotConnected (node vG);
 330 /**
 331  * \brief generates the BC-tree and the biconnected components graph
 332  * recursively.
 333  *
 334  * The DFS algorithm is based on J. Hopcroft and R. E. Tarjan: Algorithm 447:
 335  * Efficient algorithms for graph manipulation. <em>Comm. ACM</em>, 16:372-378
 336  * (1973).
 337  */
 338         void biComp (adjEntry adjuG, node vG);
 339
 340 /** @{
 341  * \brief returns the parent of a given BC-tree-vertex.
 342  * \param vB is a vertex of the BC-tree or \e NULL.
 343  * \return the parent of \a vB in the BC-tree structure, if \a vB is not the
 344  * root of the BC-tree, and \e NULL, if \a vB is \e NULL or the root of the
 345  * BC-tree.
 346  */
 347         virtual node parent (node vB) const;
 348 /**
 349  * \brief calculates the nearest common ancestor of two vertices of the
 350  * BC-tree.
 351  * \param uB is a vertex of the BC-tree.
 352  * \param vB is a vertex of the BC-tree.
 353  * \return the nearest common ancestor of \a uB and \a vB.
 354  */
 355         node findNCA (node uB, node vB) const;
 356
 357 public:
 358
 359 /** @}
 360  * \brief A constructor.
 361  *
 362  * This constructor does only call init() or initNotConnected().
 363  * BCTree(\a G) is equivalent to BCTree(<em>G</em>,<em>G</em>.firstNode()).
 364  * \param G is the original graph.
 365  * \param callInitConnected decides which init is called, default call is init()
 366  */
 367         BCTree (Graph& G, bool callInitConnected = false) : m_G(G), m_eStack(G.numberOfEdges()) {
 368                 if (!callInitConnected)
 369                         init(G.firstNode());
 370                 else initNotConnected(G.firstNode());
 371         }
 372
 373 /**
 374  * \brief A constructor.
 375  *
 376  * This constructor does only call init() or initNotConnected().
 377  * \param G is the original graph.
 378  * \param vG is the vertex of the original graph which the DFS algorithm starts
 379  * \param callInitConnected decides which init is called, default call is init()
 380  */
 381         BCTree (Graph& G, node vG, bool callInitConnected = false) : m_G(G), m_eStack(G.numberOfEdges()) {
 382                 if (!callInitConnected)
 383                         init(vG);
 384                 else initNotConnected(vG);
 385         }
 386
 387 /**
 388  * \brief Virtual destructor.
 389  */
 390         virtual ~BCTree () { }
 391
 392 /** @{
 393  * \brief returns the original graph.
 394  * \return the original graph.
 395  */
 396         const Graph& originalGraph () const { return m_G; }
 397 /**
 398  * \brief returns the BC-tree graph.
 399  * \return the BC-tree graph.
 400  */
 401         const Graph& bcTree () const { return m_B; }
 402 /**
 403  * \brief returns the biconnected components graph.
 404  * \return the biconnected components graph.
 405  */
 406         const Graph& auxiliaryGraph () const { return m_H; }
 407
 408 /** @} @{
 409  * \brief returns the number of B-components.
 410  * \return the number of B-components.
 411  */
 412         int numberOfBComps () const { return m_numB; }
 413 /**
 414  * \brief returns the number of C-components.
 415  * \return the number of C-components.
 416  */
 417         int numberOfCComps () const { return m_numC; }
 418
 419 /** @} @{
 420  * \brief returns the type of a vertex of the original graph.
 421  * \param vG is a vertex of the original graph.
 422  * \return the type of \a vG.
 423  */
 424         GNodeType typeOfGNode (node vG) const { return m_bNode_type[m_hNode_bNode[m_gNode_hNode[vG]]]==BComp ? Normal : CutVertex; }
 425 /**
 426  * \brief returns a BC-tree-vertex representing a biconnected component which a
 427  * given vertex of the original graph is belonging to.
 428  * \param vG is a vertex of the original graph.
 429  * \return a vertex of the BC-tree:
 430  * - If \a vG is not a cut-vertex, then typeOfGNode(\a vG) returns the very
 431  *   vertex of the BC-tree representing the unambiguous B-component which \a vG
 432  *   is belonging to.
 433  * - If \a vG is a cut-vertex, then typeOfGNode(\a vG) returns the very vertex
 434  *   of the BC-tree representing the unambiguous C-component which \a vG is
 435  *   belonging to.
 436  */
 437         virtual node bcproper (node vG) const { return m_hNode_bNode[m_gNode_hNode[vG]]; }
 438 /**
 439  * \brief returns the BC-tree-vertex representing the biconnected component
 440  * which a given edge of the original graph is belonging to.
 441  * \param eG is an edge of the original graph.
 442  * \return the vertex of the BC-tree representing the B-component which \a eG
 443  * is belonging to.
 444  */
 445         virtual node bcproper (edge eG) const { return m_hEdge_bNode[m_gEdge_hEdge[eG]]; }
 446 /**
 447  * \brief returns a vertex of the biconnected components graph corresponding to
 448  * a given vertex of the original graph.
 449  * \param vG is a vertex of the original graph.
 450  * \return a vertex of the biconnected components graph:
 451  * - If \a vG is not a cut-vertex, then rep(\a vG) returns the very vertex of
 452  *   the biconnected components graph corresponding to \a vG.
 453  * - If \a vG is a cut-vertex, then rep(\a vG) returns the very vertex of the
 454  *   biconnected components graph representing the C-component which \a vG is
 455  *   belonging to.
 456  */
 457         node rep (node vG) const { return m_gNode_hNode[vG]; }
 458 /**
 459  * \brief returns the edge of the biconnected components graph corresponding to
 460  * a given edge of the original graph.
 461  * \param eG is an edge of the original graph.
 462  * \return the edge of the biconnected components graph corresponding to \a eG.
 463  */
 464         edge rep (edge eG) const { return m_gEdge_hEdge[eG]; }
 465
 466 /** @} @{
 467  * \brief returns the vertex of the original graph which a given vertex of the
 468  * biconnected components graph is corresponding to.
 469  * \param vH is a vertex of the biconnected components graph.
 470  * \return the vertex of the original graph which \a vH is corresponding to.
 471  */
 472         node original (node vH) { return m_hNode_gNode[vH]; }
 473 /**
 474  * \brief returns the edge of the original graph which a given edge of the
 475  * biconnected components graph is corresponding to.
 476  * \param eH is an edge of the biconnected components graph.
 477  * \return the edge of the original graph which \a eH is corresponding to.
 478  */
 479         edge original (edge eH) const { return m_hEdge_gEdge[eH]; }
 480
 481 /** @} @{
 482  * \brief returns the type of the biconnected component represented by a given
 483  * BC-tree-vertex.
 484  * \param vB is a vertex of the BC-tree.
 485  * \return the type of the biconnected component represented by \a vB.
 486  */
 487         BNodeType typeOfBNode (node vB) const { return m_bNode_type[vB]; }
 488 /**
 489  * \brief returns a linear list of the edges of the biconnected components
 490  * graph belonging to the biconnected component represented by a given
 491  * BC-tree-vertex.
 492  * \param vB is a vertex of the BC-tree.
 493  * \return a linear list of edges of the biconnected components graph:
 494  * - If \a vB is representing a B-component, then the edges in the list are the
 495  *   copies of the edges belonging to the B-component.
 496  * - If \a vB is representing a C-component, then the list is empty.
 497  */
 498         const SList<edge>& hEdges (node vB) const { return m_bNode_hEdges[vB]; }
 499 /**
 500  * \brief returns the number of edges belonging to the biconnected component
 501  * represented by a given BC-tree-vertex.
 502  * \param vB is a vertex of the BC-tree.
 503  * \return the number of edges belonging to the B- or C-component represented
 504  * by \a vB, particularly 0 if it is a C-component.
 505  */
 506         int numberOfEdges (node vB) const { return m_bNode_hEdges[vB].size(); }
 507 /**
 508  * \brief returns the number of vertices belonging to the biconnected component
 509  * represented by a given BC-tree-vertex.
 510  * \param vB is a vertex of the BC-tree.
 511  * \return the number of vertices belonging to the B- or C-component
 512  * represented by \a vB, cut-vertices inclusive, particularly 1 if it is a
 513  * C-component.
 514  */
 515         int numberOfNodes (node vB) const { return m_bNode_numNodes[vB]; }
 516
 517 /** @} @{
 518  * \brief returns the BC-tree-vertex representing the B-component which two
 519  * given vertices of the original graph are belonging to.
 520  * \param uG is a vertex of the original graph.
 521  * \param vG is a vertex of the original graph.
 522  * \return If \a uG and \a vG are belonging to the same B-component, the very
 523  * vertex of the BC-tree representing this B-component is returned. Otherwise,
 524  * \e NULL is returned. This member function returns the representant of the
 525  * correct B-component even if \a uG or \a vG or either are cut-vertices and
 526  * are therefore belonging to C-components, too.
 527  */
 528         node bComponent (node uG, node vG) const;
 529
 530 /**
 531  * \brief calculates a path in the BC-tree.
 532  * \param sG is a vertex of the original graph.
 533  * \param tG is a vertex of the original graph.
 534  * \return the path from bcproper(\a sG) to bcproper(\a tG) in the BC-tree as a
 535  * linear list of vertices.
 536  * \post <b>The SList<node> instance is created by this function and has to be
 537  * destructed by the caller!</b>
 538  */
 539         SList<node>& findPath (node sG, node tG) const;
 540
 541 /**
 542  * \brief calculates a path in the BC-tree.
 543  * \param sB is a vertex of the BC-tree.
 544  * \param tB is a vertex of the BC-tree.
 545  * \return the path from (\a sB) to bcproper(\a tB) in the BC-tree as a
 546  * linear list of vertices.
 547  * \post <b>The SList<node> instance is created by this function and has to be
 548  * destructed by the caller!</b>
 549  */
 550         SList<node>* findPathBCTree (node sB, node tB) const;
 551
 552 /**
 553  * \brief returns a vertex of the biconnected components graph corresponding to
 554  * a given vertex of the original graph and belonging to the representation of
 555  * a certain biconnected component given by a vertex of the BC-tree.
 556  * \param uG is a vertex of the original graph.
 557  * \param vB is a vertex of the BC-tree.
 558  * \return a vertex of the biconnected components graph:
 559  * - If \a uG is belonging to the biconnected component represented by \a vB,
 560  *   then repVertex(\a uG,\a vB) returns the very vertex of the biconnected
 561  *   components graph corresponding to \a uG within the representation of
 562  *   \a vB.
 563  * - Otherwise, repVertex(\a uG,\a vB) returns \e NULL.
 564  */
 565         virtual node repVertex (node uG, node vB) const;
 566 /**
 567  * \brief returns the copy of a cut-vertex in the biconnected components graph
 568  * which belongs to a certain B-component and leads to another B-component.
 569  *
 570  * If two BC-tree-vertices are neighbours, then the biconnected components
 571  * represented by them have exactly one cut-vertex in common. But there are
 572  * several copies of this cut-vertex in the biconnected components graph,
 573  * namely one copy for each biconnected component which the cut-vertex is
 574  * belonging to. The member function rep() had been designed for returning the
 575  * very copy of the cut-vertex belonging to the copy of the unambiguous
 576  * C-component which it is belonging to, whereas this member function is
 577  * designed to return the very copy of the cut-vertex connecting two
 578  * biconnected components which belongs to the copy of the second one.
 579  * \param uB is a vertex of the BC-tree.
 580  * \param vB is a vertex of the BC-tree.
 581  * \return a vertex of the biconnected components graph:
 582  * - If \a uB == \a vB and they are representing a B-component, then
 583  *   cutVertex(\a uB,\a vB) returns \e NULL.
 584  * - If \a uB == \a vB and they are representing a C-component, then
 585  *   cutVertex(\a uB,\a vB) returns the single isolated vertex of the
 586  *   biconnected components graph which is the copy of the C-component.
 587  * - If \a uB and \a vB are \e neighbours in the BC-tree, then there exists
 588  *   a cut-vertex leading from the biconnected component represented by \a vB
 589  *   to the biconnected component represented by \a uB. cutVertex(\a uB,\a vB)
 590  *   returns the very copy of this vertex within the biconnected components
 591  *   graph which belongs to the copy of the biconnected component represented
 592  *   by \a vB.
 593  * - Otherwise, cutVertex(\a uB,\a vB) returns \e NULL.
 594  */
 595         virtual node cutVertex (node uB, node vB) const;
 596
 597 /** @}
 598  */
 599 private:
 600         // avoid automatic creation of assignment operator
 601
 602         //! Copy constructor is undefined!
 603         BCTree(const BCTree &);
 604
 605         //! Assignment operator is undefined!
 606         BCTree &operator=(const BCTree &);
 607 };
 608
 609 }
 610
 611 #endif