?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix warning
[TortoiseGit.git] / ext / OGDF / src / upward / SubgraphUpwardPlanarizer.cpp
blob22d7cb75c7b82b6f115bfdecefd87494b8337f82
1 /*
2 * $Revision: 2564 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of SubgraphUpwardPlanarizer class.
11 *
12 * \author Hoi-Ming Wong
13 *
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
16 *
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
20 *
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
27 *
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
39 *
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
42
43 #include <ogdf/upward/SubgraphUpwardPlanarizer.h>
44 #include <ogdf/upward/FeasibleUpwardPlanarSubgraph.h>
45 #include <ogdf/basic/simple_graph_alg.h>
46 #include <ogdf/basic/GraphCopy.h>
47 #include <ogdf/basic/Queue.h>
48 #include <ogdf/upward/UpwardPlanarModule.h>
49 #include <ogdf/upward/FaceSinkGraph.h>
50 #include <limits.h>
51
52 #ifdef OGDF_DEBUG
53 #include <ogdf/basic/GraphAttributes.h>
54 #include <ogdf/upward/LayerBasedUPRLayout.h>
55 #endif
56
57
58 namespace ogdf {
59
60 Module::ReturnType SubgraphUpwardPlanarizer::doCall(UpwardPlanRep &UPR,
61 const EdgeArray<int> &cost,
62 const EdgeArray<bool> &forbid)
63 {
64 const Graph &G = UPR.original();
65 GraphCopy GC(G);
66
67 //reverse some edges in order to obtain a DAG
68 List<edge> feedBackArcSet;
69 m_acyclicMod.get().call(GC, feedBackArcSet);
70 forall_listiterators(edge, it, feedBackArcSet) {
71 GC.reverseEdge(*it);
72 }
73
74 OGDF_ASSERT(isSimple(G));
75
76 //mapping cost
77 EdgeArray<int> cost_GC(GC);
78 edge e;
79 forall_edges(e, GC) {
80 if (forbid[GC.original(e)])
81 cost_GC[e] = INT_MAX;
82 else
83 cost_GC[e] = cost[GC.original(e)];
84 }
85
86 // tranform to single source graph by adding a super source s_hat and connect it with the other sources
87 EdgeArray<bool> sourceArcs(GC, false);
88 node s_hat = GC.newNode();
89 node v;
90 forall_nodes(v, GC) {
91 if (v->indeg() == 0 && v != s_hat) {
92 edge e_tmp = GC.newEdge(s_hat, v);
93 cost_GC[e_tmp] = 0; // crossings source arcs cause not cost
94 sourceArcs[e_tmp] = true;
95 }
96 }
97
98
99 /*
100 //------------------------------------------------debug
101 GraphAttributes AG_GC(GC, GraphAttributes::nodeGraphics|
102 GraphAttributes::edgeGraphics|
103 GraphAttributes::nodeColor|
104 GraphAttributes::edgeColor|
105 GraphAttributes::nodeLabel|
106 GraphAttributes::edgeLabel
107 );
108 AG_GC.setAllHeight(30.0);
109 AG_GC.setAllWidth(30.0);
110 node z;
111 forall_nodes(z, AG_GC.constGraph()) {
112 char str[255];
113 sprintf_s(str, 255, "%d", z->index()); // convert to string
114 AG_GC.labelNode(z) = str;
115 }
116 AG_GC.writeGML("c:/temp/GC.gml");
117 // --------------------------------------------end debug
118 */
119
120 BCTree BC(GC);
121 const Graph &bcTree = BC.bcTree();
122
123 GraphCopy G_dummy;
124 G_dummy.createEmpty(G);
125 NodeArray<GraphCopy> biComps(bcTree, G_dummy); // bicomps of G; init with an empty graph
126 UpwardPlanRep UPR_dummy;
127 UPR_dummy.createEmpty(G);
128 NodeArray<UpwardPlanRep> uprs(bcTree, UPR_dummy); // the upward planarized representation of the bicomps; init with an empty UpwarPlanRep
129
130 constructComponentGraphs(BC, biComps);
131
132 forall_nodes(v, bcTree) {
133
134 if (BC.typeOfBNode(v) == BCTree::CComp)
135 continue;
136
137 GraphCopy &block = biComps[v];
138
139 OGDF_ASSERT(m_subgraph.valid());
140
141 // construct a super source for this block
142 node s, s_block;
143 hasSingleSource(block, s);
144 s_block = block.newNode();
145 block.newEdge(s_block, s); //connect s
146
147 UpwardPlanarModule upMod;
148 UpwardPlanRep bestUPR;
149
150 //upward planarize if not upward planar
151 if (!upMod.upwardPlanarEmbed(block)) {
152
153 for(int i = 0; i < m_runs; i++) {// i multistarts
154 UpwardPlanRep UPR_tmp;
155 UPR_tmp.createEmpty(block);
156 List<edge> delEdges;
157
158 m_subgraph.get().call(UPR_tmp, delEdges);
159
160 UPR_tmp.augment();
161
162 //mark the source arcs of block
163 UPR_tmp.m_isSourceArc[UPR_tmp.copy(s_block->firstAdj()->theEdge())] = true;
164 adjEntry adj_tmp;
165 forall_adj(adj_tmp, UPR_tmp.copy(s_block->firstAdj()->theEdge()->target())) {
166 edge e_tmp = UPR_tmp.original(adj_tmp->theEdge());
167 if (e_tmp != 0 && block.original(e_tmp) != 0 && sourceArcs[block.original(e_tmp)])
168 UPR_tmp.m_isSourceArc[adj_tmp->theEdge()] = true;
169 }
170
171 //assign "crossing cost"
172 EdgeArray<int> cost_Block(block);
173 forall_edges(e, block) {
174 if (block.original(e) == 0 || GC.original(block.original(e)) == 0 )
175 cost_Block[e] = 0;
176 else
177 cost_Block[e] = cost_GC[block.original(e)];
178 }
179
180 /*
181 if (false) {
182 //---------------------------------------------------debug
183 LayerBasedUPRLayout uprLayout;
184 UpwardPlanRep upr_bug(UPR_tmp.getEmbedding());
185 adjEntry adj_bug = upr_bug.getAdjEntry(upr_bug.getEmbedding(), upr_bug.getSuperSource(), upr_bug.getEmbedding().externalFace());
186 node s_upr_bug = upr_bug.newNode();
187 upr_bug.getEmbedding().splitFace(s_upr_bug, adj_bug);
188 upr_bug.m_isSourceArc.init(upr_bug, false);
189 upr_bug.m_isSourceArc[s_upr_bug->firstAdj()->theEdge()] = true;
190 upr_bug.s_hat = s_upr_bug;
191 upr_bug.augment();
192
193 GraphAttributes GA_UPR_tmp(UPR_tmp, GraphAttributes::nodeGraphics|
194 GraphAttributes::edgeGraphics|
195 GraphAttributes::nodeColor|
196 GraphAttributes::edgeColor|
197 GraphAttributes::nodeLabel|
198 GraphAttributes::edgeLabel
199 );
200 GA_UPR_tmp.setAllHeight(30.0);
201 GA_UPR_tmp.setAllWidth(30.0);
202
203 uprLayout.call(upr_bug, GA_UPR_tmp);
204
205 // label the nodes with their index
206 node z;
207 forall_nodes(z, GA_UPR_tmp.constGraph()) {
208 char str[255];
209 sprintf_s(str, 255, "%d", z->index()); // convert to string
210 GA_UPR_tmp.labelNode(z) = str;
211 GA_UPR_tmp.y(z)=-GA_UPR_tmp.y(z);
212 GA_UPR_tmp.x(z)=-GA_UPR_tmp.x(z);
213 }
214 edge eee;
215 forall_edges(eee, GA_UPR_tmp.constGraph()) {
216 DPolyline &line = GA_UPR_tmp.bends(eee);
217 ListIterator<DPoint> it;
218 for(it = line.begin(); it.valid(); it++) {
219 (*it).m_y = -(*it).m_y;
220 (*it).m_x = -(*it).m_x;
221 }
222 }
223 GA_UPR_tmp.writeGML("c:/temp/UPR_tmp_fups.gml");
224 cout << "UPR_tmp/fups faces:";
225 UPR_tmp.outputFaces(UPR_tmp.getEmbedding());
226 //end -----------------------------------------------debug
227 }
228 */
229
230 delEdges.permute();
231 m_inserter.get().call(UPR_tmp, cost_Block, delEdges);
232
233 if (i != 0) {
234 if (UPR_tmp.numberOfCrossings() < bestUPR.numberOfCrossings()) {
235 //cout << endl << "new cr_nr:" << UPR_tmp.numberOfCrossings() << " old cr_nr : " << bestUPR.numberOfCrossings() << endl;
236 bestUPR = UPR_tmp;
237 }
238 }
239 else
240 bestUPR = UPR_tmp;
241 }//for
242 }
243 else { //block is upward planar
244 CombinatorialEmbedding Gamma(block);
245 FaceSinkGraph fsg((const CombinatorialEmbedding &)Gamma, s_block);
246 SList<face> faceList;
247 fsg.possibleExternalFaces(faceList);
248 Gamma.setExternalFace(faceList.front());
249
250 UpwardPlanRep UPR_tmp(Gamma);
251 UPR_tmp.augment();
252
253 //mark the source arcs of block
254 UPR_tmp.m_isSourceArc[UPR_tmp.copy(s->firstAdj()->theEdge())] = true;
255 adjEntry adj_tmp;
256 forall_adj(adj_tmp, UPR_tmp.copy(s->firstAdj()->theEdge()->target())) {
257 edge e_tmp = UPR_tmp.original(adj_tmp->theEdge());
258 if (e_tmp != 0 && block.original(e_tmp) != 0 && sourceArcs[block.original(e_tmp)])
259 UPR_tmp.m_isSourceArc[adj_tmp->theEdge()] = true;
260 }
261
262 bestUPR = UPR_tmp;
263
264 /*
265 //debug
266 //---------------------------------------------------debug
267 GraphAttributes GA_UPR_tmp(UPR_tmp, GraphAttributes::nodeGraphics|
268 GraphAttributes::edgeGraphics|
269 GraphAttributes::nodeColor|
270 GraphAttributes::edgeColor|
271 GraphAttributes::nodeLabel|
272 GraphAttributes::edgeLabel
273 );
274 GA_UPR_tmp.setAllHeight(30.0);
275 GA_UPR_tmp.setAllWidth(30.0);
276
277 // label the nodes with their index
278 forall_nodes(z, GA_UPR_tmp.constGraph()) {
279 char str[255];
280 sprintf_s(str, 255, "%d", z->index()); // convert to string
281 GA_UPR_tmp.labelNode(z) = str;
282 GA_UPR_tmp.y(z)=-GA_UPR_tmp.y(z);
283 GA_UPR_tmp.x(z)=-GA_UPR_tmp.x(z);
284 }
285 edge eee;
286 forall_edges(eee, GA_UPR_tmp.constGraph()) {
287 DPolyline &line = GA_UPR_tmp.bends(eee);
288 ListIterator<DPoint> it;
289 for(it = line.begin(); it.valid(); it++) {
290 (*it).m_y = -(*it).m_y;
291 (*it).m_x = -(*it).m_x;
292 }
293 }
294 GA_UPR_tmp.writeGML("c:/temp/UPR_tmp_fups.gml");
295 cout << "UPR_tmp/fups faces:";
296 UPR_tmp.outputFaces(UPR_tmp.getEmbedding());
297 //end -----------------------------------------------debug
298 */
299
300 }
301 uprs[v] = bestUPR;
302 }//forall_nodes
303
304 // compute the number of crossings
305 int nr_cr = 0;
306 forall_nodes(v, bcTree) {
307 if (BC.typeOfBNode(v) != BCTree::CComp)
308 nr_cr = nr_cr + uprs[v].numberOfCrossings();
309 }
310
311 //merge all component to a graph
312 node parent_BC = BC.bcproper(s_hat);
313 NodeArray<bool> nodesDone(bcTree, false);
314 dfsMerge(GC, BC, biComps, uprs, UPR, 0, parent_BC, nodesDone); // start with the component which contains the super source s_hat
315
316 //augment to single sink graph
317 UPR.augment();
318
319 //set crossings
320 UPR.crossings = nr_cr;
321
322
323 //------------------------------------------------debug
324 /*
325 LayerBasedUPRLayout uprLayout;
326 UpwardPlanRep upr_bug(UPR.getEmbedding());
327 adjEntry adj_bug = upr_bug.getAdjEntry(upr_bug.getEmbedding(), upr_bug.getSuperSource(), upr_bug.getEmbedding().externalFace());
328 node s_upr_bug = upr_bug.newNode();
329 upr_bug.getEmbedding().splitFace(s_upr_bug, adj_bug);
330 upr_bug.m_isSourceArc.init(upr_bug, false);
331 upr_bug.m_isSourceArc[s_upr_bug->firstAdj()->theEdge()] = true;
332 upr_bug.s_hat = s_upr_bug;
333 upr_bug.augment();
334 GraphAttributes AG(UPR, GraphAttributes::nodeGraphics|
335 GraphAttributes::edgeGraphics|
336 GraphAttributes::nodeColor|
337 GraphAttributes::edgeColor|
338 GraphAttributes::nodeLabel|
339 GraphAttributes::edgeLabel
340 );
341 AG.setAllHeight(30.0);
342 AG.setAllWidth(30.0);
343
344 uprLayout.call(upr_bug, AG);
345
346 forall_nodes(v, AG.constGraph()) {
347 int idx;
348 idx = v->index();
349
350
351 if (UPR.original(v) != 0)
352 idx = UPR.original(v)->index();
353
354
355 char str[255];
356 sprintf_s(str, 255, "%d", idx); // convert to string
357 AG.labelNode(v) = str;
358 if (UPR.isDummy(v))
359 AG.colorNode(v) = "#ff0000";
360 AG.y(v)=-AG.y(v);
361 }
362 // label the edges with their index
363 forall_edges(e, AG.constGraph()) {
364 char str2[255];
365 sprintf_s(str2, 255, "%d", e->index()); // convert to string
366 AG.labelEdge(e) = str2;
367 if (UPR.isSourceArc(e))
368 AG.colorEdge(e) = "#00ff00";
369 if (UPR.isSinkArc(e))
370 AG.colorEdge(e) = "#ff0000";
371
372 DPolyline &line = AG.bends(e);
373 ListIterator<DPoint> it;
374 for(it = line.begin(); it.valid(); it++) {
375 (*it).m_y = -(*it).m_y;
376 }
377 }
378 AG.writeGML("c:/temp/upr_res.gml");
379 //cout << "UPR_RES";
380 //UPR.outputFaces(UPR.getEmbedding());
381 //cout << "Mapping :" << endl;
382 //forall_nodes(v, UPR) {
383 // if (UPR.original(v) != 0) {
384 // cout << "node UPR " << v << " node G " << UPR.original(v) << endl;
385 // }
386 //}
387 // --------------------------------------------end debug
388 */
389
390 #ifdef OGDF_DEBUG
391 UpwardPlanarModule upMod;
392 #endif
393 OGDF_ASSERT(hasSingleSource(UPR));
394 OGDF_ASSERT(isSimple(UPR));
395 OGDF_ASSERT(isAcyclic(UPR));
396 OGDF_ASSERT(upMod.upwardPlanarityTest(UPR));
397
398 /*
399 edge eee;
400 forall_edges(eee, UPR.original()) {
401 if (UPR.isReversed(eee))
402 cout << endl << eee << endl;
403 }
404 */
405 return Module::retFeasible;
406 }
407
408
409
410 void SubgraphUpwardPlanarizer::dfsMerge(
411 const GraphCopy &GC,
412 BCTree &BC,
413 NodeArray<GraphCopy> &biComps,
414 NodeArray<UpwardPlanRep> &uprs,
415 UpwardPlanRep &UPR_res,
416 node parent_BC,
417 node current_BC,
418 NodeArray<bool> &nodesDone)
419 {
420 // only one component.
421 if (current_BC->degree() == 0) {
422 merge(GC, UPR_res, biComps[current_BC], uprs[current_BC]);
423 return;
424 }
425
426 adjEntry adj;
427 forall_adj(adj, current_BC) {
428 node next_BC = adj->twin()->theNode();
429 if (BC.typeOfBNode(current_BC) == BCTree::CComp) {
430 if (parent_BC != 0 && !nodesDone[parent_BC]) {
431 merge(GC, UPR_res, biComps[parent_BC], uprs[parent_BC]);
432 nodesDone[parent_BC] = true;
433 }
434 if (!nodesDone[next_BC]) {
435 merge(GC, UPR_res, biComps[next_BC], uprs[next_BC]);
436 nodesDone[next_BC] = true;
437 }
438 }
439 if (next_BC != parent_BC )
440 dfsMerge(GC, BC, biComps, uprs, UPR_res, current_BC, next_BC, nodesDone);
441 }
442 }
443
444
445
446 void SubgraphUpwardPlanarizer::merge(
447 const GraphCopy &GC,
448 UpwardPlanRep &UPR_res,
449 const GraphCopy &block,
450 UpwardPlanRep &UPR)
451 {
452 node startUPR = UPR.getSuperSource()->firstAdj()->theEdge()->target();
453 node startRes;
454
455 node startG = GC.original(block.original(UPR.original(startUPR)));
456
457 bool empty = UPR_res.empty();
458
459 if (empty) {
460
461 OGDF_ASSERT(startG == 0);
462
463 // contruct a node in UPR_res assocciated with startUPR
464 startRes = UPR_res.newNode();
465 UPR_res.m_isSinkArc.init(UPR_res, false);
466 UPR_res.m_isSourceArc.init(UPR_res, false);
467 UPR_res.s_hat = startRes;
468 }
469 else {
470 startRes = UPR_res.copy(startG);
471 }
472
473 OGDF_ASSERT(startRes != 0);
474
475 // compute the adjEntry position (in UPR_res) of the cutvertex startRes
476 adjEntry pos = 0;
477 if (!empty) {
478 adjEntry run, adj_ext = 0, adj_int = 0;
479 forall_adj(run, startRes) {
480 if (UPR_res.getEmbedding().rightFace(run) == UPR_res.getEmbedding().externalFace()) {
481 adj_ext = run;
482 break;
483 }
484 if (run->theEdge()->source() == startRes)
485 adj_int = run;
486 }
487 // cutvertex is a sink in UPR_res
488 if (adj_ext == 0 && adj_int == 0) {
489 pos = UPR_res.sinkSwitchOf(startRes);
490 }
491 else {
492 if (adj_ext == 0)
493 pos = adj_int;
494 else
495 pos = adj_ext;
496 }
497 OGDF_ASSERT(pos != 0);
498 }
499
500 // construct for each node (except the two super sink and the super source) of UPR a associated of UPR to UPR_res
501 NodeArray<node> nodeUPR2UPR_res(UPR, 0);
502 nodeUPR2UPR_res[startUPR] = startRes;
503 node v;
504 forall_nodes(v, UPR) {
505
506 // allready constructed or is super sink or super source
507 if (v == startUPR || v == UPR.getSuperSink() || v == UPR.getSuperSink()->firstAdj()->theEdge()->source() || v == UPR.getSuperSource())
508 continue;
509
510 node vNew;
511 if (UPR.original(v) != 0 ) {
512 node vG = GC.original(block.original((UPR.original(v))));
513 if (vG != 0)
514 vNew = UPR_res.newNode(vG);
515 else
516 vNew = UPR_res.newNode(); //vG is the super source
517 }
518 else // crossing dummy, no original node
519 vNew = UPR_res.newNode();
520 nodeUPR2UPR_res[v] = vNew;
521 }
522
523 //add edges of UPR to UPR_res
524 EdgeArray<edge> edgeUPR2UPR_res(UPR, 0);
525 edge e;
526 forall_edges(e, block) {
527
528 if (e->source()->indeg()==0) // the artificial edge with the super source
529 continue;
530
531 List<edge> chains = UPR.chain(e);
532 edge eG = 0, eGC = block.original(e);
533 eG = GC.original(eGC);
534
535 OGDF_ASSERT(!chains.empty());
536
537 //construct new edges in UPR_res
538 forall_listiterators(edge, it, chains) {
539 node tgt = nodeUPR2UPR_res[(*it)->target()];
540 node src = nodeUPR2UPR_res[(*it)->source()];
541 edge eNew = UPR_res.newEdge(src, tgt);
542 edgeUPR2UPR_res[*it] = eNew;
543
544 if (UPR.isSinkArc(UPR.copy(e)))
545 UPR_res.m_isSinkArc[eNew] = true;
546 if (UPR.isSourceArc(UPR.copy(e)))
547 UPR_res.m_isSourceArc[eNew] = true;
548
549 if (eG == 0) { // edge is associated with a sink arc
550 UPR_res.m_eOrig[eNew] = 0;
551 continue;
552 }
553
554 UPR_res.m_eOrig[eNew] = eG;
555 if (chains.size() == 1) { // e is not split
556 UPR_res.m_eCopy[eG].pushBack(eNew);
557 UPR_res.m_eIterator[eNew] = UPR_res.m_eCopy[eG].begin();
558 break;
559 }
560 UPR_res.m_eCopy[eG].pushBack(eNew);
561 UPR_res.m_eIterator[eNew] = UPR_res.m_eCopy[eG].rbegin();
562 }
563 }
564
565
566 ///*
567 //* embed the new component in UPR_res with respect to the embedding of UPR
568 //*/
569
570 // for the cut vertex
571 if (!empty) {
572 adjEntry run = UPR.getAdjEntry(UPR.getEmbedding(), startUPR, UPR.getEmbedding().externalFace());
573 run = run->cyclicSucc();
574 adjEntry adjStart = run;
575 do {
576 if (edgeUPR2UPR_res[run->theEdge()] != 0) {
577 adjEntry adj_UPR_res = edgeUPR2UPR_res[run->theEdge()]->adjSource();
578 UPR_res.moveAdjAfter(adj_UPR_res, pos);
579 pos = adj_UPR_res;
580 }
581 run = run->cyclicSucc();
582 } while(run != adjStart);
583 }
584
585 forall_nodes(v, UPR) {
586 if (v == startUPR && !empty)
587 continue;
588
589 node v_UPR_res = nodeUPR2UPR_res[v];
590 List<adjEntry> adj_UPR, adj_UPR_res;
591 UPR.adjEntries(v, adj_UPR);
592
593 // convert adj_UPR of v to adj_UPR_res of v_UPR_res
594 forall_listiterators(adjEntry, it, adj_UPR) {
595 edge e_res = edgeUPR2UPR_res[(*it)->theEdge()];
596 if (e_res == 0) // associated edges in UPR_res
597 continue;
598 adjEntry adj_res = e_res->adjSource();
599 if (adj_res->theNode() != v_UPR_res)
600 adj_res = adj_res->twin();
601 adj_UPR_res.pushBack(adj_res);
602 }
603
604 UPR_res.sort(v_UPR_res, adj_UPR_res);
605 }
606
607 /*
608 //---------------------------------------------------debug
609 if (!UPR_res.empty()) {
610 GraphAttributes GA_UPR_res(UPR_res, GraphAttributes::nodeGraphics|
611 GraphAttributes::edgeGraphics|
612 GraphAttributes::nodeColor|
613 GraphAttributes::edgeColor|
614 GraphAttributes::nodeLabel|
615 GraphAttributes::edgeLabel
616 );
617 GA_UPR_res.setAllHeight(30.0);
618 GA_UPR_res.setAllWidth(30.0);
619 node z;
620 // label the nodes with their index
621 forall_nodes(z, GA_UPR_res.constGraph()) {
622 char str[255];
623 sprintf_s(str, 255, "%d", z->index()); // convert to string
624 GA_UPR_res.labelNode(z) = str;
625 }
626 GA_UPR_res.writeGML("c:/temp/UPR_res_tmp.gml");
627 cout << "UPR_res_tmp faces:";
628 UPR_res.outputFaces(UPR_res.getEmbedding());
629 }
630
631 GraphAttributes GA_UPR(UPR, GraphAttributes::nodeGraphics|
632 GraphAttributes::edgeGraphics|
633 GraphAttributes::nodeColor|
634 GraphAttributes::edgeColor|
635 GraphAttributes::nodeLabel|
636 GraphAttributes::edgeLabel
637 );
638 GA_UPR.setAllHeight(30.0);
639 GA_UPR.setAllWidth(30.0);
640 node z;
641 // label the nodes with their index
642 forall_nodes(z, GA_UPR.constGraph()) {
643 char str[255];
644 sprintf_s(str, 255, "%d", z->index()); // convert to string
645 GA_UPR.labelNode(z) = str;
646 }
647 GA_UPR.writeGML("c:/temp/UPR_tmp.gml");
648 cout << "UPR_tmp faces:";
649 UPR.outputFaces(UPR.getEmbedding());
650 //end -----------------------------------------------debug
651 */
652
653 // update UPR_res
654 UPR_res.initMe();
655 }
656
657
658 void SubgraphUpwardPlanarizer::constructComponentGraphs(BCTree &BC, NodeArray<GraphCopy> &biComps)
659 {
660 NodeArray<int> constructed(BC.originalGraph(), -1);
661 const Graph &bcTree = BC.bcTree();
662 node v;
663 int i = 0; // comp. number
664 forall_nodes(v, bcTree) {
665
666 if (BC.typeOfBNode(v) == BCTree::CComp)
667 continue;
668
669 const SList<edge> &edges_comp = BC.hEdges(v); //bicomp edges
670 List<edge> edges_orig;
671 forall_slistiterators(edge, it, edges_comp)
672 edges_orig.pushBack(BC.original(*it));
673
674 GraphCopy GC;
675 GC.createEmpty(BC.originalGraph());
676 // construct i-th component graph
677 forall_listiterators(edge, it, edges_orig) {
678 node srcOrig = (*it)->source();
679 node tgtOrig = (*it)->target();
680 if (constructed[srcOrig] != i) {
681 constructed[srcOrig] = i;
682 GC.newNode(srcOrig);
683 }
684 if (constructed[tgtOrig] != i) {
685 constructed[tgtOrig] = i;
686 GC.newNode(tgtOrig);
687 }
688 GC.newEdge(*it);
689 }
690 biComps[v] = GC;
691 i++;
692 }
693 }
694
695 }
Windows Explorer Extension to Operate Git