Linear-time implementation of dynamic SPQR-trees. More...

#include <ogdf/decomposition/DynamicSPQRTree.h>

Inheritance diagram for ogdf::DynamicSPQRTree:

Public Member Functions
	DynamicSPQRTree (Graph &G)
	Creates an SPQR tree T for graph `G` rooted at the first edge of `G`.

	DynamicSPQRTree (Graph &G, edge e)
	Creates an SPQR tree T for graph `G` rooted at the edge `e`.

	~DynamicSPQRTree ()

edge	copyOfReal (edge e) const override
	Returns the skeleton edge that corresponds to the real edge `e`.

SList< node > &	findPath (node s, node t)
	Finds the shortest path between the two sets of vertices of T which `s` and `t` of G belong to.

List< node >	nodesOfType (NodeType t) const override
	Returns the list of all nodes with type `t`.

int	numberOfPNodes () const override
	Returns the number of P-nodes in T.

int	numberOfRNodes () const override
	Returns the number of R-nodes in T.

int	numberOfSNodes () const override
	Returns the number of S-nodes in T.

const Graph &	originalGraph () const override
	Returns a reference to the original graph G.

edge	rootEdge () const override
	Returns the edge of G at which T is rooted.

node	rootNode () const override
	Returns the root node of T.

node	rootTreeAt (edge e) override
	Roots T at edge `e` and returns the new root node of T.

node	rootTreeAt (node v) override
	Roots T at node `v` and returns `v`.

Skeleton &	skeleton (node v) const override
	Returns the skeleton of node `v`.

edge	skeletonEdge (node v, node w) const
	Returns the virtual edge in the skeleton of `w` that corresponds to the tree edge between `v` and `w`.

const Skeleton &	skeletonOfReal (edge e) const override
	Returns the skeleton that contains the real edge `e`.

const Graph &	tree () const override
	Returns a reference to the tree T.

NodeType	typeOf (node v) const override
	Returns the type of node `v`.

edge	updateInsertedEdge (edge e) override
	Updates the whole data structure after a new edge `e` has been inserted into G.

node	updateInsertedNode (edge e, edge f) override
	Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into `e` and `f`.

Public Member Functions inherited from ogdf::SPQRTree
virtual	~SPQRTree ()

void	pertinentGraph (node v, PertinentGraph &Gp) const
	Returns the pertinent graph of tree node `v` in `Gp`.

void	directSkEdge (node vT, edge e, node src)

void	replaceSkEdgeByPeak (node vT, edge e)

Public Member Functions inherited from ogdf::DynamicSPQRForest
	DynamicSPQRForest (Graph &G)
	A constructor.

	~DynamicSPQRForest ()

node	spqrproper (edge eH) const

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.

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.

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.

Public Member Functions inherited from ogdf::DynamicBCTree
	DynamicBCTree (Graph &G, bool callInitConnected=false)

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

node	bcproper (node vG) const override

node	bcproper (edge eG) const override
	Returns the BC-tree-vertex representing the biconnected component which a given edge of the original graph is belonging to.

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.

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

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

node	bComponent (node uG, node vG) const

Public Member Functions inherited from ogdf::BCTree
	BCTree (Graph &G, bool callInitConnected=false)
	A constructor.

	BCTree (Graph &G, List< node > &vG)
	Constructor for not connected graphs.

	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

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)

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

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

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.

Protected Member Functions
void	cpRec (node v, PertinentGraph &Gp) const override
	Recursively performs the task of adding edges (and nodes) to the pertinent graph `Gp` for each involved skeleton graph.

DynamicSkeleton &	createSkeleton (node vT) const
	Creates the skeleton graph belonging to a given vertex `vT` of T.

void	init (edge e)
	Initialization (called by constructors).

Protected Member Functions inherited from ogdf::SPQRTree
edge	cpAddEdge (edge eOrig, PertinentGraph &Gp) const
	Add an edge to `Gp` corresponding to `eOrig`.

node	cpAddNode (node vOrig, PertinentGraph &Gp) const
	Add a node to `Gp` corresponding to `vOrig` if required.

Protected Member Functions inherited from ogdf::DynamicSPQRForest
void	addHEdge (edge eH, node vT) const
	Adds edge `eH` to a vertex `vT` of the SPQRForest.

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

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

void	init ()
	Initialization.

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.

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

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

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.

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

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.

node	parent (node vB) const override

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

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

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

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

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

void	init (node vG)

Protected Attributes
NodeArray< node >	m_mapV
	temporary array used by createSkeleton()

edge	m_rootEdge
	edge of G at which T is rooted

NodeArray< DynamicSkeleton * >	m_sk
	pointer to skeleton of a node in T

EdgeArray< edge >	m_skelEdge
	copies of real and virtual edges in their skeleton graphs (invalid, if the skeleton does not actually exist)

Protected Attributes inherited from ogdf::SPQRTree
NodeArray< node > *	m_cpV
	node in pertinent graph corresponding to an original node (auxiliary member)

SList< node >	m_cpVAdded
	list of added nodes (auxiliary member)

Protected Attributes inherited from ogdf::DynamicSPQRForest
Graph	m_T
	A Graph structure containing all SPQR-trees.

NodeArray< node >	m_bNode_SPQR

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 (nullptr if real).

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

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

Protected Attributes inherited from ogdf::DynamicBCTree
NodeArray< int >	m_bNode_degree
	Array that contains for each proper BC-tree-vertex its degree.

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

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

Graph &	m_G
	The original graph.

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

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

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

NodeArray< int >	m_number
	Temporary array.

NodeArray< int >	m_lowpt
	Temporary array.

ArrayBuffer< adjEntry >	m_eStack
	Temporary stack.

NodeArray< node >	m_gtoh
	Temporary array.

SList< node >	m_nodes
	Temporary list.

Friends
class	DynamicSkeleton

Additional Inherited Members
Public Types inherited from ogdf::SPQRTree
enum class	NodeType { SNode , PNode , RNode }
	The type of a tree node in T. More...

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

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

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

Detailed Description

Linear-time implementation of dynamic SPQR-trees.

The class DynamicSPQRTree maintains the arrangement of the triconnected components of a biconnected multi-graph G [Hopcroft, Tarjan 1973] as a so-called SPQR tree T [Fi Battista, Tamassia, 1996]. We call G the original graph of T. The class DynamicSPQRTree supports the statical construction of an SPQR-tree for a given graph G, and supports dynamic updates, too.

Each node of the tree has an associated type (represented by SPQRTree::NodeType), which is either SNode, PNode, or RNode, and a skeleton (represented by the class DynamicSkeleton). The skeletons of the nodes of T are in one-to-one correspondence to the triconnected components of G, i.e., S-nodes correspond to polygons, P-nodes to bonds, and R-nodes to triconnected graphs.

In our representation of SPQR-trees, Q-nodes are omitted. Instead, the skeleton S of a node v in T contains two types of edges: real edges, which correspond to edges in G, and virtual edges, which correspond to edges in T having v as an endpoint. There is a special edge er in G at which T is rooted, i.e., the root node of T is the node whose skeleton contains the real edge corresponding to er.

The reference edge of the skeleton of the root node is er, the reference edge of the skeleton S of a non-root node v is the virtual edge in S that corresponds to the tree edge (parent(v),v).

Definition at line 73 of file DynamicSPQRTree.h.

Constructor & Destructor Documentation

◆ DynamicSPQRTree() [1/2]

ogdf::DynamicSPQRTree::DynamicSPQRTree ( Graph & G )

inlineexplicit

Creates an SPQR tree T for graph G rooted at the first edge of G.

Precondition: G is biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 edges.

Definition at line 84 of file DynamicSPQRTree.h.

◆ DynamicSPQRTree() [2/2]

ogdf::DynamicSPQRTree::DynamicSPQRTree	(	Graph &	G,
		edge	e
	)

inline

Creates an SPQR tree T for graph G rooted at the edge e.

Precondition: e is in G, G is biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 edges.

Definition at line 91 of file DynamicSPQRTree.h.

◆ ~DynamicSPQRTree()

ogdf::DynamicSPQRTree::~DynamicSPQRTree ( )

Member Function Documentation

◆ copyOfReal()

edge ogdf::DynamicSPQRTree::copyOfReal ( edge e ) const

inlineoverridevirtual

Returns the skeleton edge that corresponds to the real edge e.

Precondition: e is an edge in G

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ DynamicSPQRTree() [1/2]

◆ DynamicSPQRTree() [2/2]

◆ ~DynamicSPQRTree()

Member Function Documentation

◆ copyOfReal()

◆ cpRec()

◆ createSkeleton()

◆ findPath()

◆ init()

◆ nodesOfType()

◆ numberOfPNodes()

◆ numberOfRNodes()

◆ numberOfSNodes()

◆ originalGraph()

◆ rootEdge()

◆ rootNode()

◆ rootTreeAt() [1/2]

◆ rootTreeAt() [2/2]

◆ skeleton()

◆ skeletonEdge()

◆ skeletonOfReal()

◆ tree()

◆ typeOf()

◆ updateInsertedEdge()

◆ updateInsertedNode()

Friends And Related Symbol Documentation

◆ DynamicSkeleton

Member Data Documentation

◆ m_mapV

◆ m_rootEdge

◆ m_sk

◆ m_skelEdge

Open
Graph Drawing
Framework