Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::EmbedderMinDepthMaxFace Class Reference

Embedding that minimizes block-nesting depth and maximizes the external face. More...

#include <ogdf/planarity/EmbedderMinDepthMaxFace.h>

+ Inheritance diagram for ogdf::EmbedderMinDepthMaxFace:

Public Member Functions

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

Protected Types

using MDMFLengthAttribute = embedder::MDMFLengthAttribute
 

Protected Member Functions

int 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.
 
int constraintMaxFace (const node &bT, const node &cH) override
 Bottom up traversal of BC-tree.
 
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.
 
virtual 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.
 
virtual void embedBlock (const node &bT, const node &cT, ListIterator< adjEntry > &after) override
 Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.
 
void maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt) override
 Top down traversal of BC-tree.
 
void topDownTraversal (const node &bT)
 Top-down-traversal of BC-tree.
 
- Protected Member Functions inherited from ogdf::EmbedderMaxFace
void computeBlockGraphs (const node &bT, const node &cH)
 Computes recursively the block graph for every block.
 
void computeNodeLength (node bT, std::function< int &(node)> setter)
 
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.
 
void forEachIngoingNeighbor (node v, std::function< void(node)> fun)
 Calls fun for every ingoing edge (w,v).
 
template<typename T >
void internalEmbedBlock (const node bT, const node cT, ListIterator< adjEntry > &after, Graph &blockGraph, NodeArray< T > &paramNodeLength, EdgeArray< T > &paramEdgeLength, NodeArray< node > &mapNodeToH, EdgeArray< edge > &mapEdgeToH, const node nodeInBlock)
 
void internalMaximumFaceRec (const node &bT, node &bT_opt, int &ell_opt, Graph &blockGraph, NodeArray< int > &paramNodeLength, StaticSPQRTree *spqrTree, std::function< node &(node)> getBENode, std::function< int &(node, node)> getCstrLength, std::function< int &(node, node)> getNodeLength, int *const maxFaceSizeToUpdate=nullptr)
 
- 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.
 
virtual adjEntry trivialInit (Graph &G)
 Initialization code for biconnected input. Returns an adjacency entry that lies on the external face.
 

Protected Attributes

EdgeArray< intcB
 an array saving the length for each edge in the BC-tree
 
EdgeArray< MDMFLengthAttributeedgeLength
 is saving for each edge of the block graph its length
 
NodeArray< List< node > > M2
 M2 is empty, if |M_B| != 1, otherwise M_B = {cH} M2 = {cH' in V_B \ {v} | m_B(cH') = m2} with m2 = max{m_B(vH) : vH in V_B, vH != cH}.
 
NodeArray< intmaxFaceSize
 an array containing the maximum face size of each block
 
NodeArray< List< node > > md_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} ).
 
NodeArray< intmd_nodeLength
 saving for each node in the block graph its length
 
NodeArray< MDMFLengthAttributemdmf_nodeLength
 is saving for each node of the block graph its length
 
NodeArray< intmf_cstrLength
 is saving for each node of the block graph its cstrLength
 
NodeArray< intmf_nodeLength
 is saving for each node of the block graph its length
 
NodeArray< intminDepth
 an array containing the minimum depth of each block
 
- Protected Attributes inherited from ogdf::EmbedderMaxFace
NodeArray< GraphblockG
 all blocks
 
NodeArray< NodeArray< int > > cstrLength
 is saving for each node in the block graphs its cstrLength
 
NodeArray< EdgeArray< edge > > eBlockEmbedding_to_eH
 a mapping of edges in blockG to the auxiliaryGraph of the BC-tree
 
NodeArray< EdgeArray< edge > > eH_to_eBlockEmbedding
 a mapping of edges in the auxiliaryGraph of the BC-tree to blockG
 
NodeArray< NodeArray< node > > nBlockEmbedding_to_nH
 a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree
 
NodeArray< List< adjEntry > > newOrder
 saves for every node of PG the new adjacency list
 
NodeArray< NodeArray< node > > nH_to_nBlockEmbedding
 a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG
 
NodeArray< NodeArray< int > > nodeLength
 saving for each node in the block graphs its length
 
NodeArray< StaticSPQRTree * > spqrTrees
 The SPQR-trees of the blocks.
 
NodeArray< booltreeNodeTreated
 treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.
 
