Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Member Functions | Private Member Functions | Private Attributes

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:
ogdf::EmbedderModule ogdf::Module ogdf::Timeouter

List of all members.

Public Member Functions

 EmbedderMinDepthPiTa ()
void call (PlanRep &PG, adjEntry &adjExternal)
 Computes an embedding of G.

Private Member Functions

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

Private Attributes

BCTree * pBCTree
Graph bcTreePG
NodeArray< node > nBCTree_to_npBCTree
NodeArray< node > npBCTree_to_nBCTree
adjEntry * pAdjExternal
NodeArray< Graph > blockG
NodeArray< NodeArray< node > > nH_to_nBlockEmbedding
NodeArray< EdgeArray< edge > > eH_to_eBlockEmbedding
NodeArray< NodeArray< node > > nBlockEmbedding_to_nH
NodeArray< EdgeArray< edge > > eBlockEmbedding_to_eH
NodeArray< NodeArray< int > > nodeLength
EdgeArray< int > m_cB
NodeArray< List< node > > M_B
EdgeArray< int > edgeLength_blockCutfaceTree
Graph Tdiam
bool Tdiam_initialized
NodeArray< node > nBlockCutfaceTree_to_nTdiam
NodeArray< node > nTdiam_to_nBlockCutfaceTree
node knotTdiam
adjEntry tmpAdjExtFace
List< List< adjEntry > > faces
List< node > fPG_to_nDG
NodeArray< int > nDG_to_fPG
Graph blockCutfaceTree
BCTree * pm_blockCutfaceTree
NodeArray< node > nBlockCutfaceTree_to_nm_blockCutfaceTree
NodeArray< node > nm_blockCutfaceTree_to_nBlockCutfaceTree
NodeArray< node > bPG_to_bDG
NodeArray< node > bDG_to_bPG
NodeArray< int > eccentricity_alt
NodeArray< int > eccentricity
List< node > oneEdgeBlockNodes
List< node > dummyNodes
NodeArray< List< adjEntry > > newOrder
NodeArray< Graph > G_nT
NodeArray< NodeArray< node > > nG_nT_to_nPG
NodeArray< NodeArray< node > > nPG_to_nG_nT
NodeArray< EdgeArray< edge > > eG_nT_to_ePG
NodeArray< EdgeArray< edge > > ePG_to_eG_nT
NodeArray< adjEntry > Gamma_adjExt_nT

Detailed Description

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

Definition at line 70 of file EmbedderMinDepthPiTa.h.

Constructor & Destructor Documentation

ogdf::EmbedderMinDepthPiTa::EmbedderMinDepthPiTa (  )  [inline]

Definition at line 74 of file EmbedderMinDepthPiTa.h.

Member Function Documentation

void ogdf::EmbedderMinDepthPiTa::call ( PlanRep &  PG,
adjEntry &  adjExternal 
) [virtual]

Computes an embedding of G.

Parameters:
PG is the original graph.
return adjExternal is an adjacency entry in 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.
return blocksNodes is a list containing all nodes of the original graph of the associated block of bDG.
void ogdf::EmbedderMinDepthPiTa::computeTdiam ( const node &  n  )  [private]

Computes recursively the diametral tree.

Parameters:
n is a node in the block-cutface tree.
void ogdf::EmbedderMinDepthPiTa::deleteDummyNodes ( PlanRep &  PG,
adjEntry &  adjExternal 
) [private]

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

