Dynamic BC-trees. More...

#include <ogdf/decomposition/DynamicBCTree.h>

Inheritance diagram for ogdf::DynamicBCTree:

Public Member Functions

	DynamicBCTree (Graph &G, bool not_connected=false)

	DynamicBCTree (Graph &G, node vG, bool not_connected=false)
	A constructor. More...


node	bccomp (node vH) const override

node	bccomp (edge eH) const override
	Returns the BC-tree-vertex representing the biconnected component which a given edge of the auxiliary graph is belonging to. More...


node	repVertex (node uG, node vB) const override

node	cutVertex (node uB, node vB) const override
	Returns the copy of a cut-vertex in the biconnected components graph which belongs to a certain B-component and leads to another B-component. More...


virtual edge	updateInsertedEdge (edge eG)

virtual node	updateInsertedNode (edge eG, edge fG)
	Update of the dynamic BC-tree after vertex insertion into the original graph. More...

edge	insertEdge (node sG, node tG)
	Inserts a new edge into the original graph and updates the BC-tree. More...

node	insertNode (edge eG)
	Inserts a new vertex into the original graph and updates the BC-tree. More...


node	bComponent (node uG, node vG) const

Public Member Functions inherited from ogdf::BCTree
	BCTree (BCTree &&move)=delete

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

node	rep (node vG) const
	Returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph. More...

edge	rep (edge eG) const
	Returns the edge of the biconnected components graph corresponding to a given edge of the original graph. More...

node	original (node vH) const

edge	original (edge eH) const
	Returns the edge of the original graph which a given edge of the biconnected components graph is corresponding to. More...

BNodeType	typeOfBNode (node vB) const

const SList< edge > &	hEdges (node vB) const
	Returns a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by a given BC-tree-vertex. More...

int	numberOfEdges (node vB) const
	Returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex. More...

int	numberOfNodes (node vB) const
	Returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex. More...

node	bComponent (node uG, node vG) const

SList< node > &	findPath (node sG, node tG) const
	Calculates a path in the BC-tree. More...

SList< node > *	findPathBCTree (node sB, node tB) const
	Calculates a path in the BC-tree. More...

Protected Member Functions

void	init ()


node	unite (node uB, node vB, node wB)

node	find (node vB) const
	The FIND function of the UNION/FIND structure. More...


node	parent (node vB) const override

node	condensePath (node sG, node tG)
	Performs path condensation. More...

Protected Member Functions inherited from ogdf::BCTree
void	biComp (adjEntry adjuG, node vG)
	Generates the BC-tree and the biconnected components graph recursively. More...

void	initNotConnected (List< node > &vG)
	Initialization for not connected graphs. More...

void	initNotConnected (node vG)
	Initialization for not connected graphs. More...

node	findNCA (node uB, node vB) const
	Calculates the nearest common ancestor of two vertices of the BC-tree. More...

void	init (node vG)

Protected Attributes
NodeArray< int >	m_bNode_degree
	Array that contains for each proper BC-tree-vertex its degree. More...

NodeArray< node >	m_bNode_owner
	Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure. More...

Protected Attributes inherited from ogdf::BCTree
Graph	m_B
	The BC-tree. More...

Graph &	m_G
	The original graph. More...

Graph	m_H
	The biconnected components graph. More...

int	m_numB
	The number of B-components. More...

int	m_numC
	The number of C-components. More...

NodeArray< bool >	m_gNode_isMarked

NodeArray< node >	m_gNode_hNode
	An injective mapping vertices(G) -> vertices(H). More...

EdgeArray< edge >	m_gEdge_hEdge
	A bijective mapping edges(G) -> edges(H). More...

NodeArray< BNodeType >	m_bNode_type
	Array that contains the type of each BC-tree-vertex. More...

NodeArray< bool >	m_bNode_isMarked
	Array of marks for the BC-tree-vertices. More...

NodeArray< node >	m_bNode_hRefNode
	Array that contains for each BC-tree-vertex the representantive of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex. More...

NodeArray< node >	m_bNode_hParNode
	Array that contains for each BC-tree-vertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BC-tree-vertex. More...

NodeArray< SList< edge > >	m_bNode_hEdges
	Array that contains for each BC-tree-vertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex. More...

NodeArray< int >	m_bNode_numNodes
	Array that contains for each BC-tree-vertex the number of vertices belonging to the biconnected component represented by the respective BC-tree-vertex. More...

NodeArray< node >	m_hNode_bNode

EdgeArray< node >	m_hEdge_bNode
	A surjective mapping edges(H) -> vertices(B). More...

NodeArray< node >	m_hNode_gNode
	A surjective mapping vertices(H) -> vertices(G). More...

EdgeArray< edge >	m_hEdge_gEdge
	A bijective mapping edges(H) -> edges(G). More...

int	m_count

NodeArray< int >	m_number
	Temporary array. More...

NodeArray< int >	m_lowpt
	Temporary array. More...

ArrayBuffer< adjEntry >	m_eStack
	Temporary stack. More...

NodeArray< node >	m_gtoh
	Temporary array. More...

SList< node >	m_nodes
	Temporary list. More...

Friends
class	PlanarAugmentation

class	PlanarAugmentationFix

Additional Inherited Members
Public Types inherited from ogdf::BCTree
enum	BNodeType { BNodeType::BComp, BNodeType::CComp }
	Enumeration type for characterizing the BC-tree-vertices. More...

enum	GNodeType { GNodeType::Normal, GNodeType::CutVertex }
	Enumeration type for characterizing the vertices of the original graph. More...

Detailed Description

Dynamic BC-trees.

This class provides dynamic BC-trees.
The main difference of the dynamic BC-tree structure compared to the static one implemented by the class BCTree is, that B- and C-components are not any longer represented by single vertices of a BC-tree graph structure but by root vertices of UNION/FIND-trees. This allows path condensation within the BC-tree, when edges are inserted into the original graph. Path condensation is done by gathering BC-tree-vertices into a UNION/FIND-tree. However, the original vertices of the BC-tree remain in the m_B graph, but only those being the roots of their respective UNION/FIND-tree are proper representants of the biconnected components of the original graph.

Definition at line 56 of file DynamicBCTree.h.

Constructor & Destructor Documentation

◆ DynamicBCTree() [1/2]

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

inlineexplicit

A constructor.

This constructor does only call BCTree::BCTree() and DynamicBCTree::init(). DynamicBCTree(G) is equivalent to DynamicBCTree(G, G.firstNode()).

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 149 of file DynamicBCTree.h.

◆ DynamicBCTree() [2/2]

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

inlineexplicit

A constructor.

This constructor does only call BCTree::BCTree() and DynamicBCTree::init().

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 161 of file DynamicBCTree.h.

Member Function Documentation

◆ bccomp() [1/2]

node ogdf::DynamicBCTree::bccomp ( edge eH ) const

overridevirtual

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.

The difference between BCTree::bccomp() and DynamicBCTree::bccomp() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

◆ bccomp() [2/2]

node ogdf::DynamicBCTree::bccomp ( node vH ) const

