ogdf::EmbedderMinDepthMaxFaceLayers Class Reference

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

#include <EmbedderMinDepthMaxFaceLayers.h>

Inheritance diagram for ogdf::EmbedderMinDepthMaxFaceLayers:

List of all members.

Public Member Functions

EmbedderMinDepthMaxFaceLayers ()

void call (PlanRep &PG, adjEntry &adjExternal)

Call embedder algorithm.

Private Member Functions

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 c in bT is set to 1 if v 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 V_B, v != c} m_B(v) and M2 = {c 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.

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.

Private Attributes

BCTree * pBCTree

adjEntry * pAdjExternal

NodeArray< int > md_nodeLength

NodeArray< int > md_minDepth

EdgeArray< int > md_m_cB

NodeArray< List< node > > md_M_B

NodeArray< List< node > > md_M2

NodeArray< int > mf_nodeLength

NodeArray< int > mf_cstrLength

NodeArray< int > mf_maxFaceSize

NodeArray< mdmf_la > mdmf_nodeLength

EdgeArray< mdmf_la > mdmf_edgeLength

NodeArray< List< adjEntry > > newOrder

NodeArray< bool > treeNodeTreated

Detailed Description

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

Definition at line 73 of file EmbedderMinDepthMaxFaceLayers.h.

Constructor & Destructor Documentation

ogdf::EmbedderMinDepthMaxFaceLayers::EmbedderMinDepthMaxFaceLayers ( ) [inline]

Definition at line 77 of file EmbedderMinDepthMaxFaceLayers.h.

Member Function Documentation

void ogdf::EmbedderMinDepthMaxFaceLayers::call	(	PlanRep &	PG,
		adjEntry &	adjExternal
	)			`[virtual]`

Call embedder algorithm.

Parameters:

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

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 c in bT is set to 1 if v M_{bT} and to 0 otherwise.

Parameters:

	\a	bT is a block vertex in the BC-tree.
	\a	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 V_B, v != c} m_B(v) and M2 = {c 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.
	return	bT_opt is a block node in BC-tree which contains a face which cann be expanded to a maximum face.
	ell_opt	is the size of a maximum face.

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:

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.

Member Data Documentation

BCTree* ogdf::EmbedderMinDepthMaxFaceLayers::pBCTree [private]

the BC-tree of PG

Definition at line 153 of file EmbedderMinDepthMaxFaceLayers.h.

adjEntry* ogdf::EmbedderMinDepthMaxFaceLayers::pAdjExternal [private]

an adjacency entry on the external face

Definition at line 156 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFaceLayers::md_nodeLength [private]

saving for each node in the block graph its length

Definition at line 159 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFaceLayers::md_minDepth [private]

an array containing the minimum depth of each block

Definition at line 162 of file EmbedderMinDepthMaxFaceLayers.h.

EdgeArray<int> ogdf::EmbedderMinDepthMaxFaceLayers::md_m_cB [private]

an array saving the length for each edge in the BC-tree

Definition at line 165 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray< List<node> > ogdf::EmbedderMinDepthMaxFaceLayers::md_M_B [private]

M_B = {cH B | m_B(cH) = m_B} with m_B = max_{c B} m_B(c) and m_B(c) = max {0} {m_{c, B'} | c B', B' B}.

Definition at line 169 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray< List<node> > ogdf::EmbedderMinDepthMaxFaceLayers::md_M2 [private]

M2 is empty, if |M_B| != 1, otherwise M_B = {cH} M2 = {cH' V_B \ {v} | m_B(cH') = m2} with m2 = max_{vH V_B, vH != cH} m_B(vH).

Definition at line 174 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFaceLayers::mf_nodeLength [private]

is saving for each node of the block graph its length

Definition at line 177 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFaceLayers::mf_cstrLength [private]

is saving for each node of the block graph its cstrLength

Definition at line 180 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFaceLayers::mf_maxFaceSize [private]

an array containing the maximum face size of each block

Definition at line 183 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray<mdmf_la> ogdf::EmbedderMinDepthMaxFaceLayers::mdmf_nodeLength [private]

is saving for each node of the block graph its length

Definition at line 186 of file EmbedderMinDepthMaxFaceLayers.h.

EdgeArray<mdmf_la> ogdf::EmbedderMinDepthMaxFaceLayers::mdmf_edgeLength [private]

is saving for each edge of the block graph its length

Definition at line 189 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray< List<adjEntry> > ogdf::EmbedderMinDepthMaxFaceLayers::newOrder [private]

saves for every node of PG the new adjacency list

Definition at line 192 of file EmbedderMinDepthMaxFaceLayers.h.

NodeArray<bool> ogdf::EmbedderMinDepthMaxFaceLayers::treeNodeTreated [private]

treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.

Definition at line 196 of file EmbedderMinDepthMaxFaceLayers.h.

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

ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h

© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.

Generated on Thu Nov 22 19:40:13 2007 by doxygen 1.5.4.


Public Member Functions
	EmbedderMinDepthMaxFaceLayers ()
void	call (PlanRep &PG, adjEntry &adjExternal)
	Call embedder algorithm.
Private Member Functions
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 c in bT is set to 1 if v 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 V_B, v != c} m_B(v) and M2 = {c 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.
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.
Private Attributes
BCTree *	pBCTree
adjEntry *	pAdjExternal
NodeArray< int >	md_nodeLength
NodeArray< int >	md_minDepth
EdgeArray< int >	md_m_cB
NodeArray< List< node > >	md_M_B
NodeArray< List< node > >	md_M2
NodeArray< int >	mf_nodeLength
NodeArray< int >	mf_cstrLength
NodeArray< int >	mf_maxFaceSize
NodeArray< mdmf_la >	mdmf_nodeLength
EdgeArray< mdmf_la >	mdmf_edgeLength
NodeArray< List< adjEntry > >	newOrder
NodeArray< bool >	treeNodeTreated

OpenGraph DrawingFramework

ogdf::EmbedderMinDepthMaxFaceLayers Class Reference

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework