Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
EmbedderMaxFace.h
Go to the documentation of this file.
1
32#pragma once
33
37
38namespace ogdf {
39
41
48public:
54 virtual void doCall(Graph& G, adjEntry& adjExternal) override;
55
56protected:
58 void forEachIngoingNeighbor(node v, std::function<void(node)> fun) {
59 for (adjEntry adj : v->adjEntries) {
60 if (adj->theEdge()->target() == v) {
61 fun(adj->twinNode());
62 }
63 }
64 }
65
66 void computeNodeLength(node bT, std::function<int&(node)> setter) {
67 forEachIngoingNeighbor(bT, [&](node vT) {
68 node vH = pBCTree->cutVertex(vT, bT);
69 int length_v_in_block = 0;
70
71 // set length of vertex v in block graph of bT:
72 forEachIngoingNeighbor(vT, [&](node bT2) {
73 node cutVertex = pBCTree->cutVertex(vT, bT2);
74 length_v_in_block += constraintMaxFace(bT2, cutVertex);
75 });
76
78 });
79 }
80
83 std::function<node&(node)> getBENode, std::function<int&(node, node)> getCstrLength,
84 std::function<int&(node, node)> getNodeLength, int* const maxFaceSizeToUpdate = nullptr) {
88
91
92 if (maxFaceSizeToUpdate != nullptr) {
94 }
95
96 forEachIngoingNeighbor(bT, [&](node cT) {
97 node cH = pBCTree->cutVertex(cT, bT);
98
100
101 if (maxFaceSizeToUpdate == nullptr) {
103 }
104
109
110 int L = 0;
111
112 // L := \sum_{(B', c) \in bcTree} cstrLength(B', c)
113 forEachIngoingNeighbor(cT, [&](node bT2) {
114 // get partner vertex of c in the block graph of B'=e->target() and add cstrLength(B', c) to L:
115 L += getCstrLength(bT2, pBCTree->cutVertex(cT, bT2));
116 });
117
118 forEachIngoingNeighbor(cT, [&](node pT) {
119 if (pT != bT) {
120 // get partner vertex of c in the block graph of B'=e->source():
121 node partnerV = pBCTree->cutVertex(cT, pT);
123
124 // pBCTree->originalGraph().chooseNode() just to get rid of warning:
125 node thisbT_opt = pBCTree->originalGraph().chooseNode();
126 int thisell_opt = 0;
127 maximumFaceRec(pT, thisbT_opt, thisell_opt);
128
129 if (thisell_opt > tmp_ell_opt) {
132 }
133 }
134 });
135 });
136
137 // return (B*, \ell*):
140 }
141
142 template<typename T>
146 // 1. Compute embedding of block
147 adjEntry m_adjExternal = nullptr;
150
151 // 2. Copy block embedding into graph embedding and call recursively
152 // embedBlock for all cut vertices in bT
154 face f = CE.leftFace(m_adjExternal);
155
156 if (*pAdjExternal == nullptr) {
157 node on = pBCTree->original(mapNodeToH[m_adjExternal->theNode()]);
158
159 for (adjEntry ae : on->adjEntries) {
160 if (ae->theEdge() == pBCTree->original(mapEdgeToH[m_adjExternal->theEdge()])) {
161 *pAdjExternal = ae->twin();
162 break;
163 }
164 }
165 }
166
167 for (node nSG : blockGraph.nodes) {
169 node nG = pBCTree->original(nH);
170 adjEntry ae = nSG->firstAdj();
172 pBCTree->bcproper(nG) == cT ? &after : new ListIterator<adjEntry>;
173
174 if (pBCTree->typeOfGNode(nG) == BCTree::GNodeType::CutVertex) {
175 node cT2 = pBCTree->bcproper(nG);
176 OGDF_ASSERT(cT2 != nullptr);
177 bool doRecurse = true;
178
179 if (cT2 == cT) {
180 node parent_bT_of_cT2 = nullptr;
181
182 for (adjEntry adj : cT2->adjEntries) {
183 if (adj->theEdge()->source() == cT2) {
184 parent_bT_of_cT2 = adj->twinNode();
185 break;
186 }
187 }
188
189 OGDF_ASSERT(parent_bT_of_cT2 != nullptr);
190
191 if (treeNodeTreated[parent_bT_of_cT2]) {
192 doRecurse = false;
193 }
194 }
195
196 // (if exists) find adjacency entry of nSG which lies on external face f:
197 for (adjEntry aeFace : f->entries) {
198 if (aeFace->theNode() == nSG) {
199 ae = aeFace->succ() == nullptr ? nSG->firstAdj() : aeFace->succ();
200 break;
201 }
202 }
203
204 if (doRecurse) {
205 for (adjEntry adj : cT2->adjEntries) {
206 node bT2 = adj->theEdge()->opposite(cT2);
207
208 if (!treeNodeTreated[bT2]) {
209 embedBlock(bT2, cT2, *pAfter);
210 }
211 }
212 }
213 }
214
215 // embed all edges of block bT:
216 bool after_ae = true;
217 for (adjEntry aeNode = ae; after_ae || aeNode != ae;
218 aeNode = aeNode->succ() == nullptr ? nSG->firstAdj() : aeNode->succ()) {
219 edge e = pBCTree->original(mapEdgeToH[aeNode->theEdge()]);
220 if (nG == e->source()) {
221 if (pAfter->valid()) {
222 *pAfter = newOrder[nG].insertAfter(e->adjSource(), *pAfter);
223 } else {
224 *pAfter = newOrder[nG].pushBack(e->adjSource());
225 }
226 } else {
227 if (pAfter->valid()) {
228 *pAfter = newOrder[nG].insertAfter(e->adjTarget(), *pAfter);
229 } else {
230 *pAfter = newOrder[nG].pushBack(e->adjTarget());
231 }
232 }
233
234 after_ae &= aeNode->succ() != nullptr;
235 }
236
237 if (*pAfter != after) {
238 delete pAfter;
239 }
240 }
241 }
242
249 void computeBlockGraphs(const node& bT, const node& cH);
250
258 virtual int constraintMaxFace(const node& bT, const node& cH);
259
268 virtual void maximumFaceRec(const node& bT, node& bT_opt, int& ell_opt);
269
276 void embedBlock(const node& bT);
277
288 virtual void embedBlock(const node& bT, const node& cT, ListIterator<adjEntry>& after);
289
292
295
298
301
304
307
310
313
317
320};
321
322}
Definition of ogdf::EmbedderBCTreeBase.
Declares ogdf::EmbedderMaxFaceBiconnectedGraphs.
Declaration of class StaticSPQRTree.
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry succ() const
Returns the successor in the adjacency list.
Definition Graph_d.h:155
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
node theNode() const
Returns the node whose adjacency list contains this element.
Definition Graph_d.h:103
Combinatorial embeddings of planar graphs with modification functionality.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
void init()
Reinitializes the array. Associates the array with no graph.
Definition EdgeArray.h:292
Class for the representation of edges.
Definition Graph_d.h:300
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition Graph_d.h:344
edge succ() const
Returns the successor in the list of all edges.
Definition Graph_d.h:370
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition Graph_d.h:347
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Embedder that maximizing the external face.
Embedder that maximizes the external face.
void embedBlock(const node &bT)
Computes the adjacency list for all nodes in a block and calls recursively the function for all block...
void computeBlockGraphs(const node &bT, const node &cH)
Computes recursively the block graph for every block.
NodeArray< NodeArray< int > > nodeLength
saving for each node in the block graphs its length
NodeArray< NodeArray< int > > cstrLength
is saving for each node in the block graphs its cstrLength
void forEachIngoingNeighbor(node v, std::function< void(node)> fun)
Calls fun for every ingoing edge (w,v).
NodeArray< Graph > blockG
all blocks
virtual void maximumFaceRec(const node &bT, node &bT_opt, int &ell_opt)
Top down traversal of BC-tree.
NodeArray< NodeArray< node > > nBlockEmbedding_to_nH
a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree
NodeArray< EdgeArray< edge > > eBlockEmbedding_to_eH
a mapping of edges in blockG to the auxiliaryGraph of the BC-tree
NodeArray< bool > treeNodeTreated
treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.
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)
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
void computeNodeLength(node bT, std::function< int &(node)> setter)
virtual int constraintMaxFace(const node &bT, const node &cH)
Bottom up traversal of BC-tree.
NodeArray< List< adjEntry > > newOrder
saves for every node of PG the new adjacency list
virtual void doCall(Graph &G, adjEntry &adjExternal) override
Computes an embedding of G with maximum external face.
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 block...
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)
NodeArray< StaticSPQRTree * > spqrTrees
The SPQR-trees of the blocks.
Faces in a combinatorial embedding.
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
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
Linear-time implementation of static SPQR-trees.
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
#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.