Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
EmbedderBCTreeBase.h
Go to the documentation of this file.
1
32#pragma once
33
38
39namespace ogdf {
40namespace embedder {
41
43template<bool EnableLayers, bool IsEmbedderMinDepth = false>
45 using BicompEmbedder = typename std::conditional<EnableLayers,
47
48protected:
50 BCTree* pBCTree = nullptr;
51
53 adjEntry* pAdjExternal = nullptr;
54
60 adjEntry m_adjExternal;
61 BicompEmbedder::embed(G, m_adjExternal, m_nodeLength, m_edgeLength);
62
63 return m_adjExternal->twin();
64 }
65
69 node result = nullptr;
70
71 // HINT: Edges are directed from child to parent in BC-trees
72 pBCTree = new BCTree(G);
73
74 // base case of biconnected graph
75 if (pBCTree->bcTree().numberOfNodes() == 1) {
76 *pAdjExternal = trivialInit(G);
77 delete pBCTree;
78 } else {
79 // Find root Block (only node with out-degree of 0):
80 for (node v : pBCTree->bcTree().nodes) {
81 if (v->outdeg() == 0) {
82 result = v;
83 break;
84 }
85 }
86
87 OGDF_ASSERT(result != nullptr);
88 }
89
90 return result;
91 }
92};
93
94}
95}
Declaration of class BCTree.
Declares ogdf::EmbedderMaxFaceBiconnectedGraphs.
Computes an embedding of a biconnected graph with maximum external face.
Defines ogdf::EmbedderModule.
Class for adjacency list elements.
Definition Graph_d.h:79
Static BC-trees.
Definition BCTree.h:55
const Graph & bcTree() const
Returns the BC-tree graph.
Definition BCTree.h:419
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Embedder that maximizing the external face.
Embedder that maximizes the external face (plus layers approach).
Base class for embedder algorithms.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition Graph_d.h:622
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
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.
virtual adjEntry trivialInit(Graph &G)
Initialization code for biconnected input. Returns an adjacency entry that lies on the external face.
node initBCTree(Graph &G)
Initializes pBCTree and returns the root node of this tree or nullptr if G is biconnected.
typename std::conditional< EnableLayers, EmbedderMaxFaceBiconnectedGraphsLayers< int >, EmbedderMaxFaceBiconnectedGraphs< int > >::type BicompEmbedder
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.