# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::StaticSPQRTree Class Reference

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

#include <ogdf/decomposition/StaticSPQRTree.h>

Inheritance diagram for ogdf::StaticSPQRTree:

## 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 GraphoriginalGraph () const override
Returns a reference to the original graph G. More...

const Graphtree () 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 S-nodes in T. More...

int numberOfPNodes () const override
Returns the number of P-nodes in T. More...

int numberOfRNodes () const override
Returns the number of R-nodes in T. More...

NodeType typeOf (node v) const override
Returns the type of node v. More...

List< nodenodesOfType (NodeType t) const override
Returns the list of all nodes with type t. More...

Skeletonskeleton (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 SkeletonskeletonOfReal (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
virtual ~SPQRTree ()

virtual List< nodenodesOfType (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< edgem_copyOf
skeleton edge corresponding to real edge e More...

int m_numP
number of P-nodes More...

int m_numR
number of R-nodes More...

int m_numS
number of S-nodes More...

const Graphm_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< edgem_skEdgeSrc
corresponding edge in skeleton(source(e)) More...

EdgeArray< edgem_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< NodeTypem_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...

list of added nodes (auxiliary member) More...

## Friends

class StaticSkeleton

Public Types inherited from ogdf::SPQRTree
enum  NodeType { NodeType::SNode, NodeType::PNode, NodeType::RNode }
The type of a tree node in T. More...

## Detailed Description

Linear-time implementation of static SPQR-trees.

The class StaticSPQRTree maintains the arrangement of the triconnected components of a biconnected multi-graph G [Hopcroft, Tarjan 1973] as a so-called 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 SPQR-tree 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 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 StaticSPQRTree.h.

## ◆ StaticSPQRTree() [1/3]

 ogdf::StaticSPQRTree::StaticSPQRTree ( const Graph & G )
inlineexplicit

Creates an SPQR tree T for graph G rooted at the first edge of G.

Precondition
G is biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 edges.

Definition at line 85 of file StaticSPQRTree.h.

## ◆ StaticSPQRTree() [2/3]

 ogdf::StaticSPQRTree::StaticSPQRTree ( const Graph & G, edge e )
inline

Creates an SPQR tree T for graph G rooted at the edge e.

Precondition
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 92 of file StaticSPQRTree.h.

## ◆ StaticSPQRTree() [3/3]

 ogdf::StaticSPQRTree::StaticSPQRTree ( const Graph & G, Triconnectivity & tricComp )
inline

Creates an SPQR tree T for graph G rooted at the first edge of G.

Precondition
G is biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 edges.

Definition at line 99 of file StaticSPQRTree.h.

## ◆ ~StaticSPQRTree()

 ogdf::StaticSPQRTree::~StaticSPQRTree ( )

Destructor.

## ◆ copyOfReal()

 edge ogdf::StaticSPQRTree::copyOfReal ( edge e ) const
inlineoverridevirtual

Returns the skeleton edge that corresponds to the real edge e.

Precondition
e is an edge in G

Implements ogdf::SPQRTree.

Definition at line 165 of file StaticSPQRTree.h.

## ◆ cpRec()

 void ogdf::StaticSPQRTree::cpRec ( node v, PertinentGraph & Gp ) const
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 200 of file StaticSPQRTree.h.

## ◆ init() [1/2]

 void ogdf::StaticSPQRTree::init ( edge e )
protected

Initialization (called by constructor).

## ◆ init() [2/2]

 void ogdf::StaticSPQRTree::init ( edge eRef, Triconnectivity & tricComp )
protected

Initialization (called by constructor).

## ◆ nodesOfType()

 List ogdf::StaticSPQRTree::nodesOfType ( NodeType t ) const
override

Returns the list of all nodes with type t.

## ◆ numberOfPNodes()

 int ogdf::StaticSPQRTree::numberOfPNodes ( ) const
inlineoverridevirtual

Returns the number of P-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 123 of file StaticSPQRTree.h.

## ◆ numberOfRNodes()

 int ogdf::StaticSPQRTree::numberOfRNodes ( ) const
inlineoverridevirtual

Returns the number of R-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 126 of file StaticSPQRTree.h.

## ◆ numberOfSNodes()

 int ogdf::StaticSPQRTree::numberOfSNodes ( ) const
inlineoverridevirtual

Returns the number of S-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 120 of file StaticSPQRTree.h.

## ◆ originalGraph()

 const Graph& ogdf::StaticSPQRTree::originalGraph ( ) const
inlineoverridevirtual

Returns a reference to the original graph G.

Implements ogdf::SPQRTree.

Definition at line 108 of file StaticSPQRTree.h.

## ◆ rootEdge()

 edge ogdf::StaticSPQRTree::rootEdge ( ) const
inlineoverridevirtual

Returns the edge of G at which T is rooted.

Implements ogdf::SPQRTree.

Definition at line 114 of file StaticSPQRTree.h.

## ◆ rootNode()

 node ogdf::StaticSPQRTree::rootNode ( ) const
inlineoverridevirtual

Returns the root node of T.

Implements ogdf::SPQRTree.

Definition at line 117 of file StaticSPQRTree.h.

## ◆ rootRec()

 void ogdf::StaticSPQRTree::rootRec ( node v, edge ef )
protected

Recursively performs rooting of tree.

## ◆ rootTreeAt() [1/2]

 node ogdf::StaticSPQRTree::rootTreeAt ( edge e )
overridevirtual

Roots T at edge e and returns the new root node of T.

Precondition
e is an edge in G

Implements ogdf::SPQRTree.

## ◆ rootTreeAt() [2/2]

 node ogdf::StaticSPQRTree::rootTreeAt ( node v )
overridevirtual

Roots T at node v and returns v.

Precondition
v is a node in T

Implements ogdf::SPQRTree.

## ◆ skeleton()

 Skeleton& ogdf::StaticSPQRTree::skeleton ( node v ) const
inlineoverridevirtual

Returns the skeleton of node v.

Precondition
v is a node in T

Implements ogdf::SPQRTree.

Definition at line 141 of file StaticSPQRTree.h.

## ◆ skeletonEdgeSrc()

 edge ogdf::StaticSPQRTree::skeletonEdgeSrc ( edge e ) const
inline

Returns the edge in skeleton of source(e) that corresponds to tree edge e.

Precondition
e is an edge in T

Definition at line 147 of file StaticSPQRTree.h.

## ◆ skeletonEdgeTgt()

 edge ogdf::StaticSPQRTree::skeletonEdgeTgt ( edge e ) const
inline

Returns the edge in skeleton of target(e) that corresponds to tree edge e.

Precondition
e is an edge in T

Definition at line 153 of file StaticSPQRTree.h.

## ◆ skeletonOfReal()

 const Skeleton& ogdf::StaticSPQRTree::skeletonOfReal ( edge e ) const
inlineoverridevirtual

Returns the skeleton that contains the real edge e.

Precondition
e is an edge in G

Implements ogdf::SPQRTree.

Definition at line 159 of file StaticSPQRTree.h.

## ◆ tree()

 const Graph& ogdf::StaticSPQRTree::tree ( ) const
inlineoverridevirtual

Returns a reference to the tree T.

Implements ogdf::SPQRTree.

Definition at line 111 of file StaticSPQRTree.h.

## ◆ typeOf()

 NodeType ogdf::StaticSPQRTree::typeOf ( node v ) const
inlineoverridevirtual

Returns the type of node v.

Precondition
v is a node in T

Implements ogdf::SPQRTree.

Definition at line 132 of file StaticSPQRTree.h.

## ◆ StaticSkeleton

 friend class StaticSkeleton
friend

Definition at line 76 of file StaticSPQRTree.h.

## ◆ m_copyOf

 EdgeArray ogdf::StaticSPQRTree::m_copyOf
protected

skeleton edge corresponding to real edge e

Definition at line 233 of file StaticSPQRTree.h.

## ◆ m_numP

 int ogdf::StaticSPQRTree::m_numP
protected

number of P-nodes

Definition at line 223 of file StaticSPQRTree.h.

## ◆ m_numR

 int ogdf::StaticSPQRTree::m_numR
protected

number of R-nodes

Definition at line 224 of file StaticSPQRTree.h.

## ◆ m_numS

 int ogdf::StaticSPQRTree::m_numS
protected

number of S-nodes

Definition at line 222 of file StaticSPQRTree.h.

## ◆ m_pGraph

 const Graph* ogdf::StaticSPQRTree::m_pGraph
protected

pointer to original graph

Definition at line 216 of file StaticSPQRTree.h.

## ◆ m_rootEdge

 edge ogdf::StaticSPQRTree::m_rootEdge
protected

edge of G at which T is rooted

Definition at line 219 of file StaticSPQRTree.h.

## ◆ m_rootNode

 node ogdf::StaticSPQRTree::m_rootNode
protected

root node of T

Definition at line 220 of file StaticSPQRTree.h.

## ◆ m_sk

 NodeArray ogdf::StaticSPQRTree::m_sk
protected

pointer to skeleton of a node in T

Definition at line 228 of file StaticSPQRTree.h.

## ◆ m_skEdgeSrc

 EdgeArray ogdf::StaticSPQRTree::m_skEdgeSrc
protected

corresponding edge in skeleton(source(e))

Definition at line 229 of file StaticSPQRTree.h.

## ◆ m_skEdgeTgt

 EdgeArray ogdf::StaticSPQRTree::m_skEdgeTgt
protected

corresponding edge in skeleton(target(e))

Definition at line 230 of file StaticSPQRTree.h.

## ◆ m_skOf

 EdgeArray ogdf::StaticSPQRTree::m_skOf
protected

skeleton containing real edge e

Definition at line 232 of file StaticSPQRTree.h.

## ◆ m_tree

 Graph ogdf::StaticSPQRTree::m_tree
protected

underlying tree graph

Definition at line 217 of file StaticSPQRTree.h.

## ◆ m_type

 NodeArray ogdf::StaticSPQRTree::m_type
protected

type of nodes in T

Definition at line 226 of file StaticSPQRTree.h.

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