Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Member Functions | Protected Member Functions | Protected Attributes | Friends

ogdf::DynamicSPQRTree Class Reference

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

#include <ogdf/decomposition/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 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

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

ogdf::DynamicSPQRTree::~DynamicSPQRTree (  ) 

Member Function Documentation

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

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

Precondition:
e is an edge in G

Definition at line 154 of file DynamicSPQRTree.h.

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

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

Definition at line 216 of file DynamicSPQRTree.h.

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

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

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

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

Initialization (called by constructors).

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

Returns the list of all nodes with type t.

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

Returns the number of P-nodes in T.

Definition at line 113 of file DynamicSPQRTree.h.

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

Returns the number of R-nodes in T.

Definition at line 116 of file DynamicSPQRTree.h.

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

Returns the number of S-nodes in T.

Definition at line 110 of file DynamicSPQRTree.h.

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

Returns a reference to the original graph G.

Reimplemented from ogdf::BCTree.

Definition at line 98 of file DynamicSPQRTree.h.

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

Returns the edge of G at which T is rooted.

Definition at line 104 of file DynamicSPQRTree.h.

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

Returns the root node of T.

Definition at line 107 of file DynamicSPQRTree.h.

node ogdf::DynamicSPQRTree::rootTreeAt ( node  v  ) 

Roots T at node v and returns v.

Precondition:
v is a node in T
node ogdf::DynamicSPQRTree::rootTreeAt ( edge  e  ) 

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

Precondition:
e is an edge in G
Skeleton& ogdf::DynamicSPQRTree::skeleton ( node  v  )  const [inline]

Returns the skeleton of node v.

Precondition:
v is a node in T

Definition at line 137 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 166 of file DynamicSPQRTree.h.

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

Returns the skeleton that contains the real edge e.

Precondition:
e is an edge in G

Definition at line 148 of file DynamicSPQRTree.h.

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

Returns a reference to the tree T.

Definition at line 101 of file DynamicSPQRTree.h.

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

Returns the type of node v.

Precondition:
v is a node in T

Definition at line 122 of file DynamicSPQRTree.h.

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.

Friends And Related Function Documentation

friend class DynamicSkeleton [friend]

Definition at line 68 of file DynamicSPQRTree.h.

Member Data Documentation

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

temporary array used by createSkeleton()

Definition at line 231 of file DynamicSPQRTree.h.

edge ogdf::DynamicSPQRTree::m_rootEdge [protected]

edge of G at which T is rooted

Definition at line 227 of file DynamicSPQRTree.h.

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

pointer to skeleton of a node in T

Definition at line 229 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 230 of file DynamicSPQRTree.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:16 by doxygen 1.7.1.