Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::DynamicBCTree Class Reference

Dynamic BC-trees. More...

#include <ogdf/decomposition/DynamicBCTree.h>

+ Inheritance diagram for ogdf::DynamicBCTree:

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 BC-tree-vertex representing a biconnected component which a given vertex of the original graph is belonging to. More...
 
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 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...
 
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...
 
virtual edge updateInsertedEdge (edge eG)
 Update of the dynamic BC-tree after edge insertion into the original graph. More...
 
virtual node updateInsertedNode (edge eG, edge fG)
 Update of the dynamic BC-tree 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 BC-tree. More...
 
node insertNode (edge eG)
 inserts a new vertex into the original graph and updates the BC-tree. 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...
 
- 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 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...
 
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...
 

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 BC-tree-vertex. 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 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...
 
node findNCA (node uB, node vB) const
 calculates the nearest common ancestor of two vertices of the BC-tree. More...
 

Protected Attributes

NodeArray< int > m_bNode_degree
 Array that contains for each proper BC-tree-vertex its degree. More...
 
NodeArray< nodem_bNode_owner
 Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure. More...
 
- Protected Attributes inherited from ogdf::BCTree
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...
 

Friends

class PlanarAugmentation
 
class PlanarAugmentationFix
 

Additional Inherited Members

- Public Types inherited from ogdf::BCTree
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...
 

Detailed Description

Dynamic BC-trees.

This class provides dynamic BC-trees.
The main difference of the dynamic BC-tree structure compared to the static one implemented by the class BCTree is, that B- and C-components are not any longer represented by single vertices of a BC-tree graph structure but by root vertices of UNION/FIND-trees. This allows path condensation within the BC-tree, when edges are inserted into the original graph. Path condensation is done by gathering BC-tree-vertices into a UNION/FIND-tree. However, the original vertices of the BC-tree remain in the m_B graph, but only those being the roots of their respective UNION/FIND-tree are proper representants of the biconnected components of the original graph.

Definition at line 69 of file DynamicBCTree.h.

Constructor & Destructor Documentation

ogdf::DynamicBCTree::DynamicBCTree ( Graph G,
bool  callInitConnected = false 
)
inline

A constructor.

This constructor does only call BCTree::BCTree() and DynamicBCTree::init(). DynamicBCTree(G) is equivalent to DynamicBCTree(G, G.firstNode()).

Parameters
Gis the original graph.
callInitConnecteddecides which init is called, default call is init().

Definition at line 158 of file DynamicBCTree.h.

ogdf::DynamicBCTree::DynamicBCTree ( Graph G,
node  vG,
bool  callInitConnected = false 
)
inline

A constructor.

This constructor does only call BCTree::BCTree() and DynamicBCTree::init().

Parameters
Gis the original graph.
vGis the vertex of the original graph which the DFS algorithm starts with.
callInitConnecteddecides which init is called, default call is init().

Definition at line 167 of file DynamicBCTree.h.

Member Function Documentation

node ogdf::DynamicBCTree::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 representant of the correct B-component even if uG or vG or either are cut-vertices and are therefore belonging to C-components, too.

The difference between BCTree::bComponent() and DynamicBCTree::bComponent() is, that the latter one considers the UNION/FIND-tree structures.

node ogdf::DynamicBCTree::bcproper ( node  vG) const
virtual

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.

The difference between BCTree::bcproper() and DynamicBCTree::bcproper() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

node ogdf::DynamicBCTree::bcproper ( edge  eG) const
virtual

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.

The difference between BCTree::bcproper() and DynamicBCTree::bcproper() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

node ogdf::DynamicBCTree::condensePath ( node  sG,
node  tG 
)
protected

performs path condensation.

This member function condenses the path from bcproper(sG) to bcproper(tG) in the BC-tree into one single B-component by calling findPath() and subsequently unite().

Parameters
sGis a vertex of the original graph.
tGis a vertex of the original graph.
Returns
the proper representant of the resulting B-component.
node ogdf::DynamicBCTree::cutVertex ( node  uB,
node  vB 
) const
inlinevirtual

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 any vertex of m_B.
vBis any vertex of m_B.
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 in 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.

The difference between BCTree::cutVertex() and DynamicBCTree::cutVertex() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

Definition at line 246 of file DynamicBCTree.h.

node ogdf::DynamicBCTree::find ( node  vB) const
protected

The FIND function of the UNION/FIND structure.

Parameters
vBis any vertex of m_B.
Returns
the owner of vB properly representing a biconnected component, i.e. the root of the UNION/FIND-tree of vB.
void ogdf::DynamicBCTree::init ( )
protected

