?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / src / planarity / EmbedderMinDepthMaxFaceLayers.cpp
blob870808424d4f637251b257f564966c94a8c89b8e
1 /*
2 * $Revision: 2566 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-07 23:10:08 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Computes an embedding of a graph with minimum depth and
11 * maximum external face.
12 *
13 * See the paper "Graph Embedding with Minimum
14 * Depth and Maximum External Face" by C. Gutwenger and P. Mutzel
15 * (2004) for details.
16 * The algorithm for minimum depth and maximum external face is
17 * combined with the algorithm for maximum external layers which
18 * defines how to embed blocks into inner faces. See diploma thesis
19 * "Algorithmen zur Bestimmung von guten Graph-Einbettungen für
20 * orthogonale Zeichnungen" (in german) by Thorsten Kerkhof (2007)
21 * for details.
22 *
23 * \author Thorsten Kerkhof
24 *
25 * \par License:
26 * This file is part of the Open Graph Drawing Framework (OGDF).
27 *
28 * \par
29 * Copyright (C)<br>
30 * See README.txt in the root directory of the OGDF installation for details.
31 *
32 * \par
33 * This program is free software; you can redistribute it and/or
34 * modify it under the terms of the GNU General Public License
35 * Version 2 or 3 as published by the Free Software Foundation;
36 * see the file LICENSE.txt included in the packaging of this file
37 * for details.
38 *
39 * \par
40 * This program is distributed in the hope that it will be useful,
41 * but WITHOUT ANY WARRANTY; without even the implied warranty of
42 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
43 * GNU General Public License for more details.
44 *
45 * \par
46 * You should have received a copy of the GNU General Public
47 * License along with this program; if not, write to the Free
48 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
49 * Boston, MA 02110-1301, USA.
50 *
51 * \see http://www.gnu.org/copyleft/gpl.html
52 ***************************************************************/
53
54 #include <ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h>
55 #include <ogdf/internal/planarity/ConnectedSubgraph.h>
56 #include <ogdf/internal/planarity/EmbedderMaxFaceBiconnectedGraphsLayers.h>
57
58 namespace ogdf {
59
60 void EmbedderMinDepthMaxFaceLayers::call(Graph& G, adjEntry& adjExternal)
61 {
62 edge e;
63 node n;
64 int maxint = 0xFFFFFF;
65
66 adjExternal = 0;
67 pAdjExternal = &adjExternal;
68
69 //simple base cases:
70 if (G.numberOfNodes() <= 1)
71 return;
72 if (G.numberOfEdges() == 1)
73 {
74 edge e = G.firstEdge();
75 adjExternal = e->adjSource();
76 return;
77 }
78
79 //HINT: Edges are directed from child to parent in BC-trees
80 pBCTree = new BCTree(G);
81
82 //base case of biconnected graph:
83 if (pBCTree->bcTree().numberOfNodes() == 1)
84 {
85 NodeArray<int> m_nodeLength(G, 0);
86 EdgeArray<int> m_edgeLength(G, 1);
87 adjEntry m_adjExternal;
88 EmbedderMaxFaceBiconnectedGraphsLayers<int>::embed(
89 G, m_adjExternal, m_nodeLength, m_edgeLength);
90 adjExternal = m_adjExternal->twin();
91
92 delete pBCTree;
93 return;
94 }
95
96
97 //============================================================================
98 // First step: calculate min depth and node lengths
99 //============================================================================
100 //Find root Block (only node with out-degree of 0):
101 node rootBlockNode;
102 forall_nodes(n, pBCTree->bcTree())
103 {
104 if (n->outdeg() == 0)
105 {
106 rootBlockNode = n;
107 break;
108 }
109 }
110
111 /****************************************************************************/
112 /* MIN DEPTH */
113 /****************************************************************************/
114 //Node lengths of block graph:
115 md_nodeLength.init(pBCTree->auxiliaryGraph(), 0);
116
117 //Edge lengths of BC-tree, values m_{c, B} for all (c, B) \in bcTree:
118 md_m_cB.init(pBCTree->bcTree(), 0);
119
120 //Bottom-up traversal: (set m_cB for all {c, B} \in bcTree)
121 forall_adj_edges(e, rootBlockNode)
122 {
123 node cT = e->source();
124 //node cH = pBCTree->cutVertex(cT, rootBlockNode);
125
126 //set length of c in block graph of root block node:
127 edge e2;
128 forall_adj_edges(e2, cT)
129 {
130 if (e2->target() != cT)
131 continue;
132
133 node blockNode = e2->source();
134 node cutVertex = pBCTree->cutVertex(cT, blockNode);
135
136 //Start recursion:
137 md_m_cB[e2] = md_bottomUpTraversal(blockNode, cutVertex);
138 }
139 }
140
141 //Top-down traversal: (set m_cB for all {B, c} \in bcTree and get min depth
142 //for each block)
143 md_nodeLength.fill(0);
144 md_minDepth.init(pBCTree->bcTree(), maxint);
145 md_M_B.init(pBCTree->bcTree());
146 md_M2.init(pBCTree->bcTree());
147 md_topDownTraversal(rootBlockNode);
148
149 /****************************************************************************/
150 /* MAX FACE */
151 /****************************************************************************/
152 mf_cstrLength.init(pBCTree->auxiliaryGraph(), 0);
153 mf_nodeLength.init(pBCTree->auxiliaryGraph(), 0);
154 mf_maxFaceSize.init(pBCTree->bcTree(), 0);
155
156 //Bottom-Up-Traversal:
157 {
158 forall_adj_edges(e, rootBlockNode)
159 {
160 node cT = e->source();
161 node cH = pBCTree->cutVertex(cT, rootBlockNode);
162
163 //set length of v in block graph of root block node:
164 int length_v_in_rootBlock = 0;
165 edge e2;
166 forall_adj_edges(e2, cT)
167 {
168 //check if edge is an incoming edge:
169 if (e2->target() != cT)
170 continue;
171
172 node blockNode = e2->source();
173 node cutVertex = pBCTree->cutVertex(cT, blockNode);
174 length_v_in_rootBlock += mf_constraintMaxFace(blockNode, cutVertex);
175 }
176 mf_nodeLength[cH] = length_v_in_rootBlock;
177 }
178 }
179
180 node mf_bT_opt = G.chooseNode(); //= G.chooseNode() only to get rid of warning
181 int mf_ell_opt = 0;
182 mf_maximumFaceRec(rootBlockNode, mf_bT_opt, mf_ell_opt);
183
184 /****************************************************************************/
185 /* MIN DEPTH + MAX FACE */
186 /****************************************************************************/
187 //compute bT_opt:
188 mdmf_edgeLength.init(pBCTree->auxiliaryGraph(), MDMFLengthAttribute(0, 1));
189 mdmf_nodeLength.init(pBCTree->auxiliaryGraph(), MDMFLengthAttribute(0, 0));
190 int d_opt = maxint;
191 int ell_opt = -1;
192 node bT_opt;
193 node bT;
194 forall_nodes(bT, pBCTree->bcTree())
195 {
196 if (pBCTree->typeOfBNode(bT) != BCTree::BComp)
197 continue;
198 if ( md_minDepth[bT] < d_opt || (md_minDepth[bT] == d_opt && mf_maxFaceSize[bT] > ell_opt))
199 {
200 d_opt = md_minDepth[bT];
201 ell_opt = mf_maxFaceSize[bT];
202 bT_opt = bT;
203 }
204 }
205
206 //============================================================================
207 // Second step: Embed G by expanding a maximum face in bT_opt
208 //============================================================================
209 newOrder.init(G);
210 treeNodeTreated.init(pBCTree->bcTree(), false);
211 //reset md_nodeLength and set them during embedBlock call, because they are
212 //calculated for starting embedding with rootBlockNode, which is not
213 //guarenteed
214 md_nodeLength.fill(0);
215 embedBlock(bT_opt);
216
217 forall_nodes(n, G)
218 G.sort(n, newOrder[n]);
219
220 delete pBCTree;
221 }
222
223
224 int EmbedderMinDepthMaxFaceLayers::md_bottomUpTraversal(const node& bT, const node& cH)
225 {
226 int m_B = 0; //max_{c \in B} m_B(c)
227 List<node> M_B; //{c \in B | m_B(c) = m_B}
228
229 //Recursion:
230 edge e;
231 forall_adj_edges(e, bT)
232 {
233 if (e->target() != bT)
234 continue;
235 node cT = e->source();
236 //node c_in_bT = pBCTree->cutVertex(cT, bT);
237
238 //set length of c in block graph of root block node:
239 edge e_cT_bT2;
240 forall_adj_edges(e_cT_bT2, cT)
241 {
242 if (e == e_cT_bT2)
243 continue;
244
245 node bT2 = e_cT_bT2->source();
246 node c_in_bT2 = pBCTree->cutVertex(cT, bT2);
247 md_m_cB[e_cT_bT2] = md_bottomUpTraversal(bT2, c_in_bT2);
248
249 //update m_B and M_B:
250 if (m_B < md_m_cB[e_cT_bT2])
251 {
252 node cV_in_bT = pBCTree->cutVertex(cT, bT);
253 m_B = md_m_cB[e_cT_bT2];
254 M_B.clear();
255 M_B.pushBack(cV_in_bT);
256 }
257 else if ( m_B == md_m_cB[e_cT_bT2] && M_B.search(pBCTree->cutVertex(cT, bT)) == -1)
258 {
259 node cV_in_bT = pBCTree->cutVertex(cT, bT);
260 M_B.pushBack(cV_in_bT);
261 }
262 }
263 }
264
265 //set vertex length for all vertices in bH to 1 if vertex is in M_B:
266 for (ListIterator<node> iterator = M_B.begin(); iterator.valid(); iterator++)
267 md_nodeLength[*iterator] = 1;
268
269 //generate block graph of bT:
270 Graph blockGraph_bT;
271 node cInBlockGraph_bT;
272 NodeArray<int> nodeLengthSG(blockGraph_bT);
273 ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockGraph_bT, cH,
274 cInBlockGraph_bT, md_nodeLength, nodeLengthSG);
275
276 //leafs of BC-tree:
277 if (M_B.size() == 0)
278 return 1;
279
280 //set edge length for all edges in block graph to 0:
281 EdgeArray<int> edgeLength(blockGraph_bT, 0);
282
283 //compute maximum external face of block graph and get its size:
284 int cstrLength_B_c = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
285 blockGraph_bT,
286 cInBlockGraph_bT,
287 nodeLengthSG,
288 edgeLength);
289
290 if (cstrLength_B_c == M_B.size())
291 return m_B;
292 //else:
293 return m_B + 2;
294 }
295
296
297 void EmbedderMinDepthMaxFaceLayers::md_topDownTraversal(const node& bT)
298 {
299 //m_B(c) = max {0} \cup {m_{c, B'} | c \in B', B' \neq B}
300 int m_B = 0; //max_{c \in B} m_B(c)
301
302 //Compute m_B and M_B:
303 node cT_parent = 0;
304 edge e_bT_cT;
305 {
306 forall_adj_edges(e_bT_cT, bT)
307 {
308 if (e_bT_cT->source() == bT)
309 cT_parent = e_bT_cT->target();
310 node cT = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
311 edge e_cT_bT2;
312 forall_adj_edges(e_cT_bT2, cT)
313 {
314 if (e_cT_bT2 == e_bT_cT)
315 continue;
316
317 //update m_B and M_B:
318 if (m_B < md_m_cB[e_cT_bT2])
319 {
320 m_B = md_m_cB[e_cT_bT2];
321 md_M_B[bT].clear();
322 md_M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
323 }
324 else if ( m_B == md_m_cB[e_cT_bT2] && md_M_B[bT].search(pBCTree->cutVertex(cT, bT)) == -1)
325 {
326 md_M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
327 }
328 }//forall_adj_edges(e_cT_bT2, cT)
329 }//forall_adj_edges(e_bT_cT, bT)
330 }
331 //set vertex length for all vertices in bH to 1 if vertex is in M_B:
332 NodeArray<int> m_nodeLength(pBCTree->auxiliaryGraph(), 0);
333 for (ListIterator<node> iterator = md_M_B[bT].begin(); iterator.valid(); iterator++)
334 {
335 md_nodeLength[*iterator] = 1;
336 m_nodeLength[*iterator] = 1;
337 }
338
339 //generate block graph of bT:
340 Graph blockGraph_bT;
341 NodeArray<int> nodeLengthSG(blockGraph_bT);
342 NodeArray<node> nG_to_nSG;
343 ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockGraph_bT,
344 (*(pBCTree->hEdges(bT).begin()))->source(),
345 m_nodeLength, nodeLengthSG, nG_to_nSG);
346
347 //set edge length for all edges in block graph to 0:
348 EdgeArray<int> edgeLengthBlock(blockGraph_bT, 0);
349
350 //compute size of a maximum external face of block graph:
351 StaticSPQRTree* spqrTree = 0;
352 if ( !blockGraph_bT.empty()
353 && blockGraph_bT.numberOfNodes() != 1
354 && blockGraph_bT.numberOfEdges() > 2)
355 {
356 spqrTree = new StaticSPQRTree(blockGraph_bT);
357 }
358 NodeArray< EdgeArray<int> > edgeLengthSkel;
359 int cstrLength_B_c = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
360 blockGraph_bT, nodeLengthSG, edgeLengthBlock, *spqrTree, edgeLengthSkel);
361
362 //Prepare recursion by setting m_{c, B} for all edges {B, c} \in bcTree:
363 if (md_M_B[bT].size() > 0)
364 {
365 node cT1 = pBCTree->bcproper(pBCTree->original(*(md_M_B[bT].begin())));
366 bool calculateNewNodeLengths;
367 if (md_M_B[bT].size() == 1 && cT1 == cT_parent)
368 calculateNewNodeLengths = true;
369 else
370 calculateNewNodeLengths = false;
371 forall_adj_edges(e_bT_cT, bT)
372 {
373 if (e_bT_cT->target() != bT)
374 continue;
375 node cT = e_bT_cT->source();
376 node cH = pBCTree->cutVertex(cT, bT);
377
378 if (md_M_B[bT].size() == 1 && cT1 == cT)
379 {
380 //Compute new vertex lengths according to
381 //m2 = max_{v \in V_B, v != c} m_B(v) and
382 //M2 = {c \in V_B \ {v} | m_B(c) = m2}.
383 int m2 = 0;
384
385 //Compute m2 and M2:
386 edge e_bT_cT2;
387 forall_adj_edges(e_bT_cT2, bT)
388 {
389 node cT2 = (e_bT_cT2->source() == bT) ? e_bT_cT2->target() : e_bT_cT2->source();
390 if (cT1 == cT2)
391 continue;
392 edge e_cT2_bT2;
393 forall_adj_edges(e_cT2_bT2, cT2)
394 {
395 if (e_cT2_bT2 == e_bT_cT2)
396 continue;
397
398 //update m_B and M_B:
399 if (m2 < md_m_cB[e_cT2_bT2])
400 {
401 m2 = md_m_cB[e_cT2_bT2];
402 md_M2[bT].clear();
403 md_M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
404 }
405 else if ( m2 == md_m_cB[e_cT2_bT2] && md_M2[bT].search(pBCTree->cutVertex(cT2, bT)) == -1)
406 {
407 md_M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
408 }
409 }//forall_adj_edges(e_cT2_bT2, cT2)
410 }//forall_adj_edges(e_bT_cT2, bT)
411
412 //set vertex length for all vertices in bH to 1 if vertex is in M2 and
413 //0 otherwise:
414 md_nodeLength[*(md_M_B[bT].begin())] = 0;
415 for (ListIterator<node> iterator = md_M2[bT].begin(); iterator.valid(); iterator++)
416 md_nodeLength[*iterator] = 1;
417
418 Graph blockGraph_bT;
419 node cInBlockGraph_bT;
420 NodeArray<int> nodeLengthSG(blockGraph_bT);
421 ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockGraph_bT, cH,
422 cInBlockGraph_bT, md_nodeLength, nodeLengthSG);
423
424 //set edge length for all edges in block graph to 0:
425 EdgeArray<int> edgeLength(blockGraph_bT, 0);
426
427 //compute a maximum external face size of a face containing c in block graph:
428 int maxFaceSize = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
429 blockGraph_bT, cInBlockGraph_bT, nodeLengthSG, edgeLength);
430 if (md_M2[bT].size() == 0)
431 md_m_cB[e_bT_cT] = 1;
432 else
433 {
434 if (maxFaceSize == md_M2[bT].size())
435 md_m_cB[e_bT_cT] = m2;
436 else
437 md_m_cB[e_bT_cT] = m2 + 2;
438 }
439
440 if (calculateNewNodeLengths)
441 calculateNewNodeLengths = false;
442 else
443 {
444 //reset node lengths:
445 for (ListIterator<node> iterator = md_M2[bT].begin(); iterator.valid(); iterator++)
446 md_nodeLength[*iterator] = 0;
447 md_nodeLength[*(md_M_B[bT].begin())] = 1;
448 }
449 }
450 else //M_B.size() != 1
451 {
452 //compute a maximum external face size of a face containing c in block graph:
453 node cInBlockGraph_bT = nG_to_nSG[cH];
454 int maxFaceSize = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
455 blockGraph_bT, cInBlockGraph_bT, nodeLengthSG, edgeLengthBlock, *spqrTree, edgeLengthSkel);
456 if (md_M_B[bT].size() == 0)
457 md_m_cB[e_bT_cT] = 1;
458 else
459 {
460 if (maxFaceSize == md_M_B[bT].size())
461 md_m_cB[e_bT_cT] = m_B;
462 else
463 md_m_cB[e_bT_cT] = m_B + 2;
464 }
465 }
466 }//forall_adj_edges(e_bT_cT, bT)
467
468 if (calculateNewNodeLengths)
469 {
470 //Compute new vertex lengths according to
471 //m2 = max_{v \in V_B, v != c} m_B(v) and
472 //M2 = {c \in V_B \ {v} | m_B(c) = m2}.
473 int m2 = 0;
474
475 //Compute m2 and M2:
476 edge e_bT_cT2;
477 forall_adj_edges(e_bT_cT2, bT)
478 {
479 node cT2 = (e_bT_cT2->source() == bT) ? e_bT_cT2->target() : e_bT_cT2->source();
480 if (cT1 == cT2)
481 continue;
482 edge e_cT2_bT2;
483 forall_adj_edges(e_cT2_bT2, cT2)
484 {
485 if (e_cT2_bT2 == e_bT_cT2)
486 continue;
487
488 //update m_B and M_B:
489 if (m2 < md_m_cB[e_cT2_bT2])
490 {
491 m2 = md_m_cB[e_cT2_bT2];
492 md_M2[bT].clear();
493 md_M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
494 }
495 else if ( m2 == md_m_cB[e_cT2_bT2] && md_M2[bT].search(pBCTree->cutVertex(cT2, bT)) == -1)
496 {
497 md_M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
498 }
499 }//forall_adj_edges(e_cT2_bT2, cT2)
500 }//forall_adj_edges(e_bT_cT2, bT)
501
502 //set vertex length for all vertices in bH to 1 if vertex is in M2 and
503 //0 otherwise:
504 md_nodeLength[*(md_M_B[bT].begin())] = 0;
505 for (ListIterator<node> iterator = md_M2[bT].begin(); iterator.valid(); iterator++)
506 md_nodeLength[*iterator] = 1;
507 } //if (calculateNewNodeLengths
508 else if (md_M_B[bT].size() == 1)
509 {
510 //Compute M2 = {c \in V_B \ {v} | m_B(c) = m2} with
511 //m2 = max_{v \in V_B, v != c} m_B(v).
512 int m2 = 0;
513 edge e_bT_cT2;
514 forall_adj_edges(e_bT_cT2, bT)
515 {
516 node cT2 = (e_bT_cT2->source() == bT) ? e_bT_cT2->target() : e_bT_cT2->source();
517 if (cT1 == cT2)
518 continue;
519 edge e_cT2_bT2;
520 forall_adj_edges(e_cT2_bT2, cT2)
521 {
522 if (e_cT2_bT2 == e_bT_cT2)
523 continue;
524
525 //update m_B and M_B:
526 if (m2 < md_m_cB[e_cT2_bT2])
527 {
528 m2 = md_m_cB[e_cT2_bT2];
529 md_M2[bT].clear();
530 md_M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
531 }
532 else if ( m2 == md_m_cB[e_cT2_bT2] && md_M2[bT].search(pBCTree->cutVertex(cT2, bT)) == -1)
533 {
534 md_M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
535 }
536 }//forall_adj_edges(e_cT2_bT2, cT2)
537 }//forall_adj_edges(e_bT_cT2, bT)
538 }
539 }
540
541 //Recursion:
542 forall_adj_edges(e_bT_cT, bT)
543 {
544 if (e_bT_cT->target() != bT)
545 continue;
546
547 node cT = e_bT_cT->source();
548 edge e_cT_bT2;
549 forall_adj_edges(e_cT_bT2, cT)
550 {
551 if (e_cT_bT2 == e_bT_cT)
552 continue;
553
554 md_topDownTraversal(e_cT_bT2->source());
555 }
556 }
557
558 //Compute M_B and M2 for embedBlock-function:
559 {
560 md_M_B[bT].clear();
561 md_M2[bT].clear();
562 m_B = 0;
563 int m2 = 0;
564 forall_adj_edges(e_bT_cT, bT)
565 {
566 node cT = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
567 edge e_cT_bT2;
568 forall_adj_edges(e_cT_bT2, cT)
569 {
570 if (e_bT_cT == e_cT_bT2)
571 continue;
572
573 //update m_B and M_B:
574 if (m_B < md_m_cB[e_cT_bT2])
575 {
576 m_B = md_m_cB[e_cT_bT2];
577 md_M_B[bT].clear();
578 md_M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
579 }
580 else if ( m_B == md_m_cB[e_cT_bT2] && md_M_B[bT].search(pBCTree->cutVertex(cT, bT)) == -1)
581 {
582 md_M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
583 }
584 }//forall_adj_edges(e_cT_bT2, cT)
585 }//forall_adj_edges(e_bT_cT, bT)
586
587 if (md_M_B[bT].size() == 1)
588 {
589 node cT1 = pBCTree->bcproper(pBCTree->original(*(md_M_B[bT].begin())));
590 forall_adj_edges(e_bT_cT, bT)
591 {
592 node cT2 = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
593 if (cT1 == cT2)
594 continue;
595 node cT = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
596 edge e_cT_bT2;
597 forall_adj_edges(e_cT_bT2, cT)
598 {
599 //update m2 and M2:
600 if (m2 < md_m_cB[e_cT_bT2])
601 {
602 m2 = md_m_cB[e_cT_bT2];
603 md_M2[bT].clear();
604 md_M2[bT].pushBack(pBCTree->cutVertex(cT, bT));
605 }
606 else if ( m2 == md_m_cB[e_cT_bT2]
607 && md_M2[bT].search(pBCTree->cutVertex(cT, bT)) == -1)
608 {
609 md_M2[bT].pushBack(pBCTree->cutVertex(cT, bT));
610 }
611 }//forall_adj_edges(e_cT_bT2, cT)
612 }//forall_adj_edges(e_bT_cT, bT)
613 }
614 }
615
616 if (cstrLength_B_c == md_M_B[bT].size())
617 md_minDepth[bT] = m_B;
618 else
619 md_minDepth[bT] = m_B + 2;
620
621 delete spqrTree;
622 }
623
624
625 int EmbedderMinDepthMaxFaceLayers::mf_constraintMaxFace(const node& bT, const node& cH)
626 {
627 //forall (v \in B, v \neq c) do:
628 // length_B(v) := \sum_{(v, B') \in B} ConstraintMaxFace(B', v);
629 edge e;
630 forall_adj_edges(e, bT)
631 {
632 if (e->target() != bT)
633 continue;
634 node vT = e->source();
635 node vH = pBCTree->cutVertex(vT, bT);
636
637 //set length of vertex v in block graph of bT:
638 int length_v_in_block = 0;
639 edge e2;
640 forall_adj_edges(e2, vT)
641 {
642 //check if edge is an incoming edge:
643 if (e2->target() != vT)
644 continue;
645
646 node bT2 = e2->source();
647 node cutVertex = pBCTree->cutVertex(vT, bT2);
648 length_v_in_block += mf_constraintMaxFace(bT2, cutVertex);
649 }
650 mf_nodeLength[vH] = length_v_in_block;
651 }
652
653 mf_nodeLength[cH] = 0;
654 Graph blockGraph;
655 node cInBlockGraph;
656 NodeArray<int> nodeLengthSG(blockGraph);
657 ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockGraph, cH, cInBlockGraph,
658 mf_nodeLength, nodeLengthSG);
659 EdgeArray<int> edgeLengthSG(blockGraph, 1);
660 int cstrLengthBc = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
661 blockGraph, cInBlockGraph, nodeLengthSG, edgeLengthSG);
662 mf_cstrLength[cH] = cstrLengthBc;
663 return cstrLengthBc;
664 }
665
666
667 void EmbedderMinDepthMaxFaceLayers::mf_maximumFaceRec(const node& bT, node& bT_opt, int& ell_opt)
668 {
669 //(B*, \ell*) := (B, size of a maximum face in B):
670 node m_bT_opt = bT;
671 Graph blockGraph_bT;
672 NodeArray<int> nodeLengthSG(blockGraph_bT);
673 NodeArray<node> nG_to_nSG;
674 ConnectedSubgraph<int>::call(
675 pBCTree->auxiliaryGraph(), blockGraph_bT,
676 (*(pBCTree->hEdges(bT).begin()))->source(),
677 mf_nodeLength, nodeLengthSG, nG_to_nSG);
678 EdgeArray<int> edgeLengthSG(blockGraph_bT, 1);
679 StaticSPQRTree* spqrTree = 0;
680 if ( !blockGraph_bT.empty()
681 && blockGraph_bT.numberOfNodes() != 1
682 && blockGraph_bT.numberOfEdges() > 2)
683 {
684 spqrTree = new StaticSPQRTree(blockGraph_bT);
685 }
686 NodeArray< EdgeArray<int> > edgeLengthSkel;
687 int m_ell_opt = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
688 blockGraph_bT, nodeLengthSG, edgeLengthSG, *spqrTree, edgeLengthSkel);
689 mf_maxFaceSize[bT] = m_ell_opt;
690
691 edge e;
692 forall_adj_edges(e, bT)
693 {
694 if (e->target() != bT)
695 continue;
696 node cT = e->source();
697 node cH = pBCTree->cutVertex(cT, bT);
698
699 //cstrLengthBc := size of a maximum face in B containing c:
700 node cInBlockGraph_bT = nG_to_nSG[cH];
701 mf_cstrLength[cH] = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
702 blockGraph_bT, cInBlockGraph_bT, nodeLengthSG, edgeLengthSG, *spqrTree, edgeLengthSkel);
703
704 //L := \sum_{(B', c) \in bcTree} cstrLength(B', c)
705 int L = 0;
706 edge e2;
707 {
708 forall_adj_edges(e2, cT)
709 {
710 //check if edge is an incoming edge:
711 if (e2->source() != cT)
712 continue;
713
714 //get partner vertex of c in the block graph of B'=e->target() and add
715 //cstrLength(B', c) to L:
716 L += mf_cstrLength[pBCTree->cutVertex(cT, e2->target())];
717 }
718 }
719
720 forall_adj_edges(e2, cT)
721 {
722 //check if edge is an outgoing edge or the edge from bT to cT:
723 if (e2->target() != cT || e2->source() == bT)
724 continue;
725
726 //get partner vertex of c in the block graph of B'=e->source():
727 node partnerV = pBCTree->cutVertex(cT, e2->source());
728 mf_nodeLength[partnerV] = L - mf_cstrLength[partnerV];
729
730 //pBCTree->originalGraph().chooseNode() just to get rid of warning:
731 node thisbT_opt = pBCTree->originalGraph().chooseNode();
732 int thisell_opt = 0;
733 mf_maximumFaceRec(e2->source(), thisbT_opt, thisell_opt);
734 if (thisell_opt > m_ell_opt)
735 {
736 m_bT_opt = thisbT_opt;
737 m_ell_opt = thisell_opt;
738 }
739 }
740 }
741
742 //return (B*, \ell*):
743 bT_opt = m_bT_opt;
744 ell_opt = m_ell_opt;
745
746 delete spqrTree;
747 }
748
749
750 void EmbedderMinDepthMaxFaceLayers::embedBlock(const node& bT)
751 {
752 ListIterator<adjEntry> after;
753 node cT = 0;
754 embedBlock(bT, cT, after);
755 }
756
757
758 void EmbedderMinDepthMaxFaceLayers::embedBlock(
759 const node& bT,
760 const node& cT,
761 ListIterator<adjEntry>& after)
762 {
763 treeNodeTreated[bT] = true;
764 node nSG;
765 node cH = 0;
766 if (!(cT == 0))
767 cH = pBCTree->cutVertex(cT, bT);
768
769 //***************************************************************************
770 // 1. Compute MinDepth node lengths depending on M_B, M2 and cT
771 //***************************************************************************
772 if (!(cT == 0) && md_M_B[bT].size() == 1 && *(md_M_B[bT].begin()) == cH)
773 {
774 //set node length to 1 if node is in M2 and 0 otherwise
775 for (ListIterator<node> iterator = md_M2[bT].begin(); iterator.valid(); iterator++)
776 md_nodeLength[*iterator] = 1;
777 }
778 else
779 {
780 //set node length to 1 if node is in M_B and 0 otherwise
781 for (ListIterator<node> iterator = md_M_B[bT].begin(); iterator.valid(); iterator++)
782 md_nodeLength[*iterator] = 1;
783 }
784
785 //***************************************************************************
786 // 2. Set MinDepthMaxFace node lengths
787 //***************************************************************************
788 //create subgraph (block bT):
789 node nodeInBlock = cH;
790 if (nodeInBlock == 0)
791 nodeInBlock = (*(pBCTree->hEdges(bT).begin()))->source();
792 Graph SG;
793 NodeArray<MDMFLengthAttribute> nodeLengthSG;
794 EdgeArray<MDMFLengthAttribute> edgeLengthSG;
795 NodeArray<node> nSG_to_nG;
796 EdgeArray<edge> eSG_to_eG;
797 node nodeInBlockSG;
798 ConnectedSubgraph<MDMFLengthAttribute>::call(
799 pBCTree->auxiliaryGraph(), SG,
800 nodeInBlock, nodeInBlockSG,
801 nSG_to_nG, eSG_to_eG,
802 mdmf_nodeLength, nodeLengthSG,
803 mdmf_edgeLength, edgeLengthSG);
804
805 //copy (0, 1)-min depth node lengths into nodeLengthSG d component and max
806 //face sice node lengths into l component:
807 forall_nodes(nSG, SG)
808 {
809 nodeLengthSG[nSG].d = md_nodeLength[nSG_to_nG[nSG]];
810 nodeLengthSG[nSG].l = mf_nodeLength[nSG_to_nG[nSG]];
811 }
812
813
814 //***************************************************************************
815 // 3. Compute embedding of block
816 //***************************************************************************
817 adjEntry m_adjExternal = 0;
818 if (cH == 0)
819 EmbedderMaxFaceBiconnectedGraphsLayers<MDMFLengthAttribute>::embed(
820 SG, m_adjExternal, nodeLengthSG, edgeLengthSG);
821 else
822 EmbedderMaxFaceBiconnectedGraphsLayers<MDMFLengthAttribute>::embed(
823 SG, m_adjExternal, nodeLengthSG, edgeLengthSG, nodeInBlockSG);
824
825 //***************************************************************************
826 // 4. Copy block embedding into graph embedding and call recursively
827 // embedBlock for all cut vertices in bT
828 //***************************************************************************
829 CombinatorialEmbedding CE(SG);
830 face f = CE.leftFace(m_adjExternal);
831
832 if (*pAdjExternal == 0)
833 {
834 node on = pBCTree->original(nSG_to_nG[m_adjExternal->theNode()]);
835 adjEntry ae1 = on->firstAdj();
836 for (adjEntry ae = ae1; ae; ae = ae->succ())
837 {
838 if (ae->theEdge() == pBCTree->original(eSG_to_eG[m_adjExternal->theEdge()]))
839 {
840 *pAdjExternal = ae->twin();
841 break;
842 }
843 }
844 }
845
846 bool DGcomputed = false;
847 int extFaceID = 0;
848 Graph* p_DG;
849 List<node>* p_fPG_to_nDG;
850 NodeArray<int>* p_nDG_to_fPG;
851 NodeArray< List<adjEntry> >* p_adjacencyList;
852 List< List<adjEntry> >* p_faces;
853 NodeArray<int>* p_distances;
854
855 forall_nodes(nSG, SG)
856 {
857 node nH = nSG_to_nG[nSG];
858 node nG = pBCTree->original(nH);
859 adjEntry ae = nSG->firstAdj();
860 ListIterator<adjEntry>* pAfter;
861 if (pBCTree->bcproper(nG) == cT)
862 pAfter = &after;
863 else
864 pAfter = new ListIterator<adjEntry>();
865
866 if (pBCTree->typeOfGNode(nG) == BCTree::CutVertex)
867 {
868 node cT2 = pBCTree->bcproper(nG);
869 bool no_recursion = false;
870 if (cT2 == cT)
871 {
872 node parent_bT_of_cT2;
873 edge e_cT2_to_bT2;
874 forall_adj_edges(e_cT2_to_bT2, cT2)
875 {
876 if (e_cT2_to_bT2->source() == cT2)
877 {
878 parent_bT_of_cT2 = e_cT2_to_bT2->target();
879 break;
880 }
881 }
882 if (treeNodeTreated[parent_bT_of_cT2])
883 no_recursion = true;
884 }
885
886 if (no_recursion)
887 {
888 //find adjacency entry of nSG which lies on external face f:
889 adjEntry aeFace = f->firstAdj();
890 do
891 {
892 if (aeFace->theNode() == nSG)
893 {
894 if (aeFace->succ())
895 ae = aeFace->succ();
896 else
897 ae = nSG->firstAdj();
898 break;
899 }
900 aeFace = aeFace->faceCycleSucc();
901 } while(aeFace != f->firstAdj());
902 }
903 else //!no_recursion
904 {
905 //(if exists) find adjacency entry of nSG which lies on external face f:
906 bool aeExtExists = false;
907 adjEntry aeFace = f->firstAdj();
908 do
909 {
910 if (aeFace->theNode() == nSG)
911 {
912 if (aeFace->succ())
913 ae = aeFace->succ();
914 else
915 ae = nSG->firstAdj();
916 aeExtExists = true;
917 break;
918 }
919 aeFace = aeFace->faceCycleSucc();
920 } while(aeFace != f->firstAdj());
921
922 if (!aeExtExists)
923 {
924 if (!DGcomputed)
925 {
926 p_DG = new Graph();
927 p_fPG_to_nDG = OGDF_NEW List<node>();
928 p_nDG_to_fPG = OGDF_NEW NodeArray<int>();
929 p_adjacencyList = OGDF_NEW NodeArray< List<adjEntry> >();
930 p_faces = OGDF_NEW List< List<adjEntry> >;
931 p_distances = OGDF_NEW NodeArray<int>;
932 DGcomputed = true;
933
934 //compute dual graph of skeleton graph:
935 p_adjacencyList->init(SG);
936 node nBG;
937 forall_nodes(nBG, SG)
938 {
939 adjEntry ae_nBG;
940 forall_adj(ae_nBG, nBG)
941 (*p_adjacencyList)[nBG].pushBack(ae_nBG);
942 }
943
944 NodeArray< List<adjEntry> > adjEntryTreated(SG);
945 forall_nodes(nBG, SG)
946 {
947 adjEntry adj;
948 forall_adj(adj, nBG)
949 {
950 if (adjEntryTreated[nBG].search(adj) != -1)
951 continue;
952
953 List<adjEntry> newFace;
954 adjEntry adj2 = adj;
955 do
956 {
957 newFace.pushBack(adj2);
958 adjEntryTreated[adj2->theNode()].pushBack(adj2);
959 node tn = adj2->twinNode();
960 int idx = (*p_adjacencyList)[tn].search(adj2->twin());
961 if (idx - 1 < 0)
962 idx = (*p_adjacencyList)[tn].size() - 1;
963 else
964 idx -= 1;
965 adj2 = *((*p_adjacencyList)[tn].get(idx));
966 } while (adj2 != adj);
967 p_faces->pushBack(newFace);
968 }
969 } //forall_nodes(nBG, blockG[bT])
970
971 p_nDG_to_fPG->init(*p_DG);
972
973 for (ListIterator< List<adjEntry> > it = p_faces->begin(); it.valid(); it++)
974 {
975 node nn = p_DG->newNode();
976 (*p_nDG_to_fPG)[nn] = p_fPG_to_nDG->search(*(p_fPG_to_nDG->pushBack(nn)));
977 }
978
979 NodeArray< List<node> > adjFaces(*p_DG);
980 int i = 0;
981 for (ListIterator< List<adjEntry> > it = p_faces->begin(); it.valid(); it++)
982 {
983 int f1_id = i;
984 for (ListIterator<adjEntry> it2 = (*it).begin(); it2.valid(); it2++)
985 {
986 int f2_id = 0;
987 int j = 0;
988 for (ListIterator< List<adjEntry> > it3 = p_faces->begin(); it3.valid(); it3++)
989 {
990 bool do_break = false;
991 for (ListIterator<adjEntry> it4 = (*it3).begin(); it4.valid(); it4++)
992 {
993 if ((*it4) == (*it2)->twin())
994 {
995 f2_id = j;
996 do_break = true;
997 break;
998 }
999 }
1000 if (do_break)
1001 break;
1002 j++;
1003 }
1004
1005 if ( f1_id != f2_id
1006 && adjFaces[*(p_fPG_to_nDG->get(f1_id))].search(*(p_fPG_to_nDG->get(f2_id))) == -1
1007 && adjFaces[*(p_fPG_to_nDG->get(f2_id))].search(*(p_fPG_to_nDG->get(f1_id))) == -1)
1008 {
1009 adjFaces[*(p_fPG_to_nDG->get(f1_id))].pushBack(*(p_fPG_to_nDG->get(f2_id)));
1010 p_DG->newEdge(*(p_fPG_to_nDG->get(f1_id)), *(p_fPG_to_nDG->get(f2_id)));
1011 }
1012
1013 if (*it2 == f->firstAdj())
1014 extFaceID = f1_id;
1015 } //for (ListIterator<adjEntry> it2 = (*it).begin(); it2.valid(); it2++)
1016 i++;
1017 } //for (ListIterator< List<adjEntry> > it = faces.begin(); it.valid(); it++)
1018
1019 //compute shortest path from every face to the external face:
1020 List<edge> DG_edges;
1021 p_DG->allEdges(DG_edges);
1022 for (ListIterator<edge> it_e = DG_edges.begin(); it_e.valid(); it_e++)
1023 {
1024 node s = (*it_e)->source();
1025 node t = (*it_e)->target();
1026 p_DG->newEdge(t, s);
1027 }
1028 ShortestPathWithBFM shortestPath;
1029 node efDG = *(p_fPG_to_nDG->get(extFaceID));
1030 EdgeArray<int> el(*p_DG, 1);
1031 p_distances->init(*p_DG);
1032 NodeArray<edge> pi(*p_DG);
1033 shortestPath.call(*p_DG, efDG, el, *p_distances, pi);
1034 } //if (!DGcomputed)
1035
1036 //choose face with minimal shortest path:
1037 List<adjEntry> optFace;
1038 int optFaceDist = -1;
1039 for (int fID = 0; fID < p_faces->size(); fID++)
1040 {
1041 List<adjEntry> theFace = *(p_faces->get(fID));
1042 adjEntry ae_nSG;
1043 bool contains_nSG = false;
1044 for (ListIterator<adjEntry> it_ae = theFace.begin(); it_ae.valid(); it_ae++)
1045 {
1046 if ((*it_ae)->theNode() == nSG)
1047 {
1048 contains_nSG = true;
1049 ae_nSG = *it_ae;
1050 break;
1051 }
1052 }
1053
1054 if (contains_nSG)
1055 {
1056 int thisDist = (*p_distances)[*p_fPG_to_nDG->get(fID)];
1057 if (optFaceDist == -1 || optFaceDist > thisDist)
1058 {
1059 optFace = theFace;
1060 optFaceDist = thisDist;
1061 if (ae_nSG->succ())
1062 ae = ae_nSG->succ();
1063 else
1064 ae = nSG->firstAdj();
1065 }
1066 }
1067 } //for (int fID = 0; fID < faces.size(); fID++)
1068 } //if (!aeExtExists)
1069
1070 edge e_cT2_to_bT2;
1071 forall_adj_edges(e_cT2_to_bT2, cT2)
1072 {
1073 node bT2;
1074 if (e_cT2_to_bT2->source() == cT2)
1075 bT2 = e_cT2_to_bT2->target();
1076 else
1077 bT2 = e_cT2_to_bT2->source();
1078 if (!treeNodeTreated[bT2])
1079 embedBlock(bT2, cT2, *pAfter);
1080 }
1081 }
1082 }
1083
1084 //embed all edges of block bT:
1085 bool after_ae = true;
1086 for (adjEntry aeNode = ae;
1087 after_ae || aeNode != ae;
1088 after_ae = (!after_ae || !aeNode->succ()) ? false : true,
1089 aeNode = aeNode->succ() ? aeNode->succ() : nSG->firstAdj())
1090 {
1091 edge eG = pBCTree->original(eSG_to_eG[aeNode->theEdge()]);
1092 if (nG == eG->source())
1093 {
1094 if (!pAfter->valid())
1095 *pAfter = newOrder[nG].pushBack(eG->adjSource());
1096 else
1097 *pAfter = newOrder[nG].insertAfter(eG->adjSource(), *pAfter);
1098 }
1099 else //!(nG == eG->source())
1100 {
1101 if (!pAfter->valid())
1102 *pAfter = newOrder[nG].pushBack(eG->adjTarget());
1103 else
1104 *pAfter = newOrder[nG].insertAfter(eG->adjTarget(), *pAfter);
1105 }
1106 } //for (adjEntry aeNode = ae; aeNode; aeNode = aeNode->succ())
1107
1108 if (!(*pAfter == after))
1109 delete pAfter;
1110 } //forall_nodes(nSG, SG)
1111
1112 if (DGcomputed)
1113 {
1114 delete p_DG;
1115 delete p_fPG_to_nDG;
1116 delete p_nDG_to_fPG;
1117 delete p_adjacencyList;
1118 delete p_faces;
1119 delete p_distances;
1120 }
1121 }
1122
1123 } // end namespace ogdf
Windows Explorer Extension to Operate Git