Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::BCTree Class Reference

Static BC-trees. More...

#include <ogdf/decomposition/BCTree.h>

+ Inheritance diagram for ogdf::BCTree:

Public Types

enum  BNodeType { BComp, CComp }
 Enumeration type for characterizing the BC-tree-vertices. More...
 
enum  GNodeType { Normal, CutVertex }
 Enumeration type for characterizing the vertices of the original graph. More...
 

Public Member Functions

 BCTree (Graph &G, bool callInitConnected=false)
 A constructor. More...
 
 BCTree (Graph &G, node vG, bool callInitConnected=false)
 A constructor. More...
 
virtual ~BCTree ()
 Virtual destructor. More...
 
const GraphoriginalGraph () const
 returns the original graph. More...
 
const GraphbcTree () const
 returns the BC-tree graph. More...
 
const GraphauxiliaryGraph () const
 returns the biconnected components graph. More...
 
int numberOfBComps () const
 returns the number of B-components. More...
 
int numberOfCComps () const
 returns the number of C-components. More...
 
GNodeType typeOfGNode (node vG) const
 returns the type of a vertex of the original graph. More...
 
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. More...
 
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. More...
 
node rep (node vG) const
 returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph. More...
 
edge rep (edge eG) const
 returns the edge of the biconnected components graph corresponding to a given edge of the original graph. More...
 
node original (node vH)
 returns the vertex of the original graph which a given vertex of the biconnected components graph is corresponding to. More...
 
edge original (edge eH) const
 returns the edge of the original graph which a given edge of the biconnected components graph is corresponding to. More...
 
BNodeType typeOfBNode (node vB) const
 returns the type of the biconnected component represented by a given BC-tree-vertex. More...
 
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. More...
 
int numberOfEdges (node vB) const
 returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex. More...
 
int numberOfNodes (node vB) const
 returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex. More...
 
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. More...
 
SList< node > & findPath (node sG, node tG) const
 calculates a path in the BC-tree. More...
 
SList< node > * findPathBCTree (node sB, node tB) const
 calculates a path in the BC-tree. More...
 
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. More...
 
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. More...
 

Protected Member Functions

void biComp (adjEntry adjuG, node vG)
 generates the BC-tree and the biconnected components graph recursively. More...
 
void init (node vG)
 Initialization. More...
 
void initNotConnected (node vG)
 Initialization for not connected graphs. More...
 
virtual node parent (node vB) const
 returns the parent of a given BC-tree-vertex. More...
 
node findNCA (node uB, node vB) const
 calculates the nearest common ancestor of two vertices of the BC-tree. More...
 

Protected Attributes

Graph m_B
 The BC-tree. More...
 
Graphm_G
 The original graph. More...
 
Graph m_H
 The biconnected components graph. More...
 
int m_numB
 The number of B-components. More...
 
int m_numC
 The number of C-components. More...
 
NodeArray< bool > m_gNode_isMarked
 Array of marks for the vertices of the original graph. More...
 
NodeArray< nodem_gNode_hNode
 An injective mapping vertices(G) -> vertices(H). More...
 
EdgeArray< edgem_gEdge_hEdge
 A bijective mapping edges(G) -> edges(H). More...
 
NodeArray< BNodeTypem_bNode_type
 Array that contains the type of each BC-tree-vertex. More...
 
NodeArray< bool > m_bNode_isMarked
 Array of marks for the BC-tree-vertices. More...
 
NodeArray< nodem_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. More...
 
NodeArray< nodem_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. More...
 
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. More...
 
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. More...
 
NodeArray< nodem_hNode_bNode
 A surjective mapping vertices(H) -> vertices(B). More...
 
EdgeArray< nodem_hEdge_bNode
 A surjective mapping edges(H) -> vertices(B). More...
 
NodeArray< nodem_hNode_gNode
 A surjective mapping vertices(H) -> vertices(G). More...
 
EdgeArray< edgem_hEdge_gEdge
 A bijective mapping edges(H) -> edges(G). More...
 
int m_count
 Temporary variable. More...
 
NodeArray< int > m_number
 Temporary array. More...
 
NodeArray< int > m_lowpt
 Temporary array. More...
 
BoundedStack< adjEntrym_eStack
 Temporary stack. More...
 
NodeArray< nodem_gtoh
 Temporary array. More...
 
SList< nodem_nodes
 Temporary list. More...
 

Private Member Functions

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

Detailed Description

Static BC-trees.

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

  • The original graph itself (G) is represented by an ordinary ogdf::Graph structure.
  • The BC-tree (B) is represented by an ogdf::Graph structure, each vertex representing a B-component or a C-component.
  • The biconnected components graph (H), which contains a set of copies of the biconnected components and the cut-vertices of the original graph, combined but not interconnected within a single ogdf::Graph structure.

Definition at line 71 of file BCTree.h.

Member Enumeration Documentation

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 95 of file BCTree.h.

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 85 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
Gis the original graph.
callInitConnecteddecides which init is called, default call is init()

Definition at line 367 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
Gis the original graph.
vGis the vertex of the original graph which the DFS algorithm starts
callInitConnecteddecides which init is called, default call is init()

Definition at line 381 of file BCTree.h.

virtual ogdf::BCTree::~BCTree ( )
inlinevirtual

Virtual destructor.

Definition at line 390 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 406 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
uGis a vertex of the original graph.
vGis 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 representative of the correct B-component even if uG or vG or either are cut-vertices and are therefore belonging to C-components, too.
virtual node ogdf::BCTree::bcproper ( node  vG) const
inlinevirtual

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

Parameters
vGis 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 437 of file BCTree.h.

virtual node ogdf::BCTree::bcproper ( edge  eG) const
inlinevirtual

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

Parameters
eGis 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 445 of file BCTree.h.

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

returns the BC-tree graph.

Returns
the BC-tree graph.

Definition at line 401 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
uBis a vertex of the BC-tree.
vBis 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
uBis a vertex of the BC-tree.
vBis 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
sGis a vertex of the original graph.
tGis 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
sBis a vertex of the BC-tree.
tBis 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
vBis 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 498 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
vGis 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
vGis 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 412 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 417 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
vBis 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 506 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
vBis 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 515 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
vHis a vertex of the biconnected components graph.
Returns
the vertex of the original graph which vH is corresponding to.

Definition at line 472 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
eHis an edge of the biconnected components graph.
Returns
the edge of the original graph which eH is corresponding to.

Definition at line 479 of file BCTree.h.

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

returns the original graph.

Returns
the original graph.

Definition at line 396 of file BCTree.h.

virtual node ogdf::BCTree::parent ( node  vB) const
protectedvirtual

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

Parameters
vBis 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
vGis 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 457 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
eGis an edge of the original graph.
Returns
the edge of the biconnected components graph corresponding to eG.

Definition at line 464 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
uGis a vertex of the original graph.
vBis 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
vBis a vertex of the BC-tree.
Returns
the type of the biconnected component represented by vB.

Definition at line 487 of file BCTree.h.

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

returns the type of a vertex of the original graph.

Parameters
vGis a vertex of the original graph.
Returns
the type of vG.

Definition at line 424 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 109 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 220 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 207 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 187 of file BCTree.h.

NodeArray<bool> ogdf::BCTree::m_bNode_isMarked
mutableprotected

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 168 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 232 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 161 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 274 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 295 of file BCTree.h.

Graph& ogdf::BCTree::m_G
protected

The original graph.

Definition at line 102 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 156 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 149 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 138 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 302 of file BCTree.h.

Graph ogdf::BCTree::m_H
mutableprotected

The biconnected components graph.

This graph contains copies of 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 122 of file BCTree.h.

EdgeArray<node> ogdf::BCTree::m_hEdge_bNode
mutableprotected

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 250 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 266 of file BCTree.h.

NodeArray<node> ogdf::BCTree::m_hNode_bNode
mutableprotected

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 242 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 258 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 288 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 309 of file BCTree.h.

int ogdf::BCTree::m_numB
protected

The number of B-components.

Definition at line 127 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 281 of file BCTree.h.

int ogdf::BCTree::m_numC
protected

The number of C-components.

Definition at line 131 of file BCTree.h.


The documentation for this class was generated from the following file: