|
|||
|
|
|
|||
|
|
Planar graph embedding with minimum block-nesting depth. More...
#include <ogdf/planarity/EmbedderMinDepth.h>
Inheritance diagram for ogdf::EmbedderMinDepth:Public Member Functions | |
| EmbedderMinDepth () | |
| void | call (Graph &G, adjEntry &adjExternal) |
| Computes an embedding of G with minimum depth. | |
| Public Member Functions inherited from ogdf::EmbedderModule | |
| EmbedderModule () | |
| Initializes an embedder module. | |
| virtual | ~EmbedderModule () |
| void | operator() (Graph &G, adjEntry &adjExternal) |
| Calls the embedder algorithm for planarized representation PG. | |
| 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 (double t) | |
| timeout is set to the given value (seconds) | |
| Timeouter (bool t) | |
| timeout is turned off (false) or on (true) (with 0 second) | |
| Timeouter (const Timeouter &t) | |
| ~Timeouter () | |
| bool | isTimeLimit () const |
| returns whether any time limit is set or not | |
| void | timeLimit (double t) |
| sets the time limit for the call (in seconds); <0 means no limit. | |
| void | timeLimit (bool t) |
| shorthand to turn timelimit off or on (with 0 seconds) | |
| double | timeLimit () const |
| returns the current time limit for the call | |
Private Member Functions | |
| 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. The length of each vertex \(v \neq c in \a bT\) is set to 1 if \(v \in M_{bT}\) and to 0 otherwise. | |
| void | computeBlockGraphs (const node &bT, const node &cH) |
| Computes recursively the block graph for every block. | |
| 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 | 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. | |
| void | topDownTraversal (const node &bT) |
| Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to 1 if it is in M2 with m2 = \(\max_{v \in V_B, v != c} m_B(v)\) and M2 = \({c \in V_B \ {v} | m_B(c) = m2}\). | |
Private Attributes | |
| NodeArray< Graph > | blockG |
| NodeArray< EdgeArray< edge > > | eBlockEmbedding_to_eH |
| NodeArray< EdgeArray< edge > > | eH_to_eBlockEmbedding |
| NodeArray< List< node > > | M2 |
| NodeArray< List< node > > | M_B |
| EdgeArray< int > | m_cB |
| NodeArray< int > | minDepth |
| NodeArray< NodeArray< node > > | nBlockEmbedding_to_nH |
| NodeArray< List< adjEntry > > | newOrder |
| NodeArray< NodeArray< node > > | nH_to_nBlockEmbedding |
| NodeArray< NodeArray< int > > | nodeLength |
| adjEntry * | pAdjExternal |
| BCTree * | pBCTree |
| NodeArray< StaticSPQRTree * > | spqrTrees |
| NodeArray< bool > | treeNodeTreated |
Planar graph embedding with minimum block-nesting depth.
See paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) for details.
Definition at line 61 of file EmbedderMinDepth.h.
|
inline |
Definition at line 65 of file EmbedderMinDepth.h.
Bottom-up-traversal of bcTree computing the values m_{cT, bT} for all edges (cT, bT) in the BC-tree. The length of each vertex \(v \neq c in \a bT\) is set to 1 if \(v \in M_{bT}\) and to 0 otherwise.
| bT | is a block vertex in the BC-tree. |
| cH | is a vertex in the original graph G. |
Computes an embedding of G with minimum depth.
| G | is the original graph. |
| adjExternal | is assigned an adjacency entry in the external face. |
Implements ogdf::EmbedderModule.
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. |
|
private |
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. |
|
private |
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. |
|
private |
Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to 1 if it is in M2 with m2 = \(\max_{v \in V_B, v != c} m_B(v)\) and M2 = \({c \in V_B \ {v} | m_B(c) = m2}\).
| bT | is a block vertex in the BC-tree. |
all blocks
Definition at line 137 of file EmbedderMinDepth.h.
a mapping of edges in blockG to the auxiliaryGraph of the BC-tree
Definition at line 149 of file EmbedderMinDepth.h.
a mapping of edges in the auxiliaryGraph of the BC-tree to blockG
Definition at line 143 of file EmbedderMinDepth.h.
M2 is empty, if |M_B| != 1, otherwise M_B = {cH} M2 = \({cH' \in V_B \ {v} | m_B(cH') = m2}\) with m2 = \(\max_{vH \in V_B, vH != cH} m_B(vH)\).
Definition at line 171 of file EmbedderMinDepth.h.
M_B = \({cH \in B | m_B(cH) = m_B}\) with m_B = \(\max_{c \in B} m_B(c)\) and m_B(c) = \(\max {0} \cup {m_{c, B'} | c \in B', B' \neq B}\).
Definition at line 164 of file EmbedderMinDepth.h.
|
private |
an array saving the length for each edge in the BC-tree
Definition at line 158 of file EmbedderMinDepth.h.
|
private |
an array containing the minimum depth of each block
Definition at line 155 of file EmbedderMinDepth.h.
a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree
Definition at line 146 of file EmbedderMinDepth.h.
saves for every node of G the new adjacency list
Definition at line 174 of file EmbedderMinDepth.h.
a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG
Definition at line 140 of file EmbedderMinDepth.h.
saving for each node in the block graphs its length
Definition at line 152 of file EmbedderMinDepth.h.
|
private |
an adjacency entry on the external face
Definition at line 134 of file EmbedderMinDepth.h.
|
private |
BC-tree of the original graph
Definition at line 131 of file EmbedderMinDepth.h.
|
private |
The SPQR-trees of the blocks
Definition at line 181 of file EmbedderMinDepth.h.
|
private |
treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.
Definition at line 178 of file EmbedderMinDepth.h.
