Static BCtrees. More...
#include <ogdf/decomposition/BCTree.h>
Public Types  
enum  BNodeType { BComp, CComp } 
Enumeration type for characterizing the BCtreevertices. 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 Graph &  originalGraph () const 
returns the original graph. More...  
const Graph &  bcTree () const 
returns the BCtree graph. More...  
const Graph &  auxiliaryGraph () const 
returns the biconnected components graph. More...  
int  numberOfBComps () const 
returns the number of Bcomponents. More...  
int  numberOfCComps () const 
returns the number of Ccomponents. 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 BCtreevertex representing a biconnected component which a given vertex of the original graph is belonging to. More...  
virtual node  bcproper (edge eG) const 
returns the BCtreevertex 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 BCtreevertex. 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 BCtreevertex. More...  
int  numberOfEdges (node vB) const 
returns the number of edges belonging to the biconnected component represented by a given BCtreevertex. More...  
int  numberOfNodes (node vB) const 
returns the number of vertices belonging to the biconnected component represented by a given BCtreevertex. More...  
node  bComponent (node uG, node vG) const 
returns the BCtreevertex representing the Bcomponent 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 BCtree. More...  
SList< node > *  findPathBCTree (node sB, node tB) const 
calculates a path in the BCtree. 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 BCtree. More...  
virtual node  cutVertex (node uB, node vB) const 
returns the copy of a cutvertex in the biconnected components graph which belongs to a certain Bcomponent and leads to another Bcomponent. More...  
Protected Member Functions  
void  biComp (adjEntry adjuG, node vG) 
generates the BCtree 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 BCtreevertex. More...  
node  findNCA (node uB, node vB) const 
calculates the nearest common ancestor of two vertices of the BCtree. More...  
Protected Attributes  
Graph  m_B 
The BCtree. More...  
Graph &  m_G 
The original graph. More...  
Graph  m_H 
The biconnected components graph. More...  
int  m_numB 
The number of Bcomponents. More...  
int  m_numC 
The number of Ccomponents. More...  
NodeArray< bool >  m_gNode_isMarked 
Array of marks for the vertices of the original graph. More...  
NodeArray< node >  m_gNode_hNode 
An injective mapping vertices(G) > vertices(H). More...  
EdgeArray< edge >  m_gEdge_hEdge 
A bijective mapping edges(G) > edges(H). More...  
NodeArray< BNodeType >  m_bNode_type 
Array that contains the type of each BCtreevertex. More...  
NodeArray< bool >  m_bNode_isMarked 
Array of marks for the BCtreevertices. More...  
NodeArray< node >  m_bNode_hRefNode 
Array that contains for each BCtreevertex the representant of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BCtreevertex. More...  
NodeArray< node >  m_bNode_hParNode 
Array that contains for each BCtreevertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BCtreevertex. More...  
NodeArray< SList< edge > >  m_bNode_hEdges 
Array that contains for each BCtreevertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BCtreevertex. More...  
NodeArray< int >  m_bNode_numNodes 
Array that contains for each BCtreevertex the number of vertices belonging to the biconnected component represented by the respective BCtreevertex. More...  
NodeArray< node >  m_hNode_bNode 
A surjective mapping vertices(H) > vertices(B). More...  
EdgeArray< node >  m_hEdge_bNode 
A surjective mapping edges(H) > vertices(B). More...  
NodeArray< node >  m_hNode_gNode 
A surjective mapping vertices(H) > vertices(G). More...  
EdgeArray< edge >  m_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< adjEntry >  m_eStack 
Temporary stack. More...  
NodeArray< node >  m_gtoh 
Temporary array. More...  
SList< node >  m_nodes 
Temporary list. More...  
Private Member Functions  
BCTree (const BCTree &)  
Copy constructor is undefined! More...  
BCTree &  operator= (const BCTree &) 
Assignment operator is undefined! More...  
Static BCtrees.
This class provides static BCtrees.
The data structure consists of three parts:

inline 
A constructor.
This constructor does only call init() or initNotConnected().
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() 

inlinevirtual 

private 
Copy constructor is undefined!

