OpenGraph DrawingFramework

v.2012.07

ogdf::EmbedderMinDepthPiTa Class Reference

Planar graph embedding with minimum block-nesting depth for given embedded blocks. More...

#include <ogdf/planarity/EmbedderMinDepthPiTa.h>

Inheritance diagram for ogdf::EmbedderMinDepthPiTa:

List of all members.

Public Member Functions

EmbedderMinDepthPiTa ()
Computes an embedding of G.
bool useExtendedDepthDefinition () const
void useExtendedDepthDefinition (bool b)
Public Member Functions inherited from ogdf::EmbedderModule
EmbedderModule ()
Initializes an embedder module.
virtual ~EmbedderModule ()
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

int computeBlockCutfaceTreeEdgeLengths (const node &n)
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.
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.
void computeTdiam (const node &n)
Computes recursively the diametral tree.
Deletes inserted dummy nodes. If adjExternal is an adjacency entry of a dummy edge it is reset.
int depthBlock (const node &bT)
Computes the depth of an embedding Gamma(B).
int depthCutvertex (const node &cT)
Computes the depth of an embedding Gamma(c).
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.
void eccentricityTopDown (const node &nT)
Computes the eccentricity of a node nT in the block-cutface tree and recursively the eccentricity of its children.
void embedBlocks (const node &bT, const node &cH)
Computes recursively an embedding for every block by using the planarEmbed function.
void embedBlockVertex (const node &bT, const node &parent_cT)
Computes entries in newOrder for nodes in a block.
void embedCutVertex (const node &vT, bool root=false)
Computes entry in newOrder for a cutvertex.
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.

Private Attributes

Graph bcTreePG
NodeArray< nodebDG_to_bPG
Graph blockCutfaceTree
NodeArray< GraphblockG
NodeArray< nodebPG_to_bDG
List< nodedummyNodes
NodeArray< EdgeArray< edge > > eBlockEmbedding_to_eH
NodeArray< int > eccentricity
NodeArray< int > eccentricity_alt
EdgeArray< int > edgeLength_blockCutfaceTree
NodeArray< EdgeArray< edge > > eG_nT_to_ePG
NodeArray< EdgeArray< edge > > eH_to_eBlockEmbedding
NodeArray< EdgeArray< edge > > ePG_to_eG_nT
List< List< adjEntry > > faces
List< nodefPG_to_nDG
NodeArray< GraphG_nT
node knotTdiam
NodeArray< List< node > > M_B
EdgeArray< int > m_cB
bool m_useExtendedDepthDefinition
NodeArray< nodenBCTree_to_npBCTree
NodeArray< nodenBlockCutfaceTree_to_nm_blockCutfaceTree
NodeArray< nodenBlockCutfaceTree_to_nTdiam
NodeArray< NodeArray< node > > nBlockEmbedding_to_nH
NodeArray< int > nDG_to_fPG
NodeArray< List< adjEntry > > newOrder
NodeArray< NodeArray< node > > nG_nT_to_nPG
NodeArray< NodeArray< node > > nH_to_nBlockEmbedding
NodeArray< nodenm_blockCutfaceTree_to_nBlockCutfaceTree
NodeArray< NodeArray< int > > nodeLength
NodeArray< nodenpBCTree_to_nBCTree
NodeArray< NodeArray< node > > nPG_to_nG_nT
NodeArray< nodenTdiam_to_nBlockCutfaceTree
List< nodeoneEdgeBlockNodes
BCTreepBCTree
BCTreepm_blockCutfaceTree
Graph Tdiam
bool Tdiam_initialized

Detailed Description

Planar graph embedding with minimum 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 62 of file EmbedderMinDepthPiTa.h.

Constructor & Destructor Documentation

 ogdf::EmbedderMinDepthPiTa::EmbedderMinDepthPiTa ( )
inline

Definition at line 66 of file EmbedderMinDepthPiTa.h.

Member Function Documentation

virtual

Computes an embedding of G.

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

Implements ogdf::EmbedderModule.

 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.
 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
 void ogdf::EmbedderMinDepthPiTa::computeTdiam ( const node & n )
private

Computes recursively the diametral tree.

Parameters:
 n is a node in the block-cutface tree.
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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 bool ogdf::EmbedderMinDepthPiTa::useExtendedDepthDefinition ( ) const
inline

Definition at line 76 of file EmbedderMinDepthPiTa.h.

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

Definition at line 77 of file EmbedderMinDepthPiTa.h.

Member Data Documentation

 Graph ogdf::EmbedderMinDepthPiTa::bcTreePG
private

the tree of pBCTree rooted at a cutface.

Definition at line 193 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::bDG_to_bPG
private

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

Definition at line 280 of file EmbedderMinDepthPiTa.h.

 Graph ogdf::EmbedderMinDepthPiTa::blockCutfaceTree
