# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::EmbedderMaxFaceLayers Class Reference

Embedder that maximizes the external face and optimizes the position of blocks afterwards. More...

#include <ogdf/planarity/EmbedderMaxFaceLayers.h>

Inheritance diagram for ogdf::EmbedderMaxFaceLayers:

## 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.

Initialization code for biconnected input. Returns an adjacency entry that lies on the external face.

Protected Member Functions inherited from ogdf::embedder::LayersBlockEmbedder< EmbedderMaxFace, int >
void internalEmbedBlock (Graph &SG, NodeArray< int > &nodeLengthSG, EdgeArray< int > &edgeLengthSG, NodeArray< node > &nSG_to_nG, EdgeArray< edge > &eSG_to_eG, node nodeInBlockSG, node cT, ListIterator< adjEntry > &after)

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)

virtual int constraintMaxFace (const node &bT, const node &cH)
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.

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)

virtual void maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt)
Top down traversal of BC-tree.

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.

Public Types inherited from ogdf::Module
enum class  ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error }
The return type of a module. More...

Public Member Functions inherited from ogdf::EmbedderMaxFace
Computes an embedding of G with maximum external face.

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

virtual ~EmbedderModule ()

Calls the embedder algorithm for graph G.

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.

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.

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

## Detailed Description

Embedder that maximizes the external face and optimizes the position of blocks afterwards.

After computing an embedding just as ogdf::EmbedderMaxFace 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 51 of file EmbedderMaxFaceLayers.h.

## ◆ embedBlock()

 void ogdf::EmbedderMaxFaceLayers::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
 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::EmbedderMaxFace.

## ◆ trivialInit()

 adjEntry ogdf::EmbedderMaxFaceLayers::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 55 of file EmbedderMaxFaceLayers.h.

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