Planar graph embedding with maximum external face. More...

#include <ogdf/planarity/EmbedderMaxFace.h>

Inheritance diagram for ogdf::EmbedderMaxFace:

Public Member Functions
	EmbedderMaxFace ()
	~EmbedderMaxFace ()
void	call (Graph &G, adjEntry &adjExternal)
	Computes an embedding of G with maximum external face.
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	computeBlockGraphs (const node &bT, const node &cH)
	Computes recursively the block graph for every block.
int	constraintMaxFace (const node &bT, const node &cH)
	Bottom up 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.
void	maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt)
	Top down traversal of BC-tree.

Private Attributes
NodeArray< Graph >	blockG
NodeArray< NodeArray< int > >	cstrLength
NodeArray< EdgeArray< edge > >	eBlockEmbedding_to_eH
NodeArray< EdgeArray< edge > >	eH_to_eBlockEmbedding
NodeArray< NodeArray< node > >	nBlockEmbedding_to_nH
NodeArray< List< adjEntry > >	newOrder
NodeArray< NodeArray< node > >	nH_to_nBlockEmbedding
NodeArray< NodeArray< int > >	nodeLength
adjEntry *	pAdjExternal
BCTree *	pBCTree
NodeArray< StaticSPQRTree * >	spqrTrees
NodeArray< bool >	treeNodeTreated

Detailed Description

Planar graph embedding with maximum external face.

See the paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) for details.

Definition at line 61 of file EmbedderMaxFace.h.

Constructor & Destructor Documentation

ogdf::EmbedderMaxFace::EmbedderMaxFace ( )

inline

Definition at line 65 of file EmbedderMaxFace.h.

ogdf::EmbedderMaxFace::~EmbedderMaxFace ( )

inline

Definition at line 66 of file EmbedderMaxFace.h.

Member Function Documentation

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

virtual

Computes an embedding of G with maximum external face.

Parameters:

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

Implements ogdf::EmbedderModule.

void ogdf::EmbedderMaxFace::computeBlockGraphs	(	const node &	bT,
		const node &	cH
	)

private

Computes recursively the block graph for every block.

Parameters:

bT	is a block node in the BC-tree.
cH	is a node of bT in the block graph.

int ogdf::EmbedderMaxFace::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::EmbedderMaxFace::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::EmbedderMaxFace::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.

void ogdf::EmbedderMaxFace::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 which cann be expanded to a maximum face.
ell_opt	is the size of a maximum face.

Member Data Documentation

NodeArray<Graph> ogdf::EmbedderMaxFace::blockG

private

all blocks

Definition at line 131 of file EmbedderMaxFace.h.

NodeArray< NodeArray<int> > ogdf::EmbedderMaxFace::cstrLength

private

is saving for each node in the block graphs its cstrLength

Definition at line 149 of file EmbedderMaxFace.h.

NodeArray< EdgeArray<edge> > ogdf::EmbedderMaxFace::eBlockEmbedding_to_eH

private

a mapping of edges in blockG to the auxiliaryGraph of the BC-tree

Definition at line 143 of file EmbedderMaxFace.h.

NodeArray< EdgeArray<edge> > ogdf::EmbedderMaxFace::eH_to_eBlockEmbedding

private

a mapping of edges in the auxiliaryGraph of the BC-tree to blockG

Definition at line 137 of file EmbedderMaxFace.h.

NodeArray< NodeArray<node> > ogdf::EmbedderMaxFace::nBlockEmbedding_to_nH

private

a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree

Definition at line 140 of file EmbedderMaxFace.h.

NodeArray< List<adjEntry> > ogdf::EmbedderMaxFace::newOrder

private

saves for every node of PG the new adjacency list

Definition at line 152 of file EmbedderMaxFace.h.

NodeArray< NodeArray<node> > ogdf::EmbedderMaxFace::nH_to_nBlockEmbedding

private

a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG

Definition at line 134 of file EmbedderMaxFace.h.

NodeArray< NodeArray<int> > ogdf::EmbedderMaxFace::nodeLength

private

saving for each node in the block graphs its length

Definition at line 146 of file EmbedderMaxFace.h.

adjEntry* ogdf::EmbedderMaxFace::pAdjExternal

private

an adjacency entry on the external face

Definition at line 128 of file EmbedderMaxFace.h.

BCTree* ogdf::EmbedderMaxFace::pBCTree

private

BC-tree of the original graph

Definition at line 125 of file EmbedderMaxFace.h.

NodeArray<StaticSPQRTree*> ogdf::EmbedderMaxFace::spqrTrees

private

The SPQR-trees of the blocks

Definition at line 159 of file EmbedderMaxFace.h.

NodeArray<bool> ogdf::EmbedderMaxFace::treeNodeTreated

private

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

Definition at line 156 of file EmbedderMaxFace.h.

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

ogdf/planarity/EmbedderMaxFace.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework