# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
EmbedderMinDepth.h
Go to the documentation of this file.
1
32#pragma once
33
37
38namespace ogdf {
39
41
48public:
55 virtual void doCall(Graph& G, adjEntry& adjExternal) override;
56
57private:
64 void computeBlockGraphs(const node& bT, const node& cH);
65
76 int bottomUpTraversal(const node& bT, const node& cH);
77
89 void topDownTraversal(const node& bT);
90
97 void embedBlock(const node& bT);
98
109 void embedBlock(const node& bT, const node& cT, ListIterator<adjEntry>& after);
110
111private:
114
117
120
123
126
129
132
135
141
148
151
155
158};
159
160}
Definition of ogdf::EmbedderBCTreeBase.
Declares ogdf::EmbedderMaxFaceBiconnectedGraphs.
Declaration of class StaticSPQRTree.
Class for adjacency list elements.
Definition Graph_d.h:79
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Embedder that minimizes block-nesting depth.
EdgeArray< int > m_cB
an array saving the length for each edge in the BC-tree
void embedBlock(const node &bT)
Computes the adjacency list for all nodes in a block and calls recursively the function for all block...
NodeArray< NodeArray< int > > nodeLength
saving for each node in the block graphs its length
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 block...
NodeArray< EdgeArray< edge > > eH_to_eBlockEmbedding
a mapping of edges in the auxiliaryGraph of the BC-tree to blockG
NodeArray< NodeArray< node > > nH_to_nBlockEmbedding
a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG
virtual void doCall(Graph &G, adjEntry &adjExternal) override
Computes an embedding of G with minimum depth.
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.
void computeBlockGraphs(const node &bT, const node &cH)
Computes recursively the block graph for every block.
NodeArray< List< adjEntry > > newOrder
saves for every node of G the new adjacency list
NodeArray< bool > treeNodeTreated
treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.
NodeArray< EdgeArray< edge > > eBlockEmbedding_to_eH
a mapping of edges in blockG to the auxiliaryGraph of the BC-tree
NodeArray< Graph > blockG
all blocks
void topDownTraversal(const node &bT)
Top-down-traversal of BC-tree.
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 = ma...
NodeArray< StaticSPQRTree * > spqrTrees
The SPQR-trees of the blocks.
NodeArray< int > minDepth
an array containing the minimum depth of each block
NodeArray< List< node > > 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,...
NodeArray< NodeArray< node > > nBlockEmbedding_to_nH
a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Encapsulates a pointer to a list element.
Definition List.h:103
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Common base for embedder algorithms based on BC trees.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.