Dynamic BCtrees. More...
#include <ogdf/decomposition/DynamicBCTree.h>
Public Member Functions  
DynamicBCTree (Graph &G, bool callInitConnected=false)  
DynamicBCTree (Graph &G, node vG, bool callInitConnected=false)  
A constructor.  
node  bcproper (node vG) const override 
node  bcproper (edge eG) const override 
Returns the BCtreevertex representing the biconnected component which a given edge of the original graph is belonging to.  
node  repVertex (node uG, node vB) const override 
node  cutVertex (node uB, node vB) const override 
Returns the copy of a cutvertex in the biconnected components graph which belongs to a certain Bcomponent and leads to another Bcomponent.  
virtual edge  updateInsertedEdge (edge eG) 
virtual node  updateInsertedNode (edge eG, edge fG) 
Update of the dynamic BCtree after vertex insertion into the original graph.  
edge  insertEdge (node sG, node tG) 
Inserts a new edge into the original graph and updates the BCtree.  
node  insertNode (edge eG) 
Inserts a new vertex into the original graph and updates the BCtree.  
node  bComponent (node uG, node vG) const 
Public Member Functions inherited from ogdf::BCTree  
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 
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.  
Protected Member Functions  
void  init () 
node  unite (node uB, node vB, node wB) 
node  find (node vB) const 
The FIND function of the UNION/FIND structure.  
node  parent (node vB) const override 
node  condensePath (node sG, node tG) 
Performs path condensation.  
Protected Member Functions inherited from ogdf::BCTree  
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.  
node  findNCA (node uB, node vB) const 
Calculates the nearest common ancestor of two vertices of the BCtree.  
void  init (node vG) 
Protected Attributes  
NodeArray< int >  m_bNode_degree 
Array that contains for each proper BCtreevertex its degree.  
NodeArray< node >  m_bNode_owner 
Array that contains for each BCtreevertex its parent in its UNION/FINDtree structure.  
Protected Attributes inherited from ogdf::BCTree  
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).  
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.  
Friends  
class  PlanarAugmentation 
class  PlanarAugmentationFix 
Additional Inherited Members  
Public Types inherited from ogdf::BCTree  
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...  
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 54 of file DynamicBCTree.h.
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 146 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 159 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. 
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 representant of the correct Bcomponent even if uG
or vG
or either are cutvertices and are therefore belonging to Ccomponents, too.The difference between BCTree::bComponent() and DynamicBCTree::bComponent() is, that the latter one considers the UNION/FINDtree structures.
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.The difference between BCTree::bcproper() and DynamicBCTree::bcproper() is, that the latter one considers the UNION/FINDtree structures.
Reimplemented from ogdf::BCTree.
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.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. 
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 in 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.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 247 of file DynamicBCTree.h.
The FIND function of the UNION/FIND structure.
vB  is any vertex of m_B. 
vB
properly representing a biconnected component, i.e. the root of the UNION/FINDtree of vB
.

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 299 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 309 of file DynamicBCTree.h.
Returns the parent of a given BCtreevertex.
vB  is any vertex of m_B 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. The UNION/FINDtree structures are considered. 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. 
uG
is belonging to the biconnected component represented by vB
, then rep(uG
,vB
) returns the very vertex of the biconnected components graph corresponding to uG
within the representation of vB
.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. 
uB
and vB
and wB
have to be proper representants of their Bcomponents, i.e. they have to be the root vertices of their respective UNION/FINDtrees. uB
and wB
have to be adjacent to vB
. 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::DynamicSPQRTree, and ogdf::DynamicSPQRForest.
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::DynamicSPQRTree, and ogdf::DynamicSPQRForest.

friend 
Definition at line 55 of file DynamicBCTree.h.

friend 
Definition at line 56 of file DynamicBCTree.h.
Array that contains for each proper BCtreevertex its degree.
For each vertex vB of the BCtree structure:
Definition at line 84 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 70 of file DynamicBCTree.h.