Open
Graph Drawing
Framework

 v.2012.07
 

ogdf::SPQRTree Class Reference

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

#include <ogdf/decomposition/SPQRTree.h>

+ Inheritance diagram for ogdf::SPQRTree:

List of all members.

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< nodenodesOfType (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 GraphoriginalGraph () 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 Skeletonskeleton (node v) const =0
 Returns the skeleton of node v.
virtual const SkeletonskeletonOfReal (edge e) const =0
 Returns the skeleton that contains the real edge e.
virtual const Graphtree () 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< nodem_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

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: