Dynamic SPQR-forest. More...

#include <ogdf/decomposition/DynamicSPQRForest.h>

Inheritance diagram for ogdf::DynamicSPQRForest:

Public Types
enum	TNodeType { TNodeType::SComp, TNodeType::PComp, TNodeType::RComp }
	Enumeration type for characterizing the SPQR-tree-vertices. More...

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

Public Member Functions
	DynamicSPQRForest (Graph &G, bool not_connected=false)
	A constructor. More...

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

	~DynamicSPQRForest ()


node	spqrproper (edge eH) const

void	createSPQR (node vB) const
	Creates the SPQR-tree for a given B-component of the BC-tree. More...

node	spqrroot (node vB) const
	Returns the root of the SPQR-tree for a given B-component of the BC-tree. More...

int	numberOfSNodes (node vB) const
	Returns the number of S-nodes in the SPQR-tree for a given B-component of the BC-tree. More...

int	numberOfPNodes (node vB) const
	Returns the number of P-nodes in the SPQR-tree for a given B-component of the BC-tree. More...

int	numberOfRNodes (node vB) const
	Returns the number of R-nodes in the SPQR-tree for a given B-component of the BC-tree. More...

const Graph &	spqrTree () const
	Returns the SPQR-tree graph. More...

node	spqrParent (node vT) const
	Returns the parent node of a node of the SPQR-tree Graph, or nullptr if `vT` is a root. More...

edge	spqrParentEdge (node vT) const
	Returns the virtual edge leading to the parents of a SPQR-tree vertex, or nullptr if `vT` is a root. More...

node	spqrNodeOf (edge eH) const
	The SPQR-tree-vertex which a real or virtual edge `eH` belongs to, if the SPQR-tree has been created using createSPQR. More...

edge	twinEdge (edge eH) const
	Returns the twin edge of a given edge of m_H, if it is virtual, or nullptr, if it is real. More...


TNodeType	typeOfTNode (node vT) const

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

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

edge	virtualEdge (node vT, node wT) const
	Returns the virtual edge which leads from one vertex of an SPQR-tree to another one. More...


edge	updateInsertedEdge (edge eG) override

node	updateInsertedNode (edge eG, edge fG) override
	Updates the whole data structure after a new vertex has been inserted into the original graph by splitting an edge into `eG` and `fG`. More...

Public Member Functions inherited from ogdf::DynamicBCTree
	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...

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	addHEdge (edge eH, node vT) const
	Adds edge `eH` to a vertex `vT` of the SPQRForest. More...

void	delHEdge (edge eH, node vT) const
	Deletes edge `eH` from m_H and removes its connection to a vertex `vT` of the SPQRForest. More...

void	init ()
	Initialization. More...

node	newSPQRNode (node vB, const TNodeType spqrNodeType) const
	Creates a new node in the SPQR-tree for a given B-component of the BC-tree. More...

edge	newTwinEdge (edge eH, node vT) const
	Creates a twin edge for `eH`, adds it to `vT` and returns it. More...


node	uniteSPQR (node vB, node sT, node tT)

node	findSPQR (node vT) const
	Finds the proper representative of an SPQR-tree-vertex (FIND part of UNION/FIND). More...


node	findNCASPQR (node sT, node tT) const

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


edge	updateInsertedEdgeSPQR (node vB, edge eG)

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

Protected Member Functions inherited from ogdf::DynamicBCTree
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
Graph	m_T
	A Graph structure containing all SPQR-trees. More...


NodeArray< node >	m_bNode_SPQR

NodeArray< int >	m_bNode_numS
	The numbers of S-components. More...

NodeArray< int >	m_bNode_numP
	The numbers of P-components. More...

NodeArray< int >	m_bNode_numR
	The numbers of R-components. More...


NodeArray< TNodeType >	m_tNode_type
	The types of the SPQR-tree-vertices. More...

NodeArray< node >	m_tNode_owner
	The owners of the SPQR-tree-vertices in the UNION/FIND structure. More...

NodeArray< edge >	m_tNode_hRefEdge
	The virtual edges leading to the parents of the SPQR-tree vertices. More...

