# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::PlanarSPQRTree Class Reference

SPQR-trees of planar graphs. More...

#include <ogdf/decomposition/PlanarSPQRTree.h>

Inheritance diagram for ogdf::PlanarSPQRTree:

## Public Member Functions

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 Member Functions inherited from ogdf::SPQRTree
virtual ~SPQRTree ()

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

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)

## Protected Member Functions

void createInnerVerticesEmbed (Graph &G, node vT)

void firstEmbedding (node &vT)

void init (bool isEmbedded)

bool nextEmbedding (ListIterator< node > it)

bool nextEmbedding (node &vT)

Protected Member Functions inherited from ogdf::SPQRTree
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...

## Protected Attributes

bool m_finished

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

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

SPQR-trees of planar graphs.

The class PlanarSPQRTree 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 52 of file PlanarSPQRTree.h.

protected

## ◆ createInnerVerticesEmbed()

 void ogdf::PlanarSPQRTree::createInnerVerticesEmbed ( Graph & G, node vT )
protected

## ◆ embed() [1/2]

 void ogdf::PlanarSPQRTree::embed ( Graph & G )

Embeds G according to the current embeddings of the skeletons of T.

Precondition
G is the graph passed to the constructor of T

## ◆ embed() [2/2]

 void ogdf::PlanarSPQRTree::embed ( node & vT, long long x )

Embeds the skeleton of the node vT with the specific embedding numbered by x.

Precondition
To work correctly vT has to be a node of the SPQR-tree and 0 ≤ x ≤ number of embeddings of vT's skeleton
It does not work at the same time with firstEmbedding and nextEmbedding

protected

## ◆ firstEmbedding() [1/2]

 void ogdf::PlanarSPQRTree::firstEmbedding ( Graph & G )

Embeds the original graph G canonically by the indices of their adjEntries.

Precondition
G is the graph passed to the constructor of T

## ◆ firstEmbedding() [2/2]

 void ogdf::PlanarSPQRTree::firstEmbedding ( node & vT )
protected

## ◆ init()

 void ogdf::PlanarSPQRTree::init ( bool isEmbedded )
protected

## ◆ nextEmbedding() [1/3]

 bool ogdf::PlanarSPQRTree::nextEmbedding ( Graph & G )

Embeds the original graph G with the next embedding.

It returns false iff there is no feasible (planar) embedding left

Precondition
G is the graph passed to the constructor of T

## ◆ nextEmbedding() [2/3]

 bool ogdf::PlanarSPQRTree::nextEmbedding ( ListIterator< node > it )
protected

## ◆ nextEmbedding() [3/3]

 bool ogdf::PlanarSPQRTree::nextEmbedding ( node & vT )
protected

## ◆ numberOfEmbeddings() [1/2]

 double ogdf::PlanarSPQRTree::numberOfEmbeddings ( ) const
inline

Returns the number of possible embeddings of G.

Definition at line 60 of file PlanarSPQRTree.h.

## ◆ numberOfEmbeddings() [2/2]

 double ogdf::PlanarSPQRTree::numberOfEmbeddings ( node v ) const

Returns the number of possible embeddings of the pertinent graph of node v.

Precondition
v is a node in T

## ◆ numberOfNodeEmbeddings()

 long long ogdf::PlanarSPQRTree::numberOfNodeEmbeddings ( node vT ) const

Returns the number of possible embeddings of the skeleton of node vT.

Precondition
vT is a node in T Returns 1 if vT is a S-node, 2 if vT is a R-node, and (number of edges in the sekeleton - 1)! if vT is a P-node.

## ◆ randomEmbed() [1/2]

 void ogdf::PlanarSPQRTree::randomEmbed ( )

Embeds all skeleton graphs randomly.

## ◆ randomEmbed() [2/2]

 void ogdf::PlanarSPQRTree::randomEmbed ( Graph & G )
inline

Embeds all skeleton graphs randomly and embeds G according to the embeddings of the skeletons.

Precondition
G is the graph passed to the constructor of T

Definition at line 115 of file PlanarSPQRTree.h.

## ◆ reverse() [1/2]

 void ogdf::PlanarSPQRTree::reverse ( node & nP, adjEntry & first, adjEntry & last )
protected

## ◆ reverse() [2/2]

 void ogdf::PlanarSPQRTree::reverse ( node vT )

Flips the skeleton S of vT around its poles.

Reverses the order of adjacency entries of each vertex in S.

Precondition
vT is an R- or P-node in T

protected

## ◆ swap() [1/2]

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

Precondition
vT is a P-node in T and adj1 and adj2 are in adjacency entries in skeleton(vT) at the same owner node.

## ◆ swap() [2/2]

 void ogdf::PlanarSPQRTree::swap ( node vT, edge e1, edge e2 )

Exchanges the positions of edges e1 and e2 in skeleton of vT.

Precondition
vT is a P-node in T and e1 and e2 are in edges in skeleton(vT)

## ◆ m_finished

 bool ogdf::PlanarSPQRTree::m_finished
protected

Definition at line 168 of file PlanarSPQRTree.h.

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