Planar graph embedding with minimum block-nesting depth and maximum external face (plus layers approach). More...

#include <ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h>

Inheritance diagram for ogdf::EmbedderMinDepthMaxFaceLayers:

Public Member Functions
	EmbedderMinDepthMaxFaceLayers ()
void	call (Graph &G, adjEntry &adjExternal)
	Call embedder algorithm.
Public Member Functions inherited from ogdf::EmbedderModule
	EmbedderModule ()
	Initializes an embedder module.
virtual	~EmbedderModule ()
void	operator() (Graph &G, adjEntry &adjExternal)
	Calls the embedder algorithm for planarized representation PG.
Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.
virtual	~Module ()
Public Member Functions inherited from ogdf::Timeouter
	Timeouter ()
	timeout is turned of by default
	Timeouter (double t)
	timeout is set to the given value (seconds)
	Timeouter (bool t)
	timeout is turned off (false) or on (true) (with 0 second)
	Timeouter (const Timeouter &t)
	~Timeouter ()
bool	isTimeLimit () const
	returns whether any time limit is set or not
void	timeLimit (double t)
	sets the time limit for the call (in seconds); <0 means no limit.
void	timeLimit (bool t)
	shorthand to turn timelimit off or on (with 0 seconds)
double	timeLimit () const
	returns the current time limit for the call

Private Member Functions
void	embedBlock (const node &bT)
	Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.
void	embedBlock (const node &bT, const node &cT, ListIterator< adjEntry > &after)
	Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.
int	md_bottomUpTraversal (const node &bT, const node &cH)
	Bottom-up-traversal of bcTree computing the values m_{cT, bT} for all edges (cT, bT) in the BC-tree. The length of each vertex \( v \neq c \) in bT is set to 1 if \( v \in M_{bT}\) and to 0 otherwise.
void	md_topDownTraversal (const node &bT)
	Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for \|M_B\| = 1, than it is set to 1 if it is in M2 with m2 = \(\max_{v \in V_B, v != c} m_B(v)\) and M2 = \({c \in V_B \ {v} \| m_B(c) = m2}\).
int	mf_constraintMaxFace (const node &bT, const node &cH)
	Bottom up traversal of BC-tree.
void	mf_maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt)
	Top down traversal of BC-tree.

Private Attributes
NodeArray< List< node > >	md_M2
NodeArray< List< node > >	md_M_B
EdgeArray< int >	md_m_cB
NodeArray< int >	md_minDepth
NodeArray< int >	md_nodeLength
EdgeArray< MDMFLengthAttribute >	mdmf_edgeLength
NodeArray< MDMFLengthAttribute >	mdmf_nodeLength
NodeArray< int >	mf_cstrLength
NodeArray< int >	mf_maxFaceSize
NodeArray< int >	mf_nodeLength
NodeArray< List< adjEntry > >	newOrder
adjEntry *	pAdjExternal
BCTree *	pBCTree
NodeArray< bool >	treeNodeTreated

Detailed Description

Planar graph embedding with minimum block-nesting depth and maximum external face (plus layers approach).

See paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) for details. The algorithm for minimum depth and maximum external face is combined with the algorithm for maximum external layers which defines how to embed blocks into inner faces. See diploma thesis "Algorithmen zur Bestimmung von guten Graph-Einbettungen für orthogonale Zeichnungen" (in german) by Thorsten Kerkhof (2007) for details.

Definition at line 67 of file EmbedderMinDepthMaxFaceLayers.h.

Constructor & Destructor Documentation

ogdf::EmbedderMinDepthMaxFaceLayers::EmbedderMinDepthMaxFaceLayers ( )

inline

Definition at line 71 of file EmbedderMinDepthMaxFaceLayers.h.

Member Function Documentation

void ogdf::EmbedderMinDepthMaxFaceLayers::call	(	Graph &	G,
		adjEntry &	adjExternal
	)

virtual

Call embedder algorithm.

Parameters:

G	is the original graph. Its adjacency list has to be changed by the embedder.
adjExternal	is an adjacency entry on the external face and has to be set by the embedder.

Implements ogdf::EmbedderModule.

void ogdf::EmbedderMinDepthMaxFaceLayers::embedBlock ( const node & bT )

private

Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.

Parameters:

bT	is the tree node treated in this function call.

void ogdf::EmbedderMinDepthMaxFaceLayers::embedBlock	(	const node &	bT,
		const node &	cT,
		ListIterator< adjEntry > &	after
	)

private

Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.

Parameters:

bT	is the tree node treated in this function call.
cT	is the parent cut vertex node of bT in the BC-tree. cT is 0 if bT is the root block.
after	is the adjacency entry of the cut vertex, after which bT has to be inserted.

int ogdf::EmbedderMinDepthMaxFaceLayers::md_bottomUpTraversal	(	const node &	bT,
		const node &	cH
	)

private

Bottom-up-traversal of bcTree computing the values m_{cT, bT} for all edges (cT, bT) in the BC-tree. The length of each vertex \( v \neq c \) in bT is set to 1 if \( v \in M_{bT}\) and to 0 otherwise.

Parameters:

bT	is a block vertex in the BC-tree.
cH	is a vertex in the original graph G.

Returns:: Minimum depth of an embedding of bT with cH on the external face.

void ogdf::EmbedderMinDepthMaxFaceLayers::md_topDownTraversal ( const node & bT )

private

Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to 1 if it is in M2 with m2 = \(\max_{v \in V_B, v != c} m_B(v)\) and M2 = \({c \in V_B \ {v} | m_B(c) = m2}\).

Parameters:

bT	is a block vertex in the BC-tree.

int ogdf::EmbedderMinDepthMaxFaceLayers::mf_constraintMaxFace	(	const node &	bT,
		const node &	cH
	)

private

Bottom up traversal of BC-tree.

Parameters:

bT	is the BC-tree node treated in this function call.
cH	is the block node which is related to the cut vertex which is parent of bT in BC-tree.

void ogdf::EmbedderMinDepthMaxFaceLayers::mf_maximumFaceRec	(	const node &	bT,
		node &	bT_opt,
		int &	ell_opt
	)

private

Top down traversal of BC-tree.

Parameters:

bT	is the tree node treated in this function call.
bT_opt	is assigned a block node in BC-tree which contains a face that can be expanded to a maximum face.
ell_opt	is the size of a maximum face.