Initialization of m_bNode_owner and m_bNode_degree.

edge ogdf::DynamicBCTree::insertEdge ( node  sG,
node  tG 
)
inline

inserts a new edge into the original graph and updates the BC-tree.

This member function inserts a new edge between sG and tG into the original graph and then calls updateInsertedEdge().

Parameters
sGis a vertex of the original graph.
tGis a vertex of the original graph.
Returns
the new edge of the original graph.

Definition at line 293 of file DynamicBCTree.h.

node ogdf::DynamicBCTree::insertNode ( edge  eG)
inline

inserts a new vertex into the original graph and updates the BC-tree.

This member function inserts a new vertex into the original graph by splitting the edge eG and then calls updateInsertedNode().

Parameters
eGis an edge of the original graph.
Returns
the new vertex of the original graph.

Definition at line 302 of file DynamicBCTree.h.

node ogdf::DynamicBCTree::parent ( node  vB) const
protectedvirtual

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

Parameters
vBis any vertex of m_B 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. The UNION/FIND-tree structures are considered.

Reimplemented from ogdf::BCTree.

node ogdf::DynamicBCTree::repVertex ( node  uG,
node  vB 
) const
inlinevirtual

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 any vertex of m_B.
Returns
a vertex of the biconnected components graph:
  • If 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.
  • Otherwise, NULL is returned.

The difference between BCTree::repVertex() and DynamicBCTree::repVertex() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

Definition at line 213 of file DynamicBCTree.h.

node ogdf::DynamicBCTree::unite ( node  uB,
node  vB,
node  wB 
)
protected

The UNION function of the UNION/FIND structure.

Parameters
uBis a vertex of the BC-tree representing a B-component.
vBis a vertex of the BC-tree representing a C-component.
wBis a vertex of the BC-tree representing a B-component.
Precondition
uB and vB and wB have to be proper representants of their B-components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.
uB and wB have to be adjacent to vB.
Returns
the vertex properly representing the condensed B-component.
virtual edge ogdf::DynamicBCTree::updateInsertedEdge ( edge  eG)
virtual

Update of the dynamic BC-tree after edge insertion into the original graph.

This member function performs on-line maintenance of the dynamic BC-tree according to J. Westbrook and R. E. Tarjan, Maintaining Bridge-Connected and Biconnected Components On-Line, Algorithmica (1992) 7:433-464.

Parameters
eGis 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 BC-tree 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.

Returns
the new edge of the original graph.

Reimplemented in ogdf::DynamicSPQRForest, and ogdf::DynamicSPQRTree.

virtual node ogdf::DynamicBCTree::updateInsertedNode ( edge  eG,
edge  fG 
)
virtual

Update of the dynamic BC-tree after vertex insertion into the original graph.

This member function performs on-line maintenance of the dynamic BC-tree according to J. Westbrook and R. E. Tarjan, Maintaining Bridge-Connected and Biconnected Components On-Line, Algorithmica (1992) 7:433-464.

Parameters
eGis the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation.
fGis 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.

Returns
the new vertex of the original graph.

Reimplemented in ogdf::DynamicSPQRForest, and ogdf::DynamicSPQRTree.

Friends And Related Function Documentation

friend class PlanarAugmentation
friend

Definition at line 71 of file DynamicBCTree.h.

friend class PlanarAugmentationFix
friend

Definition at line 72 of file DynamicBCTree.h.

Member Data Documentation

NodeArray<int> ogdf::DynamicBCTree::m_bNode_degree
protected

Array that contains for each proper BC-tree-vertex its degree.

For each vertex vB of the BC-tree structure:

  • If vB is representing a biconnected component, then m_bNode_degree[vB] is the degree of the vertex of the BC-tree.
  • If vB is not any longer representing a biconnected component due to path condensation, then m_bNode_degree[vB] is undefined. This array is necessary, because the edges of the BC-tree are not updated during path condensation for efficiency reasons. Thus, vB->degree() != m_bNode_degree[vB]

Definition at line 100 of file DynamicBCTree.h.

NodeArray<node> ogdf::DynamicBCTree::m_bNode_owner
mutableprotected

Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure.

For each vertex vB of the BC-tree structure:

  • If vB is representing a biconnected component, then m_bNode_owner[vB] points to the vertex vB itself.
  • If vB is not any longer representing a biconnected component due to path condensation, then m_bNode_owner[vB] points to the parent of vB in its UNION/FIND-tree.

Definition at line 87 of file DynamicBCTree.h.


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