Static BC-trees. More...

#include <ogdf/decomposition/BCTree.h>

Inheritance diagram for ogdf::BCTree:

Public Types
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...

Public Member Functions
	BCTree (BCTree &&move)=delete

	BCTree (const BCTree &copy)=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 &copy)=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...

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

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

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

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

Protected Member Functions
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...


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

Protected Attributes
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...

Private Member Functions
void	initBasic (node vG)

void	initEdges ()

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

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 60 of file BCTree.h.

Member Enumeration Documentation

◆ BNodeType

enum ogdf::BCTree::BNodeType

strong

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 71 of file BCTree.h.

◆ GNodeType

enum ogdf::BCTree::GNodeType

strong

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 63 of file BCTree.h.

Constructor & Destructor Documentation

◆ BCTree() [1/5]

ogdf::BCTree::BCTree	(	Graph &	G,
		bool	not_connected = `false`
	)

inlineexplicit

A constructor.

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

Parameters

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 378 of file BCTree.h.

◆ BCTree() [2/5]

ogdf::BCTree::BCTree	(	Graph &	G,
		node	vG,
		bool	not_connected = `false`
	)

inline

A constructor.

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

Parameters

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 389 of file BCTree.h.

◆ BCTree() [3/5]

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

G	is the original graph.
vG	a list of vertices of the original graph from which the DFS algorithm is run.

Definition at line 410 of file BCTree.h.

◆ ~BCTree()

virtual ogdf::BCTree::~BCTree ( )

inlinevirtual

Virtual destructor.

Definition at line 413 of file BCTree.h.

◆ BCTree() [4/5]

ogdf::BCTree::BCTree ( const BCTree & copy )

delete

◆ BCTree() [5/5]

ogdf::BCTree::BCTree ( BCTree && move )

delete

Member Function Documentation

◆ auxiliaryGraph()

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

inline

Returns the biconnected components graph.

Definition at line 428 of file BCTree.h.

◆ bccomp() [1/2]

virtual node ogdf::BCTree::bccomp ( edge eH ) const

inlinevirtual

Returns the BC-tree-vertex representing the biconnected component which a given edge of the auxiliary graph is belonging to.

Parameters

eH	is an edge of the auxiliary graph.

Returns: the vertex of the BC-tree representing the B-component which eH is belonging to.

Reimplemented in ogdf::DynamicBCTree.

Definition at line 496 of file BCTree.h.

◆ bccomp() [2/2]

virtual node ogdf::BCTree::bccomp ( node vH ) const

inlinevirtual

Returns a BC-tree-vertex representing a biconnected component which a given vertex of the auxiliary graph is belonging to.

Parameters

vH	is a vertex of the auxiliary graph.

Returns

a vertex of the BC-tree:

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

Definition at line 487 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

uG	is a vertex of the original graph.
vG	is 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]

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

inline

Returns the BC-tree-vertex representing the biconnected component which a given edge of the original graph is belonging to.

Parameters

eG	is an edge of the original graph.

Returns: the vertex of the BC-tree representing the B-component which eG is belonging to.

Definition at line 473 of file BCTree.h.

◆ bcproper() [2/2]

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

inline

Returns a BC-tree-vertex representing a biconnected component which a given vertex of the original graph is belonging to.

Parameters

vG	is a vertex of the original graph.

Returns

a vertex of the BC-tree:

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

Definition at line 464 of file BCTree.h.

◆ bcTree()

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

inline

Returns the BC-tree graph.

Definition at line 425 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).

◆ consistencyCheck()

void ogdf::BCTree::consistencyCheck ( ) const

Asserts that this BCTree is consistent.

◆ 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

uB	is a vertex of the BC-tree.
vB	is 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

uB	is a vertex of the BC-tree.
vB	is 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

sG	is a vertex of the original graph.
tG	is 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

sB	is a vertex of the BC-tree.
tB	is a vertex of the BC-tree.

Returns: the path from sB to 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

vB	is 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 557 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

vG	is 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

vG	a 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

vG	is 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 434 of file BCTree.h.

◆ numberOfCComps()

int ogdf::BCTree::numberOfCComps ( ) const

inline

Returns the number of C-components.

Definition at line 437 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

vB	is 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 566 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

vB	is 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 576 of file BCTree.h.

◆ operator=() [1/2]

BCTree& ogdf::BCTree::operator= ( BCTree && move )

delete

◆ operator=() [2/2]

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

delete

◆ 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

eH	is an edge of the biconnected components graph.

Returns: the edge of the original graph which eH is corresponding to.

Definition at line 535 of file BCTree.h.

◆ original() [2/2]

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

inline

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

Parameters

vH	is a vertex of the biconnected components graph.

Returns: the vertex of the original graph which vH is corresponding to.

Definition at line 527 of file BCTree.h.

◆ originalGraph()

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

inline

Returns the original graph.

Definition at line 422 of file BCTree.h.

◆ parent()

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

protectedvirtual

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

Parameters

vB	is 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

eG	is an edge of the original graph.

Returns: the edge of the biconnected components graph corresponding to eG.

Definition at line 517 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

vG	is 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 509 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

uG	is a vertex of the original graph.
vB	is 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

vB	is a vertex of the BC-tree.

Returns: the type of the biconnected component represented by vB.

Definition at line 545 of file BCTree.h.

◆ typeOfGNode()

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

inline

Returns the type of a vertex of the original graph.

Parameters

vG	is a vertex of the original graph.

Returns: the type of vG.

Definition at line 446 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 88 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 205 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 191 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 170 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 150 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 218 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 142 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 265 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 289 of file BCTree.h.

◆ m_G

Graph& ogdf::BCTree::m_G

protected

The original graph.

Definition at line 80 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 137 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 129 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 117 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 297 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 102 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 238 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 256 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 229 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 247 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 281 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 305 of file BCTree.h.

◆ m_numB

int ogdf::BCTree::m_numB

protected

The number of B-components.

Definition at line 106 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 274 of file BCTree.h.

◆ m_numC

int ogdf::BCTree::m_numC

protected

The number of C-components.

Definition at line 109 of file BCTree.h.

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

include/ogdf/decomposition/BCTree.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Member Enumeration Documentation

◆ BNodeType

◆ GNodeType

Constructor & Destructor Documentation

◆ BCTree() [1/5]

◆ BCTree() [2/5]

◆ BCTree() [3/5]

◆ ~BCTree()

◆ BCTree() [4/5]

◆ BCTree() [5/5]

Member Function Documentation

◆ auxiliaryGraph()

◆ bccomp() [1/2]

◆ bccomp() [2/2]

◆ bComponent()

◆ bcproper() [1/2]

◆ bcproper() [2/2]

◆ bcTree()

◆ biComp()

◆ consistencyCheck()

◆ cutVertex()

◆ findNCA()

◆ findPath()

◆ findPathBCTree()

◆ hEdges()

◆ init()

◆ initBasic()

◆ initEdges()

◆ initNotConnected() [1/2]

◆ initNotConnected() [2/2]

◆ numberOfBComps()

◆ numberOfCComps()

◆ numberOfEdges()

◆ numberOfNodes()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ original() [1/2]

◆ original() [2/2]

◆ originalGraph()

◆ parent()

◆ rep() [1/2]

◆ rep() [2/2]

◆ repVertex()

◆ typeOfBNode()

◆ typeOfGNode()

Member Data Documentation

◆ m_B

◆ m_bNode_hEdges

◆ m_bNode_hParNode

◆ m_bNode_hRefNode

◆ m_bNode_isMarked

◆ m_bNode_numNodes

◆ m_bNode_type

◆ m_count

◆ m_eStack

◆ m_G

◆ m_gEdge_hEdge

◆ m_gNode_hNode

◆ m_gNode_isMarked

◆ m_gtoh

◆ m_H

◆ m_hEdge_bNode

◆ m_hEdge_gEdge

◆ m_hNode_bNode

◆ m_hNode_gNode

◆ m_lowpt

◆ m_nodes

◆ m_numB

◆ m_number

◆ m_numC

Open
Graph Drawing
Framework