Lineartime implementation of static SPQRtrees. More...
#include <ogdf/decomposition/SPQRTree.h>
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 Pnodes in T.  
virtual int  numberOfRNodes () const =0 
Returns the number of Rnodes in T.  
virtual int  numberOfSNodes () const =0 
Returns the number of Snodes 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) 
Lineartime implementation of static SPQRtrees.
The class SPQRTree maintains the arrangement of the triconnected components of a biconnected multigraph G [Hopcroft, Tarjan 1973] as a socalled 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 onetoone correspondence to the triconnected components of G, i.e., Snodes correspond to polygons, Pnodes to bonds, and Rnodes to triconnected graphs.
In our representation of SPQRtrees, Qnodes 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 nonroot 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.
The type of a tree node in T.
Definition at line 99 of file SPQRTree.h.

inlinevirtual 
Definition at line 104 of file SPQRTree.h.
Returns the skeleton edge that corresponds to the real edge e.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

inlineprotected 
Add an edge to Gp corresponding to eOrig.
Definition at line 221 of file SPQRTree.h.

inlineprotected 
Add a node to Gp corresponding to vOrig if required.
Definition at line 229 of file SPQRTree.h.

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.
Definition at line 198 of file SPQRTree.h.
Returns the list of all nodes with type t.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

pure virtual 
Returns the number of Pnodes in T.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

pure virtual 
Returns the number of Rnodes in T.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

pure virtual 
Returns the number of Snodes in T.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

pure virtual 
Returns a reference to the original graph G.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

inline 
Returns the pertinent graph of tree node v in Gp.
Definition at line 163 of file SPQRTree.h.
Definition at line 205 of file SPQRTree.h.

pure virtual 
Returns the edge of G at which T is rooted.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

pure virtual 
Returns the root node of T.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
Roots T at edge e and returns the new root node of T.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Roots T at node v and returns v.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the skeleton of node v.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
Returns the skeleton that contains the real edge e.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

pure virtual 
Returns a reference to the tree T.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
Returns the type of node v.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
node in pertinent graph corresponding to an original node (auxiliary member)
Definition at line 241 of file SPQRTree.h.
list of added nodes (auxiliary member)
Definition at line 242 of file SPQRTree.h.