# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::EmbedderMinDepthPiTa Class Reference

Embedder that minimizes block-nesting depth for given embedded blocks. More...

#include <ogdf/planarity/EmbedderMinDepthPiTa.h>

Inheritance diagram for ogdf::EmbedderMinDepthPiTa:

## Public Member Functions

EmbedderMinDepthPiTa ()

Computes an embedding of G. More...

bool useExtendedDepthDefinition () const

void useExtendedDepthDefinition (bool b)

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

virtual ~EmbedderModule ()

Calls the embedder algorithm for graph G. More...

Calls the embedder algorithm for graph G. More...

Public Member Functions inherited from ogdf::Module
Module ()
Initializes a module. More...

virtual ~Module ()

Public Member Functions inherited from ogdf::Timeouter
Timeouter ()
timeout is turned of by default More...

Timeouter (bool t)
timeout is turned off (false) or on (true) (with 0 second) More...

Timeouter (const Timeouter &t)

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

~Timeouter ()

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

Timeouteroperator= (const Timeouter &t)

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

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

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

## Protected Member Functions

Initialization code for biconnected input. Returns an adjacency entry that lies on the external face. More...

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

## Private Member Functions

int computeBlockCutfaceTreeEdgeLengths (const node &n)
Computes recursively edge lengths for the block-cutface tree. More...

node computeBlockMapping (const node &bDG, const node &parent, List< node > &blocksNodes, List< node > &childBlocks)
Computes for a block bDG of the dual graph the associated block in the original graph. More...

void computeTdiam (const node &n)
Computes recursively the diametral tree. More...

Deletes inserted dummy nodes. More...

int depthBlock (const node &bT)
Computes the depth of an embedding Gamma(B). More...

int depthCutvertex (const node &cT)
Computes the depth of an embedding Gamma(c). More...

int eccentricityBottomUp (const node &nT)
Computes the eccentricity of a node nT in the block-cutface tree to all nodes further down in the tree and recursively the eccentricity to all nodes yet further down its children. More...

void eccentricityTopDown (const node &nT)
Computes the eccentricity of a node nT in the block-cutface tree and recursively the eccentricity of its children. More...

void embedBlocks (const node &bT, const node &cH)
Computes recursively an embedding for every block by using the planarEmbed function. More...

void embedBlockVertex (const node &bT, const node &parent_cT)
Computes entries in newOrder for nodes in a block. More...

void embedCutVertex (const node &vT, bool root=false)
Computes entry in newOrder for a cutvertex. More...

void invertPath (Graph &G, const node &n, const edge &e)
Directs all edges to n and recursively all edges of its children - except the edge to n - to the child. More...

## Private Attributes

Graph bcTreePG
the tree of pBCTree rooted at a cutface. More...

NodeArray< nodebDG_to_bPG
a mapping of blocks of the dual graph DG to its original graph G More...

Graph blockCutfaceTree
the block-cutface tree of G (only the graph, rooted at the external face More...

NodeArray< GraphblockG
all blocks More...

NodeArray< nodebPG_to_bDG
a mapping of blocks of the graph G to its dual graph DG More...

List< nodedummyNodes
this list is saving the dummy nodes which were inserted to produce a face in one-edge-blocks More...

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

NodeArray< int > eccentricity
saving eccentricity for every node of the block-cutface tree More...

NodeArray< int > eccentricity_alt
saving second highest eccentricity for every node of the block-cutface tree More...

EdgeArray< int > edgeLength_blockCutfaceTree
Saving edge lengths for the block-cutface tree. More...

NodeArray< EdgeArray< edge > > eG_nT_to_ePG
a mapping of edges in G_nT to edges in G More...

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

NodeArray< EdgeArray< edge > > ePG_to_eG_nT
a mapping of edges in G to edges in G_nT More...

List< List< adjEntry > > faces
a list of all faces in G, a face in this list is containing a list of all adjacency entries More...

ArrayBuffer< nodefPG_to_nDG
mapping faces (by ID) in G to nodes in DG More...

NodeArray< GraphG_nT
given a node nT (cutvertex or block), G_nT is the subgraph of G associated with the subtree of the BC-tree T rooted at nT More...

adjacency entry of the external face of G_nT[nT] More...

node knotTdiam
The knot of the diametrical tree. More...

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

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

bool m_useExtendedDepthDefinition

NodeArray< nodenBCTree_to_npBCTree
a mapping of nodes in bcTreePG to nodes in pBCTree->bcTree() More...

NodeArray< nodenBlockCutfaceTree_to_nm_blockCutfaceTree
mapping of nodes from the graph blockCutfaceTree to the BC-tree m_blockCutfaceTree More...

NodeArray< nodenBlockCutfaceTree_to_nTdiam
Mapping nodes from block-cutvertex tree to the diametrical tree. More...

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

NodeArray< int > nDG_to_fPG
mapping nodes in DG to faces in DG More...

NodeArray< List< adjEntry > > newOrder
saves for every node of G the new adjacency list More...

NodeArray< NodeArray< node > > nG_nT_to_nPG
a mapping of nodes in G_nT to nodes in G More...

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

NodeArray< nodenm_blockCutfaceTree_to_nBlockCutfaceTree
mapping of nodes from the BC-tree m_blockCutfaceTree to the graph blockCutfaceTree More...

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

NodeArray< nodenpBCTree_to_nBCTree
a mapping of nodes in pBCTree->bcTree() to nodes in bcTreePG More...

NodeArray< NodeArray< node > > nPG_to_nG_nT
a mapping of nodes in G to nodes in G_nT More...

NodeArray< nodenTdiam_to_nBlockCutfaceTree
Mapping nodes from the diametrical tree to block-cutvertex tree. More...

List< nodeoneEdgeBlockNodes
list of nodes which are only in one block which exists of extactly this node plus a cutvertex More...

BCTreepm_blockCutfaceTree
the block-cutface tree of G (the BC-tree of the dual graph) More...

Graph Tdiam
The diametrical tree of the block-cutface tree. More...

bool Tdiam_initialized
Needed in computeTdiam function to know if first vertex was already inserted. More...

adjacency entry of the external face of the embedding of G More...

Public Types inherited from ogdf::Module
enum  ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::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. More...

Protected Attributes inherited from ogdf::embedder::EmbedderBCTreeBase< false >
an adjacency entry on the external face More...

BCTreepBCTree
BC-tree of the original graph. More...

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

## Detailed Description

Embedder that minimizes block-nesting depth for given embedded blocks.

For details see the paper "Minimum Depth Graph Drawing" by M. Pizzonia and R. Tamassia.

Definition at line 46 of file EmbedderMinDepthPiTa.h.

## ◆ EmbedderMinDepthPiTa()

 ogdf::EmbedderMinDepthPiTa::EmbedderMinDepthPiTa ( )
inline

Definition at line 50 of file EmbedderMinDepthPiTa.h.

## ◆ computeBlockCutfaceTreeEdgeLengths()

 int ogdf::EmbedderMinDepthPiTa::computeBlockCutfaceTreeEdgeLengths ( const node & n )
private

Computes recursively edge lengths for the block-cutface tree.

The length of an edge from n to a leaf is 1, from n' to n 2 etc.

Parameters
 n is a node in the block-cutface tree.

## ◆ computeBlockMapping()

 node ogdf::EmbedderMinDepthPiTa::computeBlockMapping ( const node & bDG, const node & parent, List< node > & blocksNodes, List< node > & childBlocks )
private

Computes for a block bDG of the dual graph the associated block in the original graph.

Parameters
 bDG is a node in the block-cutface tree. parent is the parent of bDG in the block-cutface tree. blocksNodes is assigned a list containing all nodes of the original graph of the associated block of bDG. childBlocks

## ◆ computeTdiam()

 void ogdf::EmbedderMinDepthPiTa::computeTdiam ( const node & n )
private

Computes recursively the diametral tree.

Parameters
 n is a node in the block-cutface tree.

## ◆ deleteDummyNodes()

private

Deletes inserted dummy nodes.

If adjExternal is an adjacency entry of a dummy edge it is reset.

Parameters
 G is the graph. adjExternal is an adjacency entry on the external face.

## ◆ depthBlock()

 int ogdf::EmbedderMinDepthPiTa::depthBlock ( const node & bT )
private

Computes the depth of an embedding Gamma(B).

Parameters
 bT is a block-node of the BC-tree.

## ◆ depthCutvertex()

 int ogdf::EmbedderMinDepthPiTa::depthCutvertex ( const node & cT )
private

Computes the depth of an embedding Gamma(c).

Parameters
 cT is a cutvertex-node of the BC-tree.

## ◆ doCall()

overridevirtual

Computes an embedding of G.

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

Implements ogdf::EmbedderModule.

## ◆ eccentricityBottomUp()

 int ogdf::EmbedderMinDepthPiTa::eccentricityBottomUp ( const node & nT )
private

Computes the eccentricity of a node nT in the block-cutface tree to all nodes further down in the tree and recursively the eccentricity to all nodes yet further down its children.

Parameters
 nT is a node in the block-cutface tree.

## ◆ eccentricityTopDown()

 void ogdf::EmbedderMinDepthPiTa::eccentricityTopDown ( const node & nT )
private

Computes the eccentricity of a node nT in the block-cutface tree and recursively the eccentricity of its children.

Parameters
 nT is a node in the block-cutface tree.

## ◆ embedBlocks()

 void ogdf::EmbedderMinDepthPiTa::embedBlocks ( const node & bT, const node & cH )
private

Computes recursively an embedding for every block by using the planarEmbed function.

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

## ◆ embedBlockVertex()

 void ogdf::EmbedderMinDepthPiTa::embedBlockVertex ( const node & bT, const node & parent_cT )
private

Computes entries in newOrder for nodes in a block.

Parameters
 bT is a node in the BC-tree. parent_cT is a node in the BC-tree.

## ◆ embedCutVertex()

 void ogdf::EmbedderMinDepthPiTa::embedCutVertex ( const node & vT, bool root = false )
private

Computes entry in newOrder for a cutvertex.

Parameters
 vT is a cut vertex node in the BC-tree. root is true if vT is the root node of the block-cutface tree.

## ◆ invertPath()

 void ogdf::EmbedderMinDepthPiTa::invertPath ( Graph & G, const node & n, const edge & e )
private

Directs all edges to n and recursively all edges of its children - except the edge to n - to the child.

Parameters
 G is the tree with the inverted edges. n is a node in the original tree. e is an edge in the original tree.

## ◆ trivialInit()

 adjEntry ogdf::EmbedderMinDepthPiTa::trivialInit ( Graph & G )
inlineoverrideprotectedvirtual

Initialization code for biconnected input. Returns an adjacency entry that lies on the external face.

Reimplemented from ogdf::embedder::EmbedderBCTreeBase< false >.

Definition at line 65 of file EmbedderMinDepthPiTa.h.

## ◆ useExtendedDepthDefinition() [1/2]

 bool ogdf::EmbedderMinDepthPiTa::useExtendedDepthDefinition ( ) const
inline

Definition at line 61 of file EmbedderMinDepthPiTa.h.

## ◆ useExtendedDepthDefinition() [2/2]

 void ogdf::EmbedderMinDepthPiTa::useExtendedDepthDefinition ( bool b )
inline

Definition at line 62 of file EmbedderMinDepthPiTa.h.

## ◆ bcTreePG

 Graph ogdf::EmbedderMinDepthPiTa::bcTreePG
private

the tree of pBCTree rooted at a cutface.

Definition at line 185 of file EmbedderMinDepthPiTa.h.

## ◆ bDG_to_bPG

 NodeArray ogdf::EmbedderMinDepthPiTa::bDG_to_bPG
private

a mapping of blocks of the dual graph DG to its original graph G

Definition at line 269 of file EmbedderMinDepthPiTa.h.

## ◆ blockCutfaceTree

 Graph ogdf::EmbedderMinDepthPiTa::blockCutfaceTree
private

the block-cutface tree of G (only the graph, rooted at the external face

Definition at line 254 of file EmbedderMinDepthPiTa.h.

## ◆ blockG

 NodeArray ogdf::EmbedderMinDepthPiTa::blockG
private

all blocks

Definition at line 194 of file EmbedderMinDepthPiTa.h.

## ◆ bPG_to_bDG

 NodeArray ogdf::EmbedderMinDepthPiTa::bPG_to_bDG
private

a mapping of blocks of the graph G to its dual graph DG

Definition at line 266 of file EmbedderMinDepthPiTa.h.

## ◆ dummyNodes

 List ogdf::EmbedderMinDepthPiTa::dummyNodes
private

this list is saving the dummy nodes which were inserted to produce a face in one-edge-blocks

Definition at line 287 of file EmbedderMinDepthPiTa.h.

## ◆ eBlockEmbedding_to_eH

 NodeArray< EdgeArray > ogdf::EmbedderMinDepthPiTa::eBlockEmbedding_to_eH
private

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

Definition at line 206 of file EmbedderMinDepthPiTa.h.

## ◆ eccentricity

 NodeArray ogdf::EmbedderMinDepthPiTa::eccentricity
private

saving eccentricity for every node of the block-cutface tree

Definition at line 275 of file EmbedderMinDepthPiTa.h.

## ◆ eccentricity_alt

 NodeArray ogdf::EmbedderMinDepthPiTa::eccentricity_alt
private

saving second highest eccentricity for every node of the block-cutface tree

Definition at line 272 of file EmbedderMinDepthPiTa.h.

## ◆ edgeLength_blockCutfaceTree

 EdgeArray ogdf::EmbedderMinDepthPiTa::edgeLength_blockCutfaceTree
private

Saving edge lengths for the block-cutface tree.

Definition at line 221 of file EmbedderMinDepthPiTa.h.

## ◆ eG_nT_to_ePG

 NodeArray< EdgeArray > ogdf::EmbedderMinDepthPiTa::eG_nT_to_ePG
private

a mapping of edges in G_nT to edges in G

Definition at line 305 of file EmbedderMinDepthPiTa.h.

## ◆ eH_to_eBlockEmbedding

 NodeArray< EdgeArray > ogdf::EmbedderMinDepthPiTa::eH_to_eBlockEmbedding
private

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

Definition at line 200 of file EmbedderMinDepthPiTa.h.

## ◆ ePG_to_eG_nT

 NodeArray< EdgeArray > ogdf::EmbedderMinDepthPiTa::ePG_to_eG_nT
private

a mapping of edges in G to edges in G_nT

Definition at line 308 of file EmbedderMinDepthPiTa.h.

## ◆ faces

 List< List > ogdf::EmbedderMinDepthPiTa::faces
private

a list of all faces in G, a face in this list is containing a list of all adjacency entries

Definition at line 245 of file EmbedderMinDepthPiTa.h.

## ◆ fPG_to_nDG

 ArrayBuffer ogdf::EmbedderMinDepthPiTa::fPG_to_nDG
private

mapping faces (by ID) in G to nodes in DG

Definition at line 248 of file EmbedderMinDepthPiTa.h.

## ◆ G_nT

 NodeArray ogdf::EmbedderMinDepthPiTa::G_nT
private

given a node nT (cutvertex or block), G_nT is the subgraph of G associated with the subtree of the BC-tree T rooted at nT

Definition at line 296 of file EmbedderMinDepthPiTa.h.

private

adjacency entry of the external face of G_nT[nT]

Definition at line 311 of file EmbedderMinDepthPiTa.h.

## ◆ knotTdiam

 node ogdf::EmbedderMinDepthPiTa::knotTdiam
private

The knot of the diametrical tree.

Definition at line 236 of file EmbedderMinDepthPiTa.h.

## ◆ M_B

 NodeArray< List > ogdf::EmbedderMinDepthPiTa::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 218 of file EmbedderMinDepthPiTa.h.

## ◆ m_cB

 EdgeArray ogdf::EmbedderMinDepthPiTa::m_cB
private

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

Definition at line 212 of file EmbedderMinDepthPiTa.h.

## ◆ m_useExtendedDepthDefinition

 bool ogdf::EmbedderMinDepthPiTa::m_useExtendedDepthDefinition
private

Definition at line 75 of file EmbedderMinDepthPiTa.h.

## ◆ nBCTree_to_npBCTree

 NodeArray ogdf::EmbedderMinDepthPiTa::nBCTree_to_npBCTree
private

a mapping of nodes in bcTreePG to nodes in pBCTree->bcTree()

Definition at line 188 of file EmbedderMinDepthPiTa.h.

## ◆ nBlockCutfaceTree_to_nm_blockCutfaceTree

 NodeArray ogdf::EmbedderMinDepthPiTa::nBlockCutfaceTree_to_nm_blockCutfaceTree
private

mapping of nodes from the graph blockCutfaceTree to the BC-tree m_blockCutfaceTree

Definition at line 260 of file EmbedderMinDepthPiTa.h.

## ◆ nBlockCutfaceTree_to_nTdiam

 NodeArray ogdf::EmbedderMinDepthPiTa::nBlockCutfaceTree_to_nTdiam
private

Mapping nodes from block-cutvertex tree to the diametrical tree.

Definition at line 230 of file EmbedderMinDepthPiTa.h.

## ◆ nBlockEmbedding_to_nH

 NodeArray< NodeArray > ogdf::EmbedderMinDepthPiTa::nBlockEmbedding_to_nH
private

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

Definition at line 203 of file EmbedderMinDepthPiTa.h.

## ◆ nDG_to_fPG

 NodeArray ogdf::EmbedderMinDepthPiTa::nDG_to_fPG
private

mapping nodes in DG to faces in DG

Definition at line 251 of file EmbedderMinDepthPiTa.h.

## ◆ newOrder

 NodeArray< List > ogdf::EmbedderMinDepthPiTa::newOrder
private

saves for every node of G the new adjacency list

Definition at line 290 of file EmbedderMinDepthPiTa.h.

## ◆ nG_nT_to_nPG

 NodeArray< NodeArray > ogdf::EmbedderMinDepthPiTa::nG_nT_to_nPG
private

a mapping of nodes in G_nT to nodes in G

Definition at line 299 of file EmbedderMinDepthPiTa.h.

## ◆ nH_to_nBlockEmbedding

 NodeArray< NodeArray > ogdf::EmbedderMinDepthPiTa::nH_to_nBlockEmbedding
private

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

Definition at line 197 of file EmbedderMinDepthPiTa.h.

## ◆ nm_blockCutfaceTree_to_nBlockCutfaceTree

 NodeArray ogdf::EmbedderMinDepthPiTa::nm_blockCutfaceTree_to_nBlockCutfaceTree
private

mapping of nodes from the BC-tree m_blockCutfaceTree to the graph blockCutfaceTree

Definition at line 263 of file EmbedderMinDepthPiTa.h.

## ◆ nodeLength

 NodeArray< NodeArray > ogdf::EmbedderMinDepthPiTa::nodeLength
private

saving for each node in the block graphs its length

Definition at line 209 of file EmbedderMinDepthPiTa.h.

## ◆ npBCTree_to_nBCTree

 NodeArray ogdf::EmbedderMinDepthPiTa::npBCTree_to_nBCTree
private

a mapping of nodes in pBCTree->bcTree() to nodes in bcTreePG

Definition at line 191 of file EmbedderMinDepthPiTa.h.

## ◆ nPG_to_nG_nT

 NodeArray< NodeArray > ogdf::EmbedderMinDepthPiTa::nPG_to_nG_nT
private

a mapping of nodes in G to nodes in G_nT

Definition at line 302 of file EmbedderMinDepthPiTa.h.

## ◆ nTdiam_to_nBlockCutfaceTree

 NodeArray ogdf::EmbedderMinDepthPiTa::nTdiam_to_nBlockCutfaceTree
private

Mapping nodes from the diametrical tree to block-cutvertex tree.

Definition at line 233 of file EmbedderMinDepthPiTa.h.

## ◆ oneEdgeBlockNodes

 List ogdf::EmbedderMinDepthPiTa::oneEdgeBlockNodes
private

list of nodes which are only in one block which exists of extactly this node plus a cutvertex

Definition at line 281 of file EmbedderMinDepthPiTa.h.

## ◆ pm_blockCutfaceTree

 BCTree* ogdf::EmbedderMinDepthPiTa::pm_blockCutfaceTree
private

the block-cutface tree of G (the BC-tree of the dual graph)

Definition at line 257 of file EmbedderMinDepthPiTa.h.

## ◆ Tdiam

 Graph ogdf::EmbedderMinDepthPiTa::Tdiam
private

The diametrical tree of the block-cutface tree.

Definition at line 224 of file EmbedderMinDepthPiTa.h.

## ◆ Tdiam_initialized

 bool ogdf::EmbedderMinDepthPiTa::Tdiam_initialized
private

Needed in computeTdiam function to know if first vertex was already inserted.

Definition at line 227 of file EmbedderMinDepthPiTa.h.