Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | Private Member Functions

ogdf::BCTree Class Reference

Static BC-trees. More...

#include <ogdf/decomposition/BCTree.h>

Inheritance diagram for ogdf::BCTree:
ogdf::DynamicBCTree ogdf::DynamicSPQRForest ogdf::DynamicSPQRTree ogdf::DynamicPlanarSPQRTree

List of all members.

Public Types

enum  GNodeType { Normal, CutVertex }
 

Enumeration type for characterizing the vertices of the original graph.

More...
enum  BNodeType { BComp, CComp }
 

Enumeration type for characterizing the BC-tree-vertices.

More...

Public Member Functions

 BCTree (Graph &G, bool callInitConnected=false)
 A constructor.
 BCTree (Graph &G, node vG, bool callInitConnected=false)
 A constructor.
virtual ~BCTree ()
 Virtual destructor.

const Graph & originalGraph () const
 returns the original graph.
const Graph & bcTree () const
 returns the BC-tree graph.
const Graph & auxiliaryGraph () const
 returns the biconnected components graph.

int numberOfBComps () const
 returns the number of B-components.
int numberOfCComps () const
 returns the number of C-components.

GNodeType typeOfGNode (node vG) const
 returns the type of a vertex of the original graph.
virtual node bcproper (node vG) const
 returns a BC-tree-vertex representing a biconnected component which a given vertex of the original graph is belonging to.
virtual node bcproper (edge eG) const
 returns the BC-tree-vertex representing the biconnected component which a given edge of the original graph is belonging to.
node rep (node vG) const
 returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph.
edge rep (edge eG) const
 returns the edge of the biconnected components graph corresponding to a given edge of the original graph.

node original (node vH)
 returns the vertex of the original graph which a given vertex of the biconnected components graph is corresponding to.
edge original (edge eH) const
 returns the edge of the original graph which a given edge of the biconnected components graph is corresponding to.

BNodeType typeOfBNode (node vB) const
 returns the type of the biconnected component represented by a given BC-tree-vertex.
const SList< edge > & hEdges (node vB) const
 returns a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by a given BC-tree-vertex.
int numberOfEdges (node vB) const
 returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex.
int numberOfNodes (node vB) const
 returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex.

node bComponent (node uG, node vG) const
 returns the BC-tree-vertex representing the B-component which two given vertices of the original graph are belonging to.
SList< node > & findPath (node sG, node tG) const
 calculates a path in the BC-tree.
SList< node > * findPathBCTree (node sB, node tB) const
 calculates a path in the BC-tree.
virtual node repVertex (node uG, node vB) const
 returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph and belonging to the representation of a certain biconnected component given by a vertex of the BC-tree.
virtual node cutVertex (node uB, node vB) const
 returns the copy of a cut-vertex in the biconnected components graph which belongs to a certain B-component and leads to another B-component.

Protected Member Functions

void init (node vG)
 Initialization.
void initNotConnected (node vG)
 Initialization for not connected graphs.
void biComp (adjEntry adjuG, node vG)
 generates the BC-tree and the biconnected components graph recursively.

virtual node parent (node vB) const
 returns the parent of a given BC-tree-vertex.
node findNCA (node uB, node vB) const
 calculates the nearest common ancestor of two vertices of the BC-tree.

Protected Attributes

Graph & m_G
 The original graph.
Graph m_B
 The BC-tree.
Graph m_H
 The biconnected components graph.

int m_numB
 The number of B-components.
int m_numC
 The number of C-components.

NodeArray< bool > m_gNode_isMarked
 Array of marks for the vertices of the original graph.
NodeArray< node > m_gNode_hNode
 An injective mapping vertices(G) -> vertices(H).
EdgeArray< edge > m_gEdge_hEdge
 A bijective mapping edges(G) -> edges(H).

NodeArray< BNodeType > m_bNode_type
 Array that contains the type of each BC-tree-vertex.
NodeArray< bool > m_bNode_isMarked
 Array of marks for the BC-tree-vertices.
NodeArray< node > m_bNode_hRefNode
 Array that contains for each BC-tree-vertex the representant of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex.
