Embedder that minimizes block-nesting depth. More...

#include <ogdf/planarity/EmbedderMinDepth.h>

Inheritance diagram for ogdf::EmbedderMinDepth:

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

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.

Private Member Functions
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.

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

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	topDownTraversal (const node &bT)
	Top-down-traversal of BC-tree.

Private Attributes
NodeArray< Graph >	blockG
	all blocks

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< 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< List< node > >	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}.

EdgeArray< int >	m_cB
	an array saving the length for each edge in the BC-tree

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

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

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.

Protected Member Functions inherited from ogdf::embedder::EmbedderBCTreeBase< false, true >
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 inherited from ogdf::embedder::EmbedderBCTreeBase< false, true >
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

Embedder that minimizes block-nesting depth.

See 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 EmbedderMinDepth.h.

Member Function Documentation

◆ bottomUpTraversal()

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

◆ computeBlockGraphs()

void ogdf::EmbedderMinDepth::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.

◆ doCall()

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

overridevirtual

Computes an embedding of G with minimum depth.

Parameters

G	is the original graph.
adjExternal	is assigned an adjacency entry in the external face.

Implements ogdf::EmbedderModule.

◆ embedBlock() [1/2]

void ogdf::EmbedderMinDepth::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.

◆ embedBlock() [2/2]

void ogdf::EmbedderMinDepth::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.

◆ topDownTraversal()

void ogdf::EmbedderMinDepth::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{m_B(v) : v in V_B, v != c} and M2 = {c in V_B \ {v} | m_B(c) = m2}.

Parameters

bT	is a block vertex in the BC-tree.

Member Data Documentation

◆ blockG

NodeArray<Graph> ogdf::EmbedderMinDepth::blockG

private

all blocks

Definition at line 113 of file EmbedderMinDepth.h.

◆ eBlockEmbedding_to_eH

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

private

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

Definition at line 125 of file EmbedderMinDepth.h.

◆ eH_to_eBlockEmbedding

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

private

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

Definition at line 119 of file EmbedderMinDepth.h.

◆ M2

NodeArray<List<node> > ogdf::EmbedderMinDepth::M2

private

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

Definition at line 147 of file EmbedderMinDepth.h.

◆ M_B

NodeArray<List<node> > ogdf::EmbedderMinDepth::M_B

private

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

Definition at line 140 of file EmbedderMinDepth.h.

◆ m_cB

EdgeArray<int> ogdf::EmbedderMinDepth::m_cB

private

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

Definition at line 134 of file EmbedderMinDepth.h.

◆ minDepth

NodeArray<int> ogdf::EmbedderMinDepth::minDepth

private

an array containing the minimum depth of each block

Definition at line 131 of file EmbedderMinDepth.h.

◆ nBlockEmbedding_to_nH

NodeArray<NodeArray<node> > ogdf::EmbedderMinDepth::nBlockEmbedding_to_nH

private

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

Definition at line 122 of file EmbedderMinDepth.h.

◆ newOrder

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

private

saves for every node of G the new adjacency list

Definition at line 150 of file EmbedderMinDepth.h.

◆ nH_to_nBlockEmbedding

NodeArray<NodeArray<node> > ogdf::EmbedderMinDepth::nH_to_nBlockEmbedding

private

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

Definition at line 116 of file EmbedderMinDepth.h.

◆ nodeLength

NodeArray<NodeArray<int> > ogdf::EmbedderMinDepth::nodeLength

private

saving for each node in the block graphs its length

Definition at line 128 of file EmbedderMinDepth.h.

◆ spqrTrees

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

private

The SPQR-trees of the blocks.

Definition at line 157 of file EmbedderMinDepth.h.

◆ treeNodeTreated

NodeArray<bool> ogdf::EmbedderMinDepth::treeNodeTreated

private

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

Definition at line 154 of file EmbedderMinDepth.h.

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

include/ogdf/planarity/EmbedderMinDepth.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ bottomUpTraversal()

◆ computeBlockGraphs()

◆ doCall()

◆ embedBlock() [1/2]

◆ embedBlock() [2/2]

◆ topDownTraversal()

Member Data Documentation

◆ blockG

◆ eBlockEmbedding_to_eH

◆ eH_to_eBlockEmbedding

◆ M2

◆ M_B

◆ m_cB

◆ minDepth

◆ nBlockEmbedding_to_nH

◆ newOrder

◆ nH_to_nBlockEmbedding

◆ nodeLength

◆ spqrTrees

◆ treeNodeTreated

Open
Graph Drawing
Framework