Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
CompactionConstraintGraph.h
Go to the documentation of this file.
1
35#pragma once
36
41
42namespace ogdf {
43
46public:
49
51 bool verticalGen(edge e) const { return m_verticalGen[e]; }
52
55 bool verticalArc(edge e) const { return m_verticalArc[e]; }
56
58
60 void align(bool b) { m_align = b; }
61
64 bool alignmentArc(edge e) const { return m_alignmentArc[e]; }
65
67
68protected:
71 int costGen = 1, int costAssoc = 1, bool align = false);
72
73 int m_edgeCost[2];
74
75 //test fuer vorkomp. der Generalisierungen
78
81
83
84private:
85 //set special costs for node to merger generalizations
86 bool m_align;
87
91
93};
94
105template<class ATYPE>
107public:
110 int costGen = 1, int costAssoc = 1, bool align = false)
111 : CompactionConstraintGraphBase(OR, PG, arcDir, costGen, costAssoc, align) {
112 OGDF_ASSERT(&(const Graph&)PG == &(const Graph&)OR);
113
114 m_length.init((Graph&)*this, sep);
115 m_extraOfs.init((Graph&)*this, 0);
116 m_extraRep.init((Graph&)*this, nullptr);
117
118 m_sep = sep;
119
120 m_centerPriority = true; //should centering of single edges have prio. to gen. length
121 m_genToMedian = true; //should outgoing merger gen. be drawn to merger median
122
124 }
125
128 ATYPE length(edge e) const { return m_length[e]; }
129
131 ATYPE extraOfs(node v) const { return m_extraOfs[v]; }
132
135
137 void centerPriority(bool b) { m_centerPriority = b; }
138
141 ATYPE computeTotalCosts(const NodeArray<ATYPE>& pos) const;
142
148 const RoutingChannel<ATYPE>& rc);
149
157
161 void insertVisibilityArcs(const PlanRep& PG,
162 const NodeArray<ATYPE>& posDir,
164 );
165
168
172
177 bool isFeasible(const NodeArray<ATYPE>& pos);
178
180 ATYPE separation() const { return m_sep; }
181
183 bool areMulti(edge e1, edge e2) const;
184
185private:
187 struct Interval {
188 Interval(node v, ATYPE low, ATYPE high) {
189 m_low = low;
190 m_high = high;
191 m_pathNode = v;
192 }
193
196
198 friend std::ostream& operator<<(std::ostream& os, const Interval& interval) {
199 os << "[" << interval.m_low << "," << interval.m_high << ";" << interval.m_pathNode
200 << "]";
201 return os;
202 }
203 };
204
210 public:
215
216 int compare(const node& x, const node& y) const {
217 ATYPE d = (*m_pPos)[x] - (*m_pPos)[y];
218 if (d < 0) {
219 return -1;
220 } else if (d > 0) {
221 return 1;
222 } else {
223 return (*m_pSec)[x] - (*m_pSec)[y];
224 }
225 }
226
228 private:
231 };
232
233 virtual string getLengthString(edge e) const override { return to_string(m_length[e]); }
234
235 void setBasicArcsZeroLength(const PlanRep& PG);
238
239 bool checkSweepLine(const List<Interval>& sweepLine) const;
240
242
244
246
249
250 // we make vertex size arcs more expensive than basic arcs in order
251 // to get small cages
252 // should be replaced by option/value dependent on e.g. degree
258 //this does not work if generalization costs are set very small by the user
259 //because there must be a minimum cost for centering
261
262 //factor of costs relative to generalization
263 static const int c_vertexArcFactor;
264 static const int c_bungeeFactor;
265 static const int c_doubleBendFactor;
266 static const int c_MedianFactor;
267
269
270protected:
272 void setExtra(node v, node rep, ATYPE ofs) {
273 m_extraNode[v] = true;
274 m_extraRep[v] = rep;
275 m_extraOfs[v] = ofs;
276 }
277
279 // we make vertex size arcs more expensive than basic arcs in order
280 // to get small cages; not necessary if cage size fixed in improvement
281 // cost should be dependend on degree
282 // Z.B. DURCH OPTION ODER WERT; DER VON DER ZAHL ADJAZENTER KANTEN ABHAENGIG IST
283 // should be derived by number of edges times something
284 int costGen = m_edgeCost[static_cast<int>(Graph::EdgeType::generalization)];
285
286 m_vertexArcCost = c_vertexArcFactor * costGen; //spaeter aus Kompaktierungsmodul uebergeben
287 if (m_centerPriority) {
288 m_bungeeCost = c_bungeeFactor * costGen + 1; //-1;//for distance to middle position,
289 } else {
290 m_bungeeCost = c_bungeeFactor * 4 + 1; //-1;//for distance to middle position,
291 }
292 //addition value should be < gen cost!!!
295 }
296};
297
298//initialization of static members
299template<class ATYPE>
301template<class ATYPE>
303template<class ATYPE>
305 20; //double bends cost mxxx*vertexArcCost
306//factor *VertexArcCost, costs for pulling generalization to median position at merger
307template<class ATYPE>
308const int CompactionConstraintGraph<ATYPE>::c_MedianFactor = 10 * c_doubleBendFactor;
309
310// allow 0-length for sides of generalization merger cages
311template<class ATYPE>
313 adjEntry adj = adjFirst;
314 int faceSize = 0;
315
316 do {
317 if ((m_pOR->direction(adj) == m_arcDir || m_pOR->direction(adj) == m_oppArcDir)
318 && (PG.typeOf(adj->theNode()) == Graph::NodeType::dummy
319 || PG.typeOf(adj->twinNode()) == Graph::NodeType::dummy)) {
320 m_length[m_edgeToBasicArc[adj]] = 0;
321 }
322
323 adj = adj->faceCycleSucc();
324 faceSize++;
325 } while (adj != adjFirst);
326
327 //generalization position section
328 //pull upper generalization to median of merger cage's incoming lower generalizations
329
330 if (m_genToMedian
331 && (m_pOR->direction(adjFirst) == m_arcDir || m_pOR->direction(adjFirst) == m_oppArcDir)) {
332 int numIncoming = faceSize - 3;
333 int median = (numIncoming / 2) + 1;
334
335 // if (numIncoming == 2) ... just the middle position
336 node upper = m_pathNode[adjFirst->theNode()];
337 if (PG.typeOf(adjFirst->theNode()) != Graph::NodeType::generalizationMerger) {
339 }
340
341 node vMin;
342 if (m_pOR->direction(adjFirst) == m_arcDir) {
343 vMin = adjFirst->faceCyclePred()->theNode();
344 } else {
345 vMin = adjFirst->faceCycleSucc()->theNode();
346 }
347
348 adj = adjFirst->faceCycleSucc(); // target right or left boundary, depending on drawing direction
349 for (int i = 0; i < median; i++) {
350 adj = adj->faceCycleSucc();
351 }
352
353 node lower = m_pathNode[adj->theNode()];
354 node vCenter = newNode();
355 setExtra(vCenter, vMin, 0);
356
357 // it seems we dont need the helper, as only source-adjEntries lying on
358 // the outer face are considered later, but keep it in mind
359#if 0
360 edge helper = newEdge(m_pathNode[vMin], vCenter);
361 m_length[helper] = 0;
362 m_cost[helper] = 0;
364#endif
365
366 edge e1 = newEdge(vCenter, upper);
367 m_length[e1] = 0;
368 m_cost[e1] = m_MedianArcCost;
370
371 edge e2 = newEdge(vCenter, lower);
372 m_length[e2] = 0;
373 m_cost[e2] = m_MedianArcCost;
375 }
376}
377
378// set cost of edges on the cage boundary to 0
379template<class ATYPE>
381#if 0
382 adjEntry adj;
383 for (adj = cornerDir; m_pOR->direction(adj) == m_arcDir; adj = adj->faceCycleSucc())
384 m_cost[m_edgeToBasicArc[adj]] = 0;
385 for (adj = cornerOppDir; m_pOR->direction(adj) == m_oppArcDir; adj = adj->faceCycleSucc())
386 m_cost[m_edgeToBasicArc[adj]] = 0;
387#endif
388 //test for multi separation
389 adjEntry adj;
390 for (adj = cornerDir; m_pOR->direction(adj) == m_arcDir; adj = adj->faceCycleSucc()) {
391 m_cost[m_edgeToBasicArc[adj]] = 0;
392
393 if (m_pathNode[adj->twin()->cyclicSucc()->theNode()]
394 && (m_pOR->direction(adj->faceCycleSucc()) == m_arcDir)) {
395 m_originalEdge[m_pathNode[adj->twin()->cyclicSucc()->theNode()]] =
396 m_pPR->original(adj->twin()->cyclicSucc()->theEdge());
397 }
398 }
399 for (adj = cornerOppDir; m_pOR->direction(adj) == m_oppArcDir; adj = adj->faceCycleSucc()) {
400 m_cost[m_edgeToBasicArc[adj]] = 0;
401
402 if (m_pathNode[adj->twin()->cyclicSucc()->theNode()]) {
403 m_originalEdge[m_pathNode[adj->twin()->cyclicSucc()->theNode()]] =
404 m_pPR->original(adj->twin()->cyclicSucc()->theEdge());
405 }
406 }
407}
408
409//
410// insert arcs required for respecting vertex sizes, sizes of routing channels
411// and position of attached generalizations
412// vertices are represented by variable cages
413template<class ATYPE>
416 // segments in constraint graph are sides sMin and sMax; other two side
417 // are sides in which adjacency entries run in direction m_arcDir and
418 // m_oppArcDir
421
422 const ATYPE overhang = rc.overhang();
423
424 for (node v : PG.nodes) {
425 if (PG.expandAdj(v) == nullptr) {
426 continue;
427 }
428
429 if (PG.typeOf(v) == Graph::NodeType::generalizationMerger) {
430 resetGenMergerLengths(PG, PG.expandAdj(v));
431
432 } else // high/low-degree expander
433 {
434 ATYPE size = sizeOrig[v];
435
436 const OrthoRep::VertexInfoUML& vi = *m_pOR->cageInfo(v);
437
438 // determine routing channels rcMin and rcMax
439 ATYPE rcMin = overhang + rc(v, dirMin);
440 ATYPE rcMax = overhang + rc(v, dirMax);
441
442 adjEntry cornerDir = vi.m_corner[static_cast<int>(m_arcDir)];
443 adjEntry cornerOppDir = vi.m_corner[static_cast<int>(m_oppArcDir)];
444 adjEntry cornerMin = vi.m_corner[static_cast<int>(dirMin)];
445 adjEntry cornerMax = vi.m_corner[static_cast<int>(dirMax)];
446
447 // set cost of edges on the cage boundary to 0
448 setBoundaryCosts(cornerDir, cornerOppDir);
449
450 const OrthoRep::SideInfoUML& sDir = vi.m_side[static_cast<int>(m_arcDir)];
451 const OrthoRep::SideInfoUML& sOppDir = vi.m_side[static_cast<int>(m_oppArcDir)];
452
453 // correct lengths of edges within cage adjacent to corners
454 if (sDir.totalAttached() > 0) {
455 m_length[m_edgeToBasicArc[cornerDir]] = rcMin;
456 m_length[m_edgeToBasicArc[cornerMax->faceCyclePred()]] = rcMax;
457 } else {
458 // if no edges are attached at this side we need no constraint
459 m_length[m_edgeToBasicArc[cornerDir]] = 0;
460 delEdge(m_edgeToBasicArc[cornerDir]);
461 }
462
463 if (sOppDir.totalAttached() > 0) {
464 m_length[m_edgeToBasicArc[cornerOppDir]] = rcMax;
465 m_length[m_edgeToBasicArc[cornerMin->faceCyclePred()]] = rcMin;
466 } else {
467 // if no edges are attached at this side we need no constraint
468 m_length[m_edgeToBasicArc[cornerOppDir]] = 0;
469 delEdge(m_edgeToBasicArc[cornerOppDir]);
470 }
471
472
473 // insert arcs for respecting vertex size / position of generalizations
474 node vMin = m_pathNode[cornerDir->theNode()];
475 node vMax = m_pathNode[cornerOppDir->theNode()];
476
477 // any attached generalizations ?
478 if (sDir.m_adjGen == nullptr && sOppDir.m_adjGen == nullptr) {
479 // no, only one arc for vertex size + routing channels
480 edge e = newEdge(vMin, vMax);
481 m_length[e] = rcMin + size + rcMax - 2 * overhang;
482 m_cost[e] = 2 * m_vertexArcCost;
484
485 } else {
486 // yes, then two arcs for each side with an attached generalization
487 ATYPE minHalf = size / 2;
488 ATYPE maxHalf = size - minHalf;
489 ATYPE lenMin = rcMin + minHalf - overhang;
490 ATYPE lenMax = maxHalf + rcMax - overhang;
491
492 if (sDir.m_adjGen != nullptr) {
493 node vCenter = m_pathNode[sDir.m_adjGen->theNode()];
494 edge e1 = newEdge(vMin, vCenter);
495 m_length[e1] = lenMin;
496 m_cost[e1] = m_vertexArcCost;
498 edge e2 = newEdge(vCenter, vMax);
499 m_length[e2] = lenMax;
500 m_cost[e2] = m_vertexArcCost;
502 }
503
504 if (sOppDir.m_adjGen != nullptr) {
505 node vCenter = m_pathNode[sOppDir.m_adjGen->theNode()];
506 edge e1 = newEdge(vMin, vCenter);
507 m_length[e1] = lenMin;
508 m_cost[e1] = m_vertexArcCost;
510 edge e2 = newEdge(vCenter, vMax);
511 m_length[e2] = lenMax;
512 m_cost[e2] = m_vertexArcCost;
514 }
515 }
516 }
517 }
518}
519
520template<class ATYPE>
522 for (edge e : PG.edges) {
523 edge arc = m_edgeToBasicArc[e];
524 if (arc == nullptr) {
525 continue;
526 }
527
528 node v = e->source();
529 node w = e->target();
530 if (((PG.typeOf(v) == Graph::NodeType::dummy) && (PG.typeOf(w) == Graph::NodeType::dummy)
531 && (v->degree() == 2) && w->degree() == 2)
532 && (m_pOR->angle(e->adjSource()) == m_pOR->angle(e->adjTarget())) && //no uturns
533 (PG.typeOf(e) != Graph::EdgeType::generalization)) {
534 m_length[arc] = 0;
536 //we make fixtozero arcs as expensive as possible
537 m_cost[arc] = m_doubleBendCost;
538 }
539 }
540}
541
542//
543// insert arcs required for respecting vertex sizes
544// and position of attached generalizations
545// vertices are represented by tight cages
546template<class ATYPE>
549 // set the length of all basic arcs corresponding to inner edge segments
550 // to 0
551 setBasicArcsZeroLength(PG);
552
553 // segments in constraint graph are sides sMin and sMax; other two side
554 // are sides in which adjacency entries run in direction m_arcDir and
555 // m_oppArcDir
558
559 for (node v : PG.nodes) {
560 if (PG.expandAdj(v) == nullptr) {
561 continue;
562 }
563
564 if (PG.typeOf(v) == Graph::NodeType::generalizationMerger) {
565 resetGenMergerLengths(PG, PG.expandAdj(v));
566
567 } else // high/low-degree expander
568 {
569 ATYPE size = sizeOrig[v];
570 const OrthoRep::VertexInfoUML& vi = *m_pOR->cageInfo(v);
571
572 adjEntry cornerDir = vi.m_corner[static_cast<int>(m_arcDir)];
573 adjEntry cornerOppDir = vi.m_corner[static_cast<int>(m_oppArcDir)];
574 adjEntry cornerMin = vi.m_corner[static_cast<int>(dirMin)];
575 adjEntry cornerMax = vi.m_corner[static_cast<int>(dirMax)];
576
577 adjEntry adj = cornerDir, last = cornerMax->faceCyclePred();
578 if (adj != last) {
579 m_length[m_edgeToBasicArc[adj]] = minDist.epsilon(v, m_arcDir, 0);
580 m_length[m_edgeToBasicArc[last]] = minDist.epsilon(v, m_arcDir, 1);
581 int i = 0;
582 for (adj = adj->faceCycleSucc(); adj != last; adj = adj->faceCycleSucc()) {
583 if (PG.typeOf(adj->cyclicPred()->theEdge()) == Graph::EdgeType::generalization) {
584 i++;
585 }
586 m_length[m_edgeToBasicArc[adj]] = minDist.delta(v, m_arcDir, i);
587 }
588 }
589
590 adj = cornerOppDir, last = cornerMin->faceCyclePred();
591 if (adj != last) {
592 m_length[m_edgeToBasicArc[adj]] = minDist.epsilon(v, m_oppArcDir, 0);
593 m_length[m_edgeToBasicArc[last]] = minDist.epsilon(v, m_oppArcDir, 1);
594 int i = 0;
595 for (adj = adj->faceCycleSucc(); adj != last; adj = adj->faceCycleSucc()) {
596 if (PG.typeOf(adj->cyclicPred()->theEdge()) == Graph::EdgeType::generalization) {
597 i++;
598 }
599 m_length[m_edgeToBasicArc[adj]] = minDist.delta(v, m_oppArcDir, i);
600 }
601 }
602
603
604 // insert arcs for respecting vertex size / position of generalizations
605 node vMin = m_pathNode[cornerDir->theNode()];
606 node vMax = m_pathNode[cornerOppDir->theNode()];
607
608 const OrthoRep::SideInfoUML& sDir = vi.m_side[static_cast<int>(m_arcDir)];
609 const OrthoRep::SideInfoUML& sOppDir = vi.m_side[static_cast<int>(m_oppArcDir)];
610
611 // any attached generalizations ?
612 if (sDir.m_adjGen == nullptr && sOppDir.m_adjGen == nullptr) {
613 //check for single edge case => special treatment
614 //generic case could handle all numbers
615
616 if (sDir.totalAttached() == 1 || sOppDir.totalAttached() == 1) {
617 //first, insert a new center node and connect it
618 ATYPE lenMin = size / 2;
619 ATYPE lenMax = size - lenMin;
620 node vCenter = newNode();
621 setExtra(vCenter, cornerDir->theNode(), lenMin);
622
623 edge e1 = newEdge(vMin, vCenter);
624 m_length[e1] = lenMin;
625 m_cost[e1] = m_vertexArcCost;
627 edge e2 = newEdge(vCenter, vMax);
628 m_length[e2] = lenMax;
629 m_cost[e2] = m_vertexArcCost;
631
632 if (sDir.totalAttached() == 1) {
633 //then, insert a moveable node connecting center
634 //and outgoing segment
635 node vBungee = newNode();
636 //+1 should fix the fixzerolength problem
637 setExtra(vBungee, cornerDir->theNode(), minDist.epsilon(v, m_arcDir, 0));
638
639 edge eToBungee = newEdge(vMin, vBungee);
641 //BasicArc; // XXX: is this ok?
642 m_cost[eToBungee] = 0; // XXX: what about this?
643 m_length[eToBungee] = minDist.epsilon(v, m_arcDir, 0);
644
645 edge eBungeeCenter = newEdge(vBungee, vCenter);
646 //bungee, center and outgoing segment may build column if in the middle
648 m_cost[eBungeeCenter] = m_bungeeCost; // XXX: what about this?
649 m_length[eBungeeCenter] = 0;
650
651 //attention: pathnode construct works only if degree 1
652 edge eBungeeOut = newEdge(vBungee, m_pathNode[cornerDir->twinNode()]);
653 //bungee, center and outgoing segment may build column if in the middle
655 m_cost[eBungeeOut] = m_bungeeCost; // XXX: what about this?
656 m_length[eBungeeOut] = 0;
657#if 0
658 //connect outgoing segment and "right" segment, maybe obsolete
659 edge eFromOut = newEdge(m_pathNode[cornerDir->twinNode()], vMax);
660 m_type[eFromOut] = ConstraintEdgeType::BasicArc; // XXX
661 m_cost[eFromOut] = 0; // XXX
662 m_length[eFromOut] = minDist.epsilon(v,m_arcDir,1);
663#endif
664 }
665 if (sOppDir.totalAttached() == 1 && m_pathNode[cornerOppDir->twinNode()] != vMin) {
666 //then, insert a moveable node connecting center
667 //and outgoing segment
668 node vBungee = newNode();
669 //+1 for not fixzerolength
670 setExtra(vBungee, cornerDir->theNode(), minDist.epsilon(v, m_oppArcDir, 0));
671
672 edge eToBungee = newEdge(vMin, vBungee);
674 //BasicArc; // XXX: is this ok?
675 m_cost[eToBungee] = 0; // XXX: what about this?
676 m_length[eToBungee] = minDist.epsilon(v, m_oppArcDir, 0);
677
678 edge eBungeeCenter = newEdge(vBungee, vCenter);
679 //bungee, center and outgoing segment may build column if in the middle
681 m_cost[eBungeeCenter] = m_bungeeCost; // XXX: what about this?
682 m_length[eBungeeCenter] = 0;
683
684 //attention: pathnode construct works only if degree 1, sometimes not at all
685 edge eBungeeOut = newEdge(vBungee, m_pathNode[cornerOppDir->twinNode()]);
686 //bungee, center and outgoing segment may build column if in the middle
688 m_cost[eBungeeOut] = m_bungeeCost; // XXX: what about this?
689 m_length[eBungeeOut] = 0;
690#if 0
691 //connect outgoing segment and "right" segment, maybe obsolete
692 edge eFromOut = newEdge(m_pathNode[cornerOppDir->twinNode()], vMax);
693 m_type[eFromOut] = ConstraintEdgeType::BasicArc; // XXX
694 m_cost[eFromOut] = 0; // XXX
695 m_length[eFromOut] = minDist.epsilon(v,m_oppArcDir,0);
696#endif
697 }
698 } else {
699 // no, only one arc for vertex size + routing channels
700 edge e = newEdge(vMin, vMax);
701 m_length[e] = size;
702 m_cost[e] = 2 * m_vertexArcCost;
704 }
705 } else {
706 // yes, then two arcs for each side with an attached generalization
707 ATYPE lenMin = size / 2;
708 ATYPE lenMax = size - lenMin;
709
710#if 0
711 ATYPE len = size/2;
712#endif
713
714 if (sDir.m_adjGen != nullptr) {
715 node vCenter = m_pathNode[sDir.m_adjGen->theNode()];
716 edge e1 = newEdge(vMin, vCenter);
717 m_length[e1] = lenMin;
718 m_cost[e1] = m_vertexArcCost;
720 edge e2 = newEdge(vCenter, vMax);
721 m_length[e2] = lenMax;
722 m_cost[e2] = m_vertexArcCost;
724 } else {
725 if (sDir.totalAttached() == 1) {
726 node vCenter = newNode();
727 //m_pathNode[sOppDir.m_adjGen->theNode()]; //newNode();
728 setExtra(vCenter, cornerDir->theNode(), lenMin);
729
730 edge e1 = newEdge(vMin, vCenter);
731 m_length[e1] = lenMin;
732 m_cost[e1] = m_vertexArcCost;
734 edge e2 = newEdge(vCenter, vMax);
735 m_length[e2] = lenMax;
736 m_cost[e2] = m_vertexArcCost;
738
739 //then, insert a moveable node connecting center
740 //and outgoing segment
741 node vBungee = newNode();
742 //+1 for not fixzerolength
743 setExtra(vBungee, cornerDir->theNode(), minDist.epsilon(v, m_arcDir, 0));
744
745 edge eToBungee = newEdge(vMin, vBungee);
747 //BasicArc; // XXX: is this ok?
748 m_cost[eToBungee] = 0; // XXX: what about this?
749 m_length[eToBungee] = minDist.epsilon(v, m_arcDir, 0);
750
751 edge eBungeeCenter = newEdge(vBungee, vCenter);
752 //bungee, center and outgoing segment may build column if in the middle
754 m_cost[eBungeeCenter] = m_bungeeCost; // XXX: what about this?
755 m_length[eBungeeCenter] = 0;
756
757 //attention: pathnode construct works only if degree 1
758 edge eBungeeOut = newEdge(vBungee, m_pathNode[cornerDir->twinNode()]);
759 //bungee, center and outgoing segment may build column if in the middle
761 m_cost[eBungeeOut] = m_bungeeCost; // XXX: what about this?
762 m_length[eBungeeOut] = 0;
763 }
764 }
765 if (sOppDir.m_adjGen != nullptr) {
766 node vCenter = m_pathNode[sOppDir.m_adjGen->theNode()];
767 edge e1 = newEdge(vMin, vCenter);
768 m_length[e1] = lenMin;
769 m_cost[e1] = m_vertexArcCost;
771 edge e2 = newEdge(vCenter, vMax);
772 m_length[e2] = lenMax;
773 m_cost[e2] = m_vertexArcCost;
775 } else {
776 //special case single edge to middle position
777 if (sOppDir.totalAttached() == 1 && m_pathNode[cornerOppDir->twinNode()] != vMin) {
778 node vCenter = newNode();
779 //m_pathNode[sDir.m_adjGen->theNode()];//newNode();
780 setExtra(vCenter, cornerDir->theNode(), lenMin);
781
782 edge e1 = newEdge(vMin, vCenter);
783 m_length[e1] = lenMin;
784 m_cost[e1] = m_vertexArcCost;
786 edge e2 = newEdge(vCenter, vMax);
787 m_length[e2] = lenMax;
788 m_cost[e2] = m_vertexArcCost;
790 //then, insert a moveable node connecting center
791 //and outgoing segment
792 node vBungee = newNode();
793 //+1 for not fixzerolength
794 setExtra(vBungee, cornerDir->theNode(), minDist.epsilon(v, m_oppArcDir, 0));
795
796 edge eToBungee = newEdge(vMin, vBungee);
798 //BasicArc; // XXX: is this ok?
799 m_cost[eToBungee] = 0; // XXX: what about this?
800 m_length[eToBungee] = minDist.epsilon(v, m_oppArcDir, 0);
801
802 edge eBungeeCenter = newEdge(vBungee, vCenter);
803 //bungee, center and outgoing segment may build column if in the middle
805 m_cost[eBungeeCenter] = m_bungeeCost; // XXX: what about this?
806 m_length[eBungeeCenter] = 0;
807
808 //attention: pathnode construct works only if degree 1
809 edge eBungeeOut = newEdge(vBungee, m_pathNode[cornerOppDir->twinNode()]);
810 //bungee, center and outgoing segment may build column if in the middle
812 m_cost[eBungeeOut] = m_bungeeCost; // XXX: what about this?
813 m_length[eBungeeOut] = 0;
814 }
815 }
816 }
817
818 // set cost of edges on the cage boundary to 0
819 setBoundaryCosts(cornerDir, cornerOppDir);
820 }
821 }
822#if 0
823 if (m_arcDir == OrthoDir::East) {
824 writeGML("eastvertexsizeinserted.gml");
825 } else {
826 writeGML("northvertexsizeinserted.gml");
827 }
828#endif
829}
830
831// computes the total costs for coordintes given by pos, i.e.,
832// the sum of the weighted lengths of edges in the constraint graph.
833template<class ATYPE>
835 ATYPE c = 0;
836 for (edge e : edges) {
837 c += cost(e) * (pos[e->target()] - pos[e->source()]);
838 }
839
840 return c;
841}
842
843//
844// insertion of visibility arcs
845
846// checks if intervals on the sweep line are in correct order
847template<class ATYPE>
849 if (sweepLine.empty()) {
850 return true;
851 }
852
854
855 if ((*it).m_high < (*it).m_low) {
856 return false;
857 }
858
859 ATYPE x = (*it).m_low;
860
861 for (++it; it.valid(); ++it) {
862 if ((*it).m_high < (*it).m_low) {
863 return false;
864 }
865 if ((*it).m_high > x) {
866 return false;
867 }
868 x = (*it).m_low;
869 }
870
871 return true;
872}
873
874template<class ATYPE>
878
879 for (node v : PG.nodes) {
880 if (PG.expandAdj(v) == nullptr) {
881 continue;
882 }
883
884 for (int d = 0; d < 4; ++d) {
885 minDist.delta(v, OrthoDir(d), 0) = m_sep; //currentSeparation;
886 minDist.delta(v, OrthoDir(d), 1) = m_sep; //currentSeparation;
887 }
888 }
889
890 insertVisibilityArcs(PG, posDir, posOrthDir, minDist);
891}
892
893// inserts arcs connecting segments which can see each other in a drawing
894// of the associated planarized representation PG which is given by
895// posDir and posOppDir.
896
897//ersetze mindist.delta durch min(m_sep, mindist.delta) fuer skalierung
898template<class ATYPE>
904
905 // list of visibility arcs which have to be inserted
907
908 // lower and upper bound of segments
909 NodeArray<ATYPE> low(getGraph()), lowReal(getGraph()), high(getGraph());
910 NodeArray<ATYPE> segPos(getGraph(), 0); // position of segments
911 NodeArray<int> topNum(getGraph() /*,0*/); // secondary sorting criteria for segments
912
913 // compute position and lower/upper bound of segments
914 // We have to take care that segments cannot be shifted one upon the other,
915 // e.g., if we have two segments (l1,h1) and (l2,h2) with l2 > h2 and
916 // the distance l2-h2 is smaller than separation, the segments can see
917 // each other. We do this by enlarging the lower bound of all segments
918 // by separation if this lower bound is realized by a bend.
919 //
920 // Note: Be careful at segments attached at a vertex which are closer
921 // than separation to each other. Possible solution: Remove visibility
922 // arcs of segments which are connected by orthogonal segments to the
923 // same vertex and bend in opposite directions.
924 for (node v : nodes) {
925 //special case nodes
926 if (m_path[v].empty()) {
927 continue;
928 }
929
930 SListConstIterator<node> it = m_path[v].begin();
931
932 segPos[v] = posDir[*it];
933 low[v] = high[v] = posOrthDir[*it];
934 node nodeLow = *it;
935 for (++it; it.valid(); ++it) {
936 ATYPE x = posOrthDir[*it];
937 if (x < low[v]) {
938 low[v] = x;
939 nodeLow = *it;
940 }
941 if (x > high[v]) {
942 high[v] = x;
943 }
944 }
945 lowReal[v] = low[v];
948#if 0
949 bool subtractSep = true;
950 if (nodeLow->degree() == 2) {
951 adjEntry adjFound = nullptr;
952 for(adjEntry adj : nodeLow->adjEntries) {
953 if(m_pOR->direction(adj) == m_arcDir || m_pOR->direction(adj) == m_oppArcDir) {
954 adjFound = adj;
955 break;
956 }
957 }
958 if (adjFound) {
959 for(adjEntry adj2 = adjFound->faceCycleSucc();
960 m_pOR->direction(adj2) == m_pOR->direction(adjFound);
961 adj2 = adj2->twin()->faceCycleSucc()) ;
962 if(posDir[adjFound->theNode()] == posDir[adj2->twinNode()])
963 subtractSep = false;
964 }
965 }
966 if (subtractSep)
967 low[v] -= m_sep;
968#else
969 low[v] -= m_sep;
970#endif
971 }
972 }
973
974 // correct "-= m_sep" ...
977 bool isCaseA = (m_arcDir == OrthoDir::East || m_arcDir == OrthoDir::South);
978 const int angleAtMin = (m_arcDir == OrthoDir::East || m_arcDir == OrthoDir::South) ? 3 : 1;
979 const int angleAtMax = (m_arcDir == OrthoDir::East || m_arcDir == OrthoDir::South) ? 1 : 3;
980
981 for (node v : PG.nodes) {
982 if (PG.expandAdj(v) == nullptr) {
983 continue;
984 }
985 const OrthoRep::VertexInfoUML& vi = *m_pOR->cageInfo(v);
986
987 // int i = 0;
988 adjEntry adj;
989
990 for (adj = isCaseA ? vi.m_corner[static_cast<int>(dirMin)]->faceCycleSucc()->faceCycleSucc()
991 : vi.m_corner[static_cast<int>(dirMin)]->faceCycleSucc();
992 m_pOR->direction((isCaseA) ? adj : adj->faceCycleSucc())
993 == dirMin; //m_pOR->direction(adj) == dirMin;
994 adj = adj->faceCycleSucc()) {
996 adjEntry adjTwin = adjCross->twin();
997
999 ATYPE delta = (isCaseA)
1000 ? min(abs(posOrthDir[adjPred->theNode()] - posOrthDir[adjPred->twinNode()]), m_sep)
1001 : min(abs(posOrthDir[adj->theNode()] - posOrthDir[adj->twinNode()]), m_sep);
1003 ? min(posOrthDir[adjPred->theNode()], posOrthDir[adjPred->twinNode()])
1004 : min(posOrthDir[adj->theNode()], posOrthDir[adj->twinNode()]);
1005
1006 if (PG.typeOf(adjCross->theEdge()) == Graph::EdgeType::generalization) {
1007 if (isCaseA) {
1008 if (PG.typeOf(adjTwin->theNode()) == Graph::NodeType::generalizationExpander
1009 && m_pOR->angle(adjTwin) == 2) {
1010 node s1 = m_pathNode[adjTwin->theNode()];
1011 node s2 = m_pathNode[adjTwin->cyclicSucc()->twinNode()];
1012 low[s1] = lowReal[s1] - delta; // minDist.delta(v,dirMin,i);
1013 low[s2] = lowReal[s2] - delta; //minDist.delta(v,dirMin,i);
1014 }
1015 // ++i;
1016 } else {
1017 // ++i;
1018 if (PG.typeOf(adjTwin->theNode()) == Graph::NodeType::generalizationExpander
1019 && m_pOR->angle(adjTwin->cyclicPred()) == 2) {
1020 node s1 = m_pathNode[adjTwin->theNode()];
1021 node s2 = m_pathNode[adjTwin->cyclicPred()->twinNode()];
1022 low[s1] = lowReal[s1] - delta; //minDist.delta(v,dirMin,i);
1023 low[s2] = lowReal[s2] - delta; //minDist.delta(v,dirMin,i);
1024 }
1025 }
1026 continue;
1027 }
1028
1029 //we save the current direction and stop if we run in opposite
1030 OrthoDir runDir = m_pOR->direction(adjCross);
1031 // if -> while
1032 while (PG.typeOf(adjTwin->theNode()) == Graph::NodeType::dummy
1033 && adjTwin->theNode()->degree() == 2 && m_pOR->angle(adjTwin) == angleAtMin) {
1034 // We handle the case if an edge segment adjacent to a vertex
1035 // is separated by less than separation from edge segments above.
1036 node s = m_edgeToBasicArc[adjCross]->source();
1037 if (lowReal[s] != low[s]) {
1038 if (low[s] >= boundary) { // nothing to do?
1039 break;
1040 }
1041 low[s] = boundary;
1042#if 0
1043 low[s] += m_sep - delta; //minDist.delta(v,dirMin,i);
1044#endif
1045
1046 // If the compaction has eliminated bends, we can have the situation
1047 // that segment s has length 0 and the next segment s' (following the
1048 // edge) is at the same position (the edge arc has length 0).
1049 // In this case, the low-value of s' must be lowered (low[s'] := lowReal[s']
1050 // is approproate). The same situation can appear several times in a
1051 // row.
1052 //collect chains of segments compacted to zero length
1053 for (;;) { //while(true/*lowReal[s] == high[s]*/) {
1054 do {
1055 adjCross = adjCross->faceCycleSucc();
1056 } while (m_pOR->direction(adjCross) == segDir
1057 || m_pOR->direction(adjCross) == segOppDir);
1058
1059 if (adjCross->theNode()->degree() != 2) { // no longer a bend point?
1060 break;
1061 }
1062
1063 node sNext = m_edgeToBasicArc[adjCross]->opposite(s);
1064
1065 if (segPos[sNext] != segPos[s]) {
1066 break;
1067 }
1068
1069 low[sNext] = lowReal[sNext]; //?
1070 s = sNext;
1071 }
1072 }
1073
1074 adjTwin = adjCross->twin(); // update of twin for while
1075 //check if we have to stop
1076 if (runDir != m_pOR->direction(adjCross)) {
1077 break;
1078 }
1079 }
1080 }
1081
1082 // i = 0;
1083 for (adj = isCaseA ? vi.m_corner[static_cast<int>(dirMax)]->faceCycleSucc()
1084 : vi.m_corner[static_cast<int>(dirMax)]->faceCycleSucc()->faceCycleSucc();
1085 m_pOR->direction((isCaseA) ? adj->faceCycleSucc() : adj)
1086 == dirMax; // m_pOR->direction(adj) == dirMax;
1087 adj = adj->faceCycleSucc()) {
1088 adjEntry adjCross = adj->cyclicPred();
1089 adjEntry adjTwin = adjCross->twin();
1090
1091#if 0
1092 ATYPE delta = -posOrthDir[adj->twinNode()] + posOrthDir[adj->theNode()];
1093#endif
1095 ATYPE delta = (isCaseA)
1096 ? min(abs(posOrthDir[adj->twinNode()] - posOrthDir[adj->theNode()]), m_sep)
1097 : min(abs(posOrthDir[adjPred->theNode()] - posOrthDir[adjPred->twinNode()]),
1098 m_sep);
1100 ? min(posOrthDir[adj->twinNode()], posOrthDir[adj->theNode()])
1101 : min(posOrthDir[adjPred->theNode()], posOrthDir[adjPred->twinNode()]);
1102
1103 if (PG.typeOf(adjCross->theEdge()) == Graph::EdgeType::generalization) {
1104 if (isCaseA) {
1105 // ++i;
1106 if (PG.typeOf(adjTwin->theNode()) == Graph::NodeType::generalizationExpander
1107 && m_pOR->angle(adjTwin->cyclicPred()) == 2) {
1108 node s1 = m_pathNode[adjTwin->theNode()];
1109 node s2 = m_pathNode[adjTwin->cyclicPred()->twinNode()];
1110 low[s1] = lowReal[s1] - delta; //minDist.delta(v,dirMax,i);
1111 low[s2] = lowReal[s2] - delta; //minDist.delta(v,dirMax,i);
1112 }
1113 } else {
1114 if (PG.typeOf(adjTwin->theNode()) == Graph::NodeType::generalizationExpander
1115 && m_pOR->angle(adjTwin) == 2) {
1116 node s1 = m_pathNode[adjTwin->theNode()];
1117 node s2 = m_pathNode[adjTwin->cyclicSucc()->twinNode()];
1118 low[s1] = lowReal[s1] - delta; //minDist.delta(v,dirMax,i);
1119 low[s2] = lowReal[s2] - delta; //minDist.delta(v,dirMax,i);
1120 }
1121 // ++i;
1122 }
1123 continue;
1124 }
1125
1126
1127 //we save the current direction and stop if we run in opposite
1128 OrthoDir runDir = m_pOR->direction(adjCross);
1129 // if -> while
1130 while (PG.typeOf(adjTwin->theNode()) == Graph::NodeType::dummy
1131 && adjTwin->theNode()->degree() == 2 && m_pOR->angle(adjTwin) == angleAtMax) {
1132 node s = m_edgeToBasicArc[adjCross]->target();
1133 if (lowReal[s] != low[s]) {
1134 if (low[s] >= boundary) { // nothing to do?
1135 break;
1136 }
1137 low[s] = boundary;
1138#if 0
1139 low[s] += m_sep - delta; //minDist.delta(v,dirMax,i);
1140#endif
1141
1142 // If the compaction has eliminated bends, we can have the situation
1143 // that segment s has length 0 and the next segment s' (following the
1144 // edge) is at the same position (the edge arc has length 0).
1145 // In this case, the low-value of s' must be lowered (low[s'] := lowReal[s']
1146 // is approproate). The same situation can appear several times in a
1147 // row.
1148 //collect chains of segments compacted to zero length
1149 for (;;) /*lowReal[s] == high[s]*/
1150 {
1151 do {
1152 adjCross = adjCross->faceCycleSucc();
1153 } while (m_pOR->direction(adjCross) == segDir
1154 || m_pOR->direction(adjCross) == segOppDir);
1155
1156 if (adjCross->theNode()->degree() != 2) { // no longer a bend point?
1157 break;
1158 }
1159
1160 node sNext = m_edgeToBasicArc[adjCross]->opposite(s);
1161
1162 if (segPos[sNext] != segPos[s]) {
1163 break;
1164 }
1165
1166 low[sNext] = lowReal[sNext]; //was: low[s]
1167 s = sNext;
1168 }
1169 }
1170
1171 adjTwin = adjCross->twin(); // update of twin for while
1172
1173 //check if we have to stop
1174 if (runDir != m_pOR->direction(adjCross)) {
1175 break;
1176 }
1177 }
1178 }
1179 }
1180
1181 // compute topological numbering of segments as second sorting criteria
1182 // in order to process overlapping segments in the order imposed by the
1183 // embedding
1184 computeTopologicalSegmentNum(topNum);
1185
1186
1187 // sort segments
1190 allNodes(sortedPathNodes);
1191 sortedPathNodes.quicksort(cmpBySegPos);
1192
1193 // add segments in the order given by sortedPathNodes to sweep line
1195
1197 for (itV = sortedPathNodes.begin(); itV.valid(); ++itV) {
1198 //special case nodes
1199 if (m_path[*itV].empty()) {
1200 continue;
1201 }
1202 OGDF_HEAVY_ASSERT(checkSweepLine(sweepLine));
1203
1204 node v = *itV;
1206 for (it = sweepLine.begin(); it.valid(); ++it) {
1207 if ((*it).m_low < high[v]) {
1208 break;
1209 }
1210 }
1211
1212 if (!it.valid()) {
1213 sweepLine.pushBack(Interval(v, low[v], high[v]));
1214 continue;
1215 }
1216
1217 if ((*it).m_high <= low[v]) {
1218 sweepLine.insertBefore(Interval(v, low[v], high[v]), it);
1219 continue;
1220 }
1221
1223 // we store if itUp will be deleted in order not to
1224 // access the deleted iterator later
1225 bool isItUpDel = (((*itUp).m_low >= low[v]) && ((*itUp).m_high <= high[v]));
1226
1227 for (; it.valid() && (*it).m_low >= low[v]; it = itSucc) {
1228 itSucc = it.succ();
1229 if ((*it).m_high <= high[v]) {
1230 visibArcs.pushBack(Tuple2<node, node>((*it).m_pathNode, v));
1231 sweepLine.del(it);
1232 }
1233 }
1234
1235 if (it == itUp && (*it).m_high > high[v]) {
1236 node w = (*it).m_pathNode;
1237 sweepLine.insertAfter(Interval(w, (*it).m_low, low[v]), it);
1238 (*it).m_low = high[v];
1239 sweepLine.insertAfter(Interval(v, low[v], high[v]), it);
1240 visibArcs.pushBack(Tuple2<node, node>(w, v));
1241
1242 } else {
1243 if ((!isItUpDel) && itUp != it && (*itUp).m_low < high[v]) {
1244 (*itUp).m_low = high[v];
1245 visibArcs.pushBack(Tuple2<node, node>((*itUp).m_pathNode, v));
1246 }
1247 if (it.valid()) {
1248 if ((*it).m_high > low[v]) {
1249 (*it).m_high = low[v];
1250 visibArcs.pushBack(Tuple2<node, node>((*it).m_pathNode, v));
1251 }
1252 sweepLine.insertBefore(Interval(v, low[v], high[v]), it);
1253
1254 } else {
1255 sweepLine.pushBack(Interval(v, low[v], high[v]));
1256 }
1257 }
1258 }
1259
1260 // remove all arcs from visibArcs that are already in the constraint graph
1261 removeRedundantVisibArcs(visibArcs);
1262
1263 // compute original adjacency entry corresponding to a segment
1264 // We use this in order to omit visibility arcs between segments which
1265 // belong to the same edge if they can see each other from the same side
1266 // of the edge; if they see each other from different sides the arc is
1267 // essential!
1268 NodeArray<adjEntry> correspEdge(getGraph(), nullptr);
1269
1270 for (node v : PG.nodes) {
1271 node seg = m_pathNode[v];
1272 for (adjEntry adj : v->adjEntries) {
1273 if (m_pOR->direction(adj) != segDir) {
1274 continue;
1275 }
1276 edge eAdj = adj->theEdge();
1277 edge eOrig = PG.original(eAdj);
1278 if (eOrig == nullptr) {
1279 continue;
1280 }
1281 if (adj == eAdj->adjSource()) {
1282 correspEdge[seg] = eOrig->adjSource();
1283 } else {
1284 correspEdge[seg] = eOrig->adjTarget();
1285 }
1286 }
1287 }
1288
1289 // remove visibility arcs between ...
1291 for (itT = visibArcs.begin(); itT.valid(); itT = itTSucc) {
1292 itTSucc = itT.succ();
1293 node v = (*itT).x1(), w = (*itT).x2();
1294
1295 // remove arcs which connect segments belonging to the same edge
1296 if (correspEdge[v] && (correspEdge[v] == correspEdge[w])) {
1297 if (itTPred.valid()) {
1298 visibArcs.delSucc(itTPred);
1299 } else {
1300 visibArcs.popFront();
1301 }
1302 }
1303
1304 else {
1305 itTPred = itT;
1306 }
1307 }
1308
1309
1310 for (itT = visibArcs.begin(); itT.valid(); ++itT) {
1311 //CHECK if
1312 node v = (*itT).x1(), w = (*itT).x2();
1313 if (!(m_extraNode[v] || m_extraNode[w])) {
1314 //CHECK if
1315 node boundRepresentant1 = m_path[v].front();
1316 node boundRepresentant2 = m_path[w].front();
1317 node en1 = m_pPR->expandedNode(boundRepresentant1);
1318 node en2 = m_pPR->expandedNode(boundRepresentant2);
1319 //do not insert visibility in cages
1320 if (!((en1 && en2) && (en1 == en2))) {
1321 edge e = newEdge(v, w);
1322
1323 //hier vielleicht multiedges abfangen: length auf max(min(sep, dists), minDist.sep)
1324
1325 m_length[e] = max(m_sep, minDist.separation()); //m_sep;
1326 m_cost[e] = 0;
1328#if 0
1329 writeGML("visibilityinserted.gml");
1330#endif
1331 }
1332 }
1333 }
1334
1335 OGDF_HEAVY_ASSERT(checkSweepLine(sweepLine));
1336}
1337
1338// performs feasibility test for position assignment pos, i.e., checks if
1339// the segment positions given by pos fulfill the constraints in the
1340// compaction constraint graph
1341template<class ATYPE>
1343 for (edge e : getGraph().edges) {
1344 node v = m_path[e->source()].front();
1345 node w = m_path[e->target()].front();
1346 if (pos[w] - pos[v] < length(e)) {
1347 std::cout << "feasibility check failed for edge " << e << std::endl;
1348 std::cout << " representatives: " << v << ", " << w << std::endl;
1349 std::cout << " length: " << length(e) << std::endl;
1350 std::cout << " actual distance: " << pos[w] - pos[v] << std::endl;
1351 std::cout << " type of " << e << ": ";
1352 switch (m_type[e]) {
1354 std::cout << "basic arc" << std::endl;
1355 break;
1357 std::cout << "vertex-size arc" << std::endl;
1358 break;
1360 std::cout << "visibility arc" << std::endl;
1361 break;
1363 std::cout << "median arc" << std::endl;
1364 break;
1366 std::cout << "reducible arc" << std::endl;
1367 break;
1369 std::cout << "fixtozero arc" << std::endl;
1370 }
1371 return false;
1372 }
1373 }
1374
1375 return true;
1376}
1377
1378}
Declares ogdf::CommonCompactionConstraintGraphBase.
Declaration of class MinimumEdgeDistances which maintains minimum distances between attached edges at...
Declaration of a base class for planar representations of graphs and cluster graphs.
Declaration of class RoutingChannel which maintains required size of routing channels and separation,...
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry faceCyclePred() const
Returns the cyclic predecessor in face.
Definition Graph_d.h:152
adjEntry twin() const
Returns the corresponding adjacency element associated with the same edge.
Definition Graph_d.h:109
adjEntry cyclicSucc() const
Returns the cyclic successor in the adjacency list.
Definition Graph_d.h:291
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
adjEntry cyclicPred() const
Returns the cyclic predecessor in the adjacency list.
Definition Graph_d.h:295
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition Graph_d.h:112
node theNode() const
Returns the node whose adjacency list contains this element.
Definition Graph_d.h:103
adjEntry faceCycleSucc() const
Returns the cyclic successor in face.
Definition Graph_d.h:149
Exception thrown when an algorithm realizes an internal bug that prevents it from continuing.
Definition exceptions.h:241
Base class for ogdf::CompactionConstraintGraphBase.
NodeArray< bool > m_extraNode
Node does not represent drawing node as we dont have positions we save a drawing representant and an ...
NodeArray< node > m_extraRep
existing representant of extranodes position anchor
Comparer class used for sorting segments by increasing position (given by segPos) such that two overl...
SegmentComparer(const NodeArray< ATYPE > &segPos, const NodeArray< int > &secSort)
Class implementing template-parameter-independent behaviour of ogdf::CompactionConstraintGraph.
void align(bool b)
Triggers alignment (=>some special edge handling to support al.)
bool verticalArc(edge e) const
Returns true if e is basic arc of vertical edge in PlanRepUML hierarchy.
EdgeArray< bool > m_alignmentArc
Basic arcs that have to be short for alignment (node to gen expander)
void dfsInsertPathVertex(node v, node pathVertex, NodeArray< bool > &visited, const NodeArray< node > &genOpposite)
bool verticalGen(edge e) const
Returns true if e is vertical edge in PlanRepUML hierarchy.
EdgeArray< bool > m_verticalGen
generalization that runs vertical relative to hierarchy
bool alignmentArc(edge e) const
Returns if arc is important for alignment. These are the arcs representing node to gen....
void insertPathVertices(const PlanRep &PG)
CompactionConstraintGraphBase(const OrthoRep &OR, const PlanRep &PG, OrthoDir arcDir, int costGen=1, int costAssoc=1, bool align=false)
Construction.
void insertBasicArcs(const PlanRep &PG)
EdgeArray< bool > m_verticalArc
arc corresponding to such an edge
NodeArray< edge > m_pathToEdge
save the (single!) edge (segment) for a pathNode
Represents a constraint graph used for compaction.
ATYPE separation() const
Returns the separation value.
NodeArray< ATYPE > m_extraOfs
offset of extra node to its rep, should change this
bool m_genToMedian
draw outgoing generalization from merger above ingoing gen.
ATYPE extraOfs(node v) const
Returns extraNode position, change to save mem, only need some entries.
EdgeArray< ATYPE > m_length
length of an edge
void insertVertexSizeArcs(const PlanRep &PG, const NodeArray< ATYPE > &sizeOrig, const RoutingChannel< ATYPE > &rc)
Inserts arcs for respecting sizes of vertices and achieving desired placement of generalizations if v...
CompactionConstraintGraph(const OrthoRep &OR, const PlanRep &PG, OrthoDir arcDir, ATYPE sep, int costGen=1, int costAssoc=1, bool align=false)
Construction.
void setMinimumSeparation(const PlanRep &PG, const NodeArray< int > &coord, const MinimumEdgeDistances< ATYPE > &minDist)
Sets min separation for multi edge original.
void resetGenMergerLengths(const PlanRep &PG, adjEntry adjFirst)
void insertVisibilityArcs(const PlanRep &PG, const NodeArray< ATYPE > &posDir, const NodeArray< ATYPE > &posOppDir)
Inserts arcs connecting segments which can see each other in a drawing of the associated planarized r...
int m_doubleBendCost
try to minimize double bends
int m_bungeeCost
middle position distance penalty
bool centerPriority()
Gets centerPriority (center single edges?)
static const int c_MedianFactor
median arcs cost factor*vertexArcCost
bool isFeasible(const NodeArray< ATYPE > &pos)
Performs feasibility test for position assignment pos, i.e., checks if the segment positions given by...
virtual string getLengthString(edge e) const override
int m_MedianArcCost
draw merger gen at median of incoming generalizations
bool m_centerPriority
should centering be more expensive than generalizations
bool checkSweepLine(const List< Interval > &sweepLine) const
static const int c_doubleBendFactor
double bends cost factor*vertexArcCost
ATYPE length(edge e) const
Returns length of edge e.
void setBoundaryCosts(adjEntry cornerDir, adjEntry cornerOppDir)
void setExtra(node v, node rep, ATYPE ofs)
Node v has no representation in drawing, only internal representation.
void centerPriority(bool b)
Sets centerPriority (center single edges?)
bool areMulti(edge e1, edge e2) const
Return PG result for flowcompaction.
ATYPE computeTotalCosts(const NodeArray< ATYPE > &pos) const
Computes the total costs for coordintes given by pos, i.e., the sum of the weighted lengths of edges ...
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
void init()
Reinitializes the array. Associates the array with no graph.
Definition EdgeArray.h:292
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
NodeType
The type of nodes.
Definition Graph_d.h:569
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Encapsulates a pointer to a list element.
Definition List.h:103
bool valid() const
Returns true iff the iterator points to an element.
Definition List.h:137
ListIteratorBase< E, isConst, isReverse > succ() const
Returns successor iterator.
Definition List.h:158
Maintains input sizes for improvement compaction (deltas and epsilons)
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
void init()
Reinitializes the array. Associates the array with no graph.
Definition NodeArray.h:266
Class for the representation of nodes.
Definition Graph_d.h:177
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition Graph_d.h:220
Orthogonal representation of an embedded graph.
Definition OrthoRep.h:219
static OrthoDir prevDir(OrthoDir d)
Returns the previous OrthoDir (in a clockwise manner)
Definition OrthoRep.h:394
static OrthoDir nextDir(OrthoDir d)
Returns the next OrthoDir (in a clockwise manner)
Definition OrthoRep.h:389
Planarized representations (of a connected component) of a graph.
Definition PlanRep.h:57
Maintains input sizes for constructive compaction (size of routing channels, separation,...
ATYPE overhang() const
Encapsulates a pointer to an ogdf::SList element.
Definition SList.h:92
bool valid() const
Returns true iff the iterator points to an element.
Definition SList.h:122
Singly linked lists.
Definition SList.h:179
Tuples of two elements (2-tuples).
Definition tuples.h:46
#define OGDF_AUGMENT_COMPARER(type)
Add this macro to your class to turn it into a full comparer.
Definition comparer.h:179
#define OGDF_THROW(CLASS)
Replacement for throw.
Definition exceptions.h:63
#define OGDF_HEAVY_ASSERT(expr)
Assert condition expr when using heavy debugging. See OGDF_ASSERT.
Definition basic.h:44
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
@ ReducibleArc
can be compacted to zero length
@ FixToZeroArc
can be compacted to zero length, can be fixed
@ MedianArc
inserted to replace some reducible in fixzerolength
OrthoDir
Definition OrthoRep.h:50
Represents an interval on the sweep line.
friend std::ostream & operator<<(std::ostream &os, const Interval &interval)
output operator
Information about a side of a vertex in UML diagrams.
Definition OrthoRep.h:222
Further information about the cages of vertices in UML diagrams.
Definition OrthoRep.h:258