?  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 / orthogonal / ClusterOrthoShaper.cpp
blob197d5d670ca5b44f01fa9963185711cf1ff5b04d
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 the Orthogonal Representation of a Planar
11 * Representation of a UML Graph.
12 *
13 * \author Karsten Klein
14 *
15 * \par License:
16 * This file is part of the Open Graph Drawing Framework (OGDF).
17 *
18 * \par
19 * Copyright (C)<br>
20 * See README.txt in the root directory of the OGDF installation for details.
21 *
22 * \par
23 * This program is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU General Public License
25 * Version 2 or 3 as published by the Free Software Foundation;
26 * see the file LICENSE.txt included in the packaging of this file
27 * for details.
28 *
29 * \par
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
34 *
35 * \par
36 * You should have received a copy of the GNU General Public
37 * License along with this program; if not, write to the Free
38 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
39 * Boston, MA 02110-1301, USA.
40 *
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
43
44
45 #include <ogdf/cluster/ClusterOrthoShaper.h>
46 #include <ogdf/basic/FaceArray.h>
47 #include <limits.h>
48 #include <ogdf/graphalg/MinCostFlowReinelt.h>
49
50
51 const int flowBound = 4; //No more than 4 bends in cage boundary,
52 //and no more than 360 degrees at vertices
53
54 enum netArcType {defaultArc, angle, backAngle, bend};
55
56 namespace ogdf {
57
58
59 //*************************************************************
60 //call function: compute a flow in a dual network and interpret
61 //result as bends and angles (representation shape)
62 void ClusterOrthoShaper::call(ClusterPlanRep &PG,
63 CombinatorialEmbedding &E,
64 OrthoRep &OR,
65 int startBoundBendsPerEdge,
66 bool fourPlanar)
67 {
68
69 if (PG.numberOfEdges() == 0)
70 return;
71
72 m_fourPlanar = fourPlanar;
73
74 // the min cost flow we use
75 MinCostFlowReinelt flowModule;
76 const int infinity = flowModule.infinity();
77
78 //************************************************************
79 //fix some values depending on traditional or progressive mode
80 //************************************************************
81
82 //standard flow boundaries for traditional and progressive mode
83 const int upperAngleFlow = (m_traditional ? 4 : 1); //non zero
84 const int maxAngleFlow = (m_traditional ? 4 : 2); //use 2 for multialign zero degree
85 const int maxBackFlow = 2; //maximal flow on back arcs in progressive mode
86 const int upperBackAngleFlow = 2; // and 360 back (only progressive mode)
87 const int lowerAngleFlow = (m_traditional ? 1 : 0);
88 const int piAngleFlow = (m_traditional ? 2 : 0);
89 const int halfPiAngleFlow = 1;
90 //const int halfPiBackAngleFlow = 0; //(only progressive mode)
91 const int zeroAngleFlow = (m_traditional ? 0 : 2);
92 const int zeroBackAngleFlow = 0; //(only progressive mode)
93
94 //in progressive mode, angles need cost to work out properly
95 //const int tradAngleCost = 0;
96 const int progAngleCost = 1;
97 const int tradBendCost = 1;
98 const int progBendCost = 3*PG.numberOfNodes(); //should use supply
99 PG.getClusterGraph().setUpdateDepth(true);
100 const int clusterTreeDepth = PG.getClusterGraph().treeDepth();
101
102
103 OR.init(E);
104 FaceArray<node> F(E);
105
106 OGDF_ASSERT(PG.representsCombEmbedding())
107 OGDF_ASSERT(F.valid())
108
109
110
111 //******************
112 // NETWORK VARIABLES
113 //******************
114
115 Graph Network; //the dual network
116 EdgeArray<int> lowerBound(Network,0); // lower bound for flow
117 EdgeArray<int> upperBound(Network,0); // upper bound for flow
118
119 EdgeArray<int> cost(Network,0); // cost of an edge
120 NodeArray<int> supply(Network,0); // supply of every node
121
122
123 //alignment helper
124 NodeArray<bool> fixedVal(Network, false); //already set somewhere
125 EdgeArray<bool> noBendEdge(Network, false); //for splitter, brother edges etc.
126
127 //*********************************
128 //NETWORK TO PlanRep INFORMATION
129
130 // stores for edges of the Network the corresponding adjEntries
131 // nodes, and faces of PG
132 EdgeArray<adjEntry> adjCor(Network,0);
133 EdgeArray<node> nodeCor(Network,0);
134 EdgeArray<face> faceCor(Network,0);
135
136 NodeArray<n_type> nodeType(Network, low);
137
138 //*********************************
139 //PlanRep TO NETWORK INFORMATION
140
141 //Contains for every node of PG the corresponding node in the network
142 NodeArray<node> networkNode(PG,0);
143 //Contains for every adjEntry of PG the corresponding edge in the network
144 AdjEntryArray<edge> backAdjCor(PG,0); //bends
145 //contains for every adjEntry of PG the corresponding angle arc in the network
146 //note: this doesn't need to correspond to resulting drawing angles
147 //bends on the boundary define angles at expanded nodes
148 AdjEntryArray<edge> angleArc(PG, 0); //angle
149 //contains the corresponding back arc face to node in progressive mode
150 AdjEntryArray<edge> angleBackArc(PG, 0); //angle
151
152 //******************
153 // OTHER INFORMATION
154
155 // Contains for adjacency Entry of PG the face it belongs to in PG
156 AdjEntryArray<face> adjF(PG,0);
157
158 //Contains for angle network arc progressive mode backward arc
159 EdgeArray<edge> angleTwin(Network, 0);
160
161 //types of network edges, to be used in flow to values
162 EdgeArray<netArcType> l_arcType(Network, angle);
163
164 //contains the outer face
165 //face theOuterFace = E.externalFace();
166
167 //*******************
168 // STANDARD VARIABLES
169
170 node v;
171 adjEntry adj;
172 edge e;
173
174
175 //**********************************
176 // GENERATE ALL NODES OF THE NETWORK
177 //**********************************
178
179 //corresponding to the graphs nodes
180 int checksum = 0;
181 forall_nodes(v,PG)
182 {
183 OGDF_ASSERT((!m_fourPlanar) || (v->degree() < 5));
184
185 networkNode[v] = Network.newNode();
186 //maybe install a shortcut here for degree 4 nodes if not expanded
187
188 if (v->degree() > 4) nodeType[networkNode[v]] = high;
189 else nodeType[networkNode[v]] = low;
190
191 //already set the supply
192 if (m_traditional) supply[networkNode[v]] = 4;
193 else supply[networkNode[v]] = 2*v->degree() - 4;
194
195 checksum += supply[networkNode[v]];
196 }
197
198 //corresponding to the graphs faces
199 face f;
200 for (f = E.firstFace(); f; f = f->succ())
201 {
202 F[f] = Network.newNode();
203
204 if (f == E.externalFace())
205 {
206 nodeType[F[f]] = outer;
207 if (m_traditional) supply[F[f]] = - 2*f->size() - 4;
208 else supply[F[f]] = 4;
209 }
210 else {
211 nodeType[F[f]] = inner;
212 if (m_traditional) supply[F[f]] = - 2*f->size() + 4;
213 else supply[F[f]] = -4;
214 }
215 }
216
217 #ifdef OGDF_DEBUG
218 //check the supply sum
219 checksum = 0;
220 forall_nodes(v, Network)
221 checksum += supply[v];
222 OGDF_ASSERT(checksum == 0);
223 #endif
224
225
226 #ifdef OGDF_DEBUG
227 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)) {
228 forall_nodes(v,PG)
229 cout << " v = " << v << " corresponds to "
230 << networkNode[v] << endl;
231 for (f = E.firstFace(); f; f = f->succ()) {
232 cout << " face = " << f->index() << " corresponds to " << F[f];
233 if (f == E.externalFace())
234 cout<<" (Outer Face)";
235 cout << endl;
236 }
237 }
238 #endif
239
240
241
242 //**********************************
243 // GENERATE ALL EDGES OF THE NETWORK
244 //**********************************
245
246 // OPTIMIZATION POTENTIAL:
247 // Do not insert edges with upper bound 0 into the network.
248
249 // Locate for every adjacency entry its adjacent faces.
250 for (f = E.firstFace(); f; f = f->succ())
251 {
252 forall_face_adj(adj,f)
253 adjF[adj] = f;
254 }
255
256 #ifdef OGDF_DEBUG
257 if(int(ogdf::debugLevel) >= int(dlHeavyChecks)) {
258 for(f = E.firstFace(); f; f = f->succ()) {
259 cout << "Face " << f->index() << " : ";
260 forall_face_adj(adj,f)
261 cout << adj << "; ";
262 cout<<endl;
263 }
264 }
265 #endif
266
267 //*********************************************
268 // Insert for every edge the (two) network arcs
269 // entering the face nodes, flow defines bends on the edge
270 forall_edges(e,PG)
271 {
272 OGDF_ASSERT(adjF[e->adjSource()] && adjF[e->adjTarget()])
273 if (F[adjF[e->adjSource()]] != F[adjF[e->adjTarget()]])
274 {
275 // not a selfloop.
276 edge newE = Network.newEdge(F[adjF[e->adjSource()]],F[adjF[e->adjTarget()]]);
277
278 l_arcType[newE] = bend;
279
280 adjCor[newE] = e->adjSource();
281 if ( (PG.typeOf(e) == Graph::generalization) ||
282 (PG.isClusterBoundary(e) && (!m_traditional)))
283 upperBound[newE] = 0;
284 else
285 upperBound[newE] = infinity;
286 cost[newE] = (m_traditional ?
287 clusterTradBendCost(PG.getClusterGraph().clusterDepth(PG.clusterOfEdge(e)), clusterTreeDepth, tradBendCost) :
288 clusterProgBendCost(PG.getClusterGraph().clusterDepth(PG.clusterOfEdge(e)), clusterTreeDepth, progBendCost));
289
290 backAdjCor[e->adjSource()] = newE;
291
292 newE = Network.newEdge(F[adjF[e->adjTarget()]],F[adjF[e->adjSource()]]);
293
294 l_arcType[newE] = bend;
295
296 adjCor[newE] = e->adjTarget();
297 if ((PG.typeOf(e) == Graph::generalization) ||
298 (PG.isClusterBoundary(e) && (m_traditional)))
299 upperBound[newE] = 0;
300 else
301 upperBound[newE] = infinity;
302 cost[newE] = (m_traditional ?
303 clusterTradBendCost(PG.getClusterGraph().clusterDepth(PG.clusterOfEdge(e)), clusterTreeDepth, tradBendCost) :
304 clusterProgBendCost(PG.getClusterGraph().clusterDepth(PG.clusterOfEdge(e)), clusterTreeDepth, progBendCost));
305 backAdjCor[e->adjTarget()] = newE;
306 }
307 }
308
309
310 //*****************************************************************
311 // insert for every node edges to all appearances of adjacent faces
312 // flow defines angles at nodes
313 // progressive: and vice-versa
314 //*****************************************************************
315
316
317 //************************************************************
318 // Observe that two generalizations are not allowed to bend on
319 // a node. There must be a 180 degree angle between them.
320
321 // assure that there is enough flow between adjacent generalizations
322 NodeArray<bool> genshift(PG, false);
323
324 //non-expanded vertex
325 forall_nodes(v,PG)
326 {
327 //*****************************************
328 // Locate possible adjacent generalizations
329 adjEntry gen1 = 0;
330 adjEntry gen2 = 0;
331
332 if (PG.typeOf(v) != Graph::generalizationMerger
333 && PG.typeOf(v) != Graph::generalizationExpander)
334 {
335 forall_adj(adj,v)
336 {
337 if (PG.typeOf(adj->theEdge()) == Graph::generalization)
338 {
339 if (!gen1) gen1 = adj;
340 else gen2 = adj;
341 }
342 }
343 }// if not generalization
344
345
346 forall_adj(adj,v)
347 {
348 edge e2 = Network.newEdge(networkNode[v],F[adjF[adj]]);
349
350 l_arcType[e2] = angle;
351
352 //CHECK bounded edges? and upper == 2 for zero degree
353 //progressive and traditional
354 upperBound[e2] = upperAngleFlow;
355 nodeCor [e2] = v;
356 adjCor [e2] = adj;
357 faceCor [e2] = adjF[adj];
358 angleArc [adj] = e2;
359
360 //do not allow zero degree at non-expanded vertex
361 //&& !m_allowLowZero
362
363 //progressive and traditional (compatible)
364 if (m_fourPlanar) lowerBound[e2] = lowerAngleFlow; //trad 1 = 90, prog 0 = 180
365
366 //insert opposite arcs face to node in progressive style
367 edge e3;
368 if (!m_traditional)
369 {
370 e3 = Network.newEdge(F[adjF[adj]], networkNode[v]); //flow for >180 degree
371
372 l_arcType[e3] = backAngle;
373
374 angleTwin[e2] = e3;
375 angleTwin[e3] = e2;
376
377 cost[e2] = progAngleCost;
378 cost[e3] = progAngleCost;
379
380 lowerBound[e3] = lowerAngleFlow; //180 degree,check highdegree drawings
381 upperBound[e3] = upperBackAngleFlow; //infinity;
382 //nodeCor [e3] = v; has no node, is face to node
383 adjCor [e3] = adj;
384 faceCor [e3] = adjF[adj];
385 angleBackArc[adj] = e3;
386
387 }//progressive
388 }//initialize
389
390 //second run to have all angleArcs already initialized
391 //set the flow boundaries
392 forall_adj(adj,v)
393 {
394 edge e2 = angleArc[adj];
395 edge e3 = 0;
396 if (!m_traditional) e3 = angleTwin[e2];
397
398 //allow low degree node zero degree angle for non-expanded vertices
399 //if (false) {
400 // if ((gen1 || gen2) && (PG.isVertex(v)))
401 // {
402 // lowerBound[e2] = 0;
403 // }
404 //}
405 //*******************************************************************
406 //*******************************************************************
407
408 //hier muss man fuer die Kanten, die rechts ansetzen noch lowerbound 2 setzen
409
410 if (gen2 == adj && gen1 == adj->cyclicSucc())
411 {
412 upperBound[e2] = piAngleFlow;
413 lowerBound[e2] = piAngleFlow;
414 if (e3 && !m_traditional)
415 {
416 upperBound[e3] = 0;
417 lowerBound[e3] = 0;
418 }
419 genshift[v] = true;
420 }
421 else if (gen1 == adj && gen2 == adj->cyclicSucc())
422 {
423 upperBound[e2] = piAngleFlow;
424 lowerBound[e2] = piAngleFlow;
425 if (e3 && !m_traditional)
426 {
427 upperBound[e3] = 0;
428 lowerBound[e3] = 0;
429 }//progressive
430 genshift[v] = true;
431 }
432 }
433 }//forall_nodes
434
435
436 //***************************************************
437 // Reset upper and lower Bounds for network arcs that
438 // correspond to edges of generalizationmerger faces
439 // and edges of expanded nodes.
440
441
442 forall_nodes(v,PG)
443 {
444 if (PG.expandAdj(v))
445 {
446 adj = PG.expandAdj(v);
447 // Get the corresponding face in the original embedding.
448 f = adjF[adj];
449
450 //***********************+
451 //expanded merger cages
452 if (PG.typeOf(v) == Graph::generalizationMerger)
453 {
454 // Set upperBound to 0 for all edges.
455 forall_face_adj(adj,f)
456 {
457 //no bends on boundary (except special case following)
458 upperBound[backAdjCor[adj]] = 0;
459 upperBound[backAdjCor[adj->twin()]] = 0;
460
461 // Node w is in Network
462 node w = networkNode[adj->twinNode()];
463 forall_adj_edges(e,w)
464 {
465 if (e->target() == F[f])
466 {
467 //is this: 180 degree?
468 lowerBound[e] = piAngleFlow; //traditional: 2 progressive: 0
469 upperBound[e] = piAngleFlow;
470 if (!m_traditional)
471 {
472 edge aTwin = angleTwin[e];
473 if (aTwin)
474 {
475 upperBound[aTwin] = 0;
476 lowerBound[aTwin] = 0;
477 }
478 }//if not traditional limit angle back arc
479
480 }
481 }
482
483 }
484 //special bend case
485 // Set the upper and lower bound for the first edge of
486 // the mergeexpander face to guarantee a 90 degree bend.
487 if (m_traditional)
488 {
489 upperBound[backAdjCor[PG.expandAdj(v)]] = 1;
490 lowerBound[backAdjCor[PG.expandAdj(v)]]= 1;
491 }
492 else
493 {
494 //progressive mode: bends are in opposite direction
495 upperBound[backAdjCor[PG.expandAdj(v)->twin()]] = 1;
496 lowerBound[backAdjCor[PG.expandAdj(v)->twin()]]= 1;
497 }
498
499 // Set the upper and lower bound for the first node in
500 // clockwise order of the mergeexpander face to
501 // guaranty a 90 degree angle at the node in the interior
502 // and a 180 degree angle between the generalizations in the
503 // exterior.
504 node secFace;
505
506 if (F[f] == backAdjCor[PG.expandAdj(v)]->target())
507 secFace = backAdjCor[PG.expandAdj(v)]->source();
508 else if (F[f] == backAdjCor[PG.expandAdj(v)]->source())
509 secFace = backAdjCor[PG.expandAdj(v)]->target();
510 else
511 {
512 OGDF_ASSERT(false); // Edges in Network mixed up.
513 }
514 node w = networkNode[PG.expandAdj(v)->twinNode()];
515
516 forall_adj(adj,w)
517 {
518 if (adj->theEdge()->target() == F[f])
519 {
520 lowerBound[adj->theEdge()] = 1;
521 upperBound[adj->theEdge()] = 1;
522 if (!m_traditional)
523 {
524 edge aTwin = angleTwin[adj->theEdge()];
525 if (aTwin)
526 {
527 upperBound[aTwin] = 0;
528 lowerBound[aTwin] = 0;
529 }
530 }//if not traditional limit angle back arc
531 break;
532 }
533 }
534
535 if (m_traditional)
536 e = adj->cyclicSucc()->theEdge();
537 else
538 {
539 //we have two edges instead of one per face
540 adjEntry ae = adj->cyclicSucc();
541 e = ae->theEdge();
542 if (e->target() != secFace)
543 //maybe we have to jump one step further
544 e = ae->cyclicSucc()->theEdge();
545
546 }//progressive mode
547
548 if (e->target() == secFace)
549 {
550 lowerBound[e] = piAngleFlow;
551 upperBound[e] = piAngleFlow;
552 if (!m_traditional)
553 {
554 edge aTwin = angleTwin[e];
555 if (aTwin)
556 {
557 upperBound[aTwin] = piAngleFlow;
558 lowerBound[aTwin] = piAngleFlow;
559 }
560 }//if not traditional limit angle back arc
561 }
562
563 // Set the upper and lower bound for the last edge of
564 // the mergeexpander face to guarantee a 90 degree bend.
565 if (m_traditional)
566 {
567 upperBound[backAdjCor[PG.expandAdj(v)->faceCyclePred()]] = 1;
568 lowerBound[backAdjCor[PG.expandAdj(v)->faceCyclePred()]] = 1;
569 }
570 else
571 {
572 //progressive mode: bends are in opposite direction
573 upperBound[backAdjCor[PG.expandAdj(v)->faceCyclePred()->twin()]] = 1;
574 lowerBound[backAdjCor[PG.expandAdj(v)->faceCyclePred()->twin()]] = 1;
575 }//progressive
576
577
578 // Set the upper and lower bound for the last node in
579 // clockwise order of the mergeexpander face to
580 // guaranty a 90 degree angle at the node in the interior
581 // and a 180 degree angle between the generalizations in the
582 // exterior.
583 if (F[f] == backAdjCor[PG.expandAdj(v)->faceCyclePred()]->target())
584 secFace = backAdjCor[PG.expandAdj(v)->faceCyclePred()]->source();
585 else if (F[f] == backAdjCor[PG.expandAdj(v)->faceCyclePred()]->source())
586 secFace = backAdjCor[PG.expandAdj(v)->faceCyclePred()]->target();
587 else
588 {
589 OGDF_ASSERT(false); // Edges in Network mixed up.
590 }
591 w = networkNode[PG.expandAdj(v)->faceCyclePred()->theNode()];
592
593 forall_adj(adj,w)
594 {
595 if (adj->theEdge()->target() == F[f])
596 {
597 lowerBound[adj->theEdge()] = 1;
598 upperBound[adj->theEdge()] = 1;
599 if (!m_traditional)
600 {
601 edge aTwin = angleTwin[adj->theEdge()];
602 if (aTwin)
603 {
604 upperBound[aTwin] = 0;
605 lowerBound[aTwin] = 0;
606 }
607 }//if not traditional limit angle back arc
608 break;
609 }
610 }
611
612 if (m_traditional)
613 e = adj->cyclicPred()->theEdge();
614 else
615 {
616 //we have two edges instead of one per face
617 adjEntry ae = adj->cyclicPred();
618 e = ae->theEdge();
619 if (e->target() != secFace)
620 //maybe we have to jump one step further
621 e = ae->cyclicPred()->theEdge();
622
623 }//progressive mode
624
625 if (e->target() == secFace)
626 {
627 lowerBound[e] = piAngleFlow;
628 upperBound[e] = piAngleFlow;
629 if (!m_traditional)
630 {
631 edge aTwin = angleTwin[e];
632 if (aTwin)
633 {
634 upperBound[aTwin] = piAngleFlow;
635 lowerBound[aTwin] = piAngleFlow;
636 }
637 }//if not traditional limit angle back arc
638 }
639
640
641 }
642 //**************************
643 //expanded high degree cages
644 else if (PG.typeOf(v) == Graph::highDegreeExpander )
645 {
646 // Set upperBound to 1 for all edges, allowing maximal one
647 // 90 degree bend.
648 // Set upperBound to 0 for the corresponding entering edge
649 // allowing no 270 degree bend.
650 // Set upperbound to 1 for every edge corresponding to the
651 // angle of a vertex. This permitts 270 degree angles in
652 // the face
653
654 adjEntry splitter = 0;
655
656
657 //assure that edges are only spread around the sides if not too
658 //many multi edges are aligned
659
660 //************************
661 //count multiedges at node
662 int multis = 0;
663 AdjEntryArray<bool> isMulti(PG, false);
664 if (m_multiAlign)
665 {
666 //if all edges are multi edges, find a 360 degree position
667 bool allMulti = true;
668 forall_face_adj(adj, f) //this double iteration slows the algorithm down
669 {
670 //no facesplitter in attributedgraph
671 //if (!PG.faceSplitter(adj->theEdge()))
672 {
673 adjEntry srcadj = adj->cyclicPred();
674 adjEntry tgtadj = adj->twin()->cyclicSucc();
675 //check if the nodes are expanded
676 node vt1, vt2;
677 if (PG.expandedNode(srcadj->twinNode()))
678 vt1 = PG.expandedNode(srcadj->twinNode());
679 else vt1 = srcadj->twinNode();
680 if (PG.expandedNode(tgtadj->twinNode()))
681 vt2 = PG.expandedNode(tgtadj->twinNode());
682 else vt2 = tgtadj->twinNode();
683 if (vt1 == vt2)
684 {
685 //we forbid bends between two incident multiedges
686 if (m_traditional)
687 {
688 lowerBound[backAdjCor[adj]] = upperBound[backAdjCor[adj]] = 0;
689 isMulti[adj] = true;
690 }
691 else
692 {
693 lowerBound[backAdjCor[adj->twin()]] =
694 lowerBound[backAdjCor[adj]] =
695 upperBound[backAdjCor[adj]] =
696 upperBound[backAdjCor[adj->twin()]] = 0;
697 isMulti[adj->twin()] = true;
698 }
699 multis++;
700 }//multi edge
701 else allMulti = false;
702 }//if outer boundary
703
704 }//forallfaceadj count multis
705 //multi edge correction: only multi edges => one edge needs 360 degree
706 if (allMulti)
707 {
708 //find an edge that allows 360 degree without bends
709 bool twoNodeCC = true; //no foreign non-multi edge to check for
710 forall_face_adj(adj, f)
711 {
712 //now check for expanded nodes
713 adjEntry adjOut = adj->cyclicPred(); //outgoing edge entry
714 node vOpp = adjOut->twinNode();
715 if (PG.expandedNode(vOpp))
716 {
717 adjOut = adjOut->faceCycleSucc(); //on expanded boundary
718 //does not end on self loops
719 node vStop = vOpp;
720 if (PG.expandedNode(vStop)) vStop = PG.expandedNode(vStop);
721 while (PG.expandedNode(adjOut->twinNode()) == vStop)
722 //we are still on vOpps cage
723 adjOut = adjOut->faceCycleSucc();
724 }
725 //now adjOut is either a "foreign" edge or one of the
726 //original multi edges if two-node-CC
727 //adjEntry testadj = adjCor[e]->faceCycleSucc()->twin();
728 adjEntry testAdj = adjOut->twin();
729 node vBack = testAdj->theNode();
730 if (PG.expandedNode(vBack))
731 {
732 vBack = PG.expandedNode(vBack);
733 }
734 if (vBack != v) //v is expanded node
735 {
736 //dont use iteration result, set firstedge!
737 upperBound[backAdjCor[adj]] = 4; //4 bends for 360
738 twoNodeCC = false;
739 break;
740 }
741 }//forall_adj_edges
742 //if only two nodes with multiedges are in current CC,
743 //assign 360 degree to first edge
744 if (twoNodeCC)
745 {
746 //it would be difficult to guarantee that the networkedge
747 //on the other side of the face would get the 360, so alllow
748 //360 for all edges or search for the outer face
749
750 forall_face_adj(adj, f)
751 {
752 adjEntry ae = adj->cyclicPred();
753 if (adjF[ae] == E.externalFace())
754 {
755 upperBound[backAdjCor[adj]] = 4; //4 bends for 360
756 break;
757 }
758 }//forall expansion adj
759 }//if
760 }//if allMulti
761 //End multi edge correction
762 }//if multialign
763
764
765 //**********************
766 //now set the upper Bounds
767 forall_face_adj(adj,f)
768 {
769 //should be: no 270 degrees
770 if (m_traditional)
771 upperBound[backAdjCor[adj->twin()]] = 0;
772 else
773 upperBound[backAdjCor[adj]] = 0;
774
775 //if (false)//(PG.faceSplitter(adj->theEdge()))
776 //{
777 // // No bends allowed on the face splitter
778 // upperBound[backAdjCor[adj]] = 0;
779
780 // //CHECK
781 // //progressive??? sollte sein:
782 // upperBound[backAdjCor[adj->twin()]] = 0;
783
784 // splitter = adj;
785 // continue;
786 //}
787 // else
788 // //should be: only one bend
789 {
790
791 if (m_distributeEdges)
792 //CHECK
793 //maybe we should change this to setting the lower bound too,
794 //depending on the degree (<= 4 => deg 90)
795 {
796 //check the special case degree >=4 with 2
797 // generalizations following each other if degree
798 // > 4, only 90 degree allowed, nodeType high
799 // bloed, da nicht original
800 //if (nodeType[ networkNode[adj->twinNode()] ] == high)
801 //hopefully size is original degree
802 if (m_traditional)
803 {
804 if (!isMulti[adj]) //m_multiAlign???
805 {
806 //check if original node degree minus multi edges
807 //is high enough
808 //Attention: There are some lowerBounds > 1
809 #ifdef OGDF_DEBUG
810 int oldBound = upperBound[backAdjCor[adj]];
811 #endif
812 if ((!genshift[v]) && (f->size()-multis>3))
813 upperBound[backAdjCor[adj]] =
814 //max(2, lowerBound[backAdjCor[adj]]);
815 //due to mincostflowreinelt errors, we are not
816 //allowed to set ub 1
817 max(1, lowerBound[backAdjCor[adj]]);
818 else upperBound[backAdjCor[adj]] =
819 max(2, lowerBound[backAdjCor[adj]]);
820 //nur zum Testen der Faelle
821 OGDF_ASSERT(oldBound >= upperBound[backAdjCor[adj]]);
822 }// if not multi
823 }//traditional
824 else
825 {
826 //preliminary set the bound in all cases
827
828 if (!isMulti[adj])
829 {
830 //Attention: There are some lowerBounds > 1
831
832 if ((!genshift[v]) && (f->size()-multis>3))
833 upperBound[backAdjCor[adj->twin()]] =
834 max(1, lowerBound[backAdjCor[adj->twin()]]);
835 else upperBound[backAdjCor[adj->twin()]] =
836 max(2, lowerBound[backAdjCor[adj->twin()]]);
837
838 }// if not multi
839 }//progressive
840 }//distributeedges
841
842 }// else no face splitter
843
844 // Node w is in Network
845 node w = networkNode[adj->twinNode()];
846
847 // if (w && !(m_traditional && m_fourPlanar && (w->degree() != 4)))
848 {
849 //should be: inner face angles set to 180
850 forall_adj_edges(e,w)
851 {
852 if (e->target() == F[f])
853 {
854 upperBound[e] = piAngleFlow;
855 lowerBound[e] = piAngleFlow;
856 if (!m_traditional)
857 {
858 if (angleTwin[e])
859 {
860 upperBound[angleTwin[e]] = piAngleFlow;
861 lowerBound[angleTwin[e]] = piAngleFlow;
862 }//if twin
863 }//if progressive mode
864 }
865 }
866 }
867 }// forallfaceadj
868
869 //********************************************************
870 // In case a face splitter was used, we need to update the
871 // second face of the cage.
872 if (splitter)
873 {
874
875 adj = splitter->twin();
876 // Get the corresponding face in the original embedding.
877 face f2 = adjF[adj];
878
879 forall_face_adj(adj,f2)
880 {
881 if (adj == splitter->twin())
882 continue;
883
884 if (m_traditional)
885 upperBound[backAdjCor[adj->twin()]] = 0;
886 else //progressive bends are in opposite direction
887 upperBound[backAdjCor[adj]] = 0;
888
889 // Node w is in Network
890 node w = networkNode[adj->twinNode()];
891 //if (w && !(m_traditional && m_fourPlanar && (w->degree() != 4)))
892 {
893 forall_adj_edges(e,w)
894 {
895 if (e->target() == F[f2])
896 {
897 upperBound[e] = piAngleFlow;
898 lowerBound[e] = piAngleFlow;
899 if (!m_traditional)
900 {
901 if (angleTwin[e])
902 {
903 upperBound[angleTwin[e]] = piAngleFlow;
904 lowerBound[angleTwin[e]] = piAngleFlow;
905 }//angleTwin
906 }//if progressive mode
907 }
908 }//forall adjacent edges
909 }//if not preset
910 }
911 }
912 }
913 }//if expanded
914
915 else
916 {
917
918 //*********************************************
919 //non-expanded (low degree) nodes
920 //check for alignment and for multi edges
921 //*********************************************
922
923 //check for multi edges and decrease lowerbound if align
924 int lowerb = 0;
925
926 if (PG.isVertex(v))
927 {
928 node w = networkNode[v];
929 if ((nodeType[w] != low) || (w->degree()<2)) continue;
930
931 bool allMulti = true;
932 forall_adj_edges(e,w)
933 {
934 lowerb += max(lowerBound[e], 0);
935
936 OGDF_ASSERT((!m_traditional) || (e->source() == w));
937 if (m_traditional && (e->source() != w)) OGDF_THROW(AlgorithmFailureException);
938 if (e->source() != w) continue; //dont treat back angle edges
939
940 if (m_multiAlign && (v->degree()>1))
941 {
942 adjEntry srcAdj = adjCor[e];
943 adjEntry tgtAdj = adjCor[e]->faceCyclePred();
944
945 //check if the nodes are expanded
946 node vt1, vt2;
947 if (PG.expandedNode(srcAdj->twinNode()))
948 vt1 = PG.expandedNode(srcAdj->twinNode());
949 else vt1 = srcAdj->twinNode();
950
951 if (PG.expandedNode(tgtAdj->theNode()))
952 vt2 = PG.expandedNode(tgtAdj->theNode());
953 else vt2 = tgtAdj->theNode();
954
955 if (vt1 == vt2)
956 {
957
958 fixedVal[w] = true;
959
960 //we forbid bends between incident multi edges
961 //or is it angle?
962 lowerBound[e] = upperBound[e] = zeroAngleFlow;
963 if (!m_traditional)
964 {
965 lowerBound[angleTwin[e]] = upperBound[angleTwin[e]]
966 = zeroBackAngleFlow;
967 }//if progressive mode
968
969 }//multi edge
970 else
971 {
972 //CHECK
973 //to be done: only if multiedges
974 if (!genshift[v]) upperBound[e] = upperAngleFlow;
975 allMulti = false;
976 }
977 }//multiAlign
978 }//foralladjedges
979
980
981 if (m_multiAlign && allMulti && (v->degree()>1))
982 {
983
984 fixedVal[w] = true;
985
986 //find an edge that allows 360 degree without bends
987 bool twoNodeCC = true;
988 forall_adj_edges(e, w)
989 {
990 //now check for expanded nodes
991 adjEntry runAdj = adjCor[e];
992 node vOpp = runAdj->twinNode();
993 node vStop;
994 vStop = vOpp;
995 runAdj = runAdj->faceCycleSucc();
996 if (PG.expandedNode(vStop))
997 {
998
999 //does not end on self loops
1000 vStop = PG.expandedNode(vStop);
1001 while (PG.expandedNode(runAdj->twinNode()) == vStop)
1002 //we are still on vOpps cage
1003 runAdj = runAdj->faceCycleSucc();
1004 }
1005 //adjEntry testadj = adjCor[e]->faceCycleSucc()->twin();
1006 adjEntry testAdj = runAdj->twin();
1007 node vBack = testAdj->theNode();
1008
1009 if (vBack != v) //not same node
1010 {
1011 if (PG.expandedNode(vBack))
1012 {
1013 vBack = PG.expandedNode(vBack);
1014 }
1015 if (vBack != vStop) //vstop !=0, not inner face in 2nodeCC
1016 {
1017 //CHECK: 4? upper
1018 OGDF_ASSERT(!PG.expandedNode(v)); //otherwise not angle flow
1019 if (m_traditional)
1020 upperBound[e] = maxAngleFlow; //dont use iteration result, set firstedge!
1021 else
1022 {
1023 upperBound[e] = lowerBound[e] = lowerAngleFlow;
1024 if (angleTwin[e])
1025 {
1026 upperBound[angleTwin[e]] = maxBackFlow;
1027 lowerBound[angleTwin[e]] = maxBackFlow;
1028 }
1029 }
1030 twoNodeCC = false;
1031 break;
1032 }//if not 2nodeCC
1033 }//if
1034 }//forall_adj_edges
1035 //if only two nodes with multiedges are in current CC,
1036 //assign 360 degree to first edge
1037 if (twoNodeCC)
1038 {
1039 //it would be difficult to guarantee that the networkedge
1040 //on the other side of the face would get the 360, so alllow
1041 //360 for all edges or search for external face
1042 forall_adj_edges(e, w)
1043 {
1044 adjEntry adje = adjCor[e];
1045 if (adjF[adje] == E.externalFace())
1046 {
1047 //CHECK: 4? upper
1048 OGDF_ASSERT(!PG.expandedNode(v)); //otherwise not angle flow
1049 if (m_traditional)
1050 upperBound[e] = maxAngleFlow;//upperAngleFlow;
1051 if (!m_traditional)
1052 {
1053 upperBound[e] = lowerAngleFlow;//upperAngleFlow;
1054 lowerBound[e] = lowerAngleFlow;
1055 if (angleTwin[e])
1056 {
1057 upperBound[angleTwin[e]] = maxBackFlow;
1058 lowerBound[angleTwin[e]] = maxBackFlow;
1059 }
1060 }
1061 break;
1062 }//if
1063 }//forall
1064 }//if
1065 }//if allMulti
1066 }//replaces vertex
1067
1068 }
1069 }//forallnodes
1070
1071 //**********************************
1072 node tv; edge te;
1073 //int flowSum = 0;
1074
1075 //To Be done: hier multiedges testen
1076 forall_nodes(tv, Network)
1077 {
1078 //flowSum += supply[tv];
1079
1080 //only check representants of original nodes, not faces
1081 if (((nodeType[tv] == low) || (nodeType[tv] == high)))
1082 {
1083 //if node representant with degree 4, set angles preliminary
1084 //degree four nodes with two gens are expanded in PlanRepUML
1085 //all others are allowed to change the edge positions
1086 if ( (m_traditional && (tv->degree() == 4)) ||
1087 ((tv->degree() == 8) && !m_traditional) )
1088 {
1089 //three types: degree4 original nodes and facesplitter end nodes,
1090 //maybe crossings
1091 //fixassignment tells us that low degree nodes are not allowed to
1092 //have zero degree and special nodes are already assigned
1093 bool fixAssignment = true;
1094
1095 //check if free assignment is possible for degree 4
1096 if (m_deg4free)
1097 {
1098 fixAssignment = false;
1099 forall_adj_edges(te, tv)
1100 {
1101 if (te->source() == tv)
1102 {
1103 adjEntry pgEntry = adjCor[te];
1104 node pgNode = pgEntry->theNode();
1105
1106 if ((PG.expandedNode(pgNode))
1107 //|| (PG.faceSplitter(adjCor[te]->theEdge()))
1108 || (PG.typeOf(pgNode) == Graph::dummy) //test crossings
1109 )
1110 {
1111 fixAssignment = true;
1112 break;
1113 }
1114 }//if no angle back arc in progressive mode
1115 }//forall_adj_edges
1116 }//deg4free
1117
1118 //CHECK
1119 //now set the angles at degree 4 nodes to distribute edges
1120 forall_adj_edges(te, tv)
1121 {
1122
1123 if (te->source() == tv)
1124 {
1125 if (fixedVal[tv]) continue; //if already special values set
1126
1127 if (!fixAssignment)
1128 {
1129 lowerBound[te] = 0; //lowerAngleFlow maybe 1;//0;
1130 upperBound[te] = upperAngleFlow;//4;
1131 }
1132 else
1133 {
1134 //only allow 90 degree arc value
1135 lowerBound[te] = halfPiAngleFlow;
1136 upperBound[te] = halfPiAngleFlow;
1137 }
1138 }//if no angle back arc in progressive mode
1139 else
1140 {
1141 if (fixedVal[tv]) continue; //if already special values set
1142
1143 if (!fixAssignment)
1144 {
1145 OGDF_ASSERT(lowerAngleFlow == 0); //should only be in progressive mode
1146 lowerBound[te] = lowerAngleFlow;
1147 upperBound[te] = upperBackAngleFlow;
1148 }
1149 else
1150 {
1151 //only allow 0-180 degree back arc value
1152 lowerBound[te] = 0; //1
1153 upperBound[te] = 0; //halfPiAngleFlow; //1
1154 }
1155 }//back angle arc
1156 }//forall_adj_edges
1157 }//degree 4 node
1158 int lowsum = 0, upsum = 0;
1159 forall_adj_edges(te, tv)
1160 {
1161 OGDF_ASSERT(lowerBound[te] <= upperBound[te]);
1162 if (noBendEdge[te]) lowerBound[te] = 0;
1163 lowsum += lowerBound[te];
1164 upsum += upperBound[te];
1165 }//forall_adj_edges
1166 if (m_traditional) {
1167 OGDF_ASSERT( (lowsum <= supply[tv]) && (upsum >= supply[tv]))
1168 }
1169 }//if node, no faces
1170 }//forallnodes
1171 //only for debugging: check faces
1172 forall_nodes(tv, Network)
1173 {
1174 int lowsum = 0, upsum = 0;
1175 forall_adj_edges(te, tv)
1176 {
1177 if (noBendEdge[te]) lowerBound[te] = 0;
1178 lowsum += lowerBound[te];
1179 upsum += upperBound[te];
1180 }//forall_adj_edges
1181 //OGDF_ASSERT( (lowsum <= supply[tv]) && (upsum >= supply[tv]));
1182 }
1183 //OGDF_ASSERT(flowSum == 0);
1184
1185
1186 bool isFlow = false;
1187 SList<edge> capacityBoundedEdges;
1188 EdgeArray<int> flow(Network,0);
1189
1190 // Set upper Bound to current upper bound.
1191 // Some edges are no longer capacitybounded, therefore save their status
1192 EdgeArray<bool> isBounded(Network, false);
1193
1194 forall_edges(e,Network)
1195
1196 if (upperBound[e] == infinity)
1197 {
1198 capacityBoundedEdges.pushBack(e);
1199 isBounded[e] = true;
1200 }//if bounded
1201
1202 int currentUpperBound;
1203 if (startBoundBendsPerEdge > 0)
1204 currentUpperBound = startBoundBendsPerEdge;
1205 else
1206 currentUpperBound = 4*PG.numberOfEdges();
1207
1208
1209 while ( (!isFlow) && (currentUpperBound <= 4*PG.numberOfEdges()) )
1210 {
1211
1212 SListIterator<edge> it;
1213 for (it = capacityBoundedEdges.begin(); it.valid(); it++)
1214 upperBound[(*it)] = currentUpperBound;
1215
1216 isFlow = flowModule.call(Network,lowerBound,upperBound,cost,supply,flow);
1217
1218
1219 //#ifdef foutput
1220 //if (isFlow)
1221 // {
1222 // forall_edges(e,Network) {
1223 // fout << "e = " << e << " flow = " << flow[e];
1224 // if(nodeCor[e] == 0 && adjCor[e])
1225 // fout << " real edge = " << adjCor[e]->theEdge();
1226 // fout << endl;
1227 // }
1228 // forall_edges(e,Network) {
1229 // if(nodeCor[e] == 0 && adjCor[e] != 0 && flow[e] > 0) {
1230 // fout << "Bends " << flow[e] << " on edge "
1231 // << adjCor[e]->theEdge()
1232 // << " between faces " << adjF[adjCor[e]]->index() << " - "
1233 // << adjF[adjCor[e]->twin()]->index() << endl;
1234 // }
1235 // }
1236 // forall_edges(e,Network) {
1237 // if(nodeCor[e] != 0 && faceCor[e] != 0) {
1238 // fout << "Angle " << (flow[e])*90 << "\tdegree on node "
1239 // << nodeCor[e] << " at face " << faceCor[e]->index()
1240 // << "\tbetween edge " << adjCor[e]->faceCyclePred()
1241 // << "\tand " << adjCor[e] << endl;
1242 // }
1243 // }
1244 // if (startBoundBendsPerEdge> 0) {
1245 // fout << "Minimizing edge bends for upper bound "
1246 // << currentUpperBound;
1247 // if(isFlow)
1248 // fout << " ... Successful";
1249 // fout << endl;
1250 // }
1251 //}
1252 //#endif
1253
1254 OGDF_ASSERT(startBoundBendsPerEdge >= 1 || isFlow);
1255
1256 currentUpperBound++;
1257
1258 }// while (!isflow)
1259
1260
1261 if (startBoundBendsPerEdge && !isFlow)
1262 {
1263 // couldn't compute reasonable shape
1264 OGDF_THROW_PARAM(AlgorithmFailureException, afcNoFlow);
1265 }
1266
1267
1268 int totalNumBends = 0;
1269
1270
1271 forall_edges(e,Network)
1272 {
1273
1274 if (nodeCor[e] == 0 && adjCor[e] != 0 && (flow[e] > 0) &&
1275 (angleTwin[e] == 0) ) //no angle edges
1276 {
1277 OGDF_ASSERT(OR.bend(adjCor[e]).size() == 0)
1278
1279 char zeroChar = (m_traditional ? '0' : '1');
1280 char oneChar = (m_traditional ? '1' : '0');
1281 //we depend on the property that there is no flow
1282 //in opposite direction due to the cost
1283 OR.bend(adjCor[e]).set(zeroChar,flow[e]);
1284 OR.bend(adjCor[e]->twin()).set(oneChar,flow[e]);
1285
1286 totalNumBends += flow[e];
1287
1288 //check if bends fit bounds
1289 if (isBounded[e])
1290 {
1291 OGDF_ASSERT((int)OR.bend(adjCor[e]).size() <= currentUpperBound);
1292 OGDF_ASSERT((int)OR.bend(adjCor[e]->twin()).size() <= currentUpperBound);
1293 }//if bounded
1294 }
1295 else if (nodeCor[e] != 0 && faceCor[e] != 0)
1296 {
1297 if (m_traditional) OR.angle(adjCor[e]) = (flow[e]);
1298 else
1299 {
1300 OGDF_ASSERT(angleTwin[e] != 0);
1301 switch (flow[e])
1302 {
1303 case 0: switch (flow[angleTwin[e]])
1304 {
1305 case 0: OR.angle(adjCor[e]) = 2; break;
1306 case 1: OR.angle(adjCor[e]) = 3; break;
1307 case 2: OR.angle(adjCor[e]) = 4; break;
1308 OGDF_NODEFAULT
1309 }//switch
1310 break;
1311 case 1: switch (flow[angleTwin[e]])
1312 {
1313 case 0: OR.angle(adjCor[e]) = 1; break;
1314 OGDF_NODEFAULT
1315 }//switch
1316 break;
1317 case 2: switch (flow[angleTwin[e]])
1318 {
1319 case 0: OR.angle(adjCor[e]) = 0; break;
1320 OGDF_NODEFAULT
1321 }//switch
1322 break;
1323 OGDF_NODEFAULT
1324 }//switch
1325 }//progressive mode
1326 }//if angle arc
1327 }
1328
1329
1330 #ifdef OGDF_DEBUG
1331 if (int(ogdf::debugLevel) >= int(dlHeavyChecks))
1332 cout << "\n\nTotal Number of Bends : "<< totalNumBends << endl << endl;
1333 #endif
1334
1335 #ifdef OGDF_DEBUG
1336 String error;
1337 if (OR.check(error) == false) {
1338 cout << error << endl;
1339 OGDF_ASSERT(false);
1340 }
1341 #endif
1342
1343 }//call
1344
1345
1346 } // end namespace ogdf
1347
Windows Explorer Extension to Operate Git