Dynamic BC-trees. More...
#include <ogdf/decomposition/DynamicBCTree.h>
Public Member Functions | |
DynamicBCTree (Graph &G, bool not_connected=false) | |
DynamicBCTree (Graph &G, node vG, bool not_connected=false) | |
A constructor. More... | |
node | bccomp (node vH) const override |
node | bccomp (edge eH) const override |
Returns the BC-tree-vertex representing the biconnected component which a given edge of the auxiliary graph is belonging to. More... | |
node | repVertex (node uG, node vB) const override |
node | cutVertex (node uB, node vB) const override |
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) |
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 |
Public Member Functions inherited from ogdf::BCTree | |
BCTree (BCTree &&move)=delete | |
BCTree (const BCTree ©)=delete | |
BCTree (Graph &G, bool not_connected=false) | |
A constructor. More... | |
BCTree (Graph &G, List< node > &vG) | |
Constructor for not connected graphs. More... | |
BCTree (Graph &G, node vG, bool not_connected=false) | |
A constructor. More... | |
virtual | ~BCTree () |
Virtual destructor. More... | |
void | consistencyCheck () const |
Asserts that this BCTree is consistent. More... | |
BCTree & | operator= (BCTree &&move)=delete |
BCTree & | operator= (const BCTree ©)=delete |
const Graph & | originalGraph () const |
Returns the original graph. More... | |
const Graph & | bcTree () const |
Returns the BC-tree graph. More... | |
const Graph & | auxiliaryGraph () 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 |
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 | 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) const |
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 |
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 |
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 () |
node | unite (node uB, node vB, node wB) |
node | find (node vB) const |
The FIND function of the UNION/FIND structure. More... | |
node | parent (node vB) const override |
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 | initNotConnected (List< node > &vG) |
Initialization for not connected graphs. 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... | |
void | init (node vG) |
Protected Attributes | |
NodeArray< int > | m_bNode_degree |
Array that contains for each proper BC-tree-vertex its degree. More... | |
NodeArray< node > | m_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... | |
Graph & | m_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 |
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 BC-tree-vertex. More... | |
NodeArray< bool > | m_bNode_isMarked |
Array of marks for the BC-tree-vertices. More... | |
NodeArray< node > | m_bNode_hRefNode |
Array that contains for each BC-tree-vertex the representantive 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< node > | m_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< node > | m_hNode_bNode |
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 |
NodeArray< int > | m_number |
Temporary array. More... | |
NodeArray< int > | m_lowpt |
Temporary array. More... | |
ArrayBuffer< 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 { BNodeType::BComp, BNodeType::CComp } |
Enumeration type for characterizing the BC-tree-vertices. More... | |
enum | GNodeType { GNodeType::Normal, GNodeType::CutVertex } |
Enumeration type for characterizing the vertices of the original graph. More... | |
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 56 of file DynamicBCTree.h.
|
inlineexplicit |
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. |
not_connected | if set to true, will call initNotConnected() to process all connected components. Otherwise, only the connected component of G.firstNode() will be processed. |
Definition at line 149 of file DynamicBCTree.h.
|
inlineexplicit |
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, defaults to G.firstNode(). |
not_connected | if set to true, will call initNotConnected() to process all connected components. Otherwise, only the connected component of vG will be processed. |
Definition at line 161 of file DynamicBCTree.h.
Returns the BC-tree-vertex representing the biconnected component which a given edge of the auxiliary graph is belonging to.
eH | is an edge of the auxiliary graph. |
eH
is belonging to.The difference between BCTree::bccomp() and DynamicBCTree::bccomp() is, that the latter one considers the UNION/FIND-tree structures.
Reimplemented from ogdf::BCTree.
Returns a BC-tree-vertex representing a biconnected component which a given vertex of the auxiliary graph is belonging to.
vH | is a vertex of the auxiliary graph. |
vH
is not a cut-vertex, then bcproper(vH
) returns the very vertex of the BC-tree representing the unambiguous B-component which vH
is belonging to.vH
is a cut-vertex, then bcproper(vH
) returns the very vertex of the BC-tree representing the unambiguous C-component which vH
is belonging to.The difference between BCTree::bccomp() and DynamicBCTree::bccomp() is, that the latter one considers the UNION/FIND-tree structures.
Reimplemented from ogdf::BCTree.
Returns the BC-tree-vertex representing the B-component 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 B-component, the very vertex of the BC-tree representing this B-component is returned. Otherwise, nullptr 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.
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().
sG | is a vertex of the original graph. |
tG | is a vertex of the original graph. |
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.
uB | is any vertex of m_B. |
vB | is any vertex of m_B. |
uB
== vB
and they are representing a B-component, then cutVertex(uB
,vB
) returns nullptr.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.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
.uB
,vB
) returns nullptr.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 249 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/FIND-tree of vB
.
|
protected |
Initialization of m_bNode_owner and m_bNode_degree.
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().
sG | is a vertex of the original graph. |
tG | is a vertex of the original graph. |
Definition at line 301 of file DynamicBCTree.h.
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().
eG | is an edge of the original graph. |
Definition at line 311 of file DynamicBCTree.h.
Returns the parent of a given BC-tree-vertex.
vB | is any vertex of m_B or nullptr. |
vB
in the BC-tree structure, if vB
is not the root of the BC-tree, and nullptr, if vB
is nullptr or the root of the BC-tree. The UNION/FIND-tree 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 BC-tree.
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/FIND-tree structures.
Reimplemented from ogdf::BCTree.
Definition at line 215 of file DynamicBCTree.h.
The UNION function of the UNION/FIND structure.
uB | is a vertex of the BC-tree representing a B-component. |
vB | is a vertex of the BC-tree representing a C-component. |
wB | is a vertex of the BC-tree representing a B-component. |
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
. 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.
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 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.
Reimplemented in ogdf::DynamicSPQRForest, and ogdf::DynamicSPQRTree.
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.
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 57 of file DynamicBCTree.h.
|
friend |
Definition at line 58 of file DynamicBCTree.h.
|
protected |
Array that contains for each proper BC-tree-vertex its degree.
For each vertex vB of the BC-tree structure:
Definition at line 86 of file DynamicBCTree.h.
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:
Definition at line 72 of file DynamicBCTree.h.