Embedder that maximizes the external face. More...
#include <ogdf/planarity/EmbedderMaxFace.h>
Public Member Functions | |
EmbedderMaxFace ()=default | |
EmbedderMaxFace (const EmbedderMaxFace ©)=delete | |
virtual void | doCall (Graph &G, adjEntry &adjExternal) override |
Computes an embedding of G with maximum external face. More... | |
EmbedderMaxFace & | operator= (const EmbedderMaxFace ©)=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... | |
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... | |
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 > ¶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) |
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 | |
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... | |
Protected Attributes inherited from ogdf::embedder::EmbedderBCTreeBase< false > | |
adjEntry * | pAdjExternal |
an adjacency entry on the external face More... | |
BCTree * | pBCTree |
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... | |
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.
|
default |
|
delete |
Computes recursively the block graph for every block.
bT | is a block node in the BC-tree. |
cH | is a node of bT in the block graph. |
|
inlineprotected |
Definition at line 71 of file EmbedderMaxFace.h.
|
protectedvirtual |
Bottom up traversal of BC-tree.
bT | is the BC-tree node treated in this function call. |
cH | is the block node which is related to the cut vertex which is parent of bT in BC-tree. |
Reimplemented in ogdf::EmbedderMinDepthMaxFace.
Computes an embedding of G
with maximum external face.
G | is the original graph. Its adjacency list has to be changed by the embedder. |
adjExternal | is assigned an adjacency entry on the external face and has to be set by the embedder. |
Implements ogdf::EmbedderModule.
Reimplemented in ogdf::EmbedderMinDepthMaxFace.
|
protected |
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. |
|
protectedvirtual |
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 in ogdf::EmbedderMinDepthMaxFace, ogdf::EmbedderMinDepthMaxFaceLayers, and ogdf::EmbedderMaxFaceLayers.
|
inlineprotected |
Calls fun
for every ingoing edge (w,v
).
Definition at line 63 of file EmbedderMaxFace.h.
|
inlineprotected |
Definition at line 148 of file EmbedderMaxFace.h.
|
inlineprotected |
Definition at line 86 of file EmbedderMaxFace.h.
|
protectedvirtual |
Top down traversal of BC-tree.
bT | is the tree node treated in this function call. |
bT_opt | is assigned a block node in BC-tree which contains a face which cann be expanded to a maximum face. |
ell_opt | is the size of a maximum face. |
Reimplemented in ogdf::EmbedderMinDepthMaxFace.
|
delete |
|
protected |
all blocks
Definition at line 296 of file EmbedderMaxFace.h.
is saving for each node in the block graphs its cstrLength
Definition at line 314 of file EmbedderMaxFace.h.
a mapping of edges in blockG to the auxiliaryGraph of the BC-tree
Definition at line 308 of file EmbedderMaxFace.h.
a mapping of edges in the auxiliaryGraph of the BC-tree to blockG
Definition at line 302 of file EmbedderMaxFace.h.
a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree
Definition at line 305 of file EmbedderMaxFace.h.
saves for every node of PG the new adjacency list
Definition at line 317 of file EmbedderMaxFace.h.
a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG
Definition at line 299 of file EmbedderMaxFace.h.
saving for each node in the block graphs its length
Definition at line 311 of file EmbedderMaxFace.h.
|
protected |
The SPQR-trees of the blocks.
Definition at line 324 of file EmbedderMaxFace.h.
|
protected |
treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.
Definition at line 321 of file EmbedderMaxFace.h.