Linear-time implementation of static SPQR-trees. More...

#include <ogdf/decomposition/StaticSPQRTree.h>

Inheritance diagram for ogdf::StaticSPQRTree:

Public Member Functions
	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...

Access operations
const Graph &	originalGraph () const override
	Returns a reference to the original graph G. More...

const Graph &	tree () 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< node >	nodesOfType (NodeType t) const override
	Returns the list of all nodes with type `t`. More...

Skeleton &	skeleton (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 Skeleton &	skeletonOfReal (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...

Update operations
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
	SPQRTree ()

	SPQRTree (const SPQRTree &copy)=delete

	SPQRTree (SPQRTree &&move)=delete

virtual	~SPQRTree ()

SPQRTree &	operator= (const SPQRTree &copy)=delete

SPQRTree &	operator= (SPQRTree &&move)=delete

virtual List< node >	nodesOfType (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)

Protected Member Functions
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 Attributes
EdgeArray< edge >	m_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 Graph *	m_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< edge >	m_skEdgeSrc
	corresponding edge in skeleton(source(e)) More...

EdgeArray< edge >	m_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< NodeType >	m_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...

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

Friends
class	StaticSkeleton

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

Linear-time implementation of static SPQR-trees.

The class StaticSPQRTree maintains the arrangement of the triconnected components of a biconnected multi-graph G [Hopcroft, Tarjan 1973] as a so-called SPQR tree T [Fi Battista, Tamassia, 1996]. We call G the original graph of T. The class StaticSPQRTree supports only the statical construction of an SPQR-tree for a given graph G, dynamic updates are not supported.

Each node of the tree has an associated type (represented by SPQRTree::NodeType), which is either SNode, PNode, or RNode, and a skeleton (represented by the class StaticSkeleton). The skeletons of the nodes of T are in one-to-one correspondence to the triconnected components of G, i.e., S-nodes correspond to polygons, P-nodes to bonds, and R-nodes to triconnected graphs.

In our representation of SPQR-trees, Q-nodes are omitted. Instead, the skeleton S of a node v in T contains two types of edges: real edges, which correspond to edges in G, and virtual edges, which correspond to edges in T having v as an endpoint. There is a special edge er in G at which T is rooted, i.e., the root node of T is the node whose skeleton contains the real edge corresponding to er.

The reference edge of the skeleton of the root node is er, the reference edge of the skeleton S of a non-root node v is the virtual edge in S that corresponds to the tree edge (parent(v),v).

Definition at line 79 of file StaticSPQRTree.h.

Constructor & Destructor Documentation

◆ StaticSPQRTree() [1/3]

ogdf::StaticSPQRTree::StaticSPQRTree ( const Graph & G )

inlineexplicit

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

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

Definition at line 90 of file StaticSPQRTree.h.

◆ StaticSPQRTree() [2/3]

ogdf::StaticSPQRTree::StaticSPQRTree	(	const Graph &	G,
		edge	e
	)

inline

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

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

Definition at line 101 of file StaticSPQRTree.h.

◆ StaticSPQRTree() [3/3]

ogdf::StaticSPQRTree::StaticSPQRTree	(	const Graph &	G,
		Triconnectivity &	tricComp
	)

inline

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

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

Definition at line 111 of file StaticSPQRTree.h.

◆ ~StaticSPQRTree()

ogdf::StaticSPQRTree::~StaticSPQRTree ( )

Destructor.

Member Function Documentation

◆ copyOfReal()

edge ogdf::StaticSPQRTree::copyOfReal ( edge e ) const

inlineoverridevirtual

Returns the skeleton edge that corresponds to the real edge e.

Precondition: e is an edge in G

Implements ogdf::SPQRTree.

Definition at line 180 of file StaticSPQRTree.h.

◆ cpRec()

void ogdf::StaticSPQRTree::cpRec	(	node	v,
		PertinentGraph &	Gp
	)		const

inlineoverrideprotectedvirtual

Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph.

Implements ogdf::SPQRTree.

Definition at line 214 of file StaticSPQRTree.h.

◆ init() [1/2]

void ogdf::StaticSPQRTree::init ( edge e )

protected

Initialization (called by constructor).

◆ init() [2/2]

void ogdf::StaticSPQRTree::init	(	edge	eRef,
		Triconnectivity &	tricComp
	)

protected

Initialization (called by constructor).

◆ nodesOfType()

List<node> ogdf::StaticSPQRTree::nodesOfType ( NodeType t ) const

override

Returns the list of all nodes with type t.

◆ numberOfPNodes()

int ogdf::StaticSPQRTree::numberOfPNodes ( ) const

inlineoverridevirtual

Returns the number of P-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 138 of file StaticSPQRTree.h.

◆ numberOfRNodes()

int ogdf::StaticSPQRTree::numberOfRNodes ( ) const

inlineoverridevirtual

Returns the number of R-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 141 of file StaticSPQRTree.h.

◆ numberOfSNodes()

int ogdf::StaticSPQRTree::numberOfSNodes ( ) const

inlineoverridevirtual

Returns the number of S-nodes in T.

Implements ogdf::SPQRTree.

Definition at line 135 of file StaticSPQRTree.h.

◆ originalGraph()

const Graph& ogdf::StaticSPQRTree::originalGraph ( ) const

inlineoverridevirtual

Returns a reference to the original graph G.

Implements ogdf::SPQRTree.

Definition at line 123 of file StaticSPQRTree.h.

◆ rootEdge()

edge ogdf::StaticSPQRTree::rootEdge ( ) const

inlineoverridevirtual

Returns the edge of G at which T is rooted.

Implements ogdf::SPQRTree.

Definition at line 129 of file StaticSPQRTree.h.

◆ rootNode()

node ogdf::StaticSPQRTree::rootNode ( ) const

inlineoverridevirtual

Returns the root node of T.

Implements ogdf::SPQRTree.

Definition at line 132 of file StaticSPQRTree.h.

◆ rootRec()

void ogdf::StaticSPQRTree::rootRec	(	node	v,
		edge	ef
	)

protected

Recursively performs rooting of tree.

◆ rootTreeAt() [1/2]

node ogdf::StaticSPQRTree::rootTreeAt ( edge e )

overridevirtual

Roots T at edge e and returns the new root node of T.

Precondition: e is an edge in G

Implements ogdf::SPQRTree.

◆ rootTreeAt() [2/2]

node ogdf::StaticSPQRTree::rootTreeAt ( node v )

overridevirtual

Roots T at node v and returns v.

Precondition: v is a node in T

Implements ogdf::SPQRTree.

◆ skeleton()

Skeleton& ogdf::StaticSPQRTree::skeleton ( node v ) const

inlineoverridevirtual

Returns the skeleton of node v.

Precondition: v is a node in T

Implements ogdf::SPQRTree.

Definition at line 156 of file StaticSPQRTree.h.

◆ skeletonEdgeSrc()

edge ogdf::StaticSPQRTree::skeletonEdgeSrc ( edge e ) const

inline

Returns the edge in skeleton of source(e) that corresponds to tree edge e.

Precondition: e is an edge in T

Definition at line 162 of file StaticSPQRTree.h.

◆ skeletonEdgeTgt()

edge ogdf::StaticSPQRTree::skeletonEdgeTgt ( edge e ) const

inline

Returns the edge in skeleton of target(e) that corresponds to tree edge e.

Precondition: e is an edge in T

Definition at line 168 of file StaticSPQRTree.h.

◆ skeletonOfReal()

const Skeleton& ogdf::StaticSPQRTree::skeletonOfReal ( edge e ) const

inlineoverridevirtual

Returns the skeleton that contains the real edge e.

Precondition: e is an edge in G

Implements ogdf::SPQRTree.

Definition at line 174 of file StaticSPQRTree.h.

◆ tree()

const Graph& ogdf::StaticSPQRTree::tree ( ) const

inlineoverridevirtual

Returns a reference to the tree T.

Implements ogdf::SPQRTree.

Definition at line 126 of file StaticSPQRTree.h.

◆ typeOf()

NodeType ogdf::StaticSPQRTree::typeOf ( node v ) const

inlineoverridevirtual

Returns the type of node v.

Precondition: v is a node in T

Implements ogdf::SPQRTree.

Definition at line 147 of file StaticSPQRTree.h.

Friends And Related Function Documentation

◆ StaticSkeleton

friend class StaticSkeleton

friend

Definition at line 81 of file StaticSPQRTree.h.

Member Data Documentation

◆ m_copyOf

EdgeArray<edge> ogdf::StaticSPQRTree::m_copyOf

protected

skeleton edge corresponding to real edge e

Definition at line 249 of file StaticSPQRTree.h.

◆ m_numP

int ogdf::StaticSPQRTree::m_numP

protected

number of P-nodes

Definition at line 239 of file StaticSPQRTree.h.

◆ m_numR

int ogdf::StaticSPQRTree::m_numR

protected

number of R-nodes

Definition at line 240 of file StaticSPQRTree.h.

◆ m_numS

int ogdf::StaticSPQRTree::m_numS

protected

number of S-nodes

Definition at line 238 of file StaticSPQRTree.h.

◆ m_pGraph

const Graph* ogdf::StaticSPQRTree::m_pGraph

protected

pointer to original graph

Definition at line 232 of file StaticSPQRTree.h.

◆ m_rootEdge

edge ogdf::StaticSPQRTree::m_rootEdge

protected

edge of G at which T is rooted

Definition at line 235 of file StaticSPQRTree.h.

◆ m_rootNode

node ogdf::StaticSPQRTree::m_rootNode

protected

root node of T

Definition at line 236 of file StaticSPQRTree.h.

◆ m_sk

NodeArray<StaticSkeleton*> ogdf::StaticSPQRTree::m_sk

protected

pointer to skeleton of a node in T

Definition at line 244 of file StaticSPQRTree.h.

◆ m_skEdgeSrc

EdgeArray<edge> ogdf::StaticSPQRTree::m_skEdgeSrc

protected

corresponding edge in skeleton(source(e))

Definition at line 245 of file StaticSPQRTree.h.

◆ m_skEdgeTgt

EdgeArray<edge> ogdf::StaticSPQRTree::m_skEdgeTgt

protected

corresponding edge in skeleton(target(e))

Definition at line 246 of file StaticSPQRTree.h.

◆ m_skOf

EdgeArray<StaticSkeleton*> ogdf::StaticSPQRTree::m_skOf

protected

skeleton containing real edge e

Definition at line 248 of file StaticSPQRTree.h.

◆ m_tree

Graph ogdf::StaticSPQRTree::m_tree

protected

underlying tree graph

Definition at line 233 of file StaticSPQRTree.h.

◆ m_type

NodeArray<NodeType> ogdf::StaticSPQRTree::m_type

protected

type of nodes in T

Definition at line 242 of file StaticSPQRTree.h.

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

include/ogdf/decomposition/StaticSPQRTree.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ StaticSPQRTree() [1/3]

◆ StaticSPQRTree() [2/3]

◆ StaticSPQRTree() [3/3]

◆ ~StaticSPQRTree()

Member Function Documentation

◆ copyOfReal()

◆ cpRec()

◆ init() [1/2]

◆ init() [2/2]

◆ nodesOfType()

◆ numberOfPNodes()

◆ numberOfRNodes()

◆ numberOfSNodes()

◆ originalGraph()

◆ rootEdge()

◆ rootNode()

◆ rootRec()

◆ rootTreeAt() [1/2]

◆ rootTreeAt() [2/2]

◆ skeleton()

◆ skeletonEdgeSrc()

◆ skeletonEdgeTgt()

◆ skeletonOfReal()

◆ tree()

◆ typeOf()

Friends And Related Function Documentation

◆ StaticSkeleton

Member Data Documentation

◆ m_copyOf

◆ m_numP

◆ m_numR

◆ m_numS

◆ m_pGraph

◆ m_rootEdge

◆ m_rootNode

◆ m_sk

◆ m_skEdgeSrc

◆ m_skEdgeTgt

◆ m_skOf

◆ m_tree

◆ m_type

Open
Graph Drawing
Framework