NodeArray< List< edge > * >	m_tNode_hEdges
	Lists of real and virtual edges belonging to SPQR-tree vertices. More...


EdgeArray< ListIterator< edge > >	m_hEdge_position
	The positions of real and virtual edges in their m_tNode_hEdges lists. More...

EdgeArray< node >	m_hEdge_tNode
	The SPQR-tree-vertices which the real and virtual edges are belonging to. More...

EdgeArray< edge >	m_hEdge_twinEdge
	The partners of virtual edges (nullptr if real). More...


NodeArray< node >	m_htogc
	Auxiliary array used by createSPQR(). More...

NodeArray< bool >	m_tNode_isMarked
	Auxiliary array used by findNCASPQR() More...

Protected Attributes inherited from ogdf::DynamicBCTree
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...

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 56 of file DynamicSPQRForest.h.

Member Enumeration Documentation

◆ TNodeType

enum ogdf::DynamicSPQRForest::TNodeType

strong

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 59 of file DynamicSPQRForest.h.

Constructor & Destructor Documentation

◆ DynamicSPQRForest() [1/2]

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

inlineexplicit

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. See member function createSPQR(node).

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 309 of file DynamicSPQRForest.h.

◆ DynamicSPQRForest() [2/2]

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

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. See member functions createSPQR(node).

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 G.firstNode() will be processed.

Definition at line 323 of file DynamicSPQRForest.h.

◆ ~DynamicSPQRForest()

ogdf::DynamicSPQRForest::~DynamicSPQRForest ( )

inline

Definition at line 328 of file DynamicSPQRForest.h.

Member Function Documentation

◆ addHEdge()

void ogdf::DynamicSPQRForest::addHEdge	(	edge	eH,
		node	vT
	)		const

inlineprotected

Adds edge eH to a vertex vT of the SPQRForest.

Parameters

eH	is an edge in m_H.
vT	is a vertex in m_T.

Definition at line 181 of file DynamicSPQRForest.h.

◆ createSPQR()

void ogdf::DynamicSPQRForest::createSPQR ( node vB ) const

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

◆ delHEdge()

void ogdf::DynamicSPQRForest::delHEdge	(	edge	eH,
		node	vT
	)		const

inlineprotected

Deletes edge eH from m_H and removes its connection to a vertex vT of the SPQRForest.

Parameters

eH	is an edge in m_H.
vT	is a vertex in m_T.

Definition at line 193 of file DynamicSPQRForest.h.

◆ findNCASPQR()

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 representatives of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.

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

◆ findPathSPQR() [1/2]

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!

◆ findPathSPQR() [2/2]

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!

◆ findSPQR()

node ogdf::DynamicSPQRForest::findSPQR ( node vT ) const

protected

Finds the proper representative 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.

◆ hEdgesSPQR()

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 representative 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 457 of file DynamicSPQRForest.h.

◆ init()

void ogdf::DynamicSPQRForest::init ( )

protected

Initialization.

◆ newSPQRNode()

node ogdf::DynamicSPQRForest::newSPQRNode	(	node	vB,
		const TNodeType	spqrNodeType
	)		const

inlineprotected

Creates a new node in the SPQR-tree for a given B-component of the BC-tree.

Parameters

vB	is a vertex of the BC-tree representing a B-component.
spqrNodeType	is the type of the new SPQR-node.

Precondition: vB has to be the proper representative of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.

Returns: the newly created node in m_T.

Definition at line 158 of file DynamicSPQRForest.h.

◆ newTwinEdge()

edge ogdf::DynamicSPQRForest::newTwinEdge	(	edge	eH,
		node	vT
	)		const

inlineprotected

Creates a twin edge for eH, adds it to vT and returns it.

Parameters

eH	is an edge in m_H, whose twin edge should be created.
vT	is a vertex in m_T.

Returns: the new twin edge.

Definition at line 205 of file DynamicSPQRForest.h.

◆ numberOfPNodes()

int ogdf::DynamicSPQRForest::numberOfPNodes ( node vB ) const

inline

Returns the number of P-nodes in the SPQR-tree for a given B-component of the BC-tree.

Parameters

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

Returns: the number of P-nodes, if an SPQR-tree has been created for vB (e.g. using createSPQR(vB)) or 0 otherwise.