Parameters:
PG 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.
cT_parent is a cutvertex-node of the BC-tree.
int ogdf::EmbedderMinDepthPiTa::depthCutvetex ( 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 of the PlanarModule class.

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.

Member Data Documentation

Graph ogdf::EmbedderMinDepthPiTa::bcTreePG [private]

the tree of pBCTree rooted at a cutface.

Definition at line 195 of file EmbedderMinDepthPiTa.h.

NodeArray<node> ogdf::EmbedderMinDepthPiTa::bDG_to_bPG [private]

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

Definition at line 278 of file EmbedderMinDepthPiTa.h.

Graph ogdf::EmbedderMinDepthPiTa::blockCutfaceTree [private]

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

Definition at line 263 of file EmbedderMinDepthPiTa.h.

NodeArray<Graph> ogdf::EmbedderMinDepthPiTa::blockG [private]

all blocks

Definition at line 207 of file EmbedderMinDepthPiTa.h.

NodeArray<node> ogdf::EmbedderMinDepthPiTa::bPG_to_bDG [private]

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

Definition at line 275 of file EmbedderMinDepthPiTa.h.

List<node> 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 293 of file EmbedderMinDepthPiTa.h.

NodeArray< EdgeArray<edge> > ogdf::EmbedderMinDepthPiTa::eBlockEmbedding_to_eH [private]

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

Definition at line 219 of file EmbedderMinDepthPiTa.h.

NodeArray<int> ogdf::EmbedderMinDepthPiTa::eccentricity [private]

saving eccentricity for every node of the block-cutface tree

Definition at line 284 of file EmbedderMinDepthPiTa.h.

NodeArray<int> ogdf::EmbedderMinDepthPiTa::eccentricity_alt [private]

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

Definition at line 281 of file EmbedderMinDepthPiTa.h.

EdgeArray<int> ogdf::EmbedderMinDepthPiTa::edgeLength_blockCutfaceTree [private]

Saving edge lengths for the block-cutface tree.

Definition at line 232 of file EmbedderMinDepthPiTa.h.

NodeArray< EdgeArray<edge> > ogdf::EmbedderMinDepthPiTa::eG_nT_to_ePG [private]

a mapping of edges in G_nT to edges in PG

Definition at line 310 of file EmbedderMinDepthPiTa.h.

NodeArray< EdgeArray<edge> > ogdf::EmbedderMinDepthPiTa::eH_to_eBlockEmbedding [private]

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

Definition at line 213 of file EmbedderMinDepthPiTa.h.

NodeArray< EdgeArray<edge> > ogdf::EmbedderMinDepthPiTa::ePG_to_eG_nT [private]

a mapping of edges in PG to edges in G_nT

Definition at line 313 of file EmbedderMinDepthPiTa.h.

List< List<adjEntry> > ogdf::EmbedderMinDepthPiTa::faces [private]

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

Definition at line 254 of file EmbedderMinDepthPiTa.h.

List<node> ogdf::EmbedderMinDepthPiTa::fPG_to_nDG [private]

mapping faces in PG to nodes in DG

Definition at line 257 of file EmbedderMinDepthPiTa.h.

NodeArray<Graph> ogdf::EmbedderMinDepthPiTa::G_nT [private]

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

Definition at line 301 of file EmbedderMinDepthPiTa.h.

NodeArray<adjEntry> ogdf::EmbedderMinDepthPiTa::Gamma_adjExt_nT [private]

adjacency entry of the external face of G_nT[nT]

Definition at line 316 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<node> > ogdf::EmbedderMinDepthPiTa::M_B [private]

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

Definition at line 229 of file EmbedderMinDepthPiTa.h.

EdgeArray<int> ogdf::EmbedderMinDepthPiTa::m_cB [private]

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

Definition at line 225 of file EmbedderMinDepthPiTa.h.

NodeArray<node> ogdf::EmbedderMinDepthPiTa::nBCTree_to_npBCTree [private]

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

Definition at line 198 of file EmbedderMinDepthPiTa.h.

NodeArray<node> ogdf::EmbedderMinDepthPiTa::nBlockCutfaceTree_to_nm_blockCutfaceTree [private]

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

Definition at line 269 of file EmbedderMinDepthPiTa.h.

NodeArray<node> 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<node> > ogdf::EmbedderMinDepthPiTa::nBlockEmbedding_to_nH [private]

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

Definition at line 216 of file EmbedderMinDepthPiTa.h.

NodeArray<int> ogdf::EmbedderMinDepthPiTa::nDG_to_fPG [private]

mapping nodes in DG to faces in DG

Definition at line 260 of file EmbedderMinDepthPiTa.h.

NodeArray< List<adjEntry> > ogdf::EmbedderMinDepthPiTa::newOrder [private]

saves for every node of PG the new adjacency list

Definition at line 297 of file EmbedderMinDepthPiTa.h.

NodeArray< NodeArray<node> > ogdf::EmbedderMinDepthPiTa::nG_nT_to_nPG [private]

a mapping of nodes in G_nT to nodes in PG

Definition at line 304 of file EmbedderMinDepthPiTa.h.

NodeArray< NodeArray<node> > ogdf::EmbedderMinDepthPiTa::nH_to_nBlockEmbedding [private]

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

Definition at line 210 of file EmbedderMinDepthPiTa.h.

NodeArray<node> ogdf::EmbedderMinDepthPiTa::nm_blockCutfaceTree_to_nBlockCutfaceTree [private]

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

Definition at line 272 of file EmbedderMinDepthPiTa.h.

NodeArray< NodeArray<int> > ogdf::EmbedderMinDepthPiTa::nodeLength [private]

saving for each node in the block graphs its length

Definition at line 222 of file EmbedderMinDepthPiTa.h.

NodeArray<node> ogdf::EmbedderMinDepthPiTa::npBCTree_to_nBCTree [private]

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

Definition at line 201 of file EmbedderMinDepthPiTa.h.

NodeArray< NodeArray<node> > ogdf::EmbedderMinDepthPiTa::nPG_to_nG_nT [private]

a mapping of nodes in PG to nodes in G_nT

Definition at line 307 of file EmbedderMinDepthPiTa.h.

NodeArray<node> 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<node> 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 288 of file EmbedderMinDepthPiTa.h.

adjEntry* ogdf::EmbedderMinDepthPiTa::pAdjExternal [private]

an adjacency entry on the external face

Definition at line 204 of file EmbedderMinDepthPiTa.h.

BCTree* ogdf::EmbedderMinDepthPiTa::pBCTree [private]

the BC-tree of PG

Definition at line 192 of file EmbedderMinDepthPiTa.h.

BCTree* ogdf::EmbedderMinDepthPiTa::pm_blockCutfaceTree [private]

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

Definition at line 266 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.

adjEntry ogdf::EmbedderMinDepthPiTa::tmpAdjExtFace [private]

adjacency entry of the external face of the embedding of PG

Definition at line 250 of file EmbedderMinDepthPiTa.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:23 by doxygen 1.7.1.