Static BCtrees. More...
#include <ogdf/decomposition/BCTree.h>
Public Types  
enum class  BNodeType { BComp , CComp } 
Enumeration type for characterizing the BCtreevertices. More...  
enum class  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.  
BCTree (Graph &G, List< node > &vG)  
Constructor for not connected graphs.  
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 BCtree graph.  
const Graph &  auxiliaryGraph () const 
Returns the biconnected components graph.  
int  numberOfBComps () const 
Returns the number of Bcomponents.  
int  numberOfCComps () const 
Returns the number of Ccomponents.  
GNodeType  typeOfGNode (node vG) const 
virtual node  bcproper (node vG) const 
Returns a BCtreevertex representing a biconnected component which a given vertex of the original graph is belonging to.  
virtual node  bcproper (edge eG) const 
Returns the BCtreevertex 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) 
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 
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.  
int  numberOfEdges (node vB) const 
Returns the number of edges belonging to the biconnected component represented by a given BCtreevertex.  
int  numberOfNodes (node vB) const 
Returns the number of vertices belonging to the biconnected component represented by a given BCtreevertex.  
node  bComponent (node uG, node vG) const 
SList< node > &  findPath (node sG, node tG) const 
Calculates a path in the BCtree.  
SList< node > *  findPathBCTree (node sB, node tB) const 
Calculates a path in the BCtree.  
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.  
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.  
Protected Member Functions  
void  biComp (adjEntry adjuG, node vG) 
Generates the BCtree and the biconnected components graph recursively.  
void  initNotConnected (List< node > &vG) 
Initialization for not connected graphs.  
void  initNotConnected (node vG) 
Initialization for not connected graphs.  
virtual node  parent (node vB) const 
node  findNCA (node uB, node vB) const 
Calculates the nearest common ancestor of two vertices of the BCtree.  
Protected Attributes  
Graph  m_B 
The BCtree.  
Graph &  m_G 
The original graph.  
Graph  m_H 
The biconnected components graph.  
int  m_numB 
The number of Bcomponents.  
int  m_numC 
The number of Ccomponents.  
NodeArray< bool >  m_gNode_isMarked 
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 BCtreevertex.  
NodeArray< bool >  m_bNode_isMarked 
Array of marks for the BCtreevertices.  
NodeArray< node >  m_bNode_hRefNode 
Array that contains for each BCtreevertex the representantive of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BCtreevertex.  
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.  
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.  
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.  
NodeArray< node >  m_hNode_bNode 
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).  
Private Member Functions  
BCTree (const BCTree &)=delete  
Copy constructor is undefined!  
void  initBasic (node vG) 
void  initEdges () 
BCTree &  operator= (const BCTree &)=delete 
Assignment operator is undefined!  
int  m_count 
NodeArray< int >  m_number 
Temporary array.  
NodeArray< int >  m_lowpt 
Temporary array.  
ArrayBuffer< adjEntry >  m_eStack 
Temporary stack.  
NodeArray< node >  m_gtoh 
Temporary array.  
SList< node >  m_nodes 
Temporary list.  
void  init (node vG) 
Static BCtrees.
This class provides static BCtrees.
The data structure consists of three parts:

strong 

strong 
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() 
Constructor for not connected graphs.
Initializes all data structures and generates a forest of BCtrees and the biconnected components graph, but only for components containing a vertex from vG
.
G  is the original graph. 
vG  a list of vertices of the original graph from which the DFS algorithm is run. 

inlinevirtual 
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. 
uG
and vG
are belonging to the same Bcomponent, the very vertex of the BCtree representing this Bcomponent is returned. Otherwise, nullptr is returned. This member function returns the representative of the correct Bcomponent even if uG
or vG
or either are cutvertices and are therefore belonging to Ccomponents, too. 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. 
eG
is belonging to. Reimplemented in ogdf::DynamicBCTree.
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. 
vG
is not a cutvertex, then typeOfGNode(vG
) returns the very vertex of the BCtree representing the unambiguous Bcomponent which vG
is belonging to.vG
is a cutvertex, then typeOfGNode(vG
) returns the very vertex of the BCtree representing the unambiguous Ccomponent which vG
is belonging to. Reimplemented in ogdf::DynamicBCTree.
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. 
uB
== vB
and they are representing a Bcomponent, then cutVertex(uB
, vB
) returns nullptr.uB
== vB
and they are representing a Ccomponent, then cutVertex(uB
, vB
) returns the single isolated vertex of the biconnected components graph which is the copy of the Ccomponent.uB
and vB
are neighbours in the BCtree, then there exists a cutvertex 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
.uB
, vB
) returns nullptr. 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. 
uB
and vB
. Calculates a path in the BCtree.
sG  is a vertex of the original graph. 
tG  is a vertex of the original graph. 
sG
) to bcproper(tG
) in the BCtree as a linear list of vertices. Calculates a path in the BCtree.
sB  is a vertex of the BCtree. 
tB  is a vertex of the BCtree. 
sB
) to bcproper(tB
) in the BCtree as a linear list of vertices. 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. 
vB
is representing a Bcomponent, then the edges in the list are the copies of the edges belonging to the Bcomponent.vB
is representing a Ccomponent, then the list is empty. 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. 

private 
Initialization for not connected graphs.
Initializes all data structures and generates a forest of BCtrees and the biconnected components graph by call to biComp(), but only for components containing a vertex from vG
.
vG  a list of vertices of the original graph from which the DFS algorithm is run. 
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 
Returns the number of edges belonging to the biconnected component represented by a given BCtreevertex.
vB  is a vertex of the BCtree. 
vB
, particularly 0 if it is a Ccomponent. Returns the number of vertices belonging to the biconnected component represented by a given BCtreevertex.
vB  is a vertex of the BCtree. 
vB
, cutvertices inclusive, particularly 1 if it is a Ccomponent. Returns the parent of a given BCtreevertex.
vB  is a vertex of the BCtree or nullptr. 
vB
in the BCtree structure, if vB
is not the root of the BCtree, and nullptr
, if vB
is nullptr
or the root of the BCtree. 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. 
vG
is not a cutvertex, then rep(vG
) returns the very vertex of the biconnected components graph corresponding to vG
.vG
is a cutvertex, then rep(vG
) returns the very vertex of the biconnected components graph representing the Ccomponent which vG
is belonging to. 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. 
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
.uG
, vB
) returns nullptr. 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 representantive 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:
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:

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 