Linear-time implementation of static SPQR-trees. More...
#include <ogdf/decomposition/SPQRTree.h>
Public Types | |
enum | NodeType { NodeType::SNode, NodeType::PNode, NodeType::RNode } |
The type of a tree node in T. More... | |
Public Member Functions | |
SPQRTree () | |
SPQRTree (const SPQRTree ©)=delete | |
SPQRTree (SPQRTree &&move)=delete | |
virtual | ~SPQRTree () |
SPQRTree & | operator= (const SPQRTree ©)=delete |
SPQRTree & | operator= (SPQRTree &&move)=delete |
Access operations | |
virtual const Graph & | originalGraph () const =0 |
Returns a reference to the original graph G. More... | |
virtual const Graph & | tree () const =0 |
Returns a reference to the tree T. More... | |
virtual edge | rootEdge () const =0 |
Returns the edge of G at which T is rooted. More... | |
virtual node | rootNode () const =0 |
Returns the root node of T. More... | |
virtual int | numberOfSNodes () const =0 |
Returns the number of S-nodes in T. More... | |
virtual int | numberOfPNodes () const =0 |
Returns the number of P-nodes in T. More... | |
virtual int | numberOfRNodes () const =0 |
Returns the number of R-nodes in T. More... | |
virtual NodeType | typeOf (node v) const =0 |
Returns the type of node v . More... | |
virtual List< node > | nodesOfType (NodeType t) const =0 |
Returns the list of all nodes with type t . More... | |
virtual Skeleton & | skeleton (node v) const =0 |
Returns the skeleton of node v . More... | |
virtual const Skeleton & | skeletonOfReal (edge e) const =0 |
Returns the skeleton that contains the real edge e . More... | |
virtual edge | copyOfReal (edge e) const =0 |
Returns the skeleton edge that corresponds to the real edge e . More... | |
void | pertinentGraph (node v, PertinentGraph &Gp) const |
Returns the pertinent graph of tree node v in Gp . More... | |
Update operations | |
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... | |
virtual node | rootTreeAt (edge e)=0 |
Roots T at edge e and returns the new root node of T. More... | |
virtual node | rootTreeAt (node v)=0 |
Roots T at node v and returns v . More... | |
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. More... | |
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... | |
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 73 of file SPQRTree.h.
|
strong |
|
inlinevirtual |
Definition at line 79 of file SPQRTree.h.
|
inline |
Definition at line 81 of file SPQRTree.h.
|
delete |
|
delete |
Returns the skeleton edge that corresponds to the real edge e
.
e
is an edge in G Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
|
inlineprotected |
Add an edge to Gp
corresponding to eOrig
.
Definition at line 204 of file SPQRTree.h.
|
inlineprotected |
Add a node to Gp
corresponding to vOrig
if required.
Definition at line 211 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 180 of file SPQRTree.h.
Returns the list of all nodes with type t
.
Implemented in ogdf::DynamicSPQRTree.
|
pure virtual |
Returns the number of P-nodes in T.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
|
pure virtual |
Returns the number of R-nodes in T.
Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
|
pure virtual |
Returns the number of S-nodes 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
.
v
is a node in T Definition at line 142 of file SPQRTree.h.
Definition at line 189 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.
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::StaticSPQRTree, and ogdf::DynamicSPQRTree.
Returns the skeleton that contains the real edge e
.
e
is an edge in G 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
.
v
is a node in T Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.
node in pertinent graph corresponding to an original node (auxiliary member)
Definition at line 221 of file SPQRTree.h.
list of added nodes (auxiliary member)
Definition at line 222 of file SPQRTree.h.