Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::EmbedderMinDepthMaxFaceLayers Class Reference

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>

+ Inheritance diagram for ogdf::EmbedderMinDepthMaxFaceLayers:

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...
 
- Protected Member Functions inherited from ogdf::embedder::LayersBlockEmbedder< EmbedderMinDepthMaxFace, embedder::MDMFLengthAttribute >
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)
 
- Protected Member Functions inherited from ogdf::EmbedderMinDepthMaxFace
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...
 
- Protected Member Functions inherited from ogdf::EmbedderMaxFace
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 > &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. 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

- 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...
 
- Public Member Functions inherited from ogdf::EmbedderMinDepthMaxFace
virtual void doCall (Graph &G, adjEntry &adjExternal) override
 Call embedder algorithm. More...
 
- Public Member Functions inherited from ogdf::EmbedderMaxFace
 EmbedderMaxFace ()=default
 
 EmbedderMaxFace (const EmbedderMaxFace &copy)=delete
 
EmbedderMaxFaceoperator= (const EmbedderMaxFace &copy)=delete
 
- 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...
 
Timeouteroperator= (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 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 Types inherited from ogdf::EmbedderMinDepthMaxFace
using MDMFLengthAttribute = embedder::MDMFLengthAttribute
 
- Protected Attributes inherited from ogdf::EmbedderMinDepthMaxFace
EdgeArray< int > cB
 an array saving the length for each edge in the BC-tree More...
 
EdgeArray< MDMFLengthAttributeedgeLength
 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< MDMFLengthAttributemdmf_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...
 
- Protected Attributes inherited from ogdf::EmbedderMaxFace
NodeArrayP< GraphblockG
 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...
 
- Protected Attributes inherited from ogdf::embedder::EmbedderBCTreeBase< false >
adjEntrypAdjExternal
 an adjacency entry on the external face More...
 
BCTreepBCTree
 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

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 52 of file EmbedderMinDepthMaxFaceLayers.h.

Member Function Documentation

◆ embedBlock()

void ogdf::EmbedderMinDepthMaxFaceLayers::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::EmbedderMinDepthMaxFace.


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