Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::EmbedderMinDepthMaxFace Class Reference

Planar graph embedding with minimum block-nesting depth and maximum external face. More...

#include <ogdf/planarity/EmbedderMinDepthMaxFace.h>

+ Inheritance diagram for ogdf::EmbedderMinDepthMaxFace:

Public Member Functions

 EmbedderMinDepthMaxFace ()
 
void call (Graph &G, adjEntry &adjExternal)
 Call embedder algorithm. More...
 
- Public Member Functions inherited from ogdf::EmbedderModule
 EmbedderModule ()
 Initializes an embedder module. More...
 
virtual ~EmbedderModule ()
 
void operator() (Graph &G, adjEntry &adjExternal)
 Calls the embedder algorithm for planarized representation PG. 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 (double t)
 timeout is set to the given value (seconds) More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
double timeLimit () const
 returns the current time limit for the call More...
 

Private Member Functions

void embedBlock (const node &bT)
 Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT. More...
 
void embedBlock (const node &bT, const node &cT, ListIterator< adjEntry > &after)
 Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT. More...
 
int md_bottomUpTraversal (const node &bT, const node &cH)
 Bottom-up-traversal of bcTree computing the values m_{cT, bT} for all edges (cT, bT) in the BC-tree. The length of each vertex \(v \neq c in \a bT\) is set to 1 if \(v \in M_{bT}\) and to 0 otherwise. More...
 
void md_topDownTraversal (const node &bT)
 Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to 1 if it is in M2 with m2 = \(\max_{v \in V_B, v != c} m_B(v)\) and M2 = \({c \in V_B \ {v} | m_B(c) = m2}\). More...
 
int mf_constraintMaxFace (const node &bT, const node &cH)
 Bottom up traversal of BC-tree. More...
 
void mf_maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt)
 Top down traversal of BC-tree. More...
 

Private Attributes

NodeArray< List< node > > md_M2
 
NodeArray< List< node > > md_M_B
 
EdgeArray< int > md_m_cB
 
NodeArray< int > md_minDepth
 
NodeArray< int > md_nodeLength
 
EdgeArray< MDMFLengthAttributemdmf_edgeLength
 
NodeArray< MDMFLengthAttributemdmf_nodeLength
 
NodeArray< int > mf_cstrLength
 
NodeArray< int > mf_maxFaceSize
 
NodeArray< int > mf_nodeLength
 
NodeArray< List< adjEntry > > newOrder
 
adjEntrypAdjExternal
 
BCTreepBCTree
 
NodeArray< bool > treeNodeTreated
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum  ReturnType { retFeasible, retOptimal, retNoFeasibleSolution, retTimeoutFeasible, retTimeoutInfeasible, retError }
 The return type of a module. More...
 
- Static Public Member Functions inherited from ogdf::Module
static bool isSolution (ReturnType ret)
 Returns true iff retVal indicates that the module returned a feasible solution. More...
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit). More...
 

Detailed Description

Planar graph embedding with minimum block-nesting depth and maximum external face.

See the paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) for details.

Definition at line 62 of file EmbedderMinDepthMaxFace.h.

Constructor & Destructor Documentation

ogdf::EmbedderMinDepthMaxFace::EmbedderMinDepthMaxFace ( )
inline

Definition at line 66 of file EmbedderMinDepthMaxFace.h.

Member Function Documentation

void ogdf::EmbedderMinDepthMaxFace::call ( Graph G,
adjEntry adjExternal 
)
virtual

Call embedder algorithm.

Parameters
Gis the original graph. Its adjacency list has to be changed by the embedder.
adjExternalis an adjacency entry on the external face and has to be set by the embedder.

Implements ogdf::EmbedderModule.

void ogdf::EmbedderMinDepthMaxFace::embedBlock ( const node bT)
private

Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.

Parameters
bTis the tree node treated in this function call.
void ogdf::EmbedderMinDepthMaxFace::embedBlock ( const node bT,
const node cT,
ListIterator< adjEntry > &  after 
)
private

Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.

Parameters
bTis the tree node treated in this function call.
cTis the parent cut vertex node of bT in the BC-tree. cT is 0 if bT is the root block.
afteris the adjacency entry of the cut vertex, after which bT has to be inserted.
int ogdf::EmbedderMinDepthMaxFace::md_bottomUpTraversal ( const node bT,
const node cH 
)
private

Bottom-up-traversal of bcTree computing the values m_{cT, bT} for all edges (cT, bT) in the BC-tree. The length of each vertex \(v \neq c in \a bT\) is set to 1 if \(v \in M_{bT}\) and to 0 otherwise.

Parameters
bTis a block vertex in the BC-tree.
cHis a vertex in the original graph G.
Returns
Minimum depth of an embedding of bT with cH on the external face.
void ogdf::EmbedderMinDepthMaxFace::md_topDownTraversal ( const node bT)
private

Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to 1 if it is in M2 with m2 = \(\max_{v \in V_B, v != c} m_B(v)\) and M2 = \({c \in V_B \ {v} | m_B(c) = m2}\).

Parameters
bTis a block vertex in the BC-tree.
int ogdf::EmbedderMinDepthMaxFace::mf_constraintMaxFace ( const node bT,
const node cH 
)
private

Bottom up traversal of BC-tree.

Parameters
bTis the BC-tree node treated in this function call.
cHis the block node which is related to the cut vertex which is parent of bT in BC-tree.
void ogdf::EmbedderMinDepthMaxFace::mf_maximumFaceRec ( const node bT,
node bT_opt,
int &  ell_opt 
)
private

Top down traversal of BC-tree.

Parameters
bTis the tree node treated in this function call.
bT_optis assigned a block node in BC-tree which contains a face which cann be expanded to a maximum face.
ell_optis the size of a maximum face.

Member Data Documentation

NodeArray< List<node> > ogdf::EmbedderMinDepthMaxFace::md_M2
private

M2 is empty, if |M_B| != 1, otherwise M_B = {cH} M2 = \({cH' \in V_B \ {v} | m_B(cH') = m2}\) with m2 = \(\max_{vH \in V_B, vH != cH} m_B(vH)\).

Definition at line 163 of file EmbedderMinDepthMaxFace.h.

NodeArray< List<node> > ogdf::EmbedderMinDepthMaxFace::md_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 158 of file EmbedderMinDepthMaxFace.h.

EdgeArray<int> ogdf::EmbedderMinDepthMaxFace::md_m_cB
private

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

Definition at line 154 of file EmbedderMinDepthMaxFace.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFace::md_minDepth
private

an array containing the minimum depth of each block

Definition at line 151 of file EmbedderMinDepthMaxFace.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFace::md_nodeLength
private

saving for each node in the block graph its length

Definition at line 148 of file EmbedderMinDepthMaxFace.h.

EdgeArray<MDMFLengthAttribute> ogdf::EmbedderMinDepthMaxFace::mdmf_edgeLength
private

is saving for each edge of the block graph its length

Definition at line 178 of file EmbedderMinDepthMaxFace.h.

NodeArray<MDMFLengthAttribute> ogdf::EmbedderMinDepthMaxFace::mdmf_nodeLength
private

is saving for each node of the block graph its length

Definition at line 175 of file EmbedderMinDepthMaxFace.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFace::mf_cstrLength
private

is saving for each node of the block graph its cstrLength

Definition at line 169 of file EmbedderMinDepthMaxFace.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFace::mf_maxFaceSize
private

an array containing the maximum face size of each block

Definition at line 172 of file EmbedderMinDepthMaxFace.h.

NodeArray<int> ogdf::EmbedderMinDepthMaxFace::mf_nodeLength
private

is saving for each node of the block graph its length

Definition at line 166 of file EmbedderMinDepthMaxFace.h.

NodeArray< List<adjEntry> > ogdf::EmbedderMinDepthMaxFace::newOrder
private

saves for every node of G the new adjacency list

Definition at line 181 of file EmbedderMinDepthMaxFace.h.

adjEntry* ogdf::EmbedderMinDepthMaxFace::pAdjExternal
private

an adjacency entry on the external face

Definition at line 145 of file EmbedderMinDepthMaxFace.h.

BCTree* ogdf::EmbedderMinDepthMaxFace::pBCTree
private

the BC-tree of G

Definition at line 142 of file EmbedderMinDepthMaxFace.h.

NodeArray<bool> ogdf::EmbedderMinDepthMaxFace::treeNodeTreated
private

treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.

Definition at line 185 of file EmbedderMinDepthMaxFace.h.


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