NodeArray< node > m_bNode_hParNode
 Array that contains for each BC-tree-vertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BC-tree-vertex.
NodeArray< SList< edge > > m_bNode_hEdges
 Array that contains for each BC-tree-vertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex.
NodeArray< int > m_bNode_numNodes
 Array that contains for each BC-tree-vertex the number of vertices belonging to the biconnected component represented by the respective BC-tree-vertex.

NodeArray< node > m_hNode_bNode
 A surjective mapping vertices(H) -> vertices(B).
EdgeArray< node > m_hEdge_bNode
 A surjective mapping edges(H) -> vertices(B).
NodeArray< node > m_hNode_gNode
 A surjective mapping vertices(H) -> vertices(G).
EdgeArray< edge > m_hEdge_gEdge
 A bijective mapping edges(H) -> edges(G).

int m_count
 Temporary variable.
NodeArray< int > m_number
 Temporary array.
NodeArray< int > m_lowpt
 Temporary array.
BoundedStack< adjEntry > m_eStack
 Temporary stack.
NodeArray< node > m_gtoh
 Temporary array.
SList< node > m_nodes
 Temporary list.

Private Member Functions

 BCTree (const BCTree &)
 Copy constructor is undefined!
BCTree & operator= (const BCTree &)
 Assignment operator is undefined!

Detailed Description

Static BC-trees.

This class provides static BC-trees.
The data structure consists of three parts:

Definition at line 80 of file BCTree.h.

Member Enumeration Documentation

enum ogdf::BCTree::BNodeType

Enumeration type for characterizing the BC-tree-vertices.

Enumerator:
BComp 

denotes a vertex representing a B-component.

CComp 

denotes a vertex representing a C-component.

Definition at line 104 of file BCTree.h.

enum ogdf::BCTree::GNodeType

Enumeration type for characterizing the vertices of the original graph.

Enumerator:
Normal 

denotes an ordinary vertex, i.e. not a cut-vertex.

CutVertex 

denotes a cut-vertex.

Definition at line 94 of file BCTree.h.

Constructor & Destructor Documentation

ogdf::BCTree::BCTree ( Graph &  G,
bool  callInitConnected = false 
) [inline]

A constructor.

This constructor does only call init() or initNotConnected(). BCTree(G) is equivalent to BCTree(G,G.firstNode()).

Parameters:
G is the original graph.
callInitConnected decides which init is called, default call is init()

Definition at line 376 of file BCTree.h.

ogdf::BCTree::BCTree ( Graph &  G,
node  vG,
bool  callInitConnected = false 
) [inline]

A constructor.

This constructor does only call init() or initNotConnected().

Parameters:
G is the original graph.
vG is the vertex of the original graph which the DFS algorithm starts
callInitConnected decides which init is called, default call is init()

Definition at line 390 of file BCTree.h.

virtual ogdf::BCTree::~BCTree (  )  [inline, virtual]

Virtual destructor.

Definition at line 399 of file BCTree.h.

ogdf::BCTree::BCTree ( const BCTree &   )  [private]

Copy constructor is undefined!

Member Function Documentation

const Graph& ogdf::BCTree::auxiliaryGraph (  )  const [inline]

returns the biconnected components graph.

Returns:
the biconnected components graph.

Definition at line 415 of file BCTree.h.

node ogdf::BCTree::bComponent ( node  uG,
node  vG 
) const

returns the BC-tree-vertex representing the B-component which two given vertices of the original graph are belonging to.

Parameters:
uG is a vertex of the original graph.
vG is a vertex of the original graph.
Returns:
If uG and vG are belonging to the same B-component, the very vertex of the BC-tree representing this B-component is returned. Otherwise, NULL is returned. This member function returns the representant of the correct B-component even if uG or vG or either are cut-vertices and are therefore belonging to C-components, too.

Reimplemented in ogdf::DynamicBCTree.

virtual node ogdf::BCTree::bcproper ( node  vG  )  const [inline, virtual]

returns a BC-tree-vertex representing a biconnected component which a given vertex of the original graph is belonging to.

