|
|||
|
|
|
|||
|
|
Static BC-trees. More...
#include <ogdf/decomposition/BCTree.h>
Inheritance diagram for ogdf::BCTree:Public Types | |
| enum class | BNodeType { BComp , CComp } |
| Enumeration type for characterizing the BC-tree-vertices. More... | |
| enum class | GNodeType { Normal , CutVertex } |
| Enumeration type for characterizing the vertices of the original graph. More... | |
Public Member Functions | |
| BCTree (BCTree &&move)=delete | |
| BCTree (const BCTree ©)=delete | |
| BCTree (Graph &G, bool not_connected=false) | |
| A constructor. | |
| BCTree (Graph &G, List< node > &vG) | |
| Constructor for not connected graphs. | |
| BCTree (Graph &G, node vG, bool not_connected=false) | |
| A constructor. | |
| virtual | ~BCTree () |
| Virtual destructor. | |
| void | consistencyCheck () const |
| Asserts that this BCTree is consistent. | |
| BCTree & | operator= (BCTree &&move)=delete |
| BCTree & | operator= (const BCTree ©)=delete |
| const Graph & | originalGraph () const |
| Returns the original graph. | |
| const Graph & | bcTree () const |
| Returns the BC-tree graph. | |
| const Graph & | auxiliaryGraph () const |
| Returns the biconnected components graph. | |
| int | numberOfBComps () const |
| Returns the number of B-components. | |
| int | numberOfCComps () const |
| Returns the number of C-components. | |
| 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. | |
| 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. | |
| virtual node | bccomp (node vH) const |
| Returns a BC-tree-vertex representing a biconnected component which a given vertex of the auxiliary graph is belonging to. | |
| virtual node | bccomp (edge eH) const |
| Returns the BC-tree-vertex representing the biconnected component which a given edge of the auxiliary 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) 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. | |
| 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. | |
| int | numberOfEdges (node vB) const |
| Returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex. | |
| int | numberOfNodes (node vB) const |
| Returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex. | |
| node | bComponent (node uG, node vG) const |
| SList< node > & | findPath (node sG, node tG) const |
| Calculates a path in the BC-tree. | |
| SList< node > * | findPathBCTree (node sB, node tB) const |
| Calculates a path in the BC-tree. | |
| 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 BC-tree. | |
| virtual 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. | |
Protected Member Functions | |
| void | biComp (adjEntry adjuG, node vG) |
| Generates the BC-tree 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 BC-tree. | |
Protected Attributes | |
| Graph | m_B |
| The BC-tree. | |
| Graph & | m_G |
| The original graph. | |
| Graph | m_H |
| The biconnected components graph. | |
| int | m_numB |
| The number of B-components. | |
| int | m_numC |
| The number of C-components. | |
| 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 BC-tree-vertex. | |
| NodeArray< bool > | m_bNode_isMarked |
| Array of marks for the BC-tree-vertices. | |
| 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. | |
| 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. | |
| 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. | |
| 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. | |
| 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 | |
| void | initBasic (node vG) |
| void | initEdges () |
| 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 BC-trees.
This class provides static BC-trees.
The data structure consists of three parts:
|
strong |
|
strong |
|
inlineexplicit |
A constructor.
This constructor does only call init() or initNotConnected().
| 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. |
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, 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. |
Constructor for not connected graphs.
Initializes all data structures and generates a forest of BC-trees 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 |
|
delete |
|
delete |
|
inline |
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. Reimplemented in ogdf::DynamicBCTree.
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 bccomp(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 bccomp(vH) returns the very vertex of the BC-tree representing the unambiguous C-component which vH is belonging to. Reimplemented in ogdf::DynamicBCTree.
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 representative of the correct B-component even if uG or vG or either are cut-vertices and are therefore belonging to C-components, too. Returns a BC-tree-vertex 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 cut-vertex, then bcproper(vG) returns the very vertex of the BC-tree representing the unambiguous B-component which vG is belonging to.vG is a cut-vertex, then bcproper(vG) returns the very vertex of the BC-tree representing the unambiguous C-component which vG is belonging to.
|
inline |
Generates the BC-tree 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:372-378 (1973).
| void ogdf::BCTree::consistencyCheck | ( | ) | const |
Asserts that this BCTree is consistent.
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 a vertex of the BC-tree. |
| vB | is a vertex of the BC-tree. |
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 of 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. Reimplemented in ogdf::DynamicBCTree.
Calculates the nearest common ancestor of two vertices of the BC-tree.
| uB | is a vertex of the BC-tree. |
| vB | is a vertex of the BC-tree. |
uB and vB. Calculates a path in the BC-tree.
| sG | is a vertex of the original graph. |
| tG | is a vertex of the original graph. |
sG) to bcproper(tG) in the BC-tree as a linear list of vertices. Calculates a path in the BC-tree.
| sB | is a vertex of the BC-tree. |
| tB | is a vertex of the BC-tree. |
sB to tB in the BC-tree 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 BC-tree-vertex.
| vB | is a vertex of the BC-tree. |
vB is representing a B-component, then the edges in the list are the copies of the edges belonging to the B-component.vB is representing a C-component, then the list is empty.
|
protected |
initializes all data structures and generates the BC-tree and the biconnected components graph by call to biComp().
| vG | is the vertex of the original graph which the DFS algorithm starts with. |
|
private |
|
private |
Initialization for not connected graphs.
Initializes all data structures and generates a forest of BC-trees 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. |
|
protected |
Initialization for not connected graphs.
initializes all data structures and generates a forest of BC-trees 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 |
|
inline |
Returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex.
| vB | is a vertex of the BC-tree. |
vB, particularly 0 if it is a C-component.
|
inline |
Returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex.
| vB | is a vertex of the BC-tree. |
vB, cut-vertices inclusive, particularly 1 if it is a C-component.
|
inline |
Returns the parent of a given BC-tree-vertex.
| vB | is a vertex of the BC-tree 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. 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 cut-vertex, then rep(vG) returns the very vertex of the biconnected components graph corresponding to vG.vG is a cut-vertex, then rep(vG) returns the very vertex of the biconnected components graph representing the C-component 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 BC-tree.
| uG | is a vertex of the original graph. |
| vB | is a vertex of the BC-tree. |
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 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.
For each vertex vB of the BC-tree:
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.
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.
For each vertex vB of the BC-tree:
|
mutableprotected |
|
protected |
Array that contains for each BC-tree-vertex the number of vertices belonging to the biconnected component represented by the respective BC-tree-vertex.
For each vertex vB of the BC-tree:
|
protected |
|
protected |
An injective mapping vertices(G) -> vertices(H).
For each vertex vG of the original graph:
|
protected |
|
mutableprotected |
The biconnected components graph.
This graph contains copies of the biconnected components (B-components) and the cut-vertices (C-components) of the original graph. The copies of the B- and C-components of the original graph are not interconnected, i.e. the biconnected components graph is representing B-components as isolated biconnected subgraphs and C-components as isolated single vertices. Thus the copies of the edges and non-cut-vertices of the original graph are unambiguous, but each cut-vertex of the original graph being common to a C-component and several B-components 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 BC-tree-vertex representing the B- or C-component with respect to the copy of the very block or representation of a cut-vertex, which vH is belonging to.
|
protected |
|
protected |
|
protected |
|
protected |