Lineartime implementation of static SPQRtrees. More...
#include <ogdf/decomposition/SPQRTree.h>
Public Types  
enum class  NodeType { SNode , PNode , RNode } 
The type of a tree node in T. More...  
Public Member Functions  
virtual  ~SPQRTree () 
Access operations  
virtual const Graph &  originalGraph () const =0 
Returns a reference to the original graph G.  
virtual const Graph &  tree () const =0 
Returns a reference to the tree T.  
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 int  numberOfSNodes () const =0 
Returns the number of Snodes in 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 NodeType  typeOf (node v) const =0 
Returns the type of node v .  
virtual List< node >  nodesOfType (NodeType t) const =0 
Returns the list of all nodes with type t .  
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 edge  copyOfReal (edge e) const =0 
Returns the skeleton edge that corresponds to the real edge e .  
void  pertinentGraph (node v, PertinentGraph &Gp) const 
Returns the pertinent graph of tree node v in Gp .  
Update operations  
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)  
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 .  
void  directSkEdge (node vT, edge e, node src) 
void  replaceSkEdgeByPeak (node vT, edge e) 
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.  
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.  
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 70 of file SPQRTree.h.

strong 

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

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

inlineprotected 
Add a node to Gp
corresponding to vOrig
if required.
Definition at line 203 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 172 of file SPQRTree.h.
Returns the list of all nodes with type t
.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the number of Pnodes in T.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the number of Rnodes in T.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the number of Snodes in T.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns a reference to the original graph G.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.

inline 
Returns the pertinent graph of tree node v
in Gp
.
v
is a node in T Definition at line 134 of file SPQRTree.h.
Definition at line 181 of file SPQRTree.h.
Returns the edge of G at which T is rooted.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the root node of T.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Roots T at edge e
and returns the new root node of T.
e
is an edge in G Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Roots T at node v
and returns v
.
v
is a node in T Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the skeleton of node v
.
v
is a node in T Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the skeleton that contains the real edge e
.
e
is an edge in G Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns a reference to the tree T.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the type of node v
.
v
is a node in T Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
node in pertinent graph corresponding to an original node (auxiliary member)
Definition at line 213 of file SPQRTree.h.
list of added nodes (auxiliary member)
Definition at line 214 of file SPQRTree.h.