Definition at line 389 of file DynamicSPQRForest.h.

◆ numberOfRNodes()

int ogdf::DynamicSPQRForest::numberOfRNodes ( node vB ) const

inline

Returns the number of R-nodes in the SPQR-tree for a given B-component of the BC-tree.

Parameters

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

Returns: the number of R-nodes, if an SPQR-tree has been created for vB (e.g. using createSPQR(vB)) or 0 otherwise.

Definition at line 398 of file DynamicSPQRForest.h.

◆ numberOfSNodes()

int ogdf::DynamicSPQRForest::numberOfSNodes ( node vB ) const

inline

Returns the number of S-nodes in the SPQR-tree for a given B-component of the BC-tree.

Parameters

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

Returns: the number of S-nodes, if an SPQR-tree has been created for vB (e.g. using createSPQR(vB)) or 0 otherwise.

Definition at line 380 of file DynamicSPQRForest.h.

◆ spqrNodeOf()

node ogdf::DynamicSPQRForest::spqrNodeOf ( edge eH ) const

inline

The SPQR-tree-vertex which a real or virtual edge eH belongs to, if the SPQR-tree has been created using createSPQR.

Definition at line 421 of file DynamicSPQRForest.h.

◆ spqrParent()

node ogdf::DynamicSPQRForest::spqrParent ( node vT ) const

inline

Returns the parent node of a node of the SPQR-tree Graph, or nullptr if vT is a root.

Definition at line 404 of file DynamicSPQRForest.h.

◆ spqrParentEdge()

edge ogdf::DynamicSPQRForest::spqrParentEdge ( node vT ) const

inline

Returns the virtual edge leading to the parents of a SPQR-tree vertex, or nullptr if vT is a root.

Definition at line 418 of file DynamicSPQRForest.h.

◆ spqrproper()

node ogdf::DynamicSPQRForest::spqrproper ( edge eH ) const

inline

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

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, i.e. spqrroot(bcproper(eH)) != nullptr. Use createSPQR(eH) to initialize the respective SPQR-tree on demand otherwise.

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

Definition at line 345 of file DynamicSPQRForest.h.

◆ spqrroot()

node ogdf::DynamicSPQRForest::spqrroot ( node vB ) const

inline

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

Parameters

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

Returns: the respective root SPQR-node, if an SPQR-tree has been created for vB (e.g. using createSPQR(vB)) or nullptr otherwise.

Definition at line 371 of file DynamicSPQRForest.h.

◆ spqrTree()

const Graph& ogdf::DynamicSPQRForest::spqrTree ( ) const

inline

Returns the SPQR-tree graph.

Definition at line 401 of file DynamicSPQRForest.h.

◆ twinEdge()

edge ogdf::DynamicSPQRForest::twinEdge ( edge eH ) const

inline

Returns the twin edge of a given edge of m_H, if it is virtual, or nullptr, if it is real.

Parameters

eH	is an edge of m_H.

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

Definition at line 430 of file DynamicSPQRForest.h.

◆ typeOfTNode()

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 representative 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 444 of file DynamicSPQRForest.h.

◆ uniteSPQR()

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 representative 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 representatives of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.

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

◆ updateInsertedEdge()

edge ogdf::DynamicSPQRForest::updateInsertedEdge ( edge eG )

overridevirtual

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.

◆ updateInsertedEdgeSPQR()

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

◆ updateInsertedNode()

node ogdf::DynamicSPQRForest::updateInsertedNode	(	edge	eG,
		edge	fG
	)

overridevirtual

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.

◆ updateInsertedNodeSPQR()

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.

◆ virtualEdge()

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

◆ m_bNode_numP

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numP

mutableprotected

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 99 of file DynamicSPQRForest.h.

◆ m_bNode_numR

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numR

mutableprotected

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 109 of file DynamicSPQRForest.h.

◆ m_bNode_numS

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numS

mutableprotected

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 89 of file DynamicSPQRForest.h.

◆ m_bNode_SPQR

NodeArray<node> ogdf::DynamicSPQRForest::m_bNode_SPQR

mutableprotected

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 nullptr, if the SPQR-tree does not exist.

