Lineartime implementation of static SPQRtrees. More...
#include <ogdf/decomposition/StaticSPQRTree.h>
Public Member Functions  
StaticSPQRTree (const Graph &G)  
Creates an SPQR tree T for graph G rooted at the first edge of G . More...  
StaticSPQRTree (const Graph &G, edge e)  
Creates an SPQR tree T for graph G rooted at the edge e . More...  
StaticSPQRTree (const Graph &G, Triconnectivity &tricComp)  
Creates an SPQR tree T for graph G rooted at the first edge of G . More...  
~StaticSPQRTree ()  
Destructor. More...  
Access operations  
const Graph &  originalGraph () const override 
Returns a reference to the original graph G. More...  
const Graph &  tree () const override 
Returns a reference to the tree T. More...  
edge  rootEdge () const override 
Returns the edge of G at which T is rooted. More...  
node  rootNode () const override 
Returns the root node of T. More...  
int  numberOfSNodes () const override 
Returns the number of Snodes in T. More...  
int  numberOfPNodes () const override 
Returns the number of Pnodes in T. More...  
int  numberOfRNodes () const override 
Returns the number of Rnodes in T. More...  
NodeType  typeOf (node v) const override 
Returns the type of node v . More...  
List< node >  nodesOfType (NodeType t) const override 
Returns the list of all nodes with type t . More...  
Skeleton &  skeleton (node v) const override 
Returns the skeleton of node v . More...  
edge  skeletonEdgeSrc (edge e) const 
Returns the edge in skeleton of source(e ) that corresponds to tree edge e . More...  
edge  skeletonEdgeTgt (edge e) const 
Returns the edge in skeleton of target(e ) that corresponds to tree edge e . More...  
const Skeleton &  skeletonOfReal (edge e) const override 
Returns the skeleton that contains the real edge e . More...  
edge  copyOfReal (edge e) const override 
Returns the skeleton edge that corresponds to the real edge e . More...  
Update operations  
node  rootTreeAt (edge e) override 
Roots T at edge e and returns the new root node of T. More...  
node  rootTreeAt (node v) override 
Roots T at node v and returns v . More...  
Public Member Functions inherited from ogdf::SPQRTree  
SPQRTree ()  
SPQRTree (const SPQRTree ©)=delete  
SPQRTree (SPQRTree &&move)=delete  
virtual  ~SPQRTree () 
SPQRTree &  operator= (const SPQRTree ©)=delete 
SPQRTree &  operator= (SPQRTree &&move)=delete 
virtual List< node >  nodesOfType (NodeType t) const =0 
Returns the list of all nodes with type t . More...  
void  pertinentGraph (node v, PertinentGraph &Gp) const 
Returns the pertinent graph of tree node v in Gp . More...  
void  directSkEdge (node vT, edge e, node src) 
void  replaceSkEdgeByPeak (node vT, edge e) 
Protected Member Functions  
void  cpRec (node v, PertinentGraph &Gp) const override 
Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph. More...  
void  init (edge e) 
Initialization (called by constructor). More...  
void  init (edge eRef, Triconnectivity &tricComp) 
Initialization (called by constructor). More...  
void  rootRec (node v, edge ef) 
Recursively performs rooting of tree. More...  
Protected Member Functions inherited from ogdf::SPQRTree  
edge  cpAddEdge (edge eOrig, PertinentGraph &Gp) const 
Add an edge to Gp corresponding to eOrig . More...  
node  cpAddNode (node vOrig, PertinentGraph &Gp) const 
Add a node to Gp corresponding to vOrig if required. More...  
Protected Attributes  
EdgeArray< edge >  m_copyOf 
skeleton edge corresponding to real edge e More...  
int  m_numP 
number of Pnodes More...  
int  m_numR 
number of Rnodes More...  
int  m_numS 
number of Snodes More...  
const Graph *  m_pGraph 
pointer to original graph More...  
edge  m_rootEdge 
edge of G at which T is rooted More...  
node  m_rootNode 
root node of T More...  
NodeArray< StaticSkeleton * >  m_sk 
pointer to skeleton of a node in T More...  
EdgeArray< edge >  m_skEdgeSrc 
corresponding edge in skeleton(source(e)) More...  
EdgeArray< edge >  m_skEdgeTgt 
corresponding edge in skeleton(target(e)) More...  
EdgeArray< StaticSkeleton * >  m_skOf 
skeleton containing real edge e More...  
Graph  m_tree 
underlying tree graph More...  
NodeArray< NodeType >  m_type 
type of nodes in T More...  
Protected Attributes inherited from ogdf::SPQRTree  
NodeArray< node > *  m_cpV 
node in pertinent graph corresponding to an original node (auxiliary member) More...  
SList< node >  m_cpVAdded 
list of added nodes (auxiliary member) More...  
Friends  
class  StaticSkeleton 
Additional Inherited Members  
Public Types inherited from ogdf::SPQRTree  
enum  NodeType { NodeType::SNode, NodeType::PNode, NodeType::RNode } 
The type of a tree node in T. More...  
Lineartime implementation of static SPQRtrees.
The class StaticSPQRTree maintains the arrangement of the triconnected components of a biconnected multigraph G [Hopcroft, Tarjan 1973] as a socalled SPQR tree T [Fi Battista, Tamassia, 1996]. We call G the original graph of T. The class StaticSPQRTree supports only the statical construction of an SPQRtree for a given graph G, dynamic updates are not supported.
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 StaticSkeleton). 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 73 of file StaticSPQRTree.h.

inlineexplicit 
Creates an SPQR tree T for graph G
rooted at the first edge of G
.
G
is biconnected and contains at least 3 nodes, or G
has exactly 2 nodes and at least 3 edges. Definition at line 84 of file StaticSPQRTree.h.
Creates an SPQR tree T for graph G
rooted at the edge e
.
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 95 of file StaticSPQRTree.h.

inline 
Creates an SPQR tree T for graph G
rooted at the first edge of G
.
G
is biconnected and contains at least 3 nodes, or G
has exactly 2 nodes and at least 3 edges. Definition at line 105 of file StaticSPQRTree.h.
ogdf::StaticSPQRTree::~StaticSPQRTree  (  ) 
Destructor.
Returns the skeleton edge that corresponds to the real edge e
.
e
is an edge in G Implements ogdf::SPQRTree.
Definition at line 174 of file StaticSPQRTree.h.

inlineoverrideprotectedvirtual 
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 208 of file StaticSPQRTree.h.

protected 
Initialization (called by constructor).

protected 
Initialization (called by constructor).
Returns the list of all nodes with type t
.

inlineoverridevirtual 
Returns the number of Pnodes in T.
Implements ogdf::SPQRTree.
Definition at line 132 of file StaticSPQRTree.h.

inlineoverridevirtual 
Returns the number of Rnodes in T.
Implements ogdf::SPQRTree.
Definition at line 135 of file StaticSPQRTree.h.

inlineoverridevirtual 
Returns the number of Snodes in T.
Implements ogdf::SPQRTree.
Definition at line 129 of file StaticSPQRTree.h.

inlineoverridevirtual 
Returns a reference to the original graph G.
Implements ogdf::SPQRTree.
Definition at line 117 of file StaticSPQRTree.h.

inlineoverridevirtual 
Returns the edge of G at which T is rooted.
Implements ogdf::SPQRTree.
Definition at line 123 of file StaticSPQRTree.h.

inlineoverridevirtual 
Returns the root node of T.
Implements ogdf::SPQRTree.
Definition at line 126 of file StaticSPQRTree.h.
Recursively performs rooting of tree.
Roots T at edge e
and returns the new root node of T.
e
is an edge in G Implements ogdf::SPQRTree.
Returns the skeleton of node v
.
v
is a node in T Implements ogdf::SPQRTree.
Definition at line 150 of file StaticSPQRTree.h.
Returns the edge in skeleton of source(e
) that corresponds to tree edge e
.
e
is an edge in T Definition at line 156 of file StaticSPQRTree.h.
Returns the edge in skeleton of target(e
) that corresponds to tree edge e
.
e
is an edge in T Definition at line 162 of file StaticSPQRTree.h.
Returns the skeleton that contains the real edge e
.
e
is an edge in G Implements ogdf::SPQRTree.
Definition at line 168 of file StaticSPQRTree.h.

inlineoverridevirtual 
Returns a reference to the tree T.
Implements ogdf::SPQRTree.
Definition at line 120 of file StaticSPQRTree.h.
Returns the type of node v
.
v
is a node in T Implements ogdf::SPQRTree.
Definition at line 141 of file StaticSPQRTree.h.

friend 
Definition at line 75 of file StaticSPQRTree.h.
skeleton edge corresponding to real edge e
Definition at line 243 of file StaticSPQRTree.h.

protected 
number of Pnodes
Definition at line 233 of file StaticSPQRTree.h.

protected 
number of Rnodes
Definition at line 234 of file StaticSPQRTree.h.

protected 
number of Snodes
Definition at line 232 of file StaticSPQRTree.h.

protected 
pointer to original graph
Definition at line 226 of file StaticSPQRTree.h.

protected 
edge of G at which T is rooted
Definition at line 229 of file StaticSPQRTree.h.

protected 
root node of T
Definition at line 230 of file StaticSPQRTree.h.

protected 
pointer to skeleton of a node in T
Definition at line 238 of file StaticSPQRTree.h.
corresponding edge in skeleton(source(e))
Definition at line 239 of file StaticSPQRTree.h.
corresponding edge in skeleton(target(e))
Definition at line 240 of file StaticSPQRTree.h.

protected 
skeleton containing real edge e
Definition at line 242 of file StaticSPQRTree.h.

protected 
underlying tree graph
Definition at line 227 of file StaticSPQRTree.h.
type of nodes in T
Definition at line 236 of file StaticSPQRTree.h.