Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::SPQRTree Class Referenceabstract

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

#include <ogdf/decomposition/SPQRTree.h>

+ Inheritance diagram for ogdf::SPQRTree:

Public Types

enum  NodeType { NodeType::SNode, NodeType::PNode, NodeType::RNode }
 The type of a tree node in T. More...
 

Public Member Functions

virtual ~SPQRTree ()
 
Access operations
virtual const GraphoriginalGraph () const =0
 Returns a reference to the original graph G. More...
 
virtual const Graphtree () 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< nodenodesOfType (NodeType t) const =0
 Returns the list of all nodes with type t. More...
 
virtual Skeletonskeleton (node v) const =0
 Returns the skeleton of node v. More...
 
virtual const SkeletonskeletonOfReal (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< nodem_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...
 

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 71 of file SPQRTree.h.

Member Enumeration Documentation

◆ NodeType

The type of a tree node in T.

Enumerator
SNode 
PNode 
RNode 

Definition at line 75 of file SPQRTree.h.

Constructor & Destructor Documentation

◆ ~SPQRTree()

virtual ogdf::SPQRTree::~SPQRTree ( )
inlinevirtual

Definition at line 79 of file SPQRTree.h.

Member Function Documentation

◆ copyOfReal()

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.

◆ cpAddEdge()

edge ogdf::SPQRTree::cpAddEdge ( edge  eOrig,
PertinentGraph Gp 
) const
inlineprotected

Add an edge to Gp corresponding to eOrig.

Definition at line 195 of file SPQRTree.h.

◆ cpAddNode()

node ogdf::SPQRTree::cpAddNode ( node  vOrig,
PertinentGraph Gp 
) const
inlineprotected

Add a node to Gp corresponding to vOrig if required.

Definition at line 203 of file SPQRTree.h.

◆ cpRec()

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.

◆ directSkEdge()

void ogdf::SPQRTree::directSkEdge ( node  vT,
edge  e,
node  src 
)
inline

Definition at line 170 of file SPQRTree.h.

◆ nodesOfType()

virtual List<node> ogdf::SPQRTree::nodesOfType ( NodeType  t) const
pure virtual

Returns the list of all nodes with type t.

Implemented in ogdf::DynamicSPQRTree.

◆ numberOfPNodes()

virtual int ogdf::SPQRTree::numberOfPNodes ( ) const
pure virtual

Returns the number of P-nodes in T.

Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

◆ numberOfRNodes()

virtual int ogdf::SPQRTree::numberOfRNodes ( ) const
pure virtual

Returns the number of R-nodes in T.

Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

◆ numberOfSNodes()

virtual int ogdf::SPQRTree::numberOfSNodes ( ) const
pure virtual

Returns the number of S-nodes in T.

Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

◆ originalGraph()

virtual const Graph& ogdf::SPQRTree::originalGraph ( ) const
pure virtual

Returns a reference to the original graph G.

Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

◆ pertinentGraph()

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 136 of file SPQRTree.h.

◆ replaceSkEdgeByPeak()

void ogdf::SPQRTree::replaceSkEdgeByPeak ( node  vT,
edge  e 
)
inline

Definition at line 178 of file SPQRTree.h.

◆ rootEdge()

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.

◆ rootNode()

virtual node ogdf::SPQRTree::rootNode ( ) const
pure virtual

Returns the root node of T.

Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

◆ rootTreeAt() [1/2]

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.

◆ rootTreeAt() [2/2]

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.

◆ skeleton()

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::DynamicSPQRTree, and ogdf::StaticSPQRTree.

◆ skeletonOfReal()

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.

◆ tree()

virtual const Graph& ogdf::SPQRTree::tree ( ) const
pure virtual

Returns a reference to the tree T.

Implemented in ogdf::StaticSPQRTree, and ogdf::DynamicSPQRTree.

◆ typeOf()

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

◆ m_cpV

NodeArray<node>* ogdf::SPQRTree::m_cpV
mutableprotected

node in pertinent graph corresponding to an original node (auxiliary member)

Definition at line 214 of file SPQRTree.h.

◆ m_cpVAdded

SList<node> ogdf::SPQRTree::m_cpVAdded
mutableprotected

list of added nodes (auxiliary member)

Definition at line 215 of file SPQRTree.h.


The documentation for this class was generated from the following file: