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

#include <ogdf/decomposition/SPQRTree.h>

Inheritance diagram for ogdf::SPQRTree:

Public Types
enum class	NodeType { SNode , PNode , RNode }
	The type of a tree node in T. More...

Public Member Functions
virtual	~SPQRTree ()

Access operations
virtual const Graph &	originalGraph () const =0
	Returns a reference to the original graph G.

virtual const Graph &	tree () const =0
	Returns a reference to the tree T.

virtual edge	rootEdge () const =0
	Returns the edge of G at which T is rooted.

virtual node	rootNode () const =0
	Returns the root node of T.

virtual int	numberOfSNodes () const =0
	Returns the number of S-nodes in T.

virtual int	numberOfPNodes () const =0
	Returns the number of P-nodes in T.

virtual int	numberOfRNodes () const =0
	Returns the number of R-nodes in T.

virtual NodeType	typeOf (node v) const =0
	Returns the type of node `v`.

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

virtual Skeleton &	skeleton (node v) const =0
	Returns the skeleton of node `v`.

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

virtual edge	copyOfReal (edge e) const =0
	Returns the skeleton edge that corresponds to the real edge `e`.

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

Update operations
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)

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

virtual node	rootTreeAt (node v)=0
	Roots T at node `v` and returns `v`.

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

void	replaceSkEdgeByPeak (node vT, edge e)

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

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.

Detailed Description

Linear-time implementation of static SPQR-trees.

The class SPQRTree maintains the arrangement of the triconnected components of a biconnected multi-graph G [Hopcroft, Tarjan 1973] as a so-called SPQR tree T [Di Battista, Tamassia, 1996]. We call G the original graph of T.

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 Skeleton). 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 70 of file SPQRTree.h.

Member Enumeration Documentation

◆ NodeType

enum class ogdf::SPQRTree::NodeType

strong

The type of a tree node in T.

Enumerator
SNode
PNode
RNode

Definition at line 73 of file SPQRTree.h.

Constructor & Destructor Documentation

◆ ~SPQRTree()

virtual ogdf::SPQRTree::~SPQRTree ( )

inlinevirtual

Definition at line 77 of file SPQRTree.h.

Member Function Documentation

◆ copyOfReal()

virtual edge ogdf::SPQRTree::copyOfReal ( edge e ) const

pure virtual

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

Precondition: e is an edge in G

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ cpAddEdge()

edge ogdf::SPQRTree::cpAddEdge	(	edge	eOrig,
		PertinentGraph &	Gp
	)		const

inlineprotected

Add an edge to Gp corresponding to eOrig.

Definition at line 196 of file SPQRTree.h.

◆ cpAddNode()

node ogdf::SPQRTree::cpAddNode	(	node	vOrig,
		PertinentGraph &	Gp
	)		const

inlineprotected

Add a node to Gp corresponding to vOrig if required.

Definition at line 203 of file SPQRTree.h.

◆ cpRec()

virtual void ogdf::SPQRTree::cpRec	(	node	v,
		PertinentGraph &	Gp
	)		const

protectedpure virtual

Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ directSkEdge()

void ogdf::SPQRTree::directSkEdge	(	node	vT,
		edge	e,
		node	src
	)

inline

Definition at line 172 of file SPQRTree.h.

◆ nodesOfType()

virtual List< node > ogdf::SPQRTree::nodesOfType ( NodeType t ) const

pure virtual

Returns the list of all nodes with type t.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ numberOfPNodes()

virtual int ogdf::SPQRTree::numberOfPNodes ( ) const

pure virtual

Returns the number of P-nodes in T.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ numberOfRNodes()

virtual int ogdf::SPQRTree::numberOfRNodes ( ) const

pure virtual

Returns the number of R-nodes in T.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ numberOfSNodes()

virtual int ogdf::SPQRTree::numberOfSNodes ( ) const

pure virtual

Returns the number of S-nodes in T.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ originalGraph()

virtual const Graph & ogdf::SPQRTree::originalGraph ( ) const

pure virtual

Returns a reference to the original graph G.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ pertinentGraph()

void ogdf::SPQRTree::pertinentGraph	(	node	v,
		PertinentGraph &	Gp
	)		const

inline

Returns the pertinent graph of tree node v in Gp.

Precondition: v is a node in T

Definition at line 134 of file SPQRTree.h.

◆ replaceSkEdgeByPeak()

void ogdf::SPQRTree::replaceSkEdgeByPeak	(	node	vT,
		edge	e
	)

inline

Definition at line 181 of file SPQRTree.h.

◆ rootEdge()

virtual edge ogdf::SPQRTree::rootEdge ( ) const

pure virtual

Returns the edge of G at which T is rooted.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ rootNode()

virtual node ogdf::SPQRTree::rootNode ( ) const

pure virtual

Returns the root node of T.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ rootTreeAt() [1/2]

virtual node ogdf::SPQRTree::rootTreeAt ( edge e )

pure virtual

Roots T at edge e and returns the new root node of T.

Precondition: e is an edge in G

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ rootTreeAt() [2/2]

virtual node ogdf::SPQRTree::rootTreeAt ( node v )

pure virtual

Roots T at node v and returns v.

Precondition: v is a node in T

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ skeleton()

virtual Skeleton & ogdf::SPQRTree::skeleton ( node v ) const

pure virtual

Returns the skeleton of node v.

Precondition: v is a node in T

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ skeletonOfReal()

virtual const Skeleton & ogdf::SPQRTree::skeletonOfReal ( edge e ) const

pure virtual

Returns the skeleton that contains the real edge e.

Precondition: e is an edge in G

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ tree()

virtual const Graph & ogdf::SPQRTree::tree ( ) const

pure virtual

Returns a reference to the tree T.

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ typeOf()

virtual NodeType ogdf::SPQRTree::typeOf ( node v ) const

pure virtual

Returns the type of node v.

Precondition: v is a node in T

Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

Member Data Documentation

◆ m_cpV

NodeArray<node>* ogdf::SPQRTree::m_cpV

mutableprotected

node in pertinent graph corresponding to an original node (auxiliary member)

Definition at line 213 of file SPQRTree.h.

◆ m_cpVAdded

SList<node> ogdf::SPQRTree::m_cpVAdded

mutableprotected

list of added nodes (auxiliary member)

Definition at line 214 of file SPQRTree.h.

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

include/ogdf/decomposition/SPQRTree.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Update operations

Detailed Description

Member Enumeration Documentation

◆ NodeType

Constructor & Destructor Documentation

◆ ~SPQRTree()

Member Function Documentation

◆ copyOfReal()

◆ cpAddEdge()

◆ cpAddNode()

◆ cpRec()

◆ directSkEdge()

◆ nodesOfType()

◆ numberOfPNodes()

◆ numberOfRNodes()

◆ numberOfSNodes()

◆ originalGraph()

◆ pertinentGraph()

◆ replaceSkEdgeByPeak()

◆ rootEdge()

◆ rootNode()

◆ rootTreeAt() [1/2]

◆ rootTreeAt() [2/2]

◆ skeleton()

◆ skeletonOfReal()

◆ tree()

◆ typeOf()

Member Data Documentation

◆ m_cpV

◆ m_cpVAdded

Open
Graph Drawing
Framework