Open
Graph Drawing
Framework

 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...
 
void swap (node vT, adjEntry adj1, adjEntry adj2)
 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 adoptEmbedding ()
 
void createInnerVerticesEmbed (Graph &G, node vT)
 
void expandVirtualEmbed (node vT, adjEntry adjVirt, SListPure< adjEntry > &adjEdges)
 
void firstEmbedding (node &vT)
 
void init (bool isEmbedded)
 Initialization (adaption of embeding). More...
 
bool nextEmbedding (ListIterator< node > it)
 
bool nextEmbedding (node &vT)
 
void reverse (node &nP, adjEntry &first, adjEntry &last)
 
void setPosInEmbedding (NodeArray< SListPure< adjEntry > > &adjEdges, NodeArray< node > &currentCopy, NodeArray< adjEntry > &lastAdj, SListPure< node > &current, const Skeleton &S, adjEntry adj)
 
- 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...
 
SList< nodem_cpVAdded
 list of added nodes (auxiliary member) More...
 

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

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.

Member Function Documentation

◆ adoptEmbedding()

void ogdf::PlanarSPQRTree::adoptEmbedding ( )
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

◆ expandVirtualEmbed()

void ogdf::PlanarSPQRTree::expandVirtualEmbed ( node  vT,
adjEntry  adjVirt,
SListPure< adjEntry > &  adjEdges 
)
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

Initialization (adaption of embeding).

◆ 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
To work correctly it has to start with firstEmbedding(G)
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

◆ setPosInEmbedding()

void ogdf::PlanarSPQRTree::setPosInEmbedding ( NodeArray< SListPure< adjEntry > > &  adjEdges,
NodeArray< node > &  currentCopy,
NodeArray< adjEntry > &  lastAdj,
SListPure< node > &  current,
const Skeleton S,
adjEntry  adj 
)
protected

◆ swap() [1/2]

void ogdf::PlanarSPQRTree::swap ( node  vT,
adjEntry  adj1,
adjEntry  adj2 
)

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)

Member Data Documentation

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