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 ()

	EmbedderMinDepthPiTa (const EmbedderMinDepthPiTa &copy)=delete

virtual void	doCall (Graph &G, adjEntry &adjExternal) override
	Computes an embedding of `G`. More...

EmbedderMinDepthPiTa &	operator= (const EmbedderMinDepthPiTa &copy)=delete

bool	useExtendedDepthDefinition () const

void	useExtendedDepthDefinition (bool b)

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

virtual	~EmbedderModule ()

void	call (Graph &G, adjEntry &adjExternal)
	Calls the embedder algorithm for graph `G`. More...

void	operator() (Graph &G, adjEntry &adjExternal)
	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...

Timeouter &	operator= (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
adjEntry	trivialInit (Graph &G) override
	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...

void	deleteDummyNodes (Graph &G, adjEntry &adjExternal)
	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< node >	bDG_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...

NodeArrayP< Graph >	blockG
	all blocks More...

NodeArray< node >	bPG_to_bDG
	a mapping of blocks of the graph G to its dual graph DG More...

List< node >	dummyNodes
	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< node >	fPG_to_nDG
	mapping faces (by ID) in G to nodes in DG More...

NodeArrayP< Graph >	G_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...

NodeArray< adjEntry >	Gamma_adjExt_nT
	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< node >	nBCTree_to_npBCTree
	a mapping of nodes in bcTreePG to nodes in pBCTree->bcTree() More...

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

NodeArray< node >	nBlockCutfaceTree_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< node >	nm_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< node >	npBCTree_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< node >	nTdiam_to_nBlockCutfaceTree
	Mapping nodes from the diametrical tree to block-cutvertex tree. More...

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

BCTree *	pm_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...

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

Additional Inherited Members
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 >
adjEntry *	pAdjExternal
	an adjacency entry on the external face More...

BCTree *	pBCTree
	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 52 of file EmbedderMinDepthPiTa.h.

Constructor & Destructor Documentation

◆ EmbedderMinDepthPiTa() [1/2]

ogdf::EmbedderMinDepthPiTa::EmbedderMinDepthPiTa ( )

inline

Definition at line 55 of file EmbedderMinDepthPiTa.h.

◆ EmbedderMinDepthPiTa() [2/2]

ogdf::EmbedderMinDepthPiTa::EmbedderMinDepthPiTa ( const EmbedderMinDepthPiTa & copy )

delete

Member Function Documentation

◆ 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()

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.

◆ 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()

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

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.

◆ operator=()

EmbedderMinDepthPiTa& ogdf::EmbedderMinDepthPiTa::operator= ( const EmbedderMinDepthPiTa & copy )

delete

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

◆ useExtendedDepthDefinition() [1/2]

bool ogdf::EmbedderMinDepthPiTa::useExtendedDepthDefinition ( ) const

inline

Definition at line 68 of file EmbedderMinDepthPiTa.h.

◆ useExtendedDepthDefinition() [2/2]

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

inline

Definition at line 70 of file EmbedderMinDepthPiTa.h.

Member Data Documentation

◆ bcTreePG

Graph ogdf::EmbedderMinDepthPiTa::bcTreePG

private

the tree of pBCTree rooted at a cutface.

Definition at line 190 of file EmbedderMinDepthPiTa.h.

◆ bDG_to_bPG

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

◆ blockG

NodeArrayP<Graph> ogdf::EmbedderMinDepthPiTa::blockG

private

all blocks

Definition at line 199 of file EmbedderMinDepthPiTa.h.

◆ bPG_to_bDG

NodeArray<node> ogdf::EmbedderMinDepthPiTa::bPG_to_bDG

private

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

Definition at line 271 of file EmbedderMinDepthPiTa.h.

◆ dummyNodes

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

◆ eBlockEmbedding_to_eH

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

◆ eccentricity

NodeArray<int> ogdf::EmbedderMinDepthPiTa::eccentricity

private

saving eccentricity for every node of the block-cutface tree

Definition at line 280 of file EmbedderMinDepthPiTa.h.

◆ eccentricity_alt

NodeArray<int> ogdf::EmbedderMinDepthPiTa::eccentricity_alt

private

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

Definition at line 277 of file EmbedderMinDepthPiTa.h.

◆ edgeLength_blockCutfaceTree

EdgeArray<int> ogdf::EmbedderMinDepthPiTa::edgeLength_blockCutfaceTree

private

Saving edge lengths for the block-cutface tree.

Definition at line 226 of file EmbedderMinDepthPiTa.h.

◆ eG_nT_to_ePG

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

private

a mapping of edges in G_nT to edges in G

Definition at line 310 of file EmbedderMinDepthPiTa.h.

◆ eH_to_eBlockEmbedding

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

◆ ePG_to_eG_nT

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

private

a mapping of edges in G to edges in G_nT

Definition at line 313 of file EmbedderMinDepthPiTa.h.

◆ faces

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

◆ fPG_to_nDG

ArrayBuffer<node> ogdf::EmbedderMinDepthPiTa::fPG_to_nDG

private

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

Definition at line 253 of file EmbedderMinDepthPiTa.h.

◆ G_nT

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

◆ Gamma_adjExt_nT

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.

◆ knotTdiam

node ogdf::EmbedderMinDepthPiTa::knotTdiam

private

The knot of the diametrical tree.

Definition at line 241 of file EmbedderMinDepthPiTa.h.

◆ M_B

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

◆ m_cB

EdgeArray<int> ogdf::EmbedderMinDepthPiTa::m_cB

private

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

Definition at line 217 of file EmbedderMinDepthPiTa.h.

◆ m_useExtendedDepthDefinition

bool ogdf::EmbedderMinDepthPiTa::m_useExtendedDepthDefinition

private

Definition at line 83 of file EmbedderMinDepthPiTa.h.

◆ nBCTree_to_npBCTree

NodeArray<node> ogdf::EmbedderMinDepthPiTa::nBCTree_to_npBCTree

private

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

Definition at line 193 of file EmbedderMinDepthPiTa.h.

◆ nBlockCutfaceTree_to_nm_blockCutfaceTree

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

◆ nBlockCutfaceTree_to_nTdiam

NodeArray<node> ogdf::EmbedderMinDepthPiTa::nBlockCutfaceTree_to_nTdiam

private

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

Definition at line 235 of file EmbedderMinDepthPiTa.h.

◆ nBlockEmbedding_to_nH

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

◆ nDG_to_fPG

NodeArray<int> ogdf::EmbedderMinDepthPiTa::nDG_to_fPG

private

mapping nodes in DG to faces in DG

Definition at line 256 of file EmbedderMinDepthPiTa.h.

◆ newOrder

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

private

saves for every node of G the new adjacency list

Definition at line 295 of file EmbedderMinDepthPiTa.h.

◆ nG_nT_to_nPG

NodeArray<NodeArray<node> > ogdf::EmbedderMinDepthPiTa::nG_nT_to_nPG

private

a mapping of nodes in G_nT to nodes in G

Definition at line 304 of file EmbedderMinDepthPiTa.h.

◆ nH_to_nBlockEmbedding

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

◆ nm_blockCutfaceTree_to_nBlockCutfaceTree

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

◆ nodeLength

NodeArray<NodeArray<int> > ogdf::EmbedderMinDepthPiTa::nodeLength

private

saving for each node in the block graphs its length

Definition at line 214 of file EmbedderMinDepthPiTa.h.

◆ npBCTree_to_nBCTree

NodeArray<node> ogdf::EmbedderMinDepthPiTa::npBCTree_to_nBCTree

private

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

Definition at line 196 of file EmbedderMinDepthPiTa.h.

◆ nPG_to_nG_nT

NodeArray<NodeArray<node> > ogdf::EmbedderMinDepthPiTa::nPG_to_nG_nT

private

a mapping of nodes in G to nodes in G_nT

Definition at line 307 of file EmbedderMinDepthPiTa.h.

◆ nTdiam_to_nBlockCutfaceTree

NodeArray<node> ogdf::EmbedderMinDepthPiTa::nTdiam_to_nBlockCutfaceTree

private

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

Definition at line 238 of file EmbedderMinDepthPiTa.h.

◆ oneEdgeBlockNodes

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

◆ Tdiam

Graph ogdf::EmbedderMinDepthPiTa::Tdiam

private

The diametrical tree of the block-cutface tree.

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

◆ tmpAdjExtFace

adjEntry ogdf::EmbedderMinDepthPiTa::tmpAdjExtFace

private

adjacency entry of the external face of the embedding of G

Definition at line 244 of file EmbedderMinDepthPiTa.h.

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

include/ogdf/planarity/EmbedderMinDepthPiTa.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ EmbedderMinDepthPiTa() [1/2]

◆ EmbedderMinDepthPiTa() [2/2]

Member Function Documentation

◆ computeBlockCutfaceTreeEdgeLengths()

◆ computeBlockMapping()

◆ computeTdiam()

◆ deleteDummyNodes()

◆ depthBlock()

◆ depthCutvertex()

◆ doCall()

◆ eccentricityBottomUp()

◆ eccentricityTopDown()

◆ embedBlocks()

◆ embedBlockVertex()

◆ embedCutVertex()

◆ invertPath()

◆ operator=()

◆ trivialInit()

◆ useExtendedDepthDefinition() [1/2]

◆ useExtendedDepthDefinition() [2/2]

Member Data Documentation

◆ bcTreePG

◆ bDG_to_bPG

◆ blockCutfaceTree

◆ blockG

◆ bPG_to_bDG

◆ dummyNodes

◆ eBlockEmbedding_to_eH

◆ eccentricity

◆ eccentricity_alt

◆ edgeLength_blockCutfaceTree

◆ eG_nT_to_ePG

◆ eH_to_eBlockEmbedding

◆ ePG_to_eG_nT

◆ faces

◆ fPG_to_nDG

◆ G_nT

◆ Gamma_adjExt_nT

◆ knotTdiam

◆ M_B

◆ m_cB

◆ m_useExtendedDepthDefinition

◆ nBCTree_to_npBCTree

◆ nBlockCutfaceTree_to_nm_blockCutfaceTree

◆ nBlockCutfaceTree_to_nTdiam

◆ nBlockEmbedding_to_nH

◆ nDG_to_fPG

◆ newOrder

◆ nG_nT_to_nPG

◆ nH_to_nBlockEmbedding

◆ nm_blockCutfaceTree_to_nBlockCutfaceTree

◆ nodeLength

◆ npBCTree_to_nBCTree

◆ nPG_to_nG_nT

◆ nTdiam_to_nBlockCutfaceTree

◆ oneEdgeBlockNodes

◆ pm_blockCutfaceTree

◆ Tdiam

◆ Tdiam_initialized

◆ tmpAdjExtFace

Open
Graph Drawing
Framework