# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::DynamicSPQRTree Class Reference

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

#include <ogdf/decomposition/DynamicSPQRTree.h>

Inheritance diagram for ogdf::DynamicSPQRTree:

## Public Member Functions

DynamicSPQRTree (Graph &G)
Creates an SPQR tree T for graph G rooted at the first edge of G. More...

DynamicSPQRTree (Graph &G, edge e)
Creates an SPQR tree T for graph G rooted at the edge e. More...

~DynamicSPQRTree ()

edge copyOfReal (edge e) const override
Returns the skeleton edge that corresponds to the real edge e. More...

SList< node > & findPath (node s, node t)
Finds the shortest path between the two sets of vertices of T which s and t of G belong to. More...

List< nodenodesOfType (NodeType t) const override
Returns the list of all nodes with type 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...

int numberOfSNodes () const override
Returns the number of S-nodes in T. More...

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

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...

Skeletonskeleton (node v) const override
Returns the skeleton of node v. More...

edge skeletonEdge (node v, node w) const
Returns the virtual edge in the skeleton of w that corresponds to the tree edge between v and w. More...

const SkeletonskeletonOfReal (edge e) const override
Returns the skeleton that contains the real edge e. More...

const Graphtree () const override
Returns a reference to the tree T. More...

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

edge updateInsertedEdge (edge e) override
Updates the whole data structure after a new edge e has been inserted into G. More...

node updateInsertedNode (edge e, edge f) override
Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into e and f. More...

Public Member Functions inherited from ogdf::SPQRTree
virtual ~SPQRTree ()

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)

Public Member Functions inherited from ogdf::DynamicSPQRForest
DynamicSPQRForest (Graph &G)
A constructor. More...

~DynamicSPQRForest ()

node spqrproper (edge eH) const

edge twinEdge (edge eH) const
Returns the twin edge of a given edge of m_H, if it is virtual, or nullptr, if it is real. More...

TNodeType typeOfTNode (node vT) const

const List< edge > & hEdgesSPQR (node vT) const
Returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQR-tree-vertex. More...

SList< node > & findPathSPQR (node sH, node tH) const
Finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to. More...

edge virtualEdge (node vT, node wT) const
Returns the virtual edge which leads from one vertex of an SPQR-tree to another one. More...

Public Member Functions inherited from ogdf::DynamicBCTree
DynamicBCTree (Graph &G, bool callInitConnected=false)

DynamicBCTree (Graph &G, node vG, bool callInitConnected=false)
A constructor. More...

node bcproper (node vG) const override

node bcproper (edge eG) const override
Returns the BC-tree-vertex representing the biconnected component which a given edge of the original graph is belonging to. More...

node repVertex (node uG, node vB) const override

node cutVertex (node uB, node vB) const override
Returns the copy of a cut-vertex in the biconnected components graph which belongs to a certain B-component and leads to another B-component. More...

edge insertEdge (node sG, node tG)
Inserts a new edge into the original graph and updates the BC-tree. More...

node insertNode (edge eG)
Inserts a new vertex into the original graph and updates the BC-tree. More...

node bComponent (node uG, node vG) const

Public Member Functions inherited from ogdf::BCTree
BCTree (Graph &G, bool callInitConnected=false)
A constructor. More...

BCTree (Graph &G, List< node > &vG)
Constructor for not connected graphs. More...

BCTree (Graph &G, node vG, bool callInitConnected=false)
A constructor. More...

virtual ~BCTree ()
Virtual destructor. More...

const GraphauxiliaryGraph () const
Returns the biconnected components graph. More...

const GraphbcTree () const
Returns the BC-tree graph. More...

int numberOfBComps () const
Returns the number of B-components. More...

int numberOfCComps () const
Returns the number of C-components. More...

const GraphoriginalGraph () const
Returns the original graph. More...

GNodeType typeOfGNode (node vG) const

node rep (node vG) const
Returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph. More...

edge rep (edge eG) const
Returns the edge of the biconnected components graph corresponding to a given edge of the original graph. More...

node original (node vH)

edge original (edge eH) const
Returns the edge of the original graph which a given edge of the biconnected components graph is corresponding to. More...

BNodeType typeOfBNode (node vB) const

const SList< edge > & hEdges (node vB) const
Returns a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by a given BC-tree-vertex. More...

int numberOfEdges (node vB) const
Returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex. More...

int numberOfNodes (node vB) const
Returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex. More...

node bComponent (node uG, node vG) const

SList< node > & findPath (node sG, node tG) const
Calculates a path in the BC-tree. More...

SList< node > * findPathBCTree (node sB, node tB) const
Calculates a path in the BC-tree. More...

## 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...

DynamicSkeletoncreateSkeleton (node vT) const
Creates the skeleton graph belonging to a given vertex vT of T. More...

void init (edge e)
Initialization (called by constructors). 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 Member Functions inherited from ogdf::DynamicSPQRForest
void addHEdge (edge eH, node vT) const
Adds edge eH to a vertex vT of the SPQRForest. More...

void createSPQR (node vB) const
Creates the SPQR-tree for a given B-component of the BC-tree. More...

void delHEdge (edge eH, node vT) const
Deletes edge eH from m_H and removes its connection to a vertex vT of the SPQRForest. More...

void init ()
Initialization. More...

node newSPQRNode (node vB, const TNodeType spqrNodeType) const
Creates a new node in the SPQR-tree for a given B-component of the BC-tree. More...

edge newTwinEdge (edge eH, node vT) const
Creates a twin edge for eH, adds it to vT and returns it. More...

node uniteSPQR (node vB, node sT, node tT)

node findSPQR (node vT) const
Finds the proper representative of an SPQR-tree-vertex (FIND part of UNION/FIND). More...

node findNCASPQR (node sT, node tT) const

SList< node > & findPathSPQR (node sH, node tH, node &rT) const
Finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to. More...

edge updateInsertedEdgeSPQR (node vB, edge eG)

node updateInsertedNodeSPQR (node vB, edge eG, edge fG)
Updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG. More...

Protected Member Functions inherited from ogdf::DynamicBCTree
void init ()

node unite (node uB, node vB, node wB)

node find (node vB) const
The FIND function of the UNION/FIND structure. More...

node parent (node vB) const override

node condensePath (node sG, node tG)
Performs path condensation. More...

Protected Member Functions inherited from ogdf::BCTree
Generates the BC-tree and the biconnected components graph recursively. More...

void init (node vG)
Initialization. More...

void initNotConnected (List< node > &vG)
Initialization for not connected graphs. More...

void initNotConnected (node vG)
Initialization for not connected graphs. More...

node findNCA (node uB, node vB) const
Calculates the nearest common ancestor of two vertices of the BC-tree. More...

## Protected Attributes

NodeArray< nodem_mapV
temporary array used by createSkeleton() More...

edge m_rootEdge
edge of G at which T is rooted More...

NodeArray< DynamicSkeleton * > m_sk
pointer to skeleton of a node in T More...

EdgeArray< edgem_skelEdge
copies of real and virtual edges in their skeleton graphs (invalid, if the skeleton does not actually exist) 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...

Protected Attributes inherited from ogdf::DynamicSPQRForest
Graph m_T
A Graph structure containing all SPQR-trees. More...

NodeArray< nodem_bNode_SPQR

NodeArray< int > m_bNode_numS
The numbers of S-components. More...

NodeArray< int > m_bNode_numP
The numbers of P-components. More...

NodeArray< int > m_bNode_numR
The numbers of R-components. More...

NodeArray< TNodeTypem_tNode_type
The types of the SPQR-tree-vertices. More...

NodeArray< nodem_tNode_owner
The owners of the SPQR-tree-vertices in the UNION/FIND structure. More...

NodeArray< edgem_tNode_hRefEdge
The virtual edges leading to the parents of the SPQR-tree vertices. More...

NodeArray< List< edge > * > m_tNode_hEdges
Lists of real and virtual edges belonging to SPQR-tree vertices. More...

EdgeArray< ListIterator< edge > > m_hEdge_position
The positions of real and virtual edges in their m_tNode_hEdges lists. More...

EdgeArray< nodem_hEdge_tNode
The SPQR-tree-vertices which the real and virtual edges are belonging to. More...

EdgeArray< edgem_hEdge_twinEdge
The partners of virtual edges (nullptr if real). More...

NodeArray< nodem_htogc
Auxiliary array used by createSPQR(). More...

NodeArray< bool > m_tNode_isMarked
Auxiliary array used by findNCASPQR() More...

Protected Attributes inherited from ogdf::DynamicBCTree
NodeArray< int > m_bNode_degree
Array that contains for each proper BC-tree-vertex its degree. More...

NodeArray< nodem_bNode_owner
Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure. More...

Protected Attributes inherited from ogdf::BCTree
Graph m_B
The BC-tree. More...

Graphm_G
The original graph. More...

Graph m_H
The biconnected components graph. More...

int m_numB
The number of B-components. More...

int m_numC
The number of C-components. More...

NodeArray< bool > m_gNode_isMarked

NodeArray< nodem_gNode_hNode
An injective mapping vertices(G) -> vertices(H). More...

EdgeArray< edgem_gEdge_hEdge
A bijective mapping edges(G) -> edges(H). More...

NodeArray< BNodeTypem_bNode_type
Array that contains the type of each BC-tree-vertex. More...

NodeArray< bool > m_bNode_isMarked
Array of marks for the BC-tree-vertices. More...

NodeArray< nodem_bNode_hRefNode
Array that contains for each BC-tree-vertex the representantive of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex. More...

NodeArray< nodem_bNode_hParNode
Array that contains for each BC-tree-vertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BC-tree-vertex. More...

NodeArray< SList< edge > > m_bNode_hEdges
Array that contains for each BC-tree-vertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex. More...

NodeArray< int > m_bNode_numNodes
Array that contains for each BC-tree-vertex the number of vertices belonging to the biconnected component represented by the respective BC-tree-vertex. More...

NodeArray< nodem_hNode_bNode

EdgeArray< nodem_hEdge_bNode
A surjective mapping edges(H) -> vertices(B). More...

NodeArray< nodem_hNode_gNode
A surjective mapping vertices(H) -> vertices(G). More...

EdgeArray< edgem_hEdge_gEdge
A bijective mapping edges(H) -> edges(G). More...

int m_count

NodeArray< int > m_number
Temporary array. More...

NodeArray< int > m_lowpt
Temporary array. More...

Temporary stack. More...

NodeArray< nodem_gtoh
Temporary array. More...

SList< nodem_nodes
Temporary list. More...

## Friends

class DynamicSkeleton

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

Public Types inherited from ogdf::DynamicSPQRForest
enum  TNodeType { TNodeType::SComp = static_cast<int>(SPQRTree::NodeType::SNode), TNodeType::PComp = static_cast<int>(SPQRTree::NodeType::PNode), TNodeType::RComp = static_cast<int>(SPQRTree::NodeType::RNode) }
Enumeration type for characterizing the SPQR-tree-vertices. More...

Public Types inherited from ogdf::BCTree
enum  BNodeType { BNodeType::BComp, BNodeType::CComp }
Enumeration type for characterizing the BC-tree-vertices. More...

enum  GNodeType { GNodeType::Normal, GNodeType::CutVertex }
Enumeration type for characterizing the vertices of the original graph. More...

## Detailed Description

Linear-time implementation of dynamic SPQR-trees.

The class DynamicSPQRTree 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 DynamicSPQRTree supports the statical construction of an SPQR-tree for a given graph G, and supports dynamic updates, too.

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 DynamicSkeleton). 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 DynamicSPQRTree.h.

## ◆ DynamicSPQRTree() [1/2]

 ogdf::DynamicSPQRTree::DynamicSPQRTree ( 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 DynamicSPQRTree.h.

## ◆ DynamicSPQRTree() [2/2]

 ogdf::DynamicSPQRTree::DynamicSPQRTree ( 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 DynamicSPQRTree.h.

## ◆ ~DynamicSPQRTree()

 ogdf::DynamicSPQRTree::~DynamicSPQRTree ( )

## ◆ copyOfReal()

 edge ogdf::DynamicSPQRTree::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 161 of file DynamicSPQRTree.h.

## ◆ cpRec()

 void ogdf::DynamicSPQRTree::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 223 of file DynamicSPQRTree.h.

## ◆ createSkeleton()

 DynamicSkeleton& ogdf::DynamicSPQRTree::createSkeleton ( node vT ) const
protected

Creates the skeleton graph belonging to a given vertex vT of T.

## ◆ findPath()

 SList& ogdf::DynamicSPQRTree::findPath ( node s, node t )
inline

Finds the shortest path between the two sets of vertices of T which s and t of G belong to.

Definition at line 138 of file DynamicSPQRTree.h.

## ◆ init()

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

Initialization (called by constructors).

## ◆ nodesOfType()

 List ogdf::DynamicSPQRTree::nodesOfType ( NodeType t ) const
overridevirtual

Returns the list of all nodes with type t.

Implements ogdf::SPQRTree.

## ◆ numberOfPNodes()

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

Returns the number of P-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 120 of file DynamicSPQRTree.h.

## ◆ numberOfRNodes()

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

Returns the number of R-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 123 of file DynamicSPQRTree.h.

## ◆ numberOfSNodes()

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

Returns the number of S-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 117 of file DynamicSPQRTree.h.

## ◆ originalGraph()

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

Returns a reference to the original graph G.

Implements ogdf::SPQRTree.

Definition at line 105 of file DynamicSPQRTree.h.

## ◆ rootEdge()

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

Returns the edge of G at which T is rooted.

Implements ogdf::SPQRTree.

Definition at line 111 of file DynamicSPQRTree.h.

## ◆ rootNode()

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

Returns the root node of T.

Implements ogdf::SPQRTree.

Definition at line 114 of file DynamicSPQRTree.h.

## ◆ rootTreeAt() [1/2]

 node ogdf::DynamicSPQRTree::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::DynamicSPQRTree::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::DynamicSPQRTree::skeleton ( node v ) const
inlineoverridevirtual

Returns the skeleton of node v.

Precondition
v is a node in T

Implements ogdf::SPQRTree.

Definition at line 144 of file DynamicSPQRTree.h.

## ◆ skeletonEdge()

 edge ogdf::DynamicSPQRTree::skeletonEdge ( node v, node w ) const
inline

Returns the virtual edge in the skeleton of w that corresponds to the tree edge between v and w.

Precondition
v and w are adjacent nodes in T

Definition at line 173 of file DynamicSPQRTree.h.

## ◆ skeletonOfReal()

 const Skeleton& ogdf::DynamicSPQRTree::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 155 of file DynamicSPQRTree.h.

## ◆ tree()

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

Returns a reference to the tree T.

Implements ogdf::SPQRTree.

Definition at line 108 of file DynamicSPQRTree.h.

## ◆ typeOf()

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

Returns the type of node v.

Precondition
v is a node in T

Implements ogdf::SPQRTree.

Definition at line 129 of file DynamicSPQRTree.h.

## ◆ updateInsertedEdge()

 edge ogdf::DynamicSPQRTree::updateInsertedEdge ( edge e )
overridevirtual

Updates the whole data structure after a new edge e has been inserted into G.

Reimplemented from ogdf::DynamicSPQRForest.

## ◆ updateInsertedNode()

 node ogdf::DynamicSPQRTree::updateInsertedNode ( edge e, edge f )
overridevirtual

Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into e and f.

Reimplemented from ogdf::DynamicSPQRForest.

## ◆ DynamicSkeleton

 friend class DynamicSkeleton
friend

Definition at line 76 of file DynamicSPQRTree.h.

## ◆ m_mapV

 NodeArray ogdf::DynamicSPQRTree::m_mapV
mutableprotected

temporary array used by createSkeleton()

Definition at line 238 of file DynamicSPQRTree.h.

## ◆ m_rootEdge

 edge ogdf::DynamicSPQRTree::m_rootEdge
protected

edge of G at which T is rooted

Definition at line 234 of file DynamicSPQRTree.h.

## ◆ m_sk

 NodeArray ogdf::DynamicSPQRTree::m_sk
mutableprotected

pointer to skeleton of a node in T

Definition at line 236 of file DynamicSPQRTree.h.

## ◆ m_skelEdge

 EdgeArray ogdf::DynamicSPQRTree::m_skelEdge
mutableprotected

copies of real and virtual edges in their skeleton graphs (invalid, if the skeleton does not actually exist)

Definition at line 237 of file DynamicSPQRTree.h.

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