# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::StaticPlanarSPQRTree Class Reference

SPQR-trees of planar graphs. More...

#include <ogdf/decomposition/StaticPlanarSPQRTree.h>

Inheritance diagram for ogdf::StaticPlanarSPQRTree:

## Public Member Functions

StaticPlanarSPQRTree (const Graph &G, bool isEmbedded=false)
Creates an SPQR tree T for planar graph G rooted at the first edge of G. More...

StaticPlanarSPQRTree (const Graph &G, edge e, bool isEmbedded=false)
Creates an SPQR tree T for planar graph G rooted at edge e. More...

Public Member Functions inherited from ogdf::StaticSPQRTree
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...

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

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)

Public Member Functions inherited from ogdf::PlanarSPQRTree
void embed (Graph &G)
Embeds G according to the current embeddings of the skeletons of T. More...

void embed (node &vT, long long x)
Embeds the skeleton of the node vT with the specific embedding numbered by x. More...

void firstEmbedding (Graph &G)
Embeds the original graph G canonically by the indices of their adjEntries. More...

bool nextEmbedding (Graph &G)
Embeds the original graph G with the next embedding. More...

double numberOfEmbeddings () const
Returns the number of possible embeddings of G. More...

double numberOfEmbeddings (node v) const
Returns the number of possible embeddings of the pertinent graph of node v. More...

long long numberOfNodeEmbeddings (node vT) const
Returns the number of possible embeddings of the skeleton of node vT. More...

void randomEmbed ()
Embeds all skeleton graphs randomly. More...

void randomEmbed (Graph &G)
Embeds all skeleton graphs randomly and embeds G according to the embeddings of the skeletons. More...

void reverse (node vT)
Flips the skeleton S of vT around its poles. More...

Exchanges the positions of the two edges corresponding to adj1 and adj2 in skeleton of vT. More...

void swap (node vT, edge e1, edge e2)
Exchanges the positions of edges e1 and e2 in skeleton of vT. More...

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

Protected Member Functions inherited from ogdf::StaticSPQRTree
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 Member Functions inherited from ogdf::PlanarSPQRTree

void createInnerVerticesEmbed (Graph &G, node vT)

void firstEmbedding (node &vT)

void init (bool isEmbedded)

bool nextEmbedding (ListIterator< node > it)

bool nextEmbedding (node &vT)

Protected Attributes inherited from ogdf::StaticSPQRTree
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...

Protected Attributes inherited from ogdf::PlanarSPQRTree
bool m_finished

## Detailed Description

SPQR-trees of planar graphs.

The class StaticPlanarSPQRTree maintains the triconnected components of a planar biconnected graph G and represents all possible embeddings of G. Each skeleton graph is embedded.

The current embeddings of the skeletons define an embedding of G. There are two basic operations for obtaining another embedding of G: reverse(v), which flips the skeleton of an R-node v around its poles, and swap(v,e_1,e_2), which exchanges the positions of the edges e_1 and e_2 in the skeleton of a P-node v.

Definition at line 55 of file StaticPlanarSPQRTree.h.

## ◆ StaticPlanarSPQRTree() [1/2]

 ogdf::StaticPlanarSPQRTree::StaticPlanarSPQRTree ( const Graph & G, bool isEmbedded = false )
inlineexplicit

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

If isEmbedded is set to true, G must represent a combinatorial embedding, i.e., the counter-clockwise order of the adjacency entries around each vertex defines an embedding.

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

Definition at line 68 of file StaticPlanarSPQRTree.h.

## ◆ StaticPlanarSPQRTree() [2/2]

 ogdf::StaticPlanarSPQRTree::StaticPlanarSPQRTree ( const Graph & G, edge e, bool isEmbedded = false )
inline

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

If isEmbedded is set to true, G must represent a combinatorial embedding, i.e., the counter-clockwise order of the adjacency entries around each vertex defines an embedding.

Precondition
e is an edge in G, and G is planar and biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 edges.

Definition at line 83 of file StaticPlanarSPQRTree.h.

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