Open
Graph Drawing
Framework

 v.2007.11
 

ogdf::DynamicSPQRTree Class Reference

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

#include <DynamicSPQRTree.h>

Inheritance diagram for ogdf::DynamicSPQRTree:

ogdf::SPQRTree ogdf::DynamicSPQRForest ogdf::DynamicBCTree ogdf::BCTree ogdf::DynamicPlanarSPQRTree

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 GraphoriginalGraph () const
 Returns a reference to the original graph G.
const Graphtree () 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< nodenodesOfType (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.
Skeletonskeleton (node v) const
 Returns the skeleton of node v.
const SkeletonskeletonOfReal (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).
DynamicSkeletoncreateSkeleton (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< edgem_skelEdge
 copies of real and virtual edges in their skeleton graphs (invalid, if the skeleton does not actually exist)
NodeArray< nodem_mapV
 temporary array used by createSkeleton()

Friends

class DynamicSkeleton


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


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.

Implements ogdf::SPQRTree.

Definition at line 137 of file DynamicSPQRTree.h.

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

Returns a reference to the tree T.

Implements ogdf::SPQRTree.

Definition at line 140 of file DynamicSPQRTree.h.

edge ogdf::DynamicSPQRTree::rootEdge (  )  const [inline, virtual]

Returns the edge of G at which T is rooted.

Implements ogdf::SPQRTree.

Definition at line 143 of file DynamicSPQRTree.h.

node ogdf::DynamicSPQRTree::rootNode (  )  const [inline, virtual]

Returns the root node of T.

Implements ogdf::SPQRTree.

Definition at line 146 of file DynamicSPQRTree.h.

int ogdf::DynamicSPQRTree::numberOfSNodes (  )  const [inline, virtual]

Returns the number of S-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 149 of file DynamicSPQRTree.h.

int ogdf::DynamicSPQRTree::numberOfPNodes (  )  const [inline, virtual]

Returns the number of P-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 152 of file DynamicSPQRTree.h.

int ogdf::DynamicSPQRTree::numberOfRNodes (  )  const [inline, virtual]

Returns the number of R-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 155 of file DynamicSPQRTree.h.

NodeType ogdf::DynamicSPQRTree::typeOf ( node  v  )  const [inline, virtual]

Returns the type of node v.

Precondition:
v is a node in T

Implements ogdf::SPQRTree.

Definition at line 161 of file DynamicSPQRTree.h.

List<node> ogdf::DynamicSPQRTree::nodesOfType ( NodeType  t  )  const [virtual]

Returns the list of all nodes with type t.

Implements ogdf::SPQRTree.

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

Finds the shortest path between the two sets of vertices of T which s and t of G belong to.

Definition at line 177 of file DynamicSPQRTree.h.

Skeleton& ogdf::DynamicSPQRTree::skeleton ( node  v  )  const [inline, virtual]

Returns the skeleton of node v.

Precondition:
v is a node in T

Implements ogdf::SPQRTree.

Definition at line 183 of file DynamicSPQRTree.h.

const Skeleton& ogdf::DynamicSPQRTree::skeletonOfReal ( edge  e  )  const [inline, virtual]

Returns the skeleton that contains the real edge e.

Precondition:
e is an edge in G

Implements ogdf::SPQRTree.

Definition at line 194 of file DynamicSPQRTree.h.

edge ogdf::DynamicSPQRTree::copyOfReal ( edge  e  )  const [inline, virtual]

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

Precondition:
e is an edge in G

Implements ogdf::SPQRTree.

Definition at line 200 of file DynamicSPQRTree.h.

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

Returns the virtual edge in the skeleton of w that corresponds to the tree edge between v and w.

Precondition:
v and w are adjacent nodes in T

Definition at line 212 of file DynamicSPQRTree.h.

node ogdf::DynamicSPQRTree::rootTreeAt ( edge  e  )  [virtual]

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

Precondition:
e is an edge in G

Implements ogdf::SPQRTree.

node ogdf::DynamicSPQRTree::rootTreeAt ( node  v  )  [virtual]

Roots T at node v and returns v.

Precondition:
v is a node in T

Implements ogdf::SPQRTree.

edge ogdf::DynamicSPQRTree::updateInsertedEdge ( edge  e  )  [virtual]

Updates the whole data structure after a new edge e has been inserted into G.

Reimplemented from ogdf::DynamicSPQRForest.

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

Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into e and f.

Reimplemented from ogdf::DynamicSPQRForest.

void ogdf::DynamicSPQRTree::init ( edge  e  )  [protected]

Initialization (called by constructors).

DynamicSkeleton& ogdf::DynamicSPQRTree::createSkeleton ( node  vT  )  const [protected]

Creates the skeleton graph belonging to a given vertex vT of T.

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

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

Implements ogdf::SPQRTree.

Definition at line 262 of file DynamicSPQRTree.h.


Friends And Related Function Documentation

friend class DynamicSkeleton [friend]

Definition at line 107 of file DynamicSPQRTree.h.


Member Data Documentation

edge ogdf::DynamicSPQRTree::m_rootEdge [protected]

edge of G at which T is rooted

Definition at line 273 of file DynamicSPQRTree.h.

NodeArray<DynamicSkeleton*> ogdf::DynamicSPQRTree::m_sk [mutable, protected]

pointer to skeleton of a node in T

Definition at line 275 of file DynamicSPQRTree.h.

EdgeArray<edge> ogdf::DynamicSPQRTree::m_skelEdge [mutable, protected]

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

Definition at line 276 of file DynamicSPQRTree.h.

NodeArray<node> ogdf::DynamicSPQRTree::m_mapV [mutable, protected]

temporary array used by createSkeleton()

Definition at line 277 of file DynamicSPQRTree.h.


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

© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.

Generated on Thu Nov 22 19:40:09 2007 by doxygen 1.5.4.