Embedder that maximizes the external face. More...

#include <ogdf/planarity/EmbedderMaxFace.h>

Inheritance diagram for ogdf::EmbedderMaxFace:

Public Member Functions
virtual void	doCall (Graph &G, adjEntry &adjExternal) override
	Computes an embedding of `G` with maximum external face.

Public Member Functions inherited from ogdf::EmbedderModule
	EmbedderModule ()
	Initializes an embedder module.

virtual	~EmbedderModule ()

void	call (Graph &G, adjEntry &adjExternal)
	Calls the embedder algorithm for graph `G`.

void	operator() (Graph &G, adjEntry &adjExternal)
	Calls the embedder algorithm for graph `G`.

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 (bool t)
	timeout is turned off (false) or on (true) (with 0 second)

	Timeouter (const Timeouter &t)

	Timeouter (double t)
	timeout is set to the given value (seconds)

	~Timeouter ()

bool	isTimeLimit () const
	returns whether any time limit is set or not

Timeouter &	operator= (const Timeouter &t)

double	timeLimit () const
	returns the current time limit for the call

void	timeLimit (bool t)
	shorthand to turn timelimit off or on (with 0 seconds)

void	timeLimit (double t)
	sets the time limit for the call (in seconds); <0 means no limit.

Protected Member Functions
void	computeBlockGraphs (const node &bT, const node &cH)
	Computes recursively the block graph for every block.

void	computeNodeLength (node bT, std::function< int &(node)> setter)

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

virtual 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	forEachIngoingNeighbor (node v, std::function< void(node)> fun)
	Calls `fun` for every ingoing edge (w,`v`).

template<typename T >
void	internalEmbedBlock (const node bT, const node cT, ListIterator< adjEntry > &after, Graph &blockGraph, NodeArray< T > &paramNodeLength, EdgeArray< T > &paramEdgeLength, NodeArray< node > &mapNodeToH, EdgeArray< edge > &mapEdgeToH, const node nodeInBlock)

void	internalMaximumFaceRec (const node &bT, node &bT_opt, int &ell_opt, Graph &blockGraph, NodeArray< int > &paramNodeLength, StaticSPQRTree spqrTree, std::function< node &(node)> getBENode, std::function< int &(node, node)> getCstrLength, std::function< int &(node, node)> getNodeLength, int const maxFaceSizeToUpdate=nullptr)

virtual void	maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt)
	Top down traversal of BC-tree.

Protected Member Functions inherited from ogdf::embedder::EmbedderBCTreeBase< false >
node	initBCTree (Graph &G)
	Initializes pBCTree and returns the root node of this tree or `nullptr` if `G` is biconnected.

virtual adjEntry	trivialInit (Graph &G)
	Initialization code for biconnected input. Returns an adjacency entry that lies on the external face.

Protected Attributes
NodeArray< Graph >	blockG
	all blocks

NodeArray< NodeArray< int > >	cstrLength
	is saving for each node in the block graphs its cstrLength

NodeArray< EdgeArray< edge > >	eBlockEmbedding_to_eH
	a mapping of edges in blockG to the auxiliaryGraph of the BC-tree

NodeArray< EdgeArray< edge > >	eH_to_eBlockEmbedding
	a mapping of edges in the auxiliaryGraph of the BC-tree to blockG

NodeArray< NodeArray< node > >	nBlockEmbedding_to_nH
	a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree

NodeArray< List< adjEntry > >	newOrder
	saves for every node of PG the new adjacency list

NodeArray< NodeArray< node > >	nH_to_nBlockEmbedding
	a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG

NodeArray< NodeArray< int > >	nodeLength
	saving for each node in the block graphs its length

NodeArray< StaticSPQRTree * >	spqrTrees
	The SPQR-trees of the blocks.

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

Protected Attributes inherited from ogdf::embedder::EmbedderBCTreeBase< false >
adjEntry *	pAdjExternal
	an adjacency entry on the external face

BCTree *	pBCTree
	BC-tree of the original graph.

Protected Attributes inherited from ogdf::Timeouter
double	m_timeLimit
	Time limit for module calls (< 0 means no limit).

Additional Inherited Members
Public Types inherited from ogdf::Module
enum class	ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error }
	The return type of a module. More...

Static Public Member Functions inherited from ogdf::Module
static bool	isSolution (ReturnType ret)
	Returns true iff `ret` indicates that the module returned a feasible solution.

Detailed Description

Embedder that maximizes the 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 47 of file EmbedderMaxFace.h.

Member Function Documentation

◆ computeBlockGraphs()

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

protected

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.

◆ computeNodeLength()

void ogdf::EmbedderMaxFace::computeNodeLength	(	node	bT,
		std::function< int &(node)>	setter
	)

inlineprotected

Definition at line 66 of file EmbedderMaxFace.h.

◆ constraintMaxFace()

virtual int ogdf::EmbedderMaxFace::constraintMaxFace	(	const node &	bT,
		const node &	cH
	)

protectedvirtual

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.

Reimplemented in ogdf::EmbedderMinDepthMaxFace.

◆ doCall()

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

overridevirtual

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.

Reimplemented in ogdf::EmbedderMinDepthMaxFace.

◆ embedBlock() [1/2]

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

protected

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.

◆ embedBlock() [2/2]

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

protectedvirtual

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.

Reimplemented in ogdf::EmbedderMinDepthMaxFace, ogdf::EmbedderMaxFaceLayers, ogdf::EmbedderMinDepthMaxFace, and ogdf::EmbedderMinDepthMaxFaceLayers.

◆ forEachIngoingNeighbor()

void ogdf::EmbedderMaxFace::forEachIngoingNeighbor	(	node	v,
		std::function< void(node)>	fun
	)

inlineprotected

Calls fun for every ingoing edge (w,v).

Definition at line 58 of file EmbedderMaxFace.h.

◆ internalEmbedBlock()

template<typename T >

void ogdf::EmbedderMaxFace::internalEmbedBlock	(	const node	bT,
		const node	cT,
		ListIterator< adjEntry > &	after,
		Graph &	blockGraph,
		NodeArray< T > &	paramNodeLength,
		EdgeArray< T > &	paramEdgeLength,
		NodeArray< node > &	mapNodeToH,
		EdgeArray< edge > &	mapEdgeToH,
		const node	nodeInBlock
	)

inlineprotected

Definition at line 143 of file EmbedderMaxFace.h.

◆ internalMaximumFaceRec()

void ogdf::EmbedderMaxFace::internalMaximumFaceRec	(	const node &	bT,
		node &	bT_opt,
		int &	ell_opt,
		Graph &	blockGraph,
		NodeArray< int > &	paramNodeLength,
		StaticSPQRTree *	spqrTree,
		std::function< node &(node)>	getBENode,
		std::function< int &(node, node)>	getCstrLength,
		std::function< int &(node, node)>	getNodeLength,
		int *const	maxFaceSizeToUpdate = `nullptr`
	)

inlineprotected

Definition at line 81 of file EmbedderMaxFace.h.

◆ maximumFaceRec()

virtual void ogdf::EmbedderMaxFace::maximumFaceRec	(	const node &	bT,
		node &	bT_opt,
		int &	ell_opt
	)

protectedvirtual

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.

Reimplemented in ogdf::EmbedderMinDepthMaxFace.

Member Data Documentation

◆ blockG

NodeArray<Graph> ogdf::EmbedderMaxFace::blockG

protected

all blocks

Definition at line 291 of file EmbedderMaxFace.h.

◆ cstrLength

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

protected

is saving for each node in the block graphs its cstrLength

Definition at line 309 of file EmbedderMaxFace.h.

◆ eBlockEmbedding_to_eH

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

protected

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

Definition at line 303 of file EmbedderMaxFace.h.

◆ eH_to_eBlockEmbedding

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

protected

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

Definition at line 297 of file EmbedderMaxFace.h.

◆ nBlockEmbedding_to_nH

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

protected

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

Definition at line 300 of file EmbedderMaxFace.h.

◆ newOrder

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

protected

saves for every node of PG the new adjacency list

Definition at line 312 of file EmbedderMaxFace.h.

◆ nH_to_nBlockEmbedding

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

protected

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

Definition at line 294 of file EmbedderMaxFace.h.

◆ nodeLength

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

protected

saving for each node in the block graphs its length

Definition at line 306 of file EmbedderMaxFace.h.

◆ spqrTrees

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

protected

The SPQR-trees of the blocks.

Definition at line 319 of file EmbedderMaxFace.h.

◆ treeNodeTreated

NodeArray<bool> ogdf::EmbedderMaxFace::treeNodeTreated

protected

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

Definition at line 316 of file EmbedderMaxFace.h.

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

include/ogdf/planarity/EmbedderMaxFace.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ computeBlockGraphs()

◆ computeNodeLength()

◆ constraintMaxFace()

◆ doCall()

◆ embedBlock() [1/2]

◆ embedBlock() [2/2]

◆ forEachIngoingNeighbor()

◆ internalEmbedBlock()

◆ internalMaximumFaceRec()

◆ maximumFaceRec()

Member Data Documentation

◆ blockG

◆ cstrLength

◆ eBlockEmbedding_to_eH

◆ eH_to_eBlockEmbedding

◆ nBlockEmbedding_to_nH

◆ newOrder

◆ nH_to_nBlockEmbedding

◆ nodeLength

◆ spqrTrees

◆ treeNodeTreated

Open
Graph Drawing
Framework