overridevirtual

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 bcproper(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 bcproper(vH) returns the very vertex of the BC-tree representing the unambiguous C-component which vH is belonging to.

The difference between BCTree::bccomp() and DynamicBCTree::bccomp() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

◆ bComponent()

node ogdf::DynamicBCTree::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 representant of the correct B-component even if uG or vG or either are cut-vertices and are therefore belonging to C-components, too.

The difference between BCTree::bComponent() and DynamicBCTree::bComponent() is, that the latter one considers the UNION/FIND-tree structures.

◆ condensePath()

node ogdf::DynamicBCTree::condensePath	(	node	sG,
		node	tG
	)

protected

Performs path condensation.

This member function condenses the path from bcproper(sG) to bcproper(tG) in the BC-tree into one single B-component by calling findPath() and subsequently unite().

Parameters

sG	is a vertex of the original graph.
tG	is a vertex of the original graph.

Returns: the proper representant of the resulting B-component.

◆ cutVertex()

node ogdf::DynamicBCTree::cutVertex	(	node	uB,
		node	vB
	)		const

inlineoverridevirtual

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 any vertex of m_B.
vB	is any vertex of m_B.

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

The difference between BCTree::cutVertex() and DynamicBCTree::cutVertex() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

Definition at line 249 of file DynamicBCTree.h.

◆ find()

node ogdf::DynamicBCTree::find ( node vB ) const

protected

The FIND function of the UNION/FIND structure.

Parameters

vB	is any vertex of m_B.

Returns: the owner of vB properly representing a biconnected component, i.e. the root of the UNION/FIND-tree of vB.

◆ init()

void ogdf::DynamicBCTree::init ( )

protected

Initialization of m_bNode_owner and m_bNode_degree.

◆ insertEdge()

edge ogdf::DynamicBCTree::insertEdge	(	node	sG,
		node	tG
	)

inline

Inserts a new edge into the original graph and updates the BC-tree.

This member function inserts a new edge between sG and tG into the original graph and then calls updateInsertedEdge().

Parameters

sG	is a vertex of the original graph.
tG	is a vertex of the original graph.

Returns: the new edge of the original graph.

Definition at line 301 of file DynamicBCTree.h.

◆ insertNode()

node ogdf::DynamicBCTree::insertNode ( edge eG )

inline

Inserts a new vertex into the original graph and updates the BC-tree.

This member function inserts a new vertex into the original graph by splitting the edge eG and then calls updateInsertedNode().

Parameters

eG	is an edge of the original graph.

Returns: the new vertex of the original graph.

Definition at line 311 of file DynamicBCTree.h.

◆ parent()

node ogdf::DynamicBCTree::parent ( node vB ) const

overrideprotectedvirtual

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

Parameters

vB	is any vertex of m_B 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. The UNION/FIND-tree structures are considered.

Reimplemented from ogdf::BCTree.

◆ repVertex()

node ogdf::DynamicBCTree::repVertex	(	node	uG,
		node	vB
	)		const

inlineoverridevirtual

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 any vertex of m_B.

Returns

a vertex of the biconnected components graph:

If uG is belonging to the biconnected component represented by vB, then rep(uG,vB) returns the very vertex of the biconnected components graph corresponding to uG within the representation of vB.
Otherwise, nullptr is returned.

The difference between BCTree::repVertex() and DynamicBCTree::repVertex() is, that the latter one considers the UNION/FIND-tree structures.

Reimplemented from ogdf::BCTree.

Definition at line 215 of file DynamicBCTree.h.

◆ unite()

node ogdf::DynamicBCTree::unite	(	node	uB,
		node	vB,
		node	wB
	)

protected

The UNION function of the UNION/FIND structure.

Parameters

uB	is a vertex of the BC-tree representing a B-component.
vB	is a vertex of the BC-tree representing a C-component.
wB	is a vertex of the BC-tree representing a B-component.

Precondition: uB and vB and wB have to be proper representants of their B-components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.; uB and wB have to be adjacent to vB.

Returns: the vertex properly representing the condensed B-component.

◆ updateInsertedEdge()

virtual edge ogdf::DynamicBCTree::updateInsertedEdge ( edge eG )

virtual

Update of the dynamic BC-tree after edge insertion into the original graph.

This member function performs on-line maintenance of the dynamic BC-tree according to J. Westbrook and R. E. Tarjan, Maintaining Bridge-Connected and Biconnected Components On-Line, Algorithmica (1992) 7:433-464.

Parameters

eG	is a newly inserted edge of the original graph.

After a new edge has been inserted into the original graph by calling Graph::newEdge(), this member function updates the corresponding BC-tree in \(O(\alpha(k,n))\) amortized time and the coponents graph in O(1 + n/k) amortized time per insertEdge() operation, where k is the number of such operations.

Returns: the new edge of the original graph.

Reimplemented in ogdf::DynamicSPQRForest, and ogdf::DynamicSPQRTree.

◆ updateInsertedNode()

virtual node ogdf::DynamicBCTree::updateInsertedNode	(	edge	eG,
		edge	fG
	)

virtual

Update of the dynamic BC-tree after vertex insertion into the original graph.

This member function performs on-line maintenance of the dynamic BC-tree according to J. Westbrook and R. E. Tarjan, Maintaining Bridge-Connected and Biconnected Components On-Line, Algorithmica (1992) 7:433-464.

Parameters

eG	is the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation.
fG	is the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation.

After a new vertex has been inserted into an edge of the original graph by splitting the edge, all data structures of the DynamicBCTree class are updated by this member funtion. It takes O(1) time.

Returns: the new vertex of the original graph.

Reimplemented in ogdf::DynamicSPQRForest, and ogdf::DynamicSPQRTree.

Friends And Related Function Documentation

◆ PlanarAugmentation

friend class PlanarAugmentation

friend

Definition at line 57 of file DynamicBCTree.h.

◆ PlanarAugmentationFix

friend class PlanarAugmentationFix

friend

Definition at line 58 of file DynamicBCTree.h.

Member Data Documentation

◆ m_bNode_degree

NodeArray<int> ogdf::DynamicBCTree::m_bNode_degree

protected

Array that contains for each proper BC-tree-vertex its degree.

For each vertex vB of the BC-tree structure:

If vB is representing a biconnected component, then m_bNode_degree[vB] is the degree of the vertex of the BC-tree.
If vB is not any longer representing a biconnected component due to path condensation, then m_bNode_degree[vB] is undefined. This array is necessary, because the edges of the BC-tree are not updated during path condensation for efficiency reasons. Thus, vB->degree() != m_bNode_degree[vB]

Definition at line 86 of file DynamicBCTree.h.

◆ m_bNode_owner

NodeArray<node> ogdf::DynamicBCTree::m_bNode_owner

mutableprotected

Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure.

For each vertex vB of the BC-tree structure:

If vB is representing a biconnected component, then m_bNode_owner[vB] points to the vertex vB itself.
If vB is not any longer representing a biconnected component due to path condensation, then m_bNode_owner[vB] points to the parent of vB in its UNION/FIND-tree.

Definition at line 72 of file DynamicBCTree.h.

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

include/ogdf/decomposition/DynamicBCTree.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ DynamicBCTree() [1/2]

◆ DynamicBCTree() [2/2]

Member Function Documentation

◆ bccomp() [1/2]

◆ bccomp() [2/2]

◆ bComponent()

◆ condensePath()

◆ cutVertex()

◆ find()

◆ init()

◆ insertEdge()

◆ insertNode()

◆ parent()

◆ repVertex()

◆ unite()

◆ updateInsertedEdge()

◆ updateInsertedNode()

Friends And Related Function Documentation

◆ PlanarAugmentation

◆ PlanarAugmentationFix

Member Data Documentation

◆ m_bNode_degree

◆ m_bNode_owner

Open
Graph Drawing
Framework