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

	StaticSPQRTree (const Graph &G, edge e)
	Creates an SPQR tree T for graph `G` rooted at the edge `e`.

	StaticSPQRTree (const Graph &G, Triconnectivity &tricComp)
	Creates an SPQR tree T for graph `G` rooted at the first edge of `G`.

	~StaticSPQRTree ()
	Destructor.

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

const Graph &	tree () const override
	Returns a reference to the tree T.

edge	rootEdge () const override
	Returns the edge of G at which T is rooted.

node	rootNode () const override
	Returns the root node of T.

int	numberOfSNodes () const override
	Returns the number of S-nodes in T.

int	numberOfPNodes () const override
	Returns the number of P-nodes in T.

int	numberOfRNodes () const override
	Returns the number of R-nodes in T.

NodeType	typeOf (node v) const override
	Returns the type of node `v`.

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

Skeleton &	skeleton (node v) const override
	Returns the skeleton of node `v`.

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

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

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

edge	copyOfReal (edge e) const override
	Returns the skeleton edge that corresponds to the real edge `e`.

Update operations
node	rootTreeAt (edge e) override
	Roots T at edge `e` and returns the new root node of T.

node	rootTreeAt (node v) override
	Roots T at node `v` and returns `v`.

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

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

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.

void	init (edge e)
	Initialization (called by constructor).

void	init (edge eRef, Triconnectivity &tricComp)
	Initialization (called by constructor).

void	rootRec (node v, edge ef)
	Recursively performs rooting of tree.

Protected Member Functions inherited from ogdf::SPQRTree
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
EdgeArray< edge >	m_copyOf
	skeleton edge corresponding to real edge e

int	m_numP
	number of P-nodes

int	m_numR
	number of R-nodes

int	m_numS
	number of S-nodes

const Graph *	m_pGraph
	pointer to original graph

edge	m_rootEdge
	edge of G at which T is rooted

node	m_rootNode
	root node of T

NodeArray< StaticSkeleton * >	m_sk
	pointer to skeleton of a node in T

EdgeArray< edge >	m_skEdgeSrc
	corresponding edge in skeleton(source(e))

EdgeArray< edge >	m_skEdgeTgt
	corresponding edge in skeleton(target(e))

EdgeArray< StaticSkeleton * >	m_skOf
	skeleton containing real edge e

Graph	m_tree
	underlying tree graph

NodeArray< NodeType >	m_type
	type of nodes in T

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)

Friends
class	StaticSkeleton

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

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 73 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 84 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 95 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 105 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

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