Dynamic BCtrees. More...
#include <ogdf/decomposition/DynamicBCTree.h>
Public Member Functions  
DynamicBCTree (Graph &G, bool callInitConnected=false)  
A constructor. More...  
DynamicBCTree (Graph &G, node vG, bool callInitConnected=false)  
A constructor. More...  
node  bcproper (node vG) const 
returns a BCtreevertex representing a biconnected component which a given vertex of the original graph is belonging to. More...  
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  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...  
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...  
virtual edge  updateInsertedEdge (edge eG) 
Update of the dynamic BCtree after edge insertion into the original graph. More...  
virtual node  updateInsertedNode (edge eG, edge fG) 
Update of the dynamic BCtree after vertex insertion into the original graph. More...  
edge  insertEdge (node sG, node tG) 
inserts a new edge into the original graph and updates the BCtree. More...  
node  insertNode (edge eG) 
inserts a new vertex into the original graph and updates the BCtree. 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...  
Public Member Functions inherited from ogdf::BCTree  
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...  
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...  
Protected Member Functions  
void  init () 
Initialization of m_bNode_owner and m_bNode_degree. More...  
node  unite (node uB, node vB, node wB) 
The UNION function of the UNION/FIND structure. More...  
node  find (node vB) const 
The FIND function of the UNION/FIND structure. More...  
node  parent (node vB) const 
returns the parent of a given BCtreevertex. More...  
node  condensePath (node sG, node tG) 
performs path condensation. More...  
Protected Member Functions inherited from ogdf::BCTree  
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...  
node  findNCA (node uB, node vB) const 
calculates the nearest common ancestor of two vertices of the BCtree. More...  
Protected Attributes  
NodeArray< int >  m_bNode_degree 
Array that contains for each proper BCtreevertex its degree. More...  
NodeArray< node >  m_bNode_owner 
Array that contains for each BCtreevertex its parent in its UNION/FINDtree structure. More...  
Protected Attributes inherited from ogdf::BCTree  
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...  
Friends  
class  PlanarAugmentation 
class  PlanarAugmentationFix 
Additional Inherited Members  
Public Types inherited from ogdf::BCTree  
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...  
Dynamic BCtrees.
This class provides dynamic BCtrees.
The main difference of the dynamic BCtree structure compared to the static one implemented by the class BCTree is, that B and Ccomponents are not any longer represented by single vertices of a BCtree graph structure but by root vertices of UNION/FINDtrees. This allows path condensation within the BCtree, when edges are inserted into the original graph. Path condensation is done by gathering BCtreevertices into a UNION/FINDtree. However, the original vertices of the BCtree remain in the m_B graph, but only those being the roots of their respective UNION/FINDtree are proper representants of the biconnected components of the original graph.
Definition at line 69 of file DynamicBCTree.h.

inline 
A constructor.
This constructor does only call BCTree::BCTree() and DynamicBCTree::init(). DynamicBCTree(G) is equivalent to DynamicBCTree(G, G.firstNode()).
G  is the original graph. 
callInitConnected  decides which init is called, default call is init(). 
Definition at line 158 of file DynamicBCTree.h.
A constructor.
This constructor does only call BCTree::BCTree() and DynamicBCTree::init().
G  is the original graph. 
vG  is the vertex of the original graph which the DFS algorithm starts with. 
callInitConnected  decides which init is called, default call is init(). 
Definition at line 167 of file DynamicBCTree.h.
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. 
The difference between BCTree::bComponent() and DynamicBCTree::bComponent() is, that the latter one considers the UNION/FINDtree structures.
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. 
The difference between BCTree::bcproper() and DynamicBCTree::bcproper() is, that the latter one considers the UNION/FINDtree structures.
Reimplemented from ogdf::BCTree.
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. 
The difference between BCTree::bcproper() and DynamicBCTree::bcproper() is, that the latter one considers the UNION/FINDtree structures.
Reimplemented from ogdf::BCTree.
performs path condensation.
This member function condenses the path from bcproper(sG) to bcproper(tG) in the BCtree into one single Bcomponent by calling findPath() and subsequently unite().
sG  is a vertex of the original graph. 
tG  is a vertex of the original graph. 
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 any vertex of m_B. 
vB  is any vertex of m_B. 
The difference between BCTree::cutVertex() and DynamicBCTree::cutVertex() is, that the latter one considers the UNION/FINDtree structures.
Reimplemented from ogdf::BCTree.
Definition at line 246 of file DynamicBCTree.h.
The FIND function of the UNION/FIND structure.
vB  is any vertex of m_B. 

protected 
Initialization of m_bNode_owner and m_bNode_degree.
inserts a new edge into the original graph and updates the BCtree.
This member function inserts a new edge between sG and tG into the original graph and then calls updateInsertedEdge().
sG  is a vertex of the original graph. 
tG  is a vertex of the original graph. 
Definition at line 293 of file DynamicBCTree.h.
inserts a new vertex into the original graph and updates the BCtree.
This member function inserts a new vertex into the original graph by splitting the edge eG and then calls updateInsertedNode().
eG  is an edge of the original graph. 
Definition at line 302 of file DynamicBCTree.h.
returns the parent of a given BCtreevertex.
vB  is any vertex of m_B or NULL. 
Reimplemented from ogdf::BCTree.
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 any vertex of m_B. 
The difference between BCTree::repVertex() and DynamicBCTree::repVertex() is, that the latter one considers the UNION/FINDtree structures.
Reimplemented from ogdf::BCTree.
Definition at line 213 of file DynamicBCTree.h.
The UNION function of the UNION/FIND structure.
uB  is a vertex of the BCtree representing a Bcomponent. 
vB  is a vertex of the BCtree representing a Ccomponent. 
wB  is a vertex of the BCtree representing a Bcomponent. 
Update of the dynamic BCtree after edge insertion into the original graph.
This member function performs online maintenance of the dynamic BCtree according to J. Westbrook and R. E. Tarjan, Maintaining BridgeConnected and Biconnected Components OnLine, Algorithmica (1992) 7:433464.
eG  is a newly inserted edge of the original graph. 
After a new edge has been inserted into the original graph by calling Graph::newEdge(), this member function updates the corresponding BCtree in \(O(\alpha(k,n))\) amortized time and the coponents graph in \(O(1 + n/k)\) amortized time per insertEdge() operation, where k is the number of such operations.
Reimplemented in ogdf::DynamicSPQRForest, and ogdf::DynamicSPQRTree.
Update of the dynamic BCtree after vertex insertion into the original graph.
This member function performs online maintenance of the dynamic BCtree according to J. Westbrook and R. E. Tarjan, Maintaining BridgeConnected and Biconnected Components OnLine, Algorithmica (1992) 7:433464.
eG  is the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation. 
fG  is the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation. 
After a new vertex has been inserted into an edge of the original graph by splitting the edge, all data structures of the DynamicBCTree class are updated by this member funtion. It takes \(O(1)\) time.
Reimplemented in ogdf::DynamicSPQRForest, and ogdf::DynamicSPQRTree.

friend 
Definition at line 71 of file DynamicBCTree.h.

friend 
Definition at line 72 of file DynamicBCTree.h.

protected 
Array that contains for each proper BCtreevertex its degree.
For each vertex vB of the BCtree structure:
Definition at line 100 of file DynamicBCTree.h.
Array that contains for each BCtreevertex its parent in its UNION/FINDtree structure.
For each vertex vB of the BCtree structure:
Definition at line 87 of file DynamicBCTree.h.