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

#include <ogdf/decomposition/SPQRTree.h>

Inheritance diagram for ogdf::SPQRTree:

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

Public Member Functions
virtual	~SPQRTree ()
virtual edge	copyOfReal (edge e) const =0
	Returns the skeleton edge that corresponds to the real edge e.
void	directSkEdge (node vT, edge e, node src)
virtual List< node >	nodesOfType (NodeType t) const =0
	Returns the list of all nodes with type 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 int	numberOfSNodes () const =0
	Returns the number of S-nodes in T.
virtual const Graph &	originalGraph () const =0
	Returns a reference to the original graph G.
void	pertinentGraph (node v, PertinentGraph &Gp) const
	Returns the pertinent graph of tree node v in Gp.
void	replaceSkEdgeByPeak (node vT, edge e)
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 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.
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 const Graph &	tree () const =0
	Returns a reference to the tree T.
virtual NodeType	typeOf (node v) const =0
	Returns the type of node v.

Protected Member Functions
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.
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.

Protected Attributes
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)

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 94 of file SPQRTree.h.

Member Enumeration Documentation

enum ogdf::SPQRTree::NodeType

The type of a tree node in T.

Enumerator:

SNode
PNode
RNode

Definition at line 99 of file SPQRTree.h.

Constructor & Destructor Documentation

virtual ogdf::SPQRTree::~SPQRTree ( )

inlinevirtual

Definition at line 104 of file SPQRTree.h.

Member Function Documentation

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::StaticSPQRTree, and ogdf::DynamicSPQRTree.

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

inlineprotected

Add an edge to Gp corresponding to eOrig.

Definition at line 221 of file SPQRTree.h.

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

inlineprotected

Add a node to Gp corresponding to vOrig if required.

Definition at line 229 of file SPQRTree.h.

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.

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

inline

Definition at line 198 of file SPQRTree.h.

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

pure virtual

Returns the list of all nodes with type t.

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

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

pure virtual

Returns the number of P-nodes in T.

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

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

pure virtual

Returns the number of R-nodes in T.

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

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

pure virtual

Returns the number of S-nodes in T.

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

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

pure virtual

Returns a reference to the original graph G.

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

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 163 of file SPQRTree.h.

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

inline

Definition at line 205 of file SPQRTree.h.

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

pure virtual

Returns the edge of G at which T is rooted.

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

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

pure virtual

Returns the root node of T.

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

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.

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.

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::StaticSPQRTree, and ogdf::DynamicSPQRTree.

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::StaticSPQRTree, and ogdf::DynamicSPQRTree.

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

pure virtual

Returns a reference to the tree T.

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

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::StaticSPQRTree, and ogdf::DynamicSPQRTree.

Member Data Documentation

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

mutableprotected

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

Definition at line 241 of file SPQRTree.h.

SList<node> ogdf::SPQRTree::m_cpVAdded

mutableprotected

list of added nodes (auxiliary member)

Definition at line 242 of file SPQRTree.h.

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

ogdf/decomposition/SPQRTree.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework