ogdf: ogdf::DynamicSPQRTree Class Reference

List of all members.


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 ()
const Graph &	originalGraph () const
	Returns a reference to the original graph G.
const Graph &	tree () const
	Returns a reference to the tree T.
edge	rootEdge () const
	Returns the edge of G at which T is rooted.
node	rootNode () const
	Returns the root node of T.
int	numberOfSNodes () const
	Returns the number of S-nodes in T.
int	numberOfPNodes () const
	Returns the number of P-nodes in T.
int	numberOfRNodes () const
	Returns the number of R-nodes in T.
NodeType	typeOf (node v) const
	Returns the type of node v.
List< node >	nodesOfType (NodeType t) const
	Returns the list of all nodes with type t.
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.
Skeleton &	skeleton (node v) const
	Returns the skeleton of node v.
const Skeleton &	skeletonOfReal (edge e) const
	Returns the skeleton that contains the real edge e.
edge	copyOfReal (edge e) const
	Returns the skeleton edge that corresponds to the real edge e.
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.
node	rootTreeAt (edge e)
	Roots T at edge e and returns the new root node of T.
node	rootTreeAt (node v)
	Roots T at node v and returns v.
edge	updateInsertedEdge (edge e)
	Updates the whole data structure after a new edge e has been inserted into G.
node	updateInsertedNode (edge e, edge f)
	Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into e and f.
Protected Member Functions
void	init (edge e)
	Initialization (called by constructors).
DynamicSkeleton &	createSkeleton (node vT) const
	Creates the skeleton graph belonging to a given vertex vT of T.
void	cpRec (node v, PertinentGraph &Gp) const
	Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph.
Protected Attributes
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)
NodeArray< node >	m_mapV
	temporary array used by createSkeleton()
Friends
class	DynamicSkeleton

Detailed Description

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

Constructor & Destructor Documentation

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

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 117 of file DynamicSPQRTree.h.

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 124 of file DynamicSPQRTree.h.

ogdf::DynamicSPQRTree::~DynamicSPQRTree ( )

Member Function Documentation

const Graph& ogdf::DynamicSPQRTree::originalGraph ( ) const [inline, virtual]

Returns a reference to the original graph G.

SList<node>& ogdf::DynamicSPQRTree::findPath	(	node	s,
		node	t
	)			`[inline]`

edge ogdf::DynamicSPQRTree::skeletonEdge	(	node	v,
		node	w
	)			const `[inline]`

node ogdf::DynamicSPQRTree::updateInsertedNode	(	edge	e,
		edge	f
	)			`[virtual]`

void ogdf::DynamicSPQRTree::cpRec	(	node	v,
		PertinentGraph &	Gp
	)			const `[inline, protected, virtual]`

OpenGraph DrawingFramework

ogdf::DynamicSPQRTree Class Reference

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework