ogdf::EmbedderMaxFaceBiconnectedGraphs< T > Class Template Reference

#include <ogdf/internal/planarity/EmbedderMaxFaceBiconnectedGraphs.h>

List of all members.

Public Member Functions
	EmbedderMaxFaceBiconnectedGraphs ()
	Creates an embedder.
Static Public Member Functions
static void	embed (Graph &G, adjEntry &adjExternal, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, const node &n=0)
	Embeds G by computing and extending a maximum face in G containing n.
static void	compute (const Graph &G, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree &spqrTree, NodeArray< EdgeArray< T > > &edgeLengthSkel)
	Computes the component lengths of all virtual edges in spqrTree.
static T	computeSize (const Graph &G, const node &n, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength)
	Returns the size of a maximum external face in G containing the node n.
static T	computeSize (const Graph &G, const node &n, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree &spqrTree)
	Returns the size of a maximum external face in G containing the node n.
static T	computeSize (const Graph &G, const node &n, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree &spqrTree, const NodeArray< EdgeArray< T > > &edgeLengthSkel)
	Returns the size of a maximum external face in G containing the node n.
static T	computeSize (const Graph &G, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength)
	Returns the size of a maximum external face in G.
static T	computeSize (const Graph &G, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree &spqrTree, NodeArray< EdgeArray< T > > &edgeLengthSkel)
	Returns the size of a maximum external face in G. The SPQR-tree is given. The computed component lengths are computed and returned.
Static Private Member Functions
static void	bottomUpTraversal (StaticSPQRTree &spqrTree, const node &mu, const NodeArray< T > &nodeLength, NodeArray< EdgeArray< T > > &edgeLength)
	Bottom up traversal of SPQR-tree computing the component length of all non-reference edges.
static void	topDownTraversal (StaticSPQRTree &spqrTree, const node &mu, const NodeArray< T > &nodeLength, NodeArray< EdgeArray< T > > &edgeLength)
	Top down traversal of SPQR-tree computing the component length of all reference edges.
static T	largestFaceContainingNode (const StaticSPQRTree &spqrTree, const node &mu, const node &n, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength)
	Computes the size of a maximum face in the skeleton graph of mu containing n.
static T	largestFaceInSkeleton (const StaticSPQRTree &spqrTree, const node &mu, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength)
	Computes the size of a maximum face in the skeleton graph of mu.
static void	expandEdge (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal, const node &n=0)
static void	expandEdgeSNode (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal)
static void	expandEdgePNode (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal)
static void	expandEdgeRNode (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal, const node &n)
static void	adjEntryForNode (adjEntry &ae, ListIterator< adjEntry > &before, const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal)

---

Detailed Description

template<class T>
class ogdf::EmbedderMaxFaceBiconnectedGraphs< T >

Definition at line 60 of file EmbedderMaxFaceBiconnectedGraphs.h.

---

Constructor & Destructor Documentation

template<class T >

ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::EmbedderMaxFaceBiconnectedGraphs

(

)

[inline]

Creates an embedder.

Definition at line 64 of file EmbedderMaxFaceBiconnectedGraphs.h.

---

Member Function Documentation

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::adjEntryForNode	(	adjEntry &	ae,
		ListIterator< adjEntry > &	before,
		const StaticSPQRTree &	spqrTree,
		NodeArray< bool > &	treeNodeTreated,
		const node &	mu,
		const node &	leftNode,
		const NodeArray< T > &	nodeLength,
		const NodeArray< EdgeArray< T > > &	edgeLength,
		NodeArray< List< adjEntry > > &	newOrder,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArraySource,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArrayTarget,
		adjEntry &	adjExternal
	)		[static, private]

(ae->theEdge() == referenceEdge)

(S.isVirtual(ae->theEdge()))

Definition at line 552 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::bottomUpTraversal	(	StaticSPQRTree &	spqrTree,
		const node &	mu,
		const NodeArray< T > &	nodeLength,
		NodeArray< EdgeArray< T > > &	edgeLength
	)		[static, private]

Bottom up traversal of SPQR-tree computing the component length of all non-reference edges.

Parameters:

spqrTree	is the SPQR-tree of G.
mu	is the SPQR-tree node treated in this function call.
nodeLength	is saving for each node of the original graph G its length.
edgeLength	is saving for each skeleton graph the length of each edge.

Definition at line 1500 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::compute	(	const Graph &	G,
		const NodeArray< T > &	nodeLength,
		const EdgeArray< T > &	edgeLength,
		StaticSPQRTree &	spqrTree,
		NodeArray< EdgeArray< T > > &	edgeLengthSkel
	)		[static]

Computes the component lengths of all virtual edges in spqrTree.

Parameters:

G	is the original graph.
nodeLength	is saving for each vertex in G its length.
edgeLength	is saving for each edge in G its length.
spqrTree	is the SPQR-tree of G.
edgeLengthSkel	is saving for each skeleton graph of the SPQR-tree all edge lengths.

Definition at line 1300 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize	(	const Graph &	G,
		const node &	n,
		const NodeArray< T > &	nodeLength,
		const EdgeArray< T > &	edgeLength
	)		[static]

Returns the size of a maximum external face in G containing the node n.

Parameters:

G	is the original graph.
n	is a node of the original graph.
nodeLength	is saving for each vertex in G its length.
edgeLength	is saving for each edge in G its length.

Returns:

The size of a maximum external face in G containing the node n.

Definition at line 1410 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize	(	const Graph &	G,
		const node &	n,
		const NodeArray< T > &	nodeLength,
		const EdgeArray< T > &	edgeLength,
		StaticSPQRTree &	spqrTree
	)		[static]

Returns the size of a maximum external face in G containing the node n.

Parameters:

G	is the original graph.
n	is a node of the original graph.
nodeLength	is saving for each vertex in G its length.
edgeLength	is saving for each edge in G its length.
spqrTree	is the SPQR-tree of G.

Returns:

The size of a maximum external face in G containing the node n.

Definition at line 1434 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize	(	const Graph &	G,
		const node &	n,
		const NodeArray< T > &	nodeLength,
		const EdgeArray< T > &	edgeLength,
		StaticSPQRTree &	spqrTree,
		const NodeArray< EdgeArray< T > > &	edgeLengthSkel
	)		[static]

Returns the size of a maximum external face in G containing the node n.

Parameters:

G	is the original graph.
n	is a node of the original graph.
nodeLength	is saving for each vertex in G its length.
edgeLength	is saving for each edge in G its length.
spqrTree	is the SPQR-tree of G.
edgeLengthSkel	is saving for each skeleton graph the length of each edge.

Returns:

The size of a maximum external face in G containing the node n.

Definition at line 1447 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize	(	const Graph &	G,
		const NodeArray< T > &	nodeLength,
		const EdgeArray< T > &	edgeLength
	)		[static]

Returns the size of a maximum external face in G.

Parameters:

G	is the original graph.
nodeLength	is saving for each vertex in G its length.
edgeLength	is saving for each edge in G its length.

Returns:

The size of a maximum external face in G.

Definition at line 1335 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize	(	const Graph &	G,
		const NodeArray< T > &	nodeLength,
		const EdgeArray< T > &	edgeLength,
		StaticSPQRTree &	spqrTree,
		NodeArray< EdgeArray< T > > &	edgeLengthSkel
	)		[static]

Returns the size of a maximum external face in G. The SPQR-tree is given. The computed component lengths are computed and returned.

Parameters:

G	is the original graph.
nodeLength	is saving for each vertex in G its length.
edgeLength	is saving for each edge in G its length.
spqrTree	is the SPQR-tree of G.
edgeLengthSkel	is saving for each skeleton graph the length of each edge.

Returns:

The size of a maximum external face in G.

Definition at line 1356 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::embed	(	Graph &	G,
		adjEntry &	adjExternal,
		const NodeArray< T > &	nodeLength,
		const EdgeArray< T > &	edgeLength,
		const node &	n = 0
	)		[static]

Embeds G by computing and extending a maximum face in G containing n.

Parameters:

G	is the original graph.
return	adjExternal is an adjacency entry of the external face.
nodeLength	is saving for each vertex in G its length.
edgeLength	is saving for each edge in G its length.
n	is a vertex of the original graph. If n is given, a maximum face containing n is computed, otherwise any maximum face.

Definition at line 445 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdge	(	const StaticSPQRTree &	spqrTree,
		NodeArray< bool > &	treeNodeTreated,
		const node &	mu,
		const node &	leftNode,
		const NodeArray< T > &	nodeLength,
		const NodeArray< EdgeArray< T > > &	edgeLength,
		NodeArray< List< adjEntry > > &	newOrder,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArraySource,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArrayTarget,
		adjEntry &	adjExternal,
		const node &	n = 0
	)		[static, private]

Definition at line 638 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdgePNode	(	const StaticSPQRTree &	spqrTree,
		NodeArray< bool > &	treeNodeTreated,
		const node &	mu,
		const node &	leftNode,
		const NodeArray< T > &	nodeLength,
		const NodeArray< EdgeArray< T > > &	edgeLength,
		NodeArray< List< adjEntry > > &	newOrder,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArraySource,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArrayTarget,
		adjEntry &	adjExternal
	)		[static, private]

Definition at line 773 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdgeRNode	(	const StaticSPQRTree &	spqrTree,
		NodeArray< bool > &	treeNodeTreated,
		const node &	mu,
		const node &	leftNode,
		const NodeArray< T > &	nodeLength,
		const NodeArray< EdgeArray< T > > &	edgeLength,
		NodeArray< List< adjEntry > > &	newOrder,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArraySource,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArrayTarget,
		adjEntry &	adjExternal,
		const node &	n
	)		[static, private]

Definition at line 1014 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdgeSNode	(	const StaticSPQRTree &	spqrTree,
		NodeArray< bool > &	treeNodeTreated,
		const node &	mu,
		const node &	leftNode,
		const NodeArray< T > &	nodeLength,
		const NodeArray< EdgeArray< T > > &	edgeLength,
		NodeArray< List< adjEntry > > &	newOrder,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArraySource,
		NodeArray< ListIterator< adjEntry > > &	adjBeforeNodeArrayTarget,
		adjEntry &	adjExternal
	)		[static, private]

Definition at line 675 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::largestFaceContainingNode	(	const StaticSPQRTree &	spqrTree,
		const node &	mu,
		const node &	n,
		const NodeArray< T > &	nodeLength,
		const NodeArray< EdgeArray< T > > &	edgeLength
	)		[static, private]

Computes the size of a maximum face in the skeleton graph of mu containing n.

Parameters:

spqrTree	is the SPQR-tree of G.
mu	is the SPQR-tree node treated in this function call.
n	is a node of the original graph G.
nodeLength	is saving for each node of the original graph G its length.
edgeLength	is saving for each skeleton graph the length of each edge.

Definition at line 1688 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::largestFaceInSkeleton	(	const StaticSPQRTree &	spqrTree,
		const node &	mu,
		const NodeArray< T > &	nodeLength,
		const NodeArray< EdgeArray< T > > &	edgeLength
	)		[static, private]

Computes the size of a maximum face in the skeleton graph of mu.

Parameters:

spqrTree	is the SPQR-tree of G.
mu	is the SPQR-tree node treated in this function call.
nodeLength	is saving for each node of the original graph G its length.
edgeLength	is saving for each skeleton graph the length of each edge.

Definition at line 1789 of file EmbedderMaxFaceBiconnectedGraphs.h.

template<class T >

void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::topDownTraversal	(	StaticSPQRTree &	spqrTree,
		const node &	mu,
		const NodeArray< T > &	nodeLength,
		NodeArray< EdgeArray< T > > &	edgeLength
	)		[static, private]

Top down traversal of SPQR-tree computing the component length of all reference edges.

Parameters:

spqrTree	is the SPQR-tree of G.
mu	is the SPQR-tree node treated in this function call.
nodeLength	is saving for each node of the original graph G its length.
edgeLength	is saving for each skeleton graph the length of each edge.

Definition at line 1595 of file EmbedderMaxFaceBiconnectedGraphs.h.

---

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

• ogdf/internal/planarity/EmbedderMaxFaceBiconnectedGraphs.h