Parameters:
vG is a vertex of the original graph.
Returns:
a vertex of the BC-tree:
  • If vG is not a cut-vertex, then typeOfGNode(vG) returns the very vertex of the BC-tree representing the unambiguous B-component which vG is belonging to.
  • If vG is a cut-vertex, then typeOfGNode(vG) returns the very vertex of the BC-tree representing the unambiguous C-component which vG is belonging to.

Reimplemented in ogdf::DynamicBCTree.

Definition at line 446 of file BCTree.h.

virtual node ogdf::BCTree::bcproper ( edge  eG  )  const [inline, virtual]

returns the BC-tree-vertex representing the biconnected component which a given edge of the original graph is belonging to.

Parameters:
eG is an edge of the original graph.
Returns:
the vertex of the BC-tree representing the B-component which eG is belonging to.

Reimplemented in ogdf::DynamicBCTree.

Definition at line 454 of file BCTree.h.

const Graph& ogdf::BCTree::bcTree (  )  const [inline]

returns the BC-tree graph.

Returns:
the BC-tree graph.

Definition at line 410 of file BCTree.h.

void ogdf::BCTree::biComp ( adjEntry  adjuG,
node  vG 
) [protected]

generates the BC-tree and the biconnected components graph recursively.

The DFS algorithm is based on J. Hopcroft and R. E. Tarjan: Algorithm 447: Efficient algorithms for graph manipulation. Comm. ACM, 16:372-378 (1973).

virtual node ogdf::BCTree::cutVertex ( node  uB,
node  vB 
) const [virtual]

returns the copy of a cut-vertex in the biconnected components graph which belongs to a certain B-component and leads to another B-component.

If two BC-tree-vertices are neighbours, then the biconnected components represented by them have exactly one cut-vertex in common. But there are several copies of this cut-vertex in the biconnected components graph, namely one copy for each biconnected component which the cut-vertex is belonging to. The member function rep() had been designed for returning the very copy of the cut-vertex belonging to the copy of the unambiguous C-component which it is belonging to, whereas this member function is designed to return the very copy of the cut-vertex connecting two biconnected components which belongs to the copy of the second one.

Parameters:
uB is a vertex of the BC-tree.
vB is a vertex of the BC-tree.
Returns:
a vertex of the biconnected components graph:
  • If uB == vB and they are representing a B-component, then cutVertex(uB,vB) returns NULL.
  • If uB == vB and they are representing a C-component, then cutVertex(uB,vB) returns the single isolated vertex of the biconnected components graph which is the copy of the C-component.
  • If uB and vB are neighbours in the BC-tree, then there exists a cut-vertex leading from the biconnected component represented by vB to the biconnected component represented by uB. cutVertex(uB,vB) returns the very copy of this vertex within the biconnected components graph which belongs to the copy of the biconnected component represented by vB.
  • Otherwise, cutVertex(uB,vB) returns NULL.

Reimplemented in ogdf::DynamicBCTree.

node ogdf::BCTree::findNCA ( node  uB,
node  vB 
) const [protected]

calculates the nearest common ancestor of two vertices of the BC-tree.

Parameters:
uB is a vertex of the BC-tree.
vB is a vertex of the BC-tree.
Returns:
the nearest common ancestor of uB and vB.
SList<node>& ogdf::BCTree::findPath ( node  sG,
node  tG 
) const

calculates a path in the BC-tree.

Parameters:
sG is a vertex of the original graph.
tG is a vertex of the original graph.
Returns:
the path from bcproper(sG) to bcproper(tG) in the BC-tree as a linear list of vertices.
Postcondition:
The SList<node> instance is created by this function and has to be destructed by the caller!
SList<node>* ogdf::BCTree::findPathBCTree ( node  sB,
node  tB 
) const

calculates a path in the BC-tree.

Parameters:
sB is a vertex of the BC-tree.
tB is a vertex of the BC-tree.
Returns:
the path from (sB) to bcproper(tB) in the BC-tree as a linear list of vertices.
Postcondition:
The SList<node> instance is created by this function and has to be destructed by the caller!
const SList<edge>& ogdf::BCTree::hEdges ( node  vB  )  const [inline]

returns a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by a given BC-tree-vertex.

Parameters:
vB is a vertex of the BC-tree.
Returns:
a linear list of edges of the biconnected components graph:
  • If vB is representing a B-component, then the edges in the list are the copies of the edges belonging to the B-component.
  • If vB is representing a C-component, then the list is empty.

Definition at line 507 of file BCTree.h.

void ogdf::BCTree::init ( node  vG  )  [protected]

Initialization.

initializes all data structures and generates the BC-tree and the biconnected components graph by call to biComp().

Parameters:
vG is the vertex of the original graph which the DFS algorithm starts with.
void ogdf::BCTree::initNotConnected ( node  vG  )  [protected]

Initialization for not connected graphs.

initializes all data structures and generates a forest of BC-trees and the biconnected components graph by call to biComp().

Parameters:
vG is the vertex of the original graph which the DFS algorithm starts first with.
int ogdf::BCTree::numberOfBComps (  )  const [inline]

returns the number of B-components.

Returns:
the number of B-components.

Definition at line 421 of file BCTree.h.

int ogdf::BCTree::numberOfCComps (  )  const [inline]

returns the number of C-components.

Returns:
the number of C-components.

Definition at line 426 of file BCTree.h.

int ogdf::BCTree::numberOfEdges ( node  vB  )  const [inline]

returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex.

Parameters:
vB is a vertex of the BC-tree.
Returns:
the number of edges belonging to the B- or C-component represented by vB, particularly 0 if it is a C-component.

Definition at line 515 of file BCTree.h.

int ogdf::BCTree::numberOfNodes ( node  vB  )  const [inline]

returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex.

Parameters:
vB is a vertex of the BC-tree.
Returns:
the number of vertices belonging to the B- or C-component represented by vB, cut-vertices inclusive, particularly 1 if it is a C-component.

Definition at line 524 of file BCTree.h.

BCTree& ogdf::BCTree::operator= ( const BCTree &   )  [private]

Assignment operator is undefined!

node ogdf::BCTree::original ( node  vH  )  [inline]

returns the vertex of the original graph which a given vertex of the biconnected components graph is corresponding to.

Parameters:
vH is a vertex of the biconnected components graph.
Returns:
the vertex of the original graph which vH is corresponding to.

Definition at line 481 of file BCTree.h.

edge ogdf::BCTree::original ( edge  eH  )  const [inline]

returns the edge of the original graph which a given edge of the biconnected components graph is corresponding to.

Parameters:
eH is an edge of the biconnected components graph.
Returns:
the edge of the original graph which eH is corresponding to.

Definition at line 488 of file BCTree.h.

const Graph& ogdf::BCTree::originalGraph (  )  const [inline]

returns the original graph.

Returns:
the original graph.

Reimplemented in ogdf::DynamicSPQRTree.

Definition at line 405 of file BCTree.h.

virtual node ogdf::BCTree::parent ( node  vB  )  const [protected, virtual]

returns the parent of a given BC-tree-vertex.

Parameters:
vB is a vertex of the BC-tree or NULL.
Returns:
the parent of vB in the BC-tree structure, if vB is not the root of the BC-tree, and NULL, if vB is NULL or the root of the BC-tree.

Reimplemented in ogdf::DynamicBCTree.

node ogdf::BCTree::rep ( node  vG  )  const [inline]

returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph.

Parameters:
vG is a vertex of the original graph.
Returns:
a vertex of the biconnected components graph:
  • If vG is not a cut-vertex, then rep(vG) returns the very vertex of the biconnected components graph corresponding to vG.
  • If vG is a cut-vertex, then rep(vG) returns the very vertex of the biconnected components graph representing the C-component which vG is belonging to.

Definition at line 466 of file BCTree.h.

edge ogdf::BCTree::rep ( edge  eG  )  const [inline]

returns the edge of the biconnected components graph corresponding to a given edge of the original graph.

Parameters:
eG is an edge of the original graph.
Returns:
the edge of the biconnected components graph corresponding to eG.

Definition at line 473 of file BCTree.h.

virtual node ogdf::BCTree::repVertex ( node  uG,
node  vB 
) const [virtual]

returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph and belonging to the representation of a certain biconnected component given by a vertex of the BC-tree.

Parameters:
uG is a vertex of the original graph.
vB is a vertex of the BC-tree.
Returns:
a vertex of the biconnected components graph:
  • If uG is belonging to the biconnected component represented by vB, then repVertex(uG,vB) returns the very vertex of the biconnected components graph corresponding to uG within the representation of vB.
  • Otherwise, repVertex(uG,vB) returns NULL.

Reimplemented in ogdf::DynamicBCTree.

BNodeType ogdf::BCTree::typeOfBNode ( node  vB  )  const [inline]

returns the type of the biconnected component represented by a given BC-tree-vertex.

Parameters:
vB is a vertex of the BC-tree.
Returns:
the type of the biconnected component represented by vB.

Definition at line 496 of file BCTree.h.

GNodeType ogdf::BCTree::typeOfGNode ( node  vG  )  const [inline]

returns the type of a vertex of the original graph.

Parameters:
vG is a vertex of the original graph.
Returns:
the type of vG.

Definition at line 433 of file BCTree.h.

Member Data Documentation

Graph ogdf::BCTree::m_B [protected]

The BC-tree.

Each vertex is representing a biconnected component (B-component) or a cut-vertex (C-component) of the original graph.

Definition at line 118 of file BCTree.h.

NodeArray<SList<edge> > ogdf::BCTree::m_bNode_hEdges [protected]

Array that contains for each BC-tree-vertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex.

For each vertex vB of the BC-tree:

  • If vB is representing a B-component, then m_bNode_hEdges[vB] is a linear list of the edges of the biconnected components graph corresponding to the edges of the original graph belonging to the B-component.
  • If vB is representing a C-component, then m_bNode_hEdges[vB] is an empty list.

Definition at line 229 of file BCTree.h.

NodeArray<node> ogdf::BCTree::m_bNode_hParNode [protected]

Array that contains for each BC-tree-vertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BC-tree-vertex.

  • If vB is the root of the BC-tree, then m_bNode_hParNode[vB] is NULL.
  • If vB is representing a B-component and vB is not the root of the BC-tree, then m_bNode_hParNode[vB] is the single isolated vertex of the biconnected components graph corresponding to the very cut-vertex, which the C-component represented by the parent of vB consists of.
  • If vB is representing to a C-component and vB is not the root of the BC-tree, then m_bNode_hParNode[vB] is the very vertex of the biconnected components graph, which is the duplicate of the cut-vertex, which the C-component consists of, in the copy of the B-component represented by the parent of vB.

Definition at line 216 of file BCTree.h.

NodeArray<node> ogdf::BCTree::m_bNode_hRefNode [protected]

Array that contains for each BC-tree-vertex the representant of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex.

For each vertex vB of the BC-tree:

  • If vB is representing a B-component and vB is the root of the BC-tree, then m_bNode_hRefNode[vB] is NULL.
  • If vB is representing a B-component and vB is not the root of the BC-tree, then m_bNode_hRefNode[vB] is the very vertex of the biconnected components graph which is the duplicate of the cut-vertex represented by the parent of vB in the copy of the B-component represented by vB.
  • If vB is representing a C-component, then m_bNode_hRefNode[vB] is the single isolated vertex of the biconnected components graph corresponding to the cut-vertex which the C-component consists of, irrespective of whether vB is the root of the BC-tree or not.

Definition at line 196 of file BCTree.h.

NodeArray<bool> ogdf::BCTree::m_bNode_isMarked [mutable, protected]

Array of marks for the BC-tree-vertices.

They are needed for searching for the nearest common ancestor of two vertices of the BC-tree.

Definition at line 177 of file BCTree.h.

NodeArray<int> ogdf::BCTree::m_bNode_numNodes [protected]

Array that contains for each BC-tree-vertex the number of vertices belonging to the biconnected component represented by the respective BC-tree-vertex.

For each vertex vB of the BC-tree:

  • If vB is representing a B-component, then m_bNode_numNodes[vB] is the number of vertices belonging to the B-component, cut-vertices inclusive.
  • If vB is representing a C-component, then m_bNode_numNodes[vB] is 1.

Definition at line 241 of file BCTree.h.

NodeArray<BNodeType> ogdf::BCTree::m_bNode_type [protected]

Array that contains the type of each BC-tree-vertex.

Definition at line 170 of file BCTree.h.

int ogdf::BCTree::m_count [protected]

Temporary variable.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 283 of file BCTree.h.

BoundedStack<adjEntry> ogdf::BCTree::m_eStack [protected]

Temporary stack.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 304 of file BCTree.h.

Graph& ogdf::BCTree::m_G [protected]

The original graph.

Definition at line 111 of file BCTree.h.

EdgeArray<edge> ogdf::BCTree::m_gEdge_hEdge [protected]

A bijective mapping edges(G) -> edges(H).

For each edge eG of the original graph, m_gEdge_hEdge[eG] is the very edge of the biconnected components graph corresponding to eG.

Definition at line 165 of file BCTree.h.

NodeArray<node> ogdf::BCTree::m_gNode_hNode [protected]

An injective mapping vertices(G) -> vertices(H).

For each vertex vG of the original graph:

  • If vG is not a cut-vertex, then m_gNode_hNode[vG] is the very vertex of the biconnected components graph corresponding to vG.
  • If vG is a cut-vertex, then m_gNode_hNode[vG] is the very vertex of the biconnected components graph representing the C-component, which vG is belonging to, as a single isolated vertex.

Definition at line 158 of file BCTree.h.

NodeArray<bool> ogdf::BCTree::m_gNode_isMarked [protected]

Array of marks for the vertices of the original graph.

They are needed during the generation of the BC-tree by DFS method.

Definition at line 147 of file BCTree.h.

NodeArray<node> ogdf::BCTree::m_gtoh [protected]

Temporary array.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 311 of file BCTree.h.

Graph ogdf::BCTree::m_H [mutable, protected]

The biconnected components graph.

This graph contains copies of the the biconnected components (B-components) and the cut-vertices (C-components) of the original graph. The copies of the B- and C-components of the original graph are not interconnected, i.e. the biconnected components graph is representing B-components as isolated biconnected subgraphs and C-components as isolated single vertices. Thus the copies of the edges and non-cut-vertices of the original graph are unambiguous, but each cut-vertex of the original graph being common to a C-component and several B-components appears multiple times.

Definition at line 131 of file BCTree.h.

EdgeArray<node> ogdf::BCTree::m_hEdge_bNode [mutable, protected]

A surjective mapping edges(H) -> vertices(B).

For each edge eH of the biconnected components graph, m_hEdge_bNode[eH] is the very BC-tree-vertex representing the unambiguous B-component, which eH is belonging to.

Definition at line 259 of file BCTree.h.

EdgeArray<edge> ogdf::BCTree::m_hEdge_gEdge [protected]

A bijective mapping edges(H) -> edges(G).

For each edge eH of the biconnected components graph, m_hEdge_gEdge[eH] is the edge of the original graph which eH is corresponding to.

Definition at line 275 of file BCTree.h.

NodeArray<node> ogdf::BCTree::m_hNode_bNode [mutable, protected]

A surjective mapping vertices(H) -> vertices(B).

For each vertex vH of the biconnected components graph, m_hNode_bNode[vH] is the very BC-tree-vertex representing the B- or C-component with respect to the copy of the very block or representation of a cut-vertex, which vH is belonging to.

Definition at line 251 of file BCTree.h.

NodeArray<node> ogdf::BCTree::m_hNode_gNode [protected]

A surjective mapping vertices(H) -> vertices(G).

For each vertex vH of the biconnected components graph, m_hNode_gNode[vH] is the vertex of the original graph which vH is corresponding to.

Definition at line 267 of file BCTree.h.

NodeArray<int> ogdf::BCTree::m_lowpt [protected]

Temporary array.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 297 of file BCTree.h.

SList<node> ogdf::BCTree::m_nodes [protected]

Temporary list.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 318 of file BCTree.h.

int ogdf::BCTree::m_numB [protected]

The number of B-components.

Definition at line 136 of file BCTree.h.

NodeArray<int> ogdf::BCTree::m_number [protected]

Temporary array.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 290 of file BCTree.h.

int ogdf::BCTree::m_numC [protected]

The number of C-components.

Definition at line 140 of file BCTree.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:16 by doxygen 1.7.1.