ogdf::BCTree

ogdf::BCTree Class Reference

Static BC-trees. More...

#include <BCTree.h>

Inheritance diagram for ogdf::BCTree:

List of all members.

Public Types

enum GNodeType { Normal, CutVertex }

Enumeration type for characterizing the vertices of the original graph. More...

enum BNodeType { BComp, CComp }

Enumeration type for characterizing the BC-tree-vertices. More...

Public Member Functions

BCTree (Graph &G, bool callInitConnected=false)

A constructor.

BCTree (Graph &G, node vG, bool callInitConnected=false)

A constructor.

virtual ~BCTree ()

Virtual destructor.

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

returns the type of a vertex of the original graph.

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)

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

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

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

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

returns the BC-tree-vertex representing the B-component which two given vertices of the original graph are belonging to.

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 init (node vG)

Initialization.

void initNotConnected (node vG)

Initialization for not connected graphs.

void biComp (adjEntry adjuG, node vG)

generates the BC-tree and the biconnected components graph recursively.

virtual node parent (node vB) const

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

node findNCA (node uB, node vB) const

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

Protected Attributes

Graph & m_G

The original graph.

Graph m_B

The BC-tree.

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

Array of marks for the vertices of the original graph.

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

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

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

int m_count

Temporary variable.

NodeArray< int > m_number

Temporary array.

NodeArray< int > m_lowpt

Temporary array.

BoundedStack< adjEntry > m_eStack

Temporary stack.

NodeArray< node > m_gtoh

Temporary array.

SList< node > m_nodes

Temporary list.

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

Member Enumeration Documentation

enum ogdf::BCTree::GNodeType

Enumeration type for characterizing the vertices of the original graph.

Enumerator:

Normal	denotes an ordinary vertex, i.e. not a cut-vertex.
CutVertex	denotes a cut-vertex.

Definition at line 92 of file BCTree.h.

enum ogdf::BCTree::BNodeType

Enumeration type for characterizing the BC-tree-vertices.

Enumerator:

BComp	denotes a vertex representing a B-component.
CComp	denotes a vertex representing a C-component.

Definition at line 102 of file BCTree.h.

Constructor & Destructor Documentation

ogdf::BCTree::BCTree	(	Graph &	G,
		bool	callInitConnected = `false`
	)			`[inline]`

A constructor.

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

Parameters:

	G	is the original graph.
	callInitConnected	decides which init is called, default call is init()

Definition at line 374 of file BCTree.h.

ogdf::BCTree::BCTree	(	Graph &	G,
		node	vG,
		bool	callInitConnected = `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
	callInitConnected	decides which init is called, default call is init()

Definition at line 388 of file BCTree.h.

virtual ogdf::BCTree::~BCTree ( ) [inline, virtual]

Virtual destructor.

Definition at line 397 of file BCTree.h.

Member Function Documentation

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:

is the vertex of the original graph which the DFS algorithm starts with.

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:

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

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

virtual node ogdf::BCTree::parent ( node vB ) const [protected, virtual]

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

Parameters:

is a vertex of the BC-tree or NULL.

Returns:: the parent of vB in the BC-tree structure, if vB is not the root of the BC-tree, and NULL, if vB is NULL or the root of the BC-tree.

Reimplemented in ogdf::DynamicBCTree.

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.

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

returns the original graph.

Returns:: the original graph.

Reimplemented in ogdf::DynamicSPQRTree.

Definition at line 403 of file BCTree.h.

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

returns the BC-tree graph.

Returns:: the BC-tree graph.

Definition at line 408 of file BCTree.h.

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

returns the biconnected components graph.

Returns:: the biconnected components graph.

Definition at line 413 of file BCTree.h.

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

returns the number of B-components.

Returns:: the number of B-components.

Definition at line 419 of file BCTree.h.

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

returns the number of C-components.

Returns:: the number of C-components.

Definition at line 424 of file BCTree.h.

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

returns the type of a vertex of the original graph.

Parameters:

is a vertex of the original graph.

Returns:: the type of vG.

Definition at line 431 of file BCTree.h.

virtual node ogdf::BCTree::bcproper ( node vG ) const [inline, virtual]

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

Parameters:

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

virtual node ogdf::BCTree::bcproper ( edge eG ) const [inline, virtual]

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

Parameters:

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

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:

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

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:

is an edge of the original graph.

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

Definition at line 471 of file BCTree.h.

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:

is a vertex of the biconnected components graph.

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

Definition at line 479 of file BCTree.h.

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:

is an edge of the biconnected components graph.

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

Definition at line 486 of file BCTree.h.

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

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

Parameters:

is a vertex of the BC-tree.

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

Definition at line 494 of file BCTree.h.

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:

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

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:

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

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:

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

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, NULL is returned. This member function returns the representant of the correct B-component even if uG or vG or either are cut-vertices and are therefore belonging to C-components, too.

Reimplemented in ogdf::DynamicBCTree.

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!

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

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

Reimplemented in ogdf::DynamicBCTree.

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

Reimplemented in ogdf::DynamicBCTree.

Member Data Documentation

Graph& ogdf::BCTree::m_G [protected]

The original graph.

Definition at line 109 of file BCTree.h.

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

Graph ogdf::BCTree::m_H [mutable, protected]

The biconnected components graph.

This graph contains copies of the 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 129 of file BCTree.h.

int ogdf::BCTree::m_numB [protected]

The number of B-components.

Definition at line 134 of file BCTree.h.

int ogdf::BCTree::m_numC [protected]

The number of C-components.

Definition at line 138 of file BCTree.h.

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

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

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

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

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

Definition at line 168 of file BCTree.h.

NodeArray<bool> ogdf::BCTree::m_bNode_isMarked [mutable, protected]

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

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

Array that contains for each BC-tree-vertex the representant of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex.

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

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

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

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

NodeArray<node> ogdf::BCTree::m_hNode_bNode [mutable, protected]

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

EdgeArray<node> ogdf::BCTree::m_hEdge_bNode [mutable, protected]

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

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

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

int ogdf::BCTree::m_count [protected]

Temporary variable.