Planar graph embedding that minimizes block-nesting depth and maximizes the external face and optimizes the position of blocks afterwards. More...
#include <ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h>
Protected Member Functions | |
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. More... | |
![]() | |
void | internalEmbedBlock (Graph &SG, NodeArray< embedder::MDMFLengthAttribute > &nodeLengthSG, EdgeArray< embedder::MDMFLengthAttribute > &edgeLengthSG, NodeArray< node > &nSG_to_nG, EdgeArray< edge > &eSG_to_eG, node nodeInBlockSG, node cT, ListIterator< adjEntry > &after) |
![]() | |
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. More... | |
int | constraintMaxFace (const node &bT, const node &cH) override |
Bottom up traversal of BC-tree. More... | |
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... | |
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. More... | |
void | maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt) override |
Top down traversal of BC-tree. More... | |
void | topDownTraversal (const node &bT) |
Top-down-traversal of BC-tree. More... | |
![]() | |
void | computeBlockGraphs (const node &bT, const node &cH) |
Computes recursively the block graph for every block. More... | |
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. More... | |
void | forEachIngoingNeighbor (node v, std::function< void(node)> fun) |
Calls fun for every ingoing edge (w,v ). More... | |
template<typename T > | |
void | internalEmbedBlock (const node bT, const node cT, ListIterator< adjEntry > &after, Graph &blockGraph, NodeArray< T > ¶mNodeLength, EdgeArray< T > ¶mEdgeLength, NodeArray< node > &mapNodeToH, EdgeArray< edge > &mapEdgeToH, const node nodeInBlock) |
void | internalMaximumFaceRec (const node &bT, node &bT_opt, int &ell_opt, Graph &blockGraph, NodeArray< int > ¶mNodeLength, StaticSPQRTree *spqrTree, std::function< node &(node)> getBENode, std::function< int &(node, node)> getCstrLength, std::function< int &(node, node)> getNodeLength, int *const maxFaceSizeToUpdate=nullptr) |
![]() | |
node | initBCTree (Graph &G) |
Initializes pBCTree and returns the root node of this tree or nullptr if G is biconnected. More... | |
virtual adjEntry | trivialInit (Graph &G) |
Initialization code for biconnected input. Returns an adjacency entry that lies on the external face. More... | |
Additional Inherited Members | |
![]() | |
enum | ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error } |
The return type of a module. More... | |
![]() | |
virtual void | doCall (Graph &G, adjEntry &adjExternal) override |
Call embedder algorithm. More... | |
![]() | |
EmbedderMaxFace ()=default | |
EmbedderMaxFace (const EmbedderMaxFace ©)=delete | |
EmbedderMaxFace & | operator= (const EmbedderMaxFace ©)=delete |
![]() | |
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... | |
![]() | |
Module () | |
Initializes a module. More... | |
virtual | ~Module () |
![]() | |
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... | |
![]() | |
static bool | isSolution (ReturnType ret) |
Returns true iff ret indicates that the module returned a feasible solution. More... | |
![]() | |
using | MDMFLengthAttribute = embedder::MDMFLengthAttribute |
![]() | |
EdgeArray< int > | cB |
an array saving the length for each edge in the BC-tree More... | |
EdgeArray< MDMFLengthAttribute > | edgeLength |
is saving for each edge of the block graph its length More... | |
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}. More... | |
NodeArray< int > | maxFaceSize |
an array containing the maximum face size of each block More... | |
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} ). More... | |
NodeArray< int > | md_nodeLength |
saving for each node in the block graph its length More... | |
NodeArray< MDMFLengthAttribute > | mdmf_nodeLength |
is saving for each node of the block graph its length More... | |
NodeArray< int > | mf_cstrLength |
is saving for each node of the block graph its cstrLength More... | |
NodeArray< int > | mf_nodeLength |
is saving for each node of the block graph its length More... | |
NodeArray< int > | minDepth |
an array containing the minimum depth of each block More... | |
![]() | |
NodeArrayP< Graph > | blockG |
all blocks More... | |
NodeArray< NodeArray< int > > | cstrLength |
is saving for each node in the block graphs its cstrLength More... | |
NodeArray< EdgeArray< edge > > | eBlockEmbedding_to_eH |
a mapping of edges in blockG to the auxiliaryGraph of the BC-tree More... | |
NodeArray< EdgeArray< edge > > | eH_to_eBlockEmbedding |
a mapping of edges in the auxiliaryGraph of the BC-tree to blockG More... | |
NodeArray< NodeArray< node > > | nBlockEmbedding_to_nH |
a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree More... | |
NodeArray< List< adjEntry > > | newOrder |
saves for every node of PG the new adjacency list More... | |
NodeArray< NodeArray< node > > | nH_to_nBlockEmbedding |
a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG More... | |
NodeArray< NodeArray< int > > | nodeLength |
saving for each node in the block graphs its length More... | |
NodeArray< StaticSPQRTree * > | spqrTrees |
The SPQR-trees of the blocks. More... | |
NodeArray< bool > | treeNodeTreated |
treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not. More... | |
![]() | |
adjEntry * | pAdjExternal |
an adjacency entry on the external face More... | |
BCTree * | pBCTree |
BC-tree of the original graph. More... | |
![]() | |
double | m_timeLimit |
Time limit for module calls (< 0 means no limit). More... | |
Planar graph embedding that minimizes block-nesting depth and maximizes the external face and optimizes the position of blocks afterwards.
After computing an embedding just as ogdf::EmbedderMinDepthMaxFace does, blocks are placed in faces that are closest to the external one.
See the paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) and diploma thesis "Algorithmen zur Bestimmung von guten Graph-Einbettungen für orthogonale Zeichnungen" (in German) by Thorsten Kerkhof (2007) for details.
Definition at line 56 of file EmbedderMinDepthMaxFaceLayers.h.
|
overrideprotectedvirtual |
Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.
bT | is the tree node treated in this function call. |
cT | is the parent cut vertex node of bT in the BC-tree. cT is 0 if bT is the root block. |
after | is the adjacency entry of the cut vertex, after which bT has to be inserted. |
Reimplemented from ogdf::EmbedderMinDepthMaxFace.