Open
Graph Drawing
Framework

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

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.

Constructor & Destructor Documentation

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

Member Function Documentation

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

Friends And Related Function Documentation

◆ StaticSkeleton

friend class StaticSkeleton
friend

Definition at line 76 of file StaticSPQRTree.h.

Member Data Documentation

◆ m_copyOf

EdgeArray<edge> 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<StaticSkeleton *> ogdf::StaticSPQRTree::m_sk
protected

pointer to skeleton of a node in T

Definition at line 228 of file StaticSPQRTree.h.

◆ m_skEdgeSrc

EdgeArray<edge> ogdf::StaticSPQRTree::m_skEdgeSrc
protected

corresponding edge in skeleton(source(e))

Definition at line 229 of file StaticSPQRTree.h.

◆ m_skEdgeTgt

EdgeArray<edge> ogdf::StaticSPQRTree::m_skEdgeTgt
protected

corresponding edge in skeleton(target(e))

Definition at line 230 of file StaticSPQRTree.h.

◆ m_skOf

EdgeArray<StaticSkeleton *> 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<NodeType> 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: