Dynamic SPQR-forest. More...

#include <ogdf/decomposition/DynamicSPQRForest.h>

Inheritance diagram for ogdf::DynamicSPQRForest:

Public Types
enum	TNodeType { SComp = SPQRTree::SNode, PComp = SPQRTree::PNode, RComp = SPQRTree::RNode }
	Enumeration type for characterizing the SPQR-tree-vertices. More...
Public Member Functions


	DynamicSPQRForest (Graph &G)
	A constructor.


node	spqrproper (edge eH) const
	finds the proper representant of the SPQR-tree-vertex which a given real or virtual edge is belonging to.
edge	twinEdge (edge eH) const
	returns the twin edge of a given edge of m_H, if it is virtual, or NULL, if it is real.


TNodeType	typeOfTNode (node vT) const
	returns the type of the triconnected component represented by a given SPQR-tree-vertex.
const List< edge > &	hEdgesSPQR (node vT) const
	returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQR-tree-vertex.
SList< node > &	findPathSPQR (node sH, node tH) const
	finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.
edge	virtualEdge (node vT, node wT) const
	returns the virtual edge which leads from one vertex of an SPQR-tree to another one.


edge	updateInsertedEdge (edge eG)
	updates the whole data structure after a new edge has been inserted into the original graph.
node	updateInsertedNode (edge eG, edge fG)
	updates the whole data structure after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.
Protected Member Functions
void	init ()
	Initialization.
void	createSPQR (node vB) const
	creates the SPQR-tree for a given B-component of the BC-tree.


node	uniteSPQR (node vB, node sT, node tT)
	unites two SPQR-tree-vertices (UNION part of UNION/FIND).
node	findSPQR (node vT) const
	finds the proper representant of an SPQR-tree-vertex (FIND part of UNION/FIND).


node	findNCASPQR (node sT, node tT) const
	finds the nearest common ancestor of sT and tT.
SList< node > &	findPathSPQR (node sH, node tH, node &rT) const
	finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.


edge	updateInsertedEdgeSPQR (node vB, edge eG)
	updates an SPQR-tree after a new edge has been inserted into the original graph.
node	updateInsertedNodeSPQR (node vB, edge eG, edge fG)
	updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.
Protected Attributes
Graph	m_T
	A Graph structure containing all SPQR-trees.


NodeArray< node >	m_bNode_SPQR
	The root vertices of the SPQR-trees.
NodeArray< int >	m_bNode_numS
	The numbers of S-components.
NodeArray< int >	m_bNode_numP
	The numbers of P-components.
NodeArray< int >	m_bNode_numR
	The numbers of R-components.


NodeArray< TNodeType >	m_tNode_type
	The types of the SPQR-tree-vertices.
NodeArray< node >	m_tNode_owner
	The owners of the SPQR-tree-vertices in the UNION/FIND structure.
NodeArray< edge >	m_tNode_hRefEdge
	The virtual edges leading to the parents of the SPQR-tree-vertices.
NodeArray< List< edge > >	m_tNode_hEdges
	Lists of real and virtual edges belonging to SPQR-tree-vertices.


EdgeArray< ListIterator< edge > >	m_hEdge_position
	The positions of real and virtual edges in their m_tNode_hEdges lists.
EdgeArray< node >	m_hEdge_tNode
	The SPQR-tree-vertices which the real and virtual edges are belonging to.
EdgeArray< edge >	m_hEdge_twinEdge
	The partners of virtual edges (NULL if real).


NodeArray< node >	m_htogc
	Auxiliary array used by createSPQR().
NodeArray< bool >	m_tNode_isMarked
	Auxiliary array used by findNCASPQR().

Detailed Description

Dynamic SPQR-forest.

This class is an extension of DynamicBCTree.
It provides a set of SPQR-trees for each B-component of a BC-tree. These SPQR-trees are dynamic, i.e. there are member functions for dynamic updates (edge insertion and node insertion).

Definition at line 73 of file DynamicSPQRForest.h.

Member Enumeration Documentation

enum ogdf::DynamicSPQRForest::TNodeType

Enumeration type for characterizing the SPQR-tree-vertices.

Enumerator:

SComp	denotes a vertex representing an S-component.
PComp	denotes a vertex representing a P-component.
RComp	denotes a vertex representing an R-component.

Definition at line 89 of file DynamicSPQRForest.h.

Constructor & Destructor Documentation

ogdf::DynamicSPQRForest::DynamicSPQRForest ( Graph & G ) [inline]

A constructor.

This constructor does only create the dynamic BC-tree rooted at the first edge of G. The data structure is prepared for dealing with SPQR-trees, but they will only be created on demand. Cf. member functions findPathSPQR() and updateInsertedEdge().