- Protected Attributes inherited from ogdf::embedder::EmbedderBCTreeBase< false >
adjEntrypAdjExternal
 an adjacency entry on the external face
 
BCTreepBCTree
 BC-tree of the original graph.
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit).
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum class  ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , 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.
 

Detailed Description

Embedding that minimizes block-nesting depth and maximizes the 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 46 of file EmbedderMinDepthMaxFace.h.

Member Typedef Documentation

◆ MDMFLengthAttribute

Member Function Documentation

◆ bottomUpTraversal()

int ogdf::EmbedderMinDepthMaxFace::bottomUpTraversal ( const node bT,
const node cH 
)
protected

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 != c in 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.

◆ constraintMaxFace()

int ogdf::EmbedderMinDepthMaxFace::constraintMaxFace ( const node bT,
const node cH 
)
overrideprotectedvirtual

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.

Reimplemented from ogdf::EmbedderMaxFace.

◆ doCall()

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

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.

Reimplemented from ogdf::EmbedderMaxFace.

◆ embedBlock() [1/3]

void ogdf::EmbedderMaxFace::embedBlock ( const node bT)
protected

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.

◆ embedBlock() [2/3]

virtual void ogdf::EmbedderMaxFace::embedBlock ( const node bT,
const node cT,
ListIterator< adjEntry > &  after 
)
protectedvirtual

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.

Reimplemented from ogdf::EmbedderMaxFace.

Reimplemented in ogdf::EmbedderMinDepthMaxFaceLayers.

◆ embedBlock() [3/3]

virtual void ogdf::EmbedderMinDepthMaxFace::embedBlock ( const node bT,
const node cT,
ListIterator< adjEntry > &  after 
)
overrideprotectedvirtual

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.

Reimplemented from ogdf::EmbedderMaxFace.

Reimplemented in ogdf::EmbedderMinDepthMaxFaceLayers.

◆ maximumFaceRec()

void ogdf::EmbedderMinDepthMaxFace::maximumFaceRec ( const node bT,
node bT_opt,
int ell_opt 
)
overrideprotectedvirtual

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.

Reimplemented from ogdf::EmbedderMaxFace.

◆ topDownTraversal()

void ogdf::EmbedderMinDepthMaxFace::topDownTraversal ( const node bT)
protected

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{m_B(v) : v in V_B, v != c} and M2 = {c in V_B \ {v} | m_B(c) = m2}.

Parameters
bTis a block vertex in the BC-tree.

Member Data Documentation

◆ cB

EdgeArray<int> ogdf::EmbedderMinDepthMaxFace::cB
protected

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

Definition at line 98 of file EmbedderMinDepthMaxFace.h.

◆ edgeLength

EdgeArray<MDMFLengthAttribute> ogdf::EmbedderMinDepthMaxFace::edgeLength
protected

is saving for each edge of the block graph its length

Definition at line 122 of file EmbedderMinDepthMaxFace.h.

◆ M2

NodeArray<List<node> > ogdf::EmbedderMinDepthMaxFace::M2
protected

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

Definition at line 107 of file EmbedderMinDepthMaxFace.h.

◆ maxFaceSize

NodeArray<int> ogdf::EmbedderMinDepthMaxFace::maxFaceSize
protected

an array containing the maximum face size of each block

Definition at line 116 of file EmbedderMinDepthMaxFace.h.

◆ md_M_B

NodeArray<List<node> > ogdf::EmbedderMinDepthMaxFace::md_M_B
protected

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 102 of file EmbedderMinDepthMaxFace.h.

◆ md_nodeLength

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

saving for each node in the block graph its length

Definition at line 92 of file EmbedderMinDepthMaxFace.h.

◆ mdmf_nodeLength

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

is saving for each node of the block graph its length

Definition at line 119 of file EmbedderMinDepthMaxFace.h.

◆ mf_cstrLength

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

is saving for each node of the block graph its cstrLength

Definition at line 113 of file EmbedderMinDepthMaxFace.h.

◆ mf_nodeLength

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

is saving for each node of the block graph its length

Definition at line 110 of file EmbedderMinDepthMaxFace.h.

◆ minDepth

NodeArray<int> ogdf::EmbedderMinDepthMaxFace::minDepth
protected

an array containing the minimum depth of each block

Definition at line 95 of file EmbedderMinDepthMaxFace.h.


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