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 ()
void	call (Graph &G, adjEntry &adjExternal)
	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 ()
void	operator() (Graph &G, adjEntry &adjExternal)
	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.
void	deleteDummyNodes (Graph &G, adjEntry &adjExternal)
	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< node >	bDG_to_bPG
Graph	blockCutfaceTree
NodeArray< Graph >	blockG
NodeArray< node >	bPG_to_bDG
List< node >	dummyNodes
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< node >	fPG_to_nDG
NodeArray< Graph >	G_nT
NodeArray< adjEntry >	Gamma_adjExt_nT
node	knotTdiam
NodeArray< List< node > >	M_B
EdgeArray< int >	m_cB
bool	m_useExtendedDepthDefinition
NodeArray< node >	nBCTree_to_npBCTree
NodeArray< node >	nBlockCutfaceTree_to_nm_blockCutfaceTree
NodeArray< node >	nBlockCutfaceTree_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< node >	nm_blockCutfaceTree_to_nBlockCutfaceTree
NodeArray< NodeArray< int > >	nodeLength
NodeArray< node >	npBCTree_to_nBCTree
NodeArray< NodeArray< node > >	nPG_to_nG_nT
NodeArray< node >	nTdiam_to_nBlockCutfaceTree
List< node >	oneEdgeBlockNodes
adjEntry *	pAdjExternal
BCTree *	pBCTree
BCTree *	pm_blockCutfaceTree
Graph	Tdiam
bool	Tdiam_initialized
adjEntry	tmpAdjExtFace

---

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

void ogdf::EmbedderMinDepthPiTa::call ( Graph &  G, adjEntry &  adjExternal  )

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.

void ogdf::EmbedderMinDepthPiTa::deleteDummyNodes ( Graph &  G, adjEntry &  adjExternal  )

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<node> 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<Graph> ogdf::EmbedderMinDepthPiTa::blockG

private

all blocks

Definition at line 205 of file EmbedderMinDepthPiTa.h.

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

NodeArray<int> ogdf::EmbedderMinDepthPiTa::eccentricity

private

saving eccentricity for every node of the block-cutface tree

Definition at line 286 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 283 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 G

Definition at line 316 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 211 of file EmbedderMinDepthPiTa.h.

NodeArray< EdgeArray<edge> > 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<adjEntry> > 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<node> ogdf::EmbedderMinDepthPiTa::fPG_to_nDG

private

mapping faces in G to nodes in DG

Definition at line 259 of file EmbedderMinDepthPiTa.h.

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

NodeArray<adjEntry> ogdf::EmbedderMinDepthPiTa::Gamma_adjExt_nT

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<node> > 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<int> 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<node> 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<node> 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<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 214 of file EmbedderMinDepthPiTa.h.

NodeArray<int> ogdf::EmbedderMinDepthPiTa::nDG_to_fPG

private

mapping nodes in DG to faces in DG

Definition at line 262 of file EmbedderMinDepthPiTa.h.

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

private

saves for every node of G the new adjacency list

Definition at line 301 of file EmbedderMinDepthPiTa.h.

NodeArray< NodeArray<node> > 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<node> > 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<node> 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<int> > ogdf::EmbedderMinDepthPiTa::nodeLength

private

saving for each node in the block graphs its length

Definition at line 220 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 199 of file EmbedderMinDepthPiTa.h.

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

adjEntry* ogdf::EmbedderMinDepthPiTa::pAdjExternal

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.

adjEntry ogdf::EmbedderMinDepthPiTa::tmpAdjExtFace

private

adjacency entry of the external face of the embedding of G

Definition at line 250 of file EmbedderMinDepthPiTa.h.

---

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

• ogdf/planarity/EmbedderMinDepthPiTa.h