Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

Embedder that maximizes the external face. More...

#include <ogdf/planarity/EmbedderMaxFace.h>

+ Inheritance diagram for ogdf::EmbedderMaxFace:

Public Member Functions

virtual void doCall (Graph &G, adjEntry &adjExternal) override
 Computes an embedding of G with maximum external face. More...
 
- 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...
 

Protected Member Functions

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)
 
virtual int constraintMaxFace (const node &bT, const node &cH)
 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 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)
 
virtual void maximumFaceRec (const node &bT, node &bT_opt, int &ell_opt)
 Top down traversal of BC-tree. More...
 
- 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...
 

Protected Attributes

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

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

Detailed Description

Embedder that 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 47 of file EmbedderMaxFace.h.

Member Function Documentation

◆ computeBlockGraphs()

void ogdf::EmbedderMaxFace::computeBlockGraphs ( const node bT,
const node cH 
)
protected

Computes recursively the block graph for every block.

Parameters
bTis a block node in the BC-tree.
cHis a node of bT in the block graph.

◆ computeNodeLength()

void ogdf::EmbedderMaxFace::computeNodeLength ( node  bT,
std::function< int &(node)>  setter 
)
inlineprotected

Definition at line 67 of file EmbedderMaxFace.h.

◆ constraintMaxFace()

virtual int ogdf::EmbedderMaxFace::constraintMaxFace ( const node bT,
const node cH 
)
protectedvirtual

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

◆ doCall()

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

Computes an embedding of G with maximum external face.

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

Implements ogdf::EmbedderModule.

Reimplemented in ogdf::EmbedderMinDepthMaxFace.

◆ embedBlock() [1/2]

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/2]

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 in ogdf::EmbedderMinDepthMaxFace, ogdf::EmbedderMinDepthMaxFaceLayers, and ogdf::EmbedderMaxFaceLayers.

◆ forEachIngoingNeighbor()

void ogdf::EmbedderMaxFace::forEachIngoingNeighbor ( node  v,
std::function< void(node)>  fun 
)
inlineprotected

Calls fun for every ingoing edge (w,v).

Definition at line 59 of file EmbedderMaxFace.h.

◆ internalEmbedBlock()

template<typename T >
void ogdf::EmbedderMaxFace::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 
)
inlineprotected

Definition at line 158 of file EmbedderMaxFace.h.

◆ internalMaximumFaceRec()

void ogdf::EmbedderMaxFace::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 
)
inlineprotected

Definition at line 82 of file EmbedderMaxFace.h.

◆ maximumFaceRec()

virtual void ogdf::EmbedderMaxFace::maximumFaceRec ( const node bT,
node bT_opt,
int &  ell_opt 
)
protectedvirtual

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

Member Data Documentation

◆ blockG

NodeArray<Graph> ogdf::EmbedderMaxFace::blockG
protected

all blocks

Definition at line 311 of file EmbedderMaxFace.h.

◆ cstrLength

NodeArray< NodeArray<int> > ogdf::EmbedderMaxFace::cstrLength
protected

is saving for each node in the block graphs its cstrLength

Definition at line 329 of file EmbedderMaxFace.h.

◆ eBlockEmbedding_to_eH

NodeArray< EdgeArray<edge> > ogdf::EmbedderMaxFace::eBlockEmbedding_to_eH
protected

a mapping of edges in blockG to the auxiliaryGraph of the BC-tree

Definition at line 323 of file EmbedderMaxFace.h.

◆ eH_to_eBlockEmbedding

NodeArray< EdgeArray<edge> > ogdf::EmbedderMaxFace::eH_to_eBlockEmbedding
protected

a mapping of edges in the auxiliaryGraph of the BC-tree to blockG

Definition at line 317 of file EmbedderMaxFace.h.

◆ nBlockEmbedding_to_nH

NodeArray< NodeArray<node> > ogdf::EmbedderMaxFace::nBlockEmbedding_to_nH
protected

a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree

Definition at line 320 of file EmbedderMaxFace.h.

◆ newOrder

NodeArray< List<adjEntry> > ogdf::EmbedderMaxFace::newOrder
protected

saves for every node of PG the new adjacency list

Definition at line 332 of file EmbedderMaxFace.h.

◆ nH_to_nBlockEmbedding

NodeArray< NodeArray<node> > ogdf::EmbedderMaxFace::nH_to_nBlockEmbedding
protected

a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG

Definition at line 314 of file EmbedderMaxFace.h.

◆ nodeLength

NodeArray< NodeArray<int> > ogdf::EmbedderMaxFace::nodeLength
protected

saving for each node in the block graphs its length

Definition at line 326 of file EmbedderMaxFace.h.

◆ spqrTrees

NodeArray<StaticSPQRTree*> ogdf::EmbedderMaxFace::spqrTrees
protected

The SPQR-trees of the blocks.

Definition at line 339 of file EmbedderMaxFace.h.

◆ treeNodeTreated

NodeArray<bool> ogdf::EmbedderMaxFace::treeNodeTreated
protected

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

Definition at line 336 of file EmbedderMaxFace.h.


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