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.

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

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

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

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

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

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

void	randomEmbed ()
	Embeds all skeleton graphs randomly.

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

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

void	swap (node vT, adjEntry adj1, adjEntry adj2)
	Exchanges the positions of the two edges corresponding to `adj1` and `adj2` in skeleton of `vT`.

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

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

virtual const Graph &	originalGraph () const =0
	Returns a reference to the original graph G.

virtual const Graph &	tree () const =0
	Returns a reference to the tree T.

virtual edge	rootEdge () const =0
	Returns the edge of G at which T is rooted.

virtual node	rootNode () const =0
	Returns the root node of T.

virtual int	numberOfSNodes () const =0
	Returns the number of S-nodes in T.

virtual int	numberOfPNodes () const =0
	Returns the number of P-nodes in T.

virtual int	numberOfRNodes () const =0
	Returns the number of R-nodes in T.

virtual NodeType	typeOf (node v) const =0
	Returns the type of node `v`.

virtual List< node >	nodesOfType (NodeType t) const =0
	Returns the list of all nodes with type `t`.

virtual Skeleton &	skeleton (node v) const =0
	Returns the skeleton of node `v`.

virtual const Skeleton &	skeletonOfReal (edge e) const =0
	Returns the skeleton that contains the real edge `e`.

virtual edge	copyOfReal (edge e) const =0
	Returns the skeleton edge that corresponds to the real edge `e`.

void	pertinentGraph (node v, PertinentGraph &Gp) const
	Returns the pertinent graph of tree node `v` in `Gp`.

virtual node	rootTreeAt (edge e)=0
	Roots T at edge `e` and returns the new root node of T.

virtual node	rootTreeAt (node v)=0
	Roots T at node `v` and returns `v`.

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

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.

edge	cpAddEdge (edge eOrig, PertinentGraph &Gp) const
	Add an edge to `Gp` corresponding to `eOrig`.

node	cpAddNode (node vOrig, PertinentGraph &Gp) const
	Add a node to `Gp` corresponding to `vOrig` if required.

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)

SList< node >	m_cpVAdded
	list of added nodes (auxiliary member)

Additional Inherited Members
Public Types inherited from ogdf::SPQRTree
enum class	NodeType { SNode , PNode , 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 59 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 112 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 156 of file PlanarSPQRTree.h.

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

include/ogdf/decomposition/PlanarSPQRTree.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ adoptEmbedding()

◆ createInnerVerticesEmbed()

◆ embed() [1/2]

◆ embed() [2/2]

◆ expandVirtualEmbed()

◆ firstEmbedding() [1/2]

◆ firstEmbedding() [2/2]

◆ init()

◆ nextEmbedding() [1/3]

◆ nextEmbedding() [2/3]

◆ nextEmbedding() [3/3]

◆ numberOfEmbeddings() [1/2]

◆ numberOfEmbeddings() [2/2]

◆ numberOfNodeEmbeddings()

◆ randomEmbed() [1/2]

◆ randomEmbed() [2/2]

◆ reverse() [1/2]

◆ reverse() [2/2]

◆ setPosInEmbedding()

◆ swap() [1/2]

◆ swap() [2/2]

Member Data Documentation

◆ m_finished

Open
Graph Drawing
Framework