Parameters:

G

is the original graph.

Definition at line 293 of file DynamicSPQRForest.h.

Member Function Documentation

void ogdf::DynamicSPQRForest::createSPQR ( node vB ) const [protected]

creates the SPQR-tree for a given B-component of the BC-tree.

An SPQR-tree belonging to a B-component of the BC-tree is only created on demand, i.e. this member function is only called by findSPQRTree() and - under certain circumstances - by updateInsertedEdge().

Parameters:

vB

is a vertex of the BC-tree representing a B-component.

Precondition:: vB has to be the proper representant of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.; The B-component represented by vB must contain at least 3 edges.

node ogdf::DynamicSPQRForest::findNCASPQR	(	node	sT,
		node	tT
	)			const `[protected]`

finds the nearest common ancestor of sT and tT.

Parameters:

	sT	is a vertex of an SPQR-tree.
	tT	is a vertex of an SPQR-tree.

Precondition:: sT and tT must belong to the same SPQR-tree.; sT and tT have to be proper representants of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.

Returns:: the proper representant of the nearest common ancestor of sT and tT.

SList<node>& ogdf::DynamicSPQRForest::findPathSPQR	(	node	sH,
		node	tH,
		node &	rT
	)			const `[protected]`

finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.

Parameters:

	sH	is a vertex of m_H.
	tH	is a vertex of m_H.
	rT	is a reference! It is set to the very vertex of the found path which is nearest to the root vertex of the SPQR-tree.

Precondition:: sH and tH must belong to the same B-component, i.e. to the same SPQR-tree. This SPQR-tree must exist!

Returns:: the path in the SPQR-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::DynamicSPQRForest::findPathSPQR	(	node	sH,
		node	tH
	)			const

finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.

Parameters:

	sH	is a vertex of m_H.
	tH	is a vertex of m_H.

Precondition:: sH and tH must belong to the same B-component, i.e. to the same SPQR-tree. This SPQR-tree does not need to exist. If it it does not exist, it will be created.

Returns:: the path in the SPQR-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!

node ogdf::DynamicSPQRForest::findSPQR ( node vT ) const [protected]

finds the proper representant of an SPQR-tree-vertex (FIND part of UNION/FIND).

Parameters:

vT

is any vertex of m_T.

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

const List<edge>& ogdf::DynamicSPQRForest::hEdgesSPQR ( node vT ) const [inline]

returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQR-tree-vertex.

Parameters:

vT

is a vertex of an SPQR-tree.

Precondition:: vT has to be the proper representant of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FIND-tree. This condition is particularly fulfilled if vT is a member of a list gained by the findPathSPQR() member function.

Returns:: a linear list of the edges in m_H belonging to the triconnected component represented by vT.

Definition at line 342 of file DynamicSPQRForest.h.

void ogdf::DynamicSPQRForest::init ( ) [protected]

Initialization.

Reimplemented from ogdf::DynamicBCTree.

node ogdf::DynamicSPQRForest::spqrproper ( edge eH ) const [inline]

finds the proper representant of the SPQR-tree-vertex which a given real or virtual edge is belonging to.

This member function has to be used carefully (see Precondition)!

Parameters:

eH

is an edge of m_H.

Precondition:: The respective SPQR-tree belonging to the B-component represented by the BC-tree-vertex bcproper(eH) must exist! Notice, that this condition is fulfilled, if eH is a member of a list gained by the hEdgesSPQR() member function, because that member function needs an SPQR-tree-vertex as parameter, which might have been found (and eventually created) by the findPathSPQR() member function.

Returns:: the proper representant of the SPQR-tree-vertex which eH is belonging to.

Definition at line 310 of file DynamicSPQRForest.h.

edge ogdf::DynamicSPQRForest::twinEdge ( edge eH ) const [inline]

returns the twin edge of a given edge of m_H, if it is virtual, or NULL, if it is real.

Parameters:

eH

is an edge of m_H.

Returns:: the twin edge of eH, if it is virtual, or NULL, if it is real.

Definition at line 318 of file DynamicSPQRForest.h.

TNodeType ogdf::DynamicSPQRForest::typeOfTNode ( node vT ) const [inline]

returns the type of the triconnected component represented by a given SPQR-tree-vertex.

Parameters:

vT

is a vertex of an SPQR-tree.

Precondition:: vT has to be the proper representant of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FIND-tree. This condition is particularly fulfilled if vT is a member of a list gained by the findPathSPQR() member function.

Returns:: the type of the triconnected component represented by vT.

Definition at line 330 of file DynamicSPQRForest.h.

node ogdf::DynamicSPQRForest::uniteSPQR	(	node	vB,
		node	sT,
		node	tT
	)			`[protected]`

unites two SPQR-tree-vertices (UNION part of UNION/FIND).

Parameters:

	vB	is a vertex of the BC-tree representing a B-component.
	sT	is a vertex of the SPQR-tree belonging to vB.
	tT	is a vertex of the SPQR-tree belonging to vB.

Precondition:: vB has to be the proper representant of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.; sT and tT have to be proper representants of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.

Returns:: the proper representant of the united SPQR-tree-vertex.

edge ogdf::DynamicSPQRForest::updateInsertedEdge ( edge eG ) [virtual]

updates the whole data structure after a new edge has been inserted into the original graph.

This member function generally updates both BC- and SPQR-trees. If any SPQR-tree of the B-components of the insertion path through the BC-tree exists, the SPQR-tree data structure of the resulting B-component will be valid afterwards. If none of the SPQR-trees does exist in advance, then only the BC-tree is updated and no SPQR-tree is created.

Parameters:

eG

is a new edge in the original graph.

Returns:: the new edge of the original graph.

Reimplemented from ogdf::DynamicBCTree.

Reimplemented in ogdf::DynamicSPQRTree.

edge ogdf::DynamicSPQRForest::updateInsertedEdgeSPQR	(	node	vB,
		edge	eG
	)			`[protected]`

updates an SPQR-tree after a new edge has been inserted into the original graph.

Parameters:

	vB	is a BC-tree-vertex representing a B-component. The SPQR-tree, which is to be updated is identified by it.
	eG	is a new edge in the original graph.

Precondition:: vB has to be the proper representant of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.; Both the source and the target vertices of eG must belong to the same B-component represented by vB.

Returns:: the new edge of the original graph.

node ogdf::DynamicSPQRForest::updateInsertedNode	(	edge	eG,
		edge	fG
	)			`[virtual]`

updates the whole data structure after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.

This member function updates the BC-tree at first. If the SPQR-tree of the B-component which the split edge is belonging to does exist, then it is updated, too. If it does not exist, it is not created.

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.

Returns:: the new vertex of the original graph.

Reimplemented from ogdf::DynamicBCTree.

Reimplemented in ogdf::DynamicSPQRTree.

node ogdf::DynamicSPQRForest::updateInsertedNodeSPQR	(	node	vB,
		edge	eG,
		edge	fG
	)			`[protected]`

updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.

Parameters:

	vB	is a BC-tree-vertex representing a B-component. The SPQR-tree, which is to be updated is identified by it.
	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.

Precondition:: The split edge must belong to the B-component which is represented by vB.

Returns:: the new vertex of the original graph.

edge ogdf::DynamicSPQRForest::virtualEdge	(	node	vT,
		node	wT
	)			const

returns the virtual edge which leads from one vertex of an SPQR-tree to another one.

Parameters:

	vT	is a vertex of an SPQR-tree.
	wT	is a vertex of an SPQR-tree.

Precondition:: vT and wT must belong to the same SPQR-tree and must be adjacent.; vT and wT have to be proper representants of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees. This condition is particularly fulfilled if vT and wT are members of a list gained by the findPathSPQR() member function.

Returns:: the virtual edge in m_H which belongs to wT and leads to vT.

Member Data Documentation

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numP [mutable, protected]

The numbers of P-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of P-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 127 of file DynamicSPQRForest.h.

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numR [mutable, protected]

The numbers of R-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of R-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 136 of file DynamicSPQRForest.h.

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numS [mutable, protected]

The numbers of S-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of S-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 118 of file DynamicSPQRForest.h.

NodeArray<node> ogdf::DynamicSPQRForest::m_bNode_SPQR [mutable, protected]

The root vertices of the SPQR-trees.

For each vertex of the BC-tree representing a B-component, this array contains the root vertex of the respective SPQR-tree, or NULL, if the SPQR-tree does not exist.

Definition at line 109 of file DynamicSPQRForest.h.

EdgeArray<ListIterator<edge> > ogdf::DynamicSPQRForest::m_hEdge_position [mutable, protected]

The positions of real and virtual edges in their m_tNode_hEdges lists.

Definition at line 162 of file DynamicSPQRForest.h.

EdgeArray<node> ogdf::DynamicSPQRForest::m_hEdge_tNode [mutable, protected]

The SPQR-tree-vertices which the real and virtual edges are belonging to.

Definition at line 167 of file DynamicSPQRForest.h.

EdgeArray<edge> ogdf::DynamicSPQRForest::m_hEdge_twinEdge [mutable, protected]

The partners of virtual edges (NULL if real).

Definition at line 171 of file DynamicSPQRForest.h.

NodeArray<node> ogdf::DynamicSPQRForest::m_htogc [mutable, protected]

Auxiliary array used by createSPQR().