ogdf::Skeleton Class Reference

Skeleton graphs of nodes in an SPQR-tree. More...

#include <ogdf/decomposition/Skeleton.h>

Inheritance diagram for ogdf::Skeleton:

Public Member Functions
	Skeleton (node vT)
	Creates a skeleton S with owner tree T and corresponding node vT. More...
virtual	~Skeleton ()
Graph &	getGraph ()
	Returns a reference to the skeleton graph M. More...
const Graph &	getGraph () const
	Returns a reference to the skeleton graph M. More...
virtual bool	isVirtual (edge e) const =0
	Returns true iff e is a virtual edge. More...
virtual node	original (node v) const =0
	Returns the vertex in the original graph G that corresponds to v. More...
virtual const SPQRTree &	owner () const =0
	Returns the owner tree T. More...
virtual edge	realEdge (edge e) const =0
	Returns the real edge that corresponds to skeleton edge e. More...
edge	referenceEdge () const
	Returns the reference edge of S in M. More...
node	treeNode () const
	Returns the corresponding node in the owner tree T to which S belongs. More...
virtual edge	twinEdge (edge e) const =0
	Returns the twin edge of skeleton edge e. More...
virtual node	twinTreeNode (edge e) const =0
	Returns the tree node in T containing the twin edge of skeleton edge e. More...

Protected Attributes
Graph	m_M
	actual skeleton graph More...
edge	m_referenceEdge
	reference edge More...
node	m_treeNode
	corresp. More...

Detailed Description

Skeleton graphs of nodes in an SPQR-tree.

The class Skeleton maintains the skeleton S of a node vT in an SPQR-tree T. We call T the owner tree of S and vT the corresponding tree node. Let G be the original graph of T.

S consists of an undirected multi-graph M. If the owner tree of S is a PlanarSPQRTree, then M represents a combinatorial embedding. The vertices in M correspond to vertices in G. The edges in M are of two types: Real edges correspond to edges in G and virtual edges correspond to tree-edges in T having vT as an endpoint.

Let e in M be a virtual edge and eT be the corresponding tree-edge. Then there exists exactly one edge e' in another skeleton S' of T that corresponds to eT as well. We call e' the twin edge of e.

Definition at line 60 of file Skeleton.h.

Constructor & Destructor Documentation

Skeleton()

ogdf::Skeleton::Skeleton ( node  vT )

inlineexplicit

Creates a skeleton S with owner tree T and corresponding node vT.

Precondition

vT is a node in T

Remarks

Skeletons are created by the constructor of SPQRTree and can be accessed with the skeleton() function of SPQRTree.

Definition at line 71 of file Skeleton.h.

~Skeleton()

virtual ogdf::Skeleton::~Skeleton ( )

inlinevirtual

Definition at line 74 of file Skeleton.h.

Member Function Documentation

getGraph() [1/2]

Graph& ogdf::Skeleton::getGraph ( )

inline

Returns a reference to the skeleton graph M.

Definition at line 93 of file Skeleton.h.

getGraph() [2/2]

const Graph& ogdf::Skeleton::getGraph ( ) const

inline

Returns a reference to the skeleton graph M.

Definition at line 90 of file Skeleton.h.

isVirtual()

virtual bool ogdf::Skeleton::isVirtual ( edge  e ) const

pure virtual

Returns true iff e is a virtual edge.

Precondition

e is an edge in M

Implemented in ogdf::DynamicSkeleton, and ogdf::StaticSkeleton.

original()

virtual node ogdf::Skeleton::original ( node  v ) const

pure virtual

Returns the vertex in the original graph G that corresponds to v.

Precondition

v is a node in M.

Implemented in ogdf::DynamicSkeleton, and ogdf::StaticSkeleton.

owner()

virtual const SPQRTree& ogdf::Skeleton::owner ( ) const

pure virtual

Returns the owner tree T.

Implemented in ogdf::DynamicSkeleton, and ogdf::StaticSkeleton.

realEdge()

virtual edge ogdf::Skeleton::realEdge ( edge  e ) const

pure virtual

Returns the real edge that corresponds to skeleton edge e.

If e is virtual edge, then 0 is returned.

Precondition

e is an edge in M

Implemented in ogdf::StaticSkeleton, and ogdf::DynamicSkeleton.

referenceEdge()

edge ogdf::Skeleton::referenceEdge ( ) const

inline

Returns the reference edge of S in M.

The reference edge is a real edge if S is the skeleton of the root node of T, and a virtual edge otherwise.

Definition at line 87 of file Skeleton.h.

treeNode()

node ogdf::Skeleton::treeNode ( ) const

inline

Returns the corresponding node in the owner tree T to which S belongs.

Definition at line 80 of file Skeleton.h.

twinEdge()

virtual edge ogdf::Skeleton::twinEdge ( edge  e ) const

pure virtual

Returns the twin edge of skeleton edge e.

If e is not a virtual edge, then 0 is returned.

Precondition

e is an edge in M

Implemented in ogdf::DynamicSkeleton, and ogdf::StaticSkeleton.

twinTreeNode()

virtual node ogdf::Skeleton::twinTreeNode ( edge  e ) const

pure virtual

Returns the tree node in T containing the twin edge of skeleton edge e.

If e is not a virtual edge, then 0 is returned.

Precondition

e is an edge in M

Implemented in ogdf::DynamicSkeleton, and ogdf::StaticSkeleton.

Member Data Documentation

m_M

Graph ogdf::Skeleton::m_M

protected

actual skeleton graph

Definition at line 133 of file Skeleton.h.

m_referenceEdge

edge ogdf::Skeleton::m_referenceEdge

protected

reference edge

Definition at line 132 of file Skeleton.h.

m_treeNode

node ogdf::Skeleton::m_treeNode

protected

corresp.

tree node in owner tree

Definition at line 131 of file Skeleton.h.

---

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

• include/ogdf/decomposition/Skeleton.h