Planar graph embedding that minimizes block-nesting depth and maximizes the external face and optimizes the position of blocks afterwards. More...

#include <ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h>

Inheritance diagram for ogdf::EmbedderMinDepthMaxFaceLayers:

Protected Member Functions
void	embedBlock (const node &bT, const node &cT, ListIterator< adjEntry > &after) override
	Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.

Protected Member Functions inherited from ogdf::embedder::LayersBlockEmbedder< EmbedderMinDepthMaxFace, embedder::MDMFLengthAttribute >
void	internalEmbedBlock (Graph &SG, NodeArray< embedder::MDMFLengthAttribute > &nodeLengthSG, EdgeArray< embedder::MDMFLengthAttribute > &edgeLengthSG, NodeArray< node > &nSG_to_nG, EdgeArray< edge > &eSG_to_eG, node nodeInBlockSG, node cT, ListIterator< adjEntry > &after)

Protected Member Functions inherited from ogdf::EmbedderMinDepthMaxFace
int	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.

int	constraintMaxFace (const node &bT, const node &cH) override
	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	maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt) override
	Top down traversal of BC-tree.

void	topDownTraversal (const node &bT)
	Top-down-traversal of BC-tree.

Protected Member Functions inherited from ogdf::EmbedderMaxFace
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)

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	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)

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.

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

Public Member Functions inherited from ogdf::EmbedderMinDepthMaxFace
virtual void	doCall (Graph &G, adjEntry &adjExternal) override
	Call embedder algorithm.

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.

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.

Protected Types inherited from ogdf::EmbedderMinDepthMaxFace
using	MDMFLengthAttribute = embedder::MDMFLengthAttribute

Protected Attributes inherited from ogdf::EmbedderMinDepthMaxFace
EdgeArray< int >	cB
	an array saving the length for each edge in the BC-tree

EdgeArray< MDMFLengthAttribute >	edgeLength
	is saving for each edge of the block graph its length

NodeArray< List< node > >	M2
	M2 is empty, if \|M_B\| != 1, otherwise M_B = {cH} M2 = {cH' in V_B \ {v} \| m_B(cH') = m2} with m2 = max{m_B(vH) : vH in V_B, vH != cH}.

NodeArray< int >	maxFaceSize
	an array containing the maximum face size of each block

NodeArray< List< node > >	md_M_B
	M_B = {cH in B \| m_B(cH) = m_B} with m_B = max{m_B(c) : c in B} and m_B(c) = max( {0} cup {m_{c, B'} \| c in B', B' != B} ).

NodeArray< int >	md_nodeLength
	saving for each node in the block graph its length

NodeArray< MDMFLengthAttribute >	mdmf_nodeLength
	is saving for each node of the block graph its length

NodeArray< int >	mf_cstrLength
	is saving for each node of the block graph its cstrLength

NodeArray< int >	mf_nodeLength
	is saving for each node of the block graph its length

NodeArray< int >	minDepth
	an array containing the minimum depth of each block

Protected Attributes inherited from ogdf::EmbedderMaxFace
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).

Detailed Description

Planar graph embedding that minimizes block-nesting depth and maximizes the external face and optimizes the position of blocks afterwards.

After computing an embedding just as ogdf::EmbedderMinDepthMaxFace does, blocks are placed in faces that are closest to the external one.

See the paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) and diploma thesis "Algorithmen zur Bestimmung von guten Graph-Einbettungen für orthogonale Zeichnungen" (in German) by Thorsten Kerkhof (2007) for details.

Definition at line 52 of file EmbedderMinDepthMaxFaceLayers.h.

Member Function Documentation

◆ embedBlock()

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

overrideprotectedvirtual

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 from ogdf::EmbedderMinDepthMaxFace.

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

include/ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h

OpenGraph DrawingFramework

Protected Member Functions

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ embedBlock()

Open
Graph Drawing
Framework