?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Prefer to use VS2013 for compiling and testing on AppVeyor
[TortoiseGit.git] / ext / OGDF / src / planarity / EmbedderMaxFaceLayers.cpp
blob3310b947be06efeadcfd07797228e7d44160aa54
1 /*
2 * $Revision: 2565 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Computes an embedding of a graph with maximum external face.
11 *
12 * See the paper "Graph Embedding with Minimum Depth and Maximum External
13 * Face" by C. Gutwenger and P. Mutzel (2004) for details.
14 * The algorithm for maximum external face is combined with the
15 * algorithm for maximum external layers which defines how to embed
16 * blocks into inner faces. See diploma thesis "Algorithmen zur
17 * Bestimmung von guten Graph-Einbettungen für orthogonale
18 * Zeichnungen" (in german) by Thorsten Kerkhof (2007) for details.
19 *
20 * \author Thorsten Kerkhof
21 *
22 * \par License:
23 * This file is part of the Open Graph Drawing Framework (OGDF).
24 *
25 * \par
26 * Copyright (C)<br>
27 * See README.txt in the root directory of the OGDF installation for details.
28 *
29 * \par
30 * This program is free software; you can redistribute it and/or
31 * modify it under the terms of the GNU General Public License
32 * Version 2 or 3 as published by the Free Software Foundation;
33 * see the file LICENSE.txt included in the packaging of this file
34 * for details.
35 *
36 * \par
37 * This program is distributed in the hope that it will be useful,
38 * but WITHOUT ANY WARRANTY; without even the implied warranty of
39 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
40 * GNU General Public License for more details.
41 *
42 * \par
43 * You should have received a copy of the GNU General Public
44 * License along with this program; if not, write to the Free
45 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
46 * Boston, MA 02110-1301, USA.
47 *
48 * \see http://www.gnu.org/copyleft/gpl.html
49 ***************************************************************/
50
51 #include <ogdf/planarity/EmbedderMaxFaceLayers.h>
52 #include <ogdf/internal/planarity/EmbedderMaxFaceBiconnectedGraphsLayers.h>
53 #include <ogdf/internal/planarity/ConnectedSubgraph.h>
54
55 namespace ogdf {
56
57 void EmbedderMaxFaceLayers::call(Graph& G, adjEntry& adjExternal)
58 {
59 adjExternal = 0;
60 pAdjExternal = &adjExternal;
61
62 //simple base cases:
63 if (G.numberOfNodes() <= 1)
64 return;
65 if (G.numberOfEdges() == 1)
66 {
67 edge e = G.firstEdge();
68 adjExternal = e->adjSource();
69 return;
70 }
71
72 //HINT: Edges are directed from child to parent in BC-trees
73 pBCTree = new BCTree(G);
74
75 //base case of biconnected graph:
76 if (pBCTree->bcTree().numberOfNodes() == 1)
77 {
78 NodeArray<int> m_nodeLength(G, 0);
79 EdgeArray<int> m_edgeLength(G, 1);
80 adjEntry m_adjExternal;
81 EmbedderMaxFaceBiconnectedGraphsLayers<int>::embed(G, m_adjExternal, m_nodeLength, m_edgeLength);
82 adjExternal = m_adjExternal;
83
84 delete pBCTree;
85 return;
86 }
87
88 //***************************************************************************/
89 //First step: calculate maximum face and node lengths
90 //***************************************************************************/
91
92 //Find root Block (root node is only node with out-degree of 0):
93 node rootBlockNode;
94 node n;
95 forall_nodes(n, pBCTree->bcTree())
96 {
97 if (n->outdeg() == 0)
98 {
99 rootBlockNode = n;
100 break;
101 }
102 }
103
104 //compute block graphs and SPQR trees:
105 blockG.init(pBCTree->bcTree());
106 nBlockEmbedding_to_nH.init(pBCTree->bcTree());
107 eBlockEmbedding_to_eH.init(pBCTree->bcTree());
108 nH_to_nBlockEmbedding.init(pBCTree->bcTree());
109 eH_to_eBlockEmbedding.init(pBCTree->bcTree());
110 nodeLength.init(pBCTree->bcTree());
111 cstrLength.init(pBCTree->bcTree());
112 spqrTrees.init(pBCTree->bcTree(),0);
113 computeBlockGraphs(rootBlockNode, 0);
114
115 //Bottom-Up-Traversal:
116 edge e;
117 forall_adj_edges(e, rootBlockNode)
118 {
119 node cT = e->source();
120 node cH = pBCTree->cutVertex(cT, rootBlockNode);
121 node cB = nH_to_nBlockEmbedding[rootBlockNode][cH];
122
123 //set length of v in block graph of root block node:
124 int length_v_in_rootBlock = 0;
125 edge e2;
126 forall_adj_edges(e2, cT)
127 {
128 //check if edge is an incoming edge:
129 if (e2->target() != cT)
130 continue;
131
132 node blockNode = e2->source();
133 node cutVertex = pBCTree->cutVertex(cT, blockNode);
134 length_v_in_rootBlock += constraintMaxFace(blockNode, cutVertex);
135 }
136 nodeLength[rootBlockNode][cB] = length_v_in_rootBlock;
137 }
138
139 node bT_opt = G.chooseNode(); //= G.chooseNode() only to get rid of warning
140 int ell_opt = 0;
141 maximumFaceRec(rootBlockNode, bT_opt, ell_opt);
142
143
144 //****************************************************************************
145 //Second step: Embed G by expanding a maximum face in bT_opt
146 //****************************************************************************
147 newOrder.init(G);
148 treeNodeTreated.init(pBCTree->bcTree(), false);
149 embedBlock(bT_opt);
150
151 node v;
152 forall_nodes(v, G)
153 G.sort(v, newOrder[v]);
154
155 forall_nodes(v, pBCTree->bcTree())
156 delete spqrTrees[v];
157
158 delete pBCTree;
159 }
160
161
162 void EmbedderMaxFaceLayers::computeBlockGraphs(const node& bT, const node& cH)
163 {
164 //recursion:
165 edge e;
166 forall_adj_edges(e, bT)
167 {
168 if (e->source() == bT)
169 continue;
170
171 node cT = e->source();
172 edge e2;
173 forall_adj_edges(e2, cT)
174 {
175 if (e2->source() == cT)
176 continue;
177 node cH2 = pBCTree->cutVertex(cT, e2->source());
178 computeBlockGraphs(e2->source(), cH2);
179 }
180 }
181
182 //embed block bT:
183 node m_cH = cH;
184 if (m_cH == 0)
185 m_cH = pBCTree->cutVertex(bT->firstAdj()->twinNode(), bT);
186 ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockG[bT], m_cH,
187 nBlockEmbedding_to_nH[bT], eBlockEmbedding_to_eH[bT],
188 nH_to_nBlockEmbedding[bT], eH_to_eBlockEmbedding[bT]);
189 nodeLength[bT].init(blockG[bT], 0);
190 cstrLength[bT].init(blockG[bT], 0);
191 if ( !blockG[bT].empty()
192 && blockG[bT].numberOfNodes() != 1
193 && blockG[bT].numberOfEdges() > 2)
194 {
195 spqrTrees[bT] = new StaticSPQRTree(blockG[bT]);
196 }
197 }
198
199
200 int EmbedderMaxFaceLayers::constraintMaxFace(const node& bT, const node& cH)
201 {
202 //forall (v \in B, v \neq c) do:
203 // length_B(v) := \sum_{(v, B') \in B} ConstraintMaxFace(B', v);
204 edge e;
205 forall_adj_edges(e, bT)
206 {
207 if (e->target() != bT)
208 continue;
209 node vT = e->source();
210 node vH = pBCTree->cutVertex(vT, bT);
211
212 //set length of vertex v in block graph of bT:
213 int length_v_in_block = 0;
214 edge e2;
215 forall_adj_edges(e2, vT)
216 {
217 //check if edge is an incoming edge:
218 if (e2->target() != vT)
219 continue;
220
221 node bT2 = e2->source();
222 node cutVertex = pBCTree->cutVertex(vT, bT2);
223 length_v_in_block += constraintMaxFace(bT2, cutVertex);
224 }
225 nodeLength[bT][nH_to_nBlockEmbedding[bT][vH]] = length_v_in_block;
226 }
227
228 EdgeArray<int> edgeLength(blockG[bT], 1);
229 int cstrLengthBc
230 = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(blockG[bT],
231 nH_to_nBlockEmbedding[bT][cH],
232 nodeLength[bT],
233 edgeLength,
234 *spqrTrees[bT]);
235 cstrLength[bT][nH_to_nBlockEmbedding[bT][cH]] = cstrLengthBc;
236 return cstrLengthBc;
237 }
238
239
240 void EmbedderMaxFaceLayers::maximumFaceRec(const node& bT, node& bT_opt, int& ell_opt)
241 {
242 //(B*, \ell*) := (B, size of a maximum face in B):
243 node m_bT_opt = bT;
244 EdgeArray<int> edgeLength(blockG[bT], 1);
245 NodeArray< EdgeArray<int> > edgeLengthSkel;
246 int m_ell_opt = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
247 blockG[bT],
248 nodeLength[bT],
249 edgeLength,
250 *spqrTrees[bT],
251 edgeLengthSkel);
252
253 edge e;
254 forall_adj_edges(e, bT)
255 {
256 if (e->target() != bT)
257 continue;
258 node cT = e->source();
259 node cH = pBCTree->cutVertex(cT, bT);
260
261 EdgeArray<int> edgeLength(blockG[bT], 1);
262 cstrLength[bT][nH_to_nBlockEmbedding[bT][cH]] = EmbedderMaxFaceBiconnectedGraphsLayers<int>::computeSize(
263 blockG[bT],
264 nH_to_nBlockEmbedding[bT][cH],
265 nodeLength[bT],
266 edgeLength,
267 *spqrTrees[bT],
268 edgeLengthSkel);
269
270 //L := \sum_{(B', c) \in bcTree} cstrLength(B', c)
271 int L = 0;
272 edge e2;
273 {
274 forall_adj_edges(e2, cT)
275 {
276 //check if edge is an incoming edge:
277 if (e2->source() != cT)
278 continue;
279
280 //get partner vertex of c in the block graph of B'=e->target() and add
281 //cstrLength(B', c) to L:
282 node bT2 = e2->target();
283 L += cstrLength[bT2][nH_to_nBlockEmbedding[bT2][pBCTree->cutVertex(cT, bT2)]];
284 }
285 }
286
287 forall_adj_edges(e2, cT)
288 {
289 //check if edge is an outgoing edge or the edge from bT to cT:
290 if (e2->target() != cT || e2->source() == bT)
291 continue;
292
293 //get partner vertex of c in the block graph of B'=e->source():
294 node pT = e2->source();
295 node partnerV = pBCTree->cutVertex(cT, pT);
296 node pB = nH_to_nBlockEmbedding[pT][partnerV];
297 nodeLength[pT][pB] = L - cstrLength[pT][pB];
298
299 //pBCTree->originalGraph().chooseNode() just to get rid of warning:
300 node thisbT_opt = pBCTree->originalGraph().chooseNode();
301 int thisell_opt = 0;
302 maximumFaceRec(pT, thisbT_opt, thisell_opt);
303 if (thisell_opt > m_ell_opt)
304 {
305 m_bT_opt = thisbT_opt;
306 m_ell_opt = thisell_opt;
307 }
308 }
309 }
310
311 //return (B*, \ell*):
312 bT_opt = m_bT_opt;
313 ell_opt = m_ell_opt;
314 }
315
316
317 void EmbedderMaxFaceLayers::embedBlock(const node& bT)
318 {
319 ListIterator<adjEntry> after;
320 node cT = 0;
321 embedBlock(bT, cT, after);
322 }
323
324
325 void EmbedderMaxFaceLayers::embedBlock(
326 const node& bT,
327 const node& cT,
328 ListIterator<adjEntry>& after)
329 {
330 treeNodeTreated[bT] = true;
331 node cH = 0;
332 if (!(cT == 0))
333 cH = pBCTree->cutVertex(cT, bT);
334
335 //***************************************************************************
336 // 1. Compute embedding of block
337 //***************************************************************************
338 EdgeArray<int> edgeLength(blockG[bT], 1);
339 adjEntry m_adjExternal = 0;
340 if (cH == 0)
341 EmbedderMaxFaceBiconnectedGraphsLayers<int>::embed(blockG[bT], m_adjExternal,
342 nodeLength[bT], edgeLength);
343 else
344 EmbedderMaxFaceBiconnectedGraphsLayers<int>::embed(blockG[bT], m_adjExternal,
345 nodeLength[bT], edgeLength, nH_to_nBlockEmbedding[bT][cH]);
346
347 //***************************************************************************
348 // 2. Copy block embedding into graph embedding and call recursively
349 // embedBlock for all cut vertices in bT
350 //***************************************************************************
351 CombinatorialEmbedding CE(blockG[bT]);
352 face f = CE.leftFace(m_adjExternal);
353
354 if (*pAdjExternal == 0)
355 {
356 node on = pBCTree->original(nBlockEmbedding_to_nH[bT][m_adjExternal->theNode()]);
357 adjEntry ae1 = on->firstAdj();
358 for (adjEntry ae = ae1; ae; ae = ae->succ())
359 {
360 if (ae->theEdge() == pBCTree->original(eBlockEmbedding_to_eH[bT][m_adjExternal->theEdge()]))
361 {
362 *pAdjExternal = ae->twin();
363 break;
364 }
365 }
366 }
367
368 bool DGcomputed = false;
369 int extFaceID = 0;
370 Graph* p_DG;
371 List<node>* p_fPG_to_nDG;
372 NodeArray<int>* p_nDG_to_fPG;
373 NodeArray< List<adjEntry> >* p_adjacencyList;
374 List< List<adjEntry> >* p_faces;
375 NodeArray<int>* p_distances;
376
377 node nSG;
378 forall_nodes(nSG, blockG[bT])
379 {
380 node nH = nBlockEmbedding_to_nH[bT][nSG];
381 node nG = pBCTree->original(nH);
382 adjEntry ae = nSG->firstAdj();
383 ListIterator<adjEntry>* pAfter;
384 if (pBCTree->bcproper(nG) == cT)
385 pAfter = &after;
386 else
387 pAfter = OGDF_NEW ListIterator<adjEntry>();
388
389 if (pBCTree->typeOfGNode(nG) == BCTree::CutVertex)
390 {
391 node cT2 = pBCTree->bcproper(nG);
392 bool no_recursion = false;
393 if (cT2 == cT)
394 {
395 node parent_bT_of_cT2;
396 edge e_cT2_to_bT2;
397 forall_adj_edges(e_cT2_to_bT2, cT2)
398 {
399 if (e_cT2_to_bT2->source() == cT2)
400 {
401 parent_bT_of_cT2 = e_cT2_to_bT2->target();
402 break;
403 }
404 }
405 if (treeNodeTreated[parent_bT_of_cT2])
406 no_recursion = true;
407 }
408
409 if (no_recursion)
410 {
411 //find adjacency entry of nSG which lies on external face f:
412 adjEntry aeFace = f->firstAdj();
413 do
414 {
415 if (aeFace->theNode() == nSG)
416 {
417 if (aeFace->succ())
418 ae = aeFace->succ();
419 else
420 ae = nSG->firstAdj();
421 break;
422 }
423 aeFace = aeFace->faceCycleSucc();
424 } while(aeFace != f->firstAdj());
425 }
426 else //!no_recursion
427 {
428 //(if exists) find adjacency entry of nSG which lies on external face f:
429 bool aeExtExists = false;
430 adjEntry aeFace = f->firstAdj();
431 do
432 {
433 if (aeFace->theNode() == nSG)
434 {
435 if (aeFace->succ())
436 ae = aeFace->succ();
437 else
438 ae = nSG->firstAdj();
439 aeExtExists = true;
440 break;
441 }
442 aeFace = aeFace->faceCycleSucc();
443 } while(aeFace != f->firstAdj());
444
445 if (!aeExtExists)
446 {
447 if (!DGcomputed)
448 {
449 p_DG = new Graph();
450 p_fPG_to_nDG = OGDF_NEW List<node>();
451 p_nDG_to_fPG = OGDF_NEW NodeArray<int>();
452 p_adjacencyList = OGDF_NEW NodeArray< List<adjEntry> >();
453 p_faces = OGDF_NEW List< List<adjEntry> >;
454 p_distances = OGDF_NEW NodeArray<int>;
455 DGcomputed = true;
456
457 //compute dual graph of skeleton graph:
458 p_adjacencyList->init(blockG[bT]);
459 node nBG;
460 forall_nodes(nBG, blockG[bT])
461 {
462 adjEntry ae_nBG;
463 forall_adj(ae_nBG, nBG)
464 (*p_adjacencyList)[nBG].pushBack(ae_nBG);
465 }
466
467 NodeArray< List<adjEntry> > adjEntryTreated(blockG[bT]);
468 forall_nodes(nBG, blockG[bT])
469 {
470 adjEntry adj;
471 forall_adj(adj, nBG)
472 {
473 if (adjEntryTreated[nBG].search(adj) != -1)
474 continue;
475
476 List<adjEntry> newFace;
477 adjEntry adj2 = adj;
478 do
479 {
480 newFace.pushBack(adj2);
481 adjEntryTreated[adj2->theNode()].pushBack(adj2);
482 node tn = adj2->twinNode();
483 int idx = (*p_adjacencyList)[tn].search(adj2->twin());
484 if (idx - 1 < 0)
485 idx = (*p_adjacencyList)[tn].size() - 1;
486 else
487 idx -= 1;
488 adj2 = *((*p_adjacencyList)[tn].get(idx));
489 } while (adj2 != adj);
490 p_faces->pushBack(newFace);
491 }
492 } //forall_nodes(nBG, blockG[bT])
493
494 p_nDG_to_fPG->init(*p_DG);
495
496 for (ListIterator< List<adjEntry> > it = p_faces->begin(); it.valid(); it++)
497 {
498 node nn = p_DG->newNode();
499 (*p_nDG_to_fPG)[nn] = p_fPG_to_nDG->search(*(p_fPG_to_nDG->pushBack(nn)));
500 }
501
502 NodeArray< List<node> > adjFaces(*p_DG);
503 int i = 0;
504 for (ListIterator< List<adjEntry> > it = p_faces->begin(); it.valid(); it++)
505 {
506 int f1_id = i;
507 for (ListIterator<adjEntry> it2 = (*it).begin(); it2.valid(); it2++)
508 {
509 int f2_id = 0;
510 int j = 0;
511 for (ListIterator< List<adjEntry> > it3 = p_faces->begin(); it3.valid(); it3++)
512 {
513 bool do_break = false;
514 for (ListIterator<adjEntry> it4 = (*it3).begin(); it4.valid(); it4++)
515 {
516 if ((*it4) == (*it2)->twin())
517 {
518 f2_id = j;
519 do_break = true;
520 break;
521 }
522 }
523 if (do_break)
524 break;
525 j++;
526 }
527
528 if ( f1_id != f2_id
529 && adjFaces[*(p_fPG_to_nDG->get(f1_id))].search(*(p_fPG_to_nDG->get(f2_id))) == -1
530 && adjFaces[*(p_fPG_to_nDG->get(f2_id))].search(*(p_fPG_to_nDG->get(f1_id))) == -1)
531 {
532 adjFaces[*(p_fPG_to_nDG->get(f1_id))].pushBack(*(p_fPG_to_nDG->get(f2_id)));
533 p_DG->newEdge(*(p_fPG_to_nDG->get(f1_id)), *(p_fPG_to_nDG->get(f2_id)));
534 }
535
536 if (*it2 == f->firstAdj())
537 extFaceID = f1_id;
538 } //for (ListIterator<adjEntry> it2 = (*it).begin(); it2.valid(); it2++)
539 i++;
540 } //for (ListIterator< List<adjEntry> > it = faces.begin(); it.valid(); it++)
541
542 //compute shortest path from every face to the external face:
543 List<edge> DG_edges;
544 p_DG->allEdges(DG_edges);
545 for (ListIterator<edge> it_e = DG_edges.begin(); it_e.valid(); it_e++)
546 {
547 node s = (*it_e)->source();
548 node t = (*it_e)->target();
549 p_DG->newEdge(t, s);
550 }
551 ShortestPathWithBFM shortestPath;
552 node efDG = *(p_fPG_to_nDG->get(extFaceID));
553 EdgeArray<int> el(*p_DG, 1);
554 p_distances->init(*p_DG);
555 NodeArray<edge> pi(*p_DG);
556 shortestPath.call(*p_DG, efDG, el, *p_distances, pi);
557 } //if (!DGcomputed)
558
559 //choose face with minimal shortest path:
560 List<adjEntry> optFace;
561 int optFaceDist = -1;
562 for (int fID = 0; fID < p_faces->size(); fID++)
563 {
564 List<adjEntry> theFace = *(p_faces->get(fID));
565 adjEntry ae_nSG;
566 bool contains_nSG = false;
567 for (ListIterator<adjEntry> it_ae = theFace.begin(); it_ae.valid(); it_ae++)
568 {
569 if ((*it_ae)->theNode() == nSG)
570 {
571 contains_nSG = true;
572 ae_nSG = *it_ae;
573 break;
574 }
575 }
576
577 if (contains_nSG)
578 {
579 int thisDist = (*p_distances)[*p_fPG_to_nDG->get(fID)];
580 if (optFaceDist == -1 || optFaceDist > thisDist)
581 {
582 optFace = theFace;
583 optFaceDist = thisDist;
584 if (ae_nSG->succ())
585 ae = ae_nSG->succ();
586 else
587 ae = nSG->firstAdj();
588 }
589 }
590 } //for (int fID = 0; fID < faces.size(); fID++)
591 } //if (!aeExtExists)
592
593 edge e_cT2_to_bT2;
594 forall_adj_edges(e_cT2_to_bT2, cT2)
595 {
596 node bT2;
597 if (e_cT2_to_bT2->source() == cT2)
598 bT2 = e_cT2_to_bT2->target();
599 else
600 bT2 = e_cT2_to_bT2->source();
601 if (!treeNodeTreated[bT2])
602 embedBlock(bT2, cT2, *pAfter);
603 }
604 }
605 }
606
607 //embed all edges of block bT:
608 bool after_ae = true;
609 for (adjEntry aeNode = ae;
610 after_ae || aeNode != ae;
611 after_ae = (!after_ae || !aeNode->succ()) ? false : true,
612 aeNode = aeNode->succ() ? aeNode->succ() : nSG->firstAdj())
613 {
614 edge eG = pBCTree->original(eBlockEmbedding_to_eH[bT][aeNode->theEdge()]);
615 if (nG == eG->source())
616 {
617 if (!pAfter->valid())
618 *pAfter = newOrder[nG].pushBack(eG->adjSource());
619 else
620 *pAfter = newOrder[nG].insertAfter(eG->adjSource(), *pAfter);
621 }
622 else //!(nG == eG->source())
623 {
624 if (!pAfter->valid())
625 *pAfter = newOrder[nG].pushBack(eG->adjTarget());
626 else
627 *pAfter = newOrder[nG].insertAfter(eG->adjTarget(), *pAfter);
628 }
629 } //for (adjEntry aeNode = ae; aeNode; aeNode = aeNode->succ())
630
631 if (!(*pAfter == after))
632 delete pAfter;
633 } //forall_nodes(nSG, blockG[bT])
634
635 if (DGcomputed)
636 {
637 delete p_DG;
638 delete p_fPG_to_nDG;
639 delete p_nDG_to_fPG;
640 delete p_adjacencyList;
641 delete p_faces;
642 delete p_distances;
643 }
644 }
645
646 } // end namespace ogdf
Windows Explorer Extension to Operate Git