Definition at line 79 of file DynamicSPQRForest.h.

◆ m_hEdge_position

EdgeArray<ListIterator<edge> > ogdf::DynamicSPQRForest::m_hEdge_position

mutableprotected

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

Definition at line 128 of file DynamicSPQRForest.h.

◆ m_hEdge_tNode

EdgeArray<node> ogdf::DynamicSPQRForest::m_hEdge_tNode

mutableprotected

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

Definition at line 131 of file DynamicSPQRForest.h.

◆ m_hEdge_twinEdge

EdgeArray<edge> ogdf::DynamicSPQRForest::m_hEdge_twinEdge

mutableprotected

The partners of virtual edges (nullptr if real).

Definition at line 134 of file DynamicSPQRForest.h.

◆ m_htogc

NodeArray<node> ogdf::DynamicSPQRForest::m_htogc

mutableprotected

Auxiliary array used by createSPQR().

Definition at line 139 of file DynamicSPQRForest.h.

◆ m_T

Graph ogdf::DynamicSPQRForest::m_T

mutableprotected

A Graph structure containing all SPQR-trees.

Definition at line 70 of file DynamicSPQRForest.h.

◆ m_tNode_hEdges

NodeArray<List<edge>*> ogdf::DynamicSPQRForest::m_tNode_hEdges

mutableprotected

Lists of real and virtual edges belonging to SPQR-tree vertices.

Definition at line 123 of file DynamicSPQRForest.h.

◆ m_tNode_hRefEdge

NodeArray<edge> ogdf::DynamicSPQRForest::m_tNode_hRefEdge

mutableprotected

The virtual edges leading to the parents of the SPQR-tree vertices.

Definition at line 120 of file DynamicSPQRForest.h.

◆ m_tNode_isMarked

NodeArray<bool> ogdf::DynamicSPQRForest::m_tNode_isMarked

mutableprotected

Auxiliary array used by findNCASPQR()

Definition at line 142 of file DynamicSPQRForest.h.

◆ m_tNode_owner

NodeArray<node> ogdf::DynamicSPQRForest::m_tNode_owner

mutableprotected

The owners of the SPQR-tree-vertices in the UNION/FIND structure.

Definition at line 117 of file DynamicSPQRForest.h.

◆ m_tNode_type

NodeArray<TNodeType> ogdf::DynamicSPQRForest::m_tNode_type

mutableprotected

The types of the SPQR-tree-vertices.

Definition at line 114 of file DynamicSPQRForest.h.

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

include/ogdf/decomposition/DynamicSPQRForest.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

◆ TNodeType

Constructor & Destructor Documentation

◆ DynamicSPQRForest() [1/2]

◆ DynamicSPQRForest() [2/2]

◆ ~DynamicSPQRForest()

Member Function Documentation

◆ addHEdge()

◆ createSPQR()

◆ delHEdge()

◆ findNCASPQR()

◆ findPathSPQR() [1/2]

◆ findPathSPQR() [2/2]

◆ findSPQR()

◆ hEdgesSPQR()

◆ init()

◆ newSPQRNode()

◆ newTwinEdge()

◆ numberOfPNodes()

◆ numberOfRNodes()

◆ numberOfSNodes()

◆ spqrNodeOf()

◆ spqrParent()

◆ spqrParentEdge()

◆ spqrproper()

◆ spqrroot()

◆ spqrTree()

◆ twinEdge()

◆ typeOfTNode()

◆ uniteSPQR()

◆ updateInsertedEdge()

◆ updateInsertedEdgeSPQR()

◆ updateInsertedNode()

◆ updateInsertedNodeSPQR()

◆ virtualEdge()

Member Data Documentation

◆ m_bNode_numP

◆ m_bNode_numR

◆ m_bNode_numS

◆ m_bNode_SPQR

◆ m_hEdge_position

◆ m_hEdge_tNode

◆ m_hEdge_twinEdge

◆ m_htogc

◆ m_T

◆ m_tNode_hEdges

◆ m_tNode_hRefEdge

◆ m_tNode_isMarked

◆ m_tNode_owner

◆ m_tNode_type

Open
Graph Drawing
Framework