Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::BCTree Class Reference

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 (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 GraphoriginalGraph () const
 Returns the original graph.
 
const GraphbcTree () const
 Returns the BC-tree graph.
 
const GraphauxiliaryGraph () 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
 
virtual 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.
 
virtual 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.
 
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 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.
 
Graphm_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< boolm_gNode_isMarked
 
NodeArray< nodem_gNode_hNode
 An injective mapping vertices(G) -> vertices(H).
 
EdgeArray< edgem_gEdge_hEdge
 A bijective mapping edges(G) -> edges(H).
 
NodeArray< BNodeTypem_bNode_type
 Array that contains the type of each BC-tree-vertex.
 
NodeArray< boolm_bNode_isMarked
 Array of marks for the BC-tree-vertices.
 
NodeArray< nodem_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< 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.
 
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< intm_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< nodem_hNode_bNode
 
EdgeArray< nodem_hEdge_bNode
 A surjective mapping edges(H) -> vertices(B).
 
NodeArray< nodem_hNode_gNode
 A surjective mapping vertices(H) -> vertices(G).
 
EdgeArray< edgem_hEdge_gEdge
 A bijective mapping edges(H) -> edges(G).
 

Private Member Functions

 BCTree (const BCTree &)=delete
 Copy constructor is undefined!
 
void initBasic (node vG)
 
void initEdges ()
 
BCTreeoperator= (const BCTree &)=delete
 Assignment operator is undefined!
 
int m_count
 
NodeArray< intm_number
 Temporary array.
 
NodeArray< intm_lowpt
 Temporary array.
 
ArrayBuffer< adjEntrym_eStack
 Temporary stack.
 
NodeArray< nodem_gtoh
 Temporary array.
 
SList< nodem_nodes
 Temporary list.
 
void init (node vG)
 

Detailed Description

Static BC-trees.

This class provides static BC-trees.
The data structure consists of three parts:

  • The original graph itself (G) is represented by an ordinary ogdf::Graph structure.
  • The BC-tree (B) is represented by an ogdf::Graph structure, each vertex representing a B-component or a C-component.
  • The biconnected components graph (H), which contains a set of copies of the biconnected components and the cut-vertices of the original graph, combined but not interconnected within a single ogdf::Graph structure.

Definition at line 55 of file BCTree.h.

Member Enumeration Documentation

◆ BNodeType

Enumeration type for characterizing the BC-tree-vertices.

Enumerator
BComp 

a vertex representing a B-component

CComp 

a vertex representing a C-component

Definition at line 66 of file BCTree.h.

◆ GNodeType

Enumeration type for characterizing the vertices of the original graph.

Enumerator
Normal 

an ordinary vertex, i.e. not a cut-vertex

CutVertex 

a cut-vertex

Definition at line 58 of file BCTree.h.

Constructor & Destructor Documentation

◆ BCTree() [1/4]

ogdf::BCTree::BCTree ( Graph G,
bool  callInitConnected = false 
)
inlineexplicit

A constructor.

This constructor does only call init() or initNotConnected(). BCTree(G) is equivalent to BCTree(G, G.firstNode()).

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

Definition at line 373 of file BCTree.h.

◆ BCTree() [2/4]

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

A constructor.

This constructor does only call init() or initNotConnected().

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

Definition at line 390 of file BCTree.h.

◆ BCTree() [3/4]

ogdf::BCTree::BCTree ( Graph G,
List< node > &  vG 
)
inline

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.

Parameters
Gis the original graph.
vGa list of vertices of the original graph from which the DFS algorithm is run.

Definition at line 409 of file BCTree.h.

◆ ~BCTree()

virtual ogdf::BCTree::~BCTree ( )
inlinevirtual

Virtual destructor.

Definition at line 412 of file BCTree.h.

◆ BCTree() [4/4]

ogdf::BCTree::BCTree ( const BCTree )
privatedelete

Copy constructor is undefined!

Member Function Documentation

◆ auxiliaryGraph()

const Graph & ogdf::BCTree::auxiliaryGraph ( ) const
inline

Returns the biconnected components graph.

Definition at line 422 of file BCTree.h.

◆ bComponent()

node ogdf::BCTree::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, 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.

◆ bcproper() [1/2]

virtual node ogdf::BCTree::bcproper ( edge  eG) const
inlinevirtual

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.

Reimplemented in ogdf::DynamicBCTree.

Definition at line 467 of file BCTree.h.

◆ bcproper() [2/2]

virtual node ogdf::BCTree::bcproper ( node  vG) const
inlinevirtual

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.

Reimplemented in ogdf::DynamicBCTree.

Definition at line 458 of file BCTree.h.

◆ bcTree()

const Graph & ogdf::BCTree::bcTree ( ) const
inline

Returns the BC-tree graph.

Definition at line 419 of file BCTree.h.

◆ biComp()

void ogdf::BCTree::biComp ( adjEntry  adjuG,
node  vG 
)
protected

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).

◆ cutVertex()

virtual node ogdf::BCTree::cutVertex ( node  uB,
node  vB 
) const
virtual

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 a vertex of the BC-tree.
vBis a vertex of the BC-tree.
Returns
a vertex of the biconnected components graph:
  • If uB == vB and they are representing a B-component, then cutVertex(uB, vB) returns nullptr.
  • If 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.
  • 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 nullptr.

Reimplemented in ogdf::DynamicBCTree.

◆ findNCA()

node ogdf::BCTree::findNCA ( node  uB,
node  vB 
) const
protected

Calculates the nearest common ancestor of two vertices of the BC-tree.

Parameters
uBis a vertex of the BC-tree.
vBis a vertex of the BC-tree.
Returns
the nearest common ancestor of uB and vB.

◆ findPath()

SList< node > & ogdf::BCTree::findPath ( node  sG,
node  tG 
) const

Calculates a path in the BC-tree.

Parameters
sGis a vertex of the original graph.
tGis a vertex of the original graph.
Returns
the path from bcproper(sG) to bcproper(tG) in the BC-tree as a linear list of vertices.
Postcondition
The SList<node> instance is created by this function and has to be destructed by the caller!

◆ findPathBCTree()

SList< node > * ogdf::BCTree::findPathBCTree ( node  sB,
node  tB 
) const

Calculates a path in the BC-tree.

Parameters
sBis a vertex of the BC-tree.
tBis a vertex of the BC-tree.
Returns
the path from (sB) to bcproper(tB) in the BC-tree as a linear list of vertices.
Postcondition
The SList<node> instance is created by this function and has to be destructed by the caller!

◆ hEdges()

const SList< edge > & ogdf::BCTree::hEdges ( node  vB) const
inline

Returns a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by a given BC-tree-vertex.

Parameters
vBis a vertex of the BC-tree.
Returns
a linear list of edges of the biconnected components graph:
  • If vB is representing a B-component, then the edges in the list are the copies of the edges belonging to the B-component.
  • If vB is representing a C-component, then the list is empty.

Definition at line 528 of file BCTree.h.

◆ init()

void ogdf::BCTree::init ( node  vG)
protected

Initialization.

initializes all data structures and generates the BC-tree and the biconnected components graph by call to biComp().

Parameters
vGis the vertex of the original graph which the DFS algorithm starts with.

◆ initBasic()

void ogdf::BCTree::initBasic ( node  vG)
private

◆ initEdges()

void ogdf::BCTree::initEdges ( )
private

◆ initNotConnected() [1/2]

void ogdf::BCTree::initNotConnected ( List< node > &  vG)
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(), but only for components containing a vertex from vG.

Parameters
vGa list of vertices of the original graph from which the DFS algorithm is run.

◆ initNotConnected() [2/2]

void ogdf::BCTree::initNotConnected ( node  vG)
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().

Parameters
vGis the vertex of the original graph which the DFS algorithm starts first with.

◆ numberOfBComps()

int ogdf::BCTree::numberOfBComps ( ) const
inline

Returns the number of B-components.

Definition at line 428 of file BCTree.h.

◆ numberOfCComps()

int ogdf::BCTree::numberOfCComps ( ) const
inline

Returns the number of C-components.

Definition at line 431 of file BCTree.h.

◆ numberOfEdges()

int ogdf::BCTree::numberOfEdges ( node  vB) const
inline

Returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex.

Parameters
vBis a vertex of the BC-tree.
Returns
the number of edges belonging to the B- or C-component represented by vB, particularly 0 if it is a C-component.

Definition at line 537 of file BCTree.h.

◆ numberOfNodes()

int ogdf::BCTree::numberOfNodes ( node  vB) const
inline

Returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex.

Parameters
vBis a vertex of the BC-tree.
Returns
the number of vertices belonging to the B- or C-component represented by vB, cut-vertices inclusive, particularly 1 if it is a C-component.

Definition at line 547 of file BCTree.h.

◆ operator=()

BCTree & ogdf::BCTree::operator= ( const BCTree )
privatedelete

Assignment operator is undefined!

◆ original() [1/2]

edge ogdf::BCTree::original ( edge  eH) const
inline

Returns the edge of the original graph which a given edge of the biconnected components graph is corresponding to.

Parameters
eHis an edge of the biconnected components graph.
Returns
the edge of the original graph which eH is corresponding to.

Definition at line 506 of file BCTree.h.

◆ original() [2/2]

node ogdf::BCTree::original ( node  vH)
inline

returns the vertex of the original graph which a given vertex of the biconnected components graph is corresponding to.

Parameters
vHis a vertex of the biconnected components graph.
Returns
the vertex of the original graph which vH is corresponding to.

Definition at line 498 of file BCTree.h.

◆ originalGraph()

const Graph & ogdf::BCTree::originalGraph ( ) const
inline

Returns the original graph.

Definition at line 416 of file BCTree.h.

◆ parent()

virtual node ogdf::BCTree::parent ( node  vB) const
protectedvirtual

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

Parameters
vBis a vertex of the BC-tree or nullptr.
Returns
the parent of 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.

◆ rep() [1/2]

edge ogdf::BCTree::rep ( edge  eG) const
inline

Returns the edge of the biconnected components graph corresponding to a given edge of the original graph.

Parameters
eGis an edge of the original graph.
Returns
the edge of the biconnected components graph corresponding to eG.

Definition at line 488 of file BCTree.h.

◆ rep() [2/2]

node ogdf::BCTree::rep ( node  vG) const
inline

Returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph.

Parameters
vGis a vertex of the original graph.
Returns
a vertex of the biconnected components graph:
  • If vG is not a cut-vertex, then rep(vG) returns the very vertex of the biconnected components graph corresponding to vG.
  • If 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.

Definition at line 480 of file BCTree.h.

◆ repVertex()

virtual node ogdf::BCTree::repVertex ( node  uG,
node  vB 
) const
virtual

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 a vertex of the BC-tree.
Returns
a vertex of the biconnected components graph:
  • If 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.
  • Otherwise, repVertex(uG, vB) returns nullptr.

Reimplemented in ogdf::DynamicBCTree.

◆ typeOfBNode()

BNodeType ogdf::BCTree::typeOfBNode ( node  vB) const
inline

Returns the type of the biconnected component represented by a given BC-tree-vertex.

Parameters
vBis a vertex of the BC-tree.
Returns
the type of the biconnected component represented by vB.

Definition at line 516 of file BCTree.h.

◆ typeOfGNode()

GNodeType ogdf::BCTree::typeOfGNode ( node  vG) const
inline

Returns the type of a vertex of the original graph.

Parameters
vGis a vertex of the original graph.
Returns
the type of vG.

Definition at line 440 of file BCTree.h.

Member Data Documentation

◆ m_B

Graph ogdf::BCTree::m_B
protected

The BC-tree.

Each vertex is representing a biconnected component (B-component) or a cut-vertex (C-component) of the original graph.

Definition at line 83 of file BCTree.h.

◆ m_bNode_hEdges

NodeArray<SList<edge> > ogdf::BCTree::m_bNode_hEdges
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:

  • If vB is representing a B-component, then m_bNode_hEdges[vB] is a linear list of the edges of the biconnected components graph corresponding to the edges of the original graph belonging to the B-component.
  • If vB is representing a C-component, then m_bNode_hEdges[vB] is an empty list.

Definition at line 200 of file BCTree.h.

◆ m_bNode_hParNode

NodeArray<node> ogdf::BCTree::m_bNode_hParNode
protected

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.

  • If vB is the root of the BC-tree, then m_bNode_hParNode[vB] is nullptr.
  • If vB is representing a B-component and vB is not the root of the BC-tree, then m_bNode_hParNode[vB] is the single isolated vertex of the biconnected components graph corresponding to the very cut-vertex, which the C-component represented by the parent of vB consists of.
  • If vB is representing to a C-component and vB is not the root of the BC-tree, then m_bNode_hParNode[vB] is the very vertex of the biconnected components graph, which is the duplicate of the cut-vertex, which the C-component consists of, in the copy of the B-component represented by the parent of vB.

Definition at line 186 of file BCTree.h.

◆ m_bNode_hRefNode

NodeArray<node> ogdf::BCTree::m_bNode_hRefNode
protected

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:

  • If vB is representing a B-component and vB is the root of the BC-tree, then m_bNode_hRefNode[vB] is nullptr.
  • If vB is representing a B-component and vB is not the root of the BC-tree, then m_bNode_hRefNode[vB] is the very vertex of the biconnected components graph which is the duplicate of the cut-vertex represented by the parent of vB in the copy of the B-component represented by vB.
  • If vB is representing a C-component, then m_bNode_hRefNode[vB] is the single isolated vertex of the biconnected components graph corresponding to the cut-vertex which the C-component consists of, irrespective of whether vB is the root of the BC-tree or not.

Definition at line 165 of file BCTree.h.

◆ m_bNode_isMarked

NodeArray<bool> ogdf::BCTree::m_bNode_isMarked
mutableprotected

Array of marks for the BC-tree-vertices.

They are needed for searching for the nearest common ancestor of two vertices of the BC-tree.

Definition at line 145 of file BCTree.h.

◆ m_bNode_numNodes

NodeArray<int> ogdf::BCTree::m_bNode_numNodes
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:

  • If vB is representing a B-component, then m_bNode_numNodes[vB] is the number of vertices belonging to the B-component, cut-vertices inclusive.
  • If vB is representing a C-component, then m_bNode_numNodes[vB] is 1.

Definition at line 213 of file BCTree.h.

◆ m_bNode_type

NodeArray<BNodeType> ogdf::BCTree::m_bNode_type
protected

Array that contains the type of each BC-tree-vertex.

Definition at line 137 of file BCTree.h.

◆ m_count

int ogdf::BCTree::m_count
protected

Temporary variable.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 260 of file BCTree.h.

◆ m_eStack

ArrayBuffer<adjEntry> ogdf::BCTree::m_eStack
protected

Temporary stack.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 284 of file BCTree.h.

◆ m_G

Graph& ogdf::BCTree::m_G
protected

The original graph.

Definition at line 75 of file BCTree.h.

◆ m_gEdge_hEdge

EdgeArray<edge> ogdf::BCTree::m_gEdge_hEdge
protected

A bijective mapping edges(G) -> edges(H).

For each edge eG of the original graph, m_gEdge_hEdge[eG] is the very edge of the biconnected components graph corresponding to eG.

Definition at line 132 of file BCTree.h.

◆ m_gNode_hNode

NodeArray<node> ogdf::BCTree::m_gNode_hNode
protected

An injective mapping vertices(G) -> vertices(H).

For each vertex vG of the original graph:

  • If vG is not a cut-vertex, then m_gNode_hNode[vG] is the very vertex of the biconnected components graph corresponding to vG.
  • If vG is a cut-vertex, then m_gNode_hNode[vG] is the very vertex of the biconnected components graph representing the C-component, which vG is belonging to, as a single isolated vertex.

Definition at line 124 of file BCTree.h.

◆ m_gNode_isMarked

NodeArray<bool> ogdf::BCTree::m_gNode_isMarked
protected

Array of marks for the vertices of the original graph.

They are needed during the generation of the BC-tree by DFS method.

Definition at line 112 of file BCTree.h.

◆ m_gtoh

NodeArray<node> ogdf::BCTree::m_gtoh
protected

Temporary array.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 292 of file BCTree.h.

◆ m_H

Graph ogdf::BCTree::m_H
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.

Definition at line 97 of file BCTree.h.

◆ m_hEdge_bNode

EdgeArray<node> ogdf::BCTree::m_hEdge_bNode
mutableprotected

A surjective mapping edges(H) -> vertices(B).

For each edge eH of the biconnected components graph, m_hEdge_bNode[eH] is the very BC-tree-vertex representing the unambiguous B-component, which eH is belonging to.

Definition at line 233 of file BCTree.h.

◆ m_hEdge_gEdge

EdgeArray<edge> ogdf::BCTree::m_hEdge_gEdge
protected

A bijective mapping edges(H) -> edges(G).

For each edge eH of the biconnected components graph, m_hEdge_gEdge[eH] is the edge of the original graph which eH is corresponding to.

Definition at line 251 of file BCTree.h.

◆ m_hNode_bNode

NodeArray<node> ogdf::BCTree::m_hNode_bNode
mutableprotected

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.

Definition at line 224 of file BCTree.h.

◆ m_hNode_gNode

NodeArray<node> ogdf::BCTree::m_hNode_gNode
protected

A surjective mapping vertices(H) -> vertices(G).

For each vertex vH of the biconnected components graph, m_hNode_gNode[vH] is the vertex of the original graph which vH is corresponding to.

Definition at line 242 of file BCTree.h.

◆ m_lowpt

NodeArray<int> ogdf::BCTree::m_lowpt
protected

Temporary array.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 276 of file BCTree.h.

◆ m_nodes

SList<node> ogdf::BCTree::m_nodes
protected

Temporary list.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 300 of file BCTree.h.

◆ m_numB

int ogdf::BCTree::m_numB
protected

The number of B-components.

Definition at line 101 of file BCTree.h.

◆ m_number

NodeArray<int> ogdf::BCTree::m_number
protected

Temporary array.

It is needed for the generation of the BC-tree by DFS method. It has to be a member of class BCTree due to recursive calls to biComp().

Definition at line 269 of file BCTree.h.

◆ m_numC

int ogdf::BCTree::m_numC
protected

The number of C-components.

Definition at line 104 of file BCTree.h.


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