private

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

Definition at line 265 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::blockG
private

all blocks

Definition at line 205 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::bPG_to_bDG
private

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

Definition at line 277 of file EmbedderMinDepthPiTa.h.

 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 298 of file EmbedderMinDepthPiTa.h.

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

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

Definition at line 217 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::eccentricity
private

saving eccentricity for every node of the block-cutface tree

Definition at line 286 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::eccentricity_alt
private

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

Definition at line 283 of file EmbedderMinDepthPiTa.h.

 EdgeArray ogdf::EmbedderMinDepthPiTa::edgeLength_blockCutfaceTree
private

Saving edge lengths for the block-cutface tree.

Definition at line 232 of file EmbedderMinDepthPiTa.h.

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

a mapping of edges in G_nT to edges in G

Definition at line 316 of file EmbedderMinDepthPiTa.h.

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

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

Definition at line 211 of file EmbedderMinDepthPiTa.h.

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

a mapping of edges in G to edges in G_nT

Definition at line 319 of file EmbedderMinDepthPiTa.h.

 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 256 of file EmbedderMinDepthPiTa.h.

 List ogdf::EmbedderMinDepthPiTa::fPG_to_nDG
private

mapping faces in G to nodes in DG

Definition at line 259 of file EmbedderMinDepthPiTa.h.

 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 307 of file EmbedderMinDepthPiTa.h.

private

adjacency entry of the external face of G_nT[nT]

Definition at line 322 of file EmbedderMinDepthPiTa.h.

 node ogdf::EmbedderMinDepthPiTa::knotTdiam
private

The knot of the diametrical tree

Definition at line 247 of file EmbedderMinDepthPiTa.h.

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

$$M_B = {cH \in B | m_B(cH) = m_B}$$ with $$m_B = \max_{c \in B} m_B(c)$$ and $$m_B(c) = \max {0} \cup {m_{c, B'} | c \in B', B' \neq B}$$.

Definition at line 229 of file EmbedderMinDepthPiTa.h.

 EdgeArray ogdf::EmbedderMinDepthPiTa::m_cB
private

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

Definition at line 223 of file EmbedderMinDepthPiTa.h.

 bool ogdf::EmbedderMinDepthPiTa::m_useExtendedDepthDefinition
private

Definition at line 80 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::nBCTree_to_npBCTree
private

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

Definition at line 196 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::nBlockCutfaceTree_to_nm_blockCutfaceTree
private

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

Definition at line 271 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::nBlockCutfaceTree_to_nTdiam
private

Mapping nodes from block-cutvertex tree to the diametrical tree

Definition at line 241 of file EmbedderMinDepthPiTa.h.

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

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

Definition at line 214 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::nDG_to_fPG
private

mapping nodes in DG to faces in DG

Definition at line 262 of file EmbedderMinDepthPiTa.h.

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

saves for every node of G the new adjacency list

Definition at line 301 of file EmbedderMinDepthPiTa.h.

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

a mapping of nodes in G_nT to nodes in G

Definition at line 310 of file EmbedderMinDepthPiTa.h.

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

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

Definition at line 208 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::nm_blockCutfaceTree_to_nBlockCutfaceTree
private

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

Definition at line 274 of file EmbedderMinDepthPiTa.h.

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

saving for each node in the block graphs its length

Definition at line 220 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::npBCTree_to_nBCTree
private

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

Definition at line 199 of file EmbedderMinDepthPiTa.h.

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

a mapping of nodes in G to nodes in G_nT

Definition at line 313 of file EmbedderMinDepthPiTa.h.

 NodeArray ogdf::EmbedderMinDepthPiTa::nTdiam_to_nBlockCutfaceTree
private

Mapping nodes from the diametrical tree to block-cutvertex tree

Definition at line 244 of file EmbedderMinDepthPiTa.h.

 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 292 of file EmbedderMinDepthPiTa.h.

private

an adjacency entry on the external face

Definition at line 202 of file EmbedderMinDepthPiTa.h.

 BCTree* ogdf::EmbedderMinDepthPiTa::pBCTree
private

the BC-tree of G

Definition at line 190 of file EmbedderMinDepthPiTa.h.

 BCTree* ogdf::EmbedderMinDepthPiTa::pm_blockCutfaceTree
private

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

Definition at line 268 of file EmbedderMinDepthPiTa.h.

 Graph ogdf::EmbedderMinDepthPiTa::Tdiam
private

The diametrical tree of the block-cutface tree.

Definition at line 235 of file EmbedderMinDepthPiTa.h.

 bool ogdf::EmbedderMinDepthPiTa::Tdiam_initialized
private

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

Definition at line 238 of file EmbedderMinDepthPiTa.h.