inline 
returns the BCtreevertex representing the Bcomponent which two given vertices of the original graph are belonging to.
uG  is a vertex of the original graph. 
vG  is a vertex of the original graph. 
returns a BCtreevertex representing a biconnected component which a given vertex of the original graph is belonging to.
vG  is a vertex of the original graph. 
Reimplemented in ogdf::DynamicBCTree.
returns the BCtreevertex representing the biconnected component which a given edge of the original graph is belonging to.
eG  is an edge of the original graph. 
Reimplemented in ogdf::DynamicBCTree.

inline 
generates the BCtree 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:372378 (1973).
returns the copy of a cutvertex in the biconnected components graph which belongs to a certain Bcomponent and leads to another Bcomponent.
If two BCtreevertices are neighbours, then the biconnected components represented by them have exactly one cutvertex in common. But there are several copies of this cutvertex in the biconnected components graph, namely one copy for each biconnected component which the cutvertex is belonging to. The member function rep() had been designed for returning the very copy of the cutvertex belonging to the copy of the unambiguous Ccomponent which it is belonging to, whereas this member function is designed to return the very copy of the cutvertex connecting two biconnected components which belongs to the copy of the second one.
uB  is a vertex of the BCtree. 
vB  is a vertex of the BCtree. 
Reimplemented in ogdf::DynamicBCTree.
calculates the nearest common ancestor of two vertices of the BCtree.
uB  is a vertex of the BCtree. 
vB  is a vertex of the BCtree. 
calculates a path in the BCtree.
sG  is a vertex of the original graph. 
tG  is a vertex of the original graph. 
calculates a path in the BCtree.
sB  is a vertex of the BCtree. 
tB  is a vertex of the BCtree. 
returns a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by a given BCtreevertex.
vB  is a vertex of the BCtree. 

protected 
initializes all data structures and generates the BCtree and the biconnected components graph by call to biComp().
vG  is the vertex of the original graph which the DFS algorithm starts with. 

protected 
Initialization for not connected graphs.
initializes all data structures and generates a forest of BCtrees and the biconnected components graph by call to biComp().
vG  is the vertex of the original graph which the DFS algorithm starts first with. 

inline 

inline 

inline 
returns the number of edges belonging to the biconnected component represented by a given BCtreevertex.
vB  is a vertex of the BCtree. 

inline 
returns the number of vertices belonging to the biconnected component represented by a given BCtreevertex.
vB  is a vertex of the BCtree. 

inline 
returns the parent of a given BCtreevertex.
vB  is a vertex of the BCtree or NULL. 
Reimplemented in ogdf::DynamicBCTree.
returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph.
vG  is a vertex of the original graph. 
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 BCtree.
uG  is a vertex of the original graph. 
vB  is a vertex of the BCtree. 
Reimplemented in ogdf::DynamicBCTree.

protected 
Array that contains for each BCtreevertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BCtreevertex.
For each vertex vB of the BCtree:
Array that contains for each BCtreevertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BCtreevertex.
Array that contains for each BCtreevertex the representant of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BCtreevertex.
For each vertex vB of the BCtree:

mutableprotected 

protected 
Array that contains for each BCtreevertex the number of vertices belonging to the biconnected component represented by the respective BCtreevertex.
For each vertex vB of the BCtree:

protected 

protected 
An injective mapping vertices(G) > vertices(H).
For each vertex vG of the original graph:

protected 

mutableprotected 
The biconnected components graph.
This graph contains copies of the biconnected components (Bcomponents) and the cutvertices (Ccomponents) of the original graph. The copies of the B and Ccomponents of the original graph are not interconnected, i.e. the biconnected components graph is representing Bcomponents as isolated biconnected subgraphs and Ccomponents as isolated single vertices. Thus the copies of the edges and noncutvertices of the original graph are unambiguous, but each cutvertex of the original graph being common to a Ccomponent and several Bcomponents appears multiple times.
A surjective mapping vertices(H) > vertices(B).
For each vertex vH of the biconnected components graph, m_hNode_bNode[vH] is the very BCtreevertex representing the B or Ccomponent with respect to the copy of the very block or representation of a cutvertex, which vH is belonging to.

protected 

protected 

protected 

protected 