1 /** \file
2 * \brief Implementation of ExtendedNestingGraph and helper classes
3 *
4 * \author Carsten Gutwenger
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32 #include <ogdf/layered/ExtendedNestingGraph.h>
33 #include <ogdf/basic/simple_graph_alg.h>
34 #include <ogdf/layered/OptimalRanking.h>
35 #include <ogdf/basic/Queue.h>
36 #include <ogdf/basic/Array2D.h>
37 #include <ogdf/basic/Math.h>
38 #include <ogdf/cluster/ClusterSet.h>
39
40 using std::tuple;
41
42 namespace ogdf {
43
operator <<(std::ostream & os,const RCCrossings & cr)44 std::ostream& operator<<(std::ostream &os, const RCCrossings &cr)
45 {
46 os << "(" << cr.m_cnClusters << "," << cr.m_cnEdges << ")";
47 return os;
48 }
49
setPos()50 void LHTreeNode::setPos()
51 {
52 for(int i = 0; i <= m_child.high(); ++i)
53 m_child[i]->m_pos = i;
54 }
55
56
removeAuxChildren()57 void LHTreeNode::removeAuxChildren()
58 {
59 OGDF_ASSERT(isCompound());
60
61 int j = 0;
62 int i;
63 for(i = 0; i <= m_child.high(); ++i)
64 if(m_child[i]->m_type != Type::AuxNode)
65 m_child[j++] = m_child[i];
66 else
67 delete m_child[i];
68
69 int add = j-i;
70 if(add != 0)
71 m_child.grow(add, nullptr);
72 }
73
74
operator <<(std::ostream & os,const LHTreeNode * n)75 std::ostream &operator<<(std::ostream &os, const LHTreeNode *n)
76 {
77 if(n->isCompound()) {
78 os << "C" << n->originalCluster();
79
80 os << " [";
81 for(int i = 0; i < n->numberOfChildren(); ++i)
82 os << " " << n->child(i);
83 os << " ]";
84
85 } else {
86 os << "N" << n->getNode() << " ";
87 }
88
89 return os;
90 }
91
92
93 //! Compares adjacency entries in an LHTreeNode
94 class AdjacencyComparer
95 {
compare(const LHTreeNode::Adjacency & x,const LHTreeNode::Adjacency & y)96 static int compare(const LHTreeNode::Adjacency &x, const LHTreeNode::Adjacency &y)
97 {
98 if(x.m_u->index() < y.m_u->index())
99 return -1;
100
101 else if(x.m_u == y.m_u) {
102 if(x.m_v->isCompound()) {
103 if(!y.m_v->isCompound()) return -1;
104 return (x.m_v->originalCluster()->index() < y.m_v->originalCluster()->index()) ? -1 : +1;
105
106 } else if(y.m_v->isCompound())
107 return +1;
108
109 else
110 return (x.m_v->getNode()->index() < y.m_v->getNode()->index()) ? -1 : +1;
111
112 } else
113 return +1;
114 }
115
116 OGDF_AUGMENT_STATICCOMPARER(LHTreeNode::Adjacency)
117 };
118
119
~ENGLayer()120 ENGLayer::~ENGLayer()
121 {
122 Queue<LHTreeNode*> Q;
123 Q.append(m_root);
124
125 while(!Q.empty()) {
126 LHTreeNode *p = Q.pop();
127
128 for(int i = 0; i < p->numberOfChildren(); ++i)
129 Q.append(p->child(i));
130
131 delete p;
132 }
133 }
134
135
store()136 void ENGLayer::store() {
137 Queue<LHTreeNode*> Q;
138 Q.append(m_root);
139
140 while(!Q.empty()) {
141 LHTreeNode *p = Q.pop();
142
143 if(p->isCompound()) {
144 p->store();
145
146 for(int i = 0; i < p->numberOfChildren(); ++i)
147 Q.append(p->child(i));
148 }
149 }
150 }
151
152
restore()153 void ENGLayer::restore() {
154 Queue<LHTreeNode*> Q;
155 Q.append(m_root);
156
157 while(!Q.empty()) {
158 LHTreeNode *p = Q.pop();
159
160 if(p->isCompound()) {
161 p->restore();
162
163 for(int i = 0; i < p->numberOfChildren(); ++i)
164 Q.append(p->child(i));
165 }
166 }
167 }
168
169
permute()170 void ENGLayer::permute() {
171 Queue<LHTreeNode*> Q;
172 Q.append(m_root);
173
174 while(!Q.empty()) {
175 LHTreeNode *p = Q.pop();
176
177 if(p->isCompound()) {
178 p->permute();
179
180 for(int i = 0; i < p->numberOfChildren(); ++i)
181 Q.append(p->child(i));
182 }
183 }
184 }
185
186
removeAuxNodes()187 void ENGLayer::removeAuxNodes() {
188 Queue<LHTreeNode*> Q;
189 Q.append(m_root);
190
191 while(!Q.empty()) {
192 LHTreeNode *p = Q.pop();
193
194 if(p->isCompound()) {
195 p->removeAuxChildren();
196
197 for(int i = 0; i < p->numberOfChildren(); ++i)
198 Q.append(p->child(i));
199 }
200 }
201 }
202
203
simplifyAdjacencies(List<LHTreeNode::Adjacency> & adjs)204 void ENGLayer::simplifyAdjacencies(List<LHTreeNode::Adjacency> &adjs)
205 {
206 AdjacencyComparer cmp;
207
208 if(!adjs.empty()) {
209 adjs.quicksort(cmp);
210
211 ListIterator<LHTreeNode::Adjacency> it = adjs.begin();
212 ListIterator<LHTreeNode::Adjacency> itNext = it.succ();
213
214 while(itNext.valid()) {
215 if((*it).m_u == (*itNext).m_u && (*it).m_v == (*itNext).m_v) {
216 (*it).m_weight += (*itNext).m_weight;
217
218 adjs.del(itNext);
219 itNext = it.succ();
220
221 } else {
222 it = itNext;
223 ++itNext;
224 }
225 }
226 }
227 }
228
229
simplifyAdjacencies()230 void ENGLayer::simplifyAdjacencies()
231 {
232 Queue<LHTreeNode*> Q;
233 Q.append(m_root);
234
235 while(!Q.empty()) {
236 LHTreeNode *p = Q.pop();
237
238 simplifyAdjacencies(p->m_upperAdj);
239 simplifyAdjacencies(p->m_lowerAdj);
240
241 for(int i = 0; i < p->numberOfChildren(); ++i)
242 Q.append(p->child(i));
243 }
244 }
245
246
ClusterGraphCopy()247 ClusterGraphCopy::ClusterGraphCopy()
248 {
249 m_pCG = nullptr;
250 m_pH = nullptr;
251 }
252
ClusterGraphCopy(const ExtendedNestingGraph & H,const ClusterGraph & CG)253 ClusterGraphCopy::ClusterGraphCopy(const ExtendedNestingGraph &H, const ClusterGraph &CG)
254 : ClusterGraph(H), m_pCG(&CG), m_pH(&H), m_copy(CG,nullptr)
255 {
256 m_original.init(*this,nullptr);
257 m_copy [CG.rootCluster()] = rootCluster();
258 m_original[rootCluster()] = CG.rootCluster();
259
260 createClusterTree(CG.rootCluster());
261 }
262
263
init(const ExtendedNestingGraph & H,const ClusterGraph & CG)264 void ClusterGraphCopy::init(const ExtendedNestingGraph &H, const ClusterGraph &CG)
265 {
266 ClusterGraph::init(H);
267 m_pCG = &CG;
268 m_pH = &H;
269 m_copy .init(CG,nullptr);
270 m_original.init(*this,nullptr);
271
272 m_copy [CG.rootCluster()] = rootCluster();
273 m_original[rootCluster()] = CG.rootCluster();
274
275 createClusterTree(CG.rootCluster());
276 }
277
278
createClusterTree(cluster cOrig)279 void ClusterGraphCopy::createClusterTree(cluster cOrig)
280 {
281 cluster c = m_copy[cOrig];
282
283 for (cluster childOrig : cOrig->children) {
284 cluster child = newCluster(c);
285 m_copy [childOrig] = child;
286 m_original[child] = childOrig;
287
288 createClusterTree(childOrig);
289 }
290
291 ListConstIterator<node> itV;
292 for(itV = cOrig->nBegin(); itV.valid(); ++itV) {
293 reassignNode(m_pH->copy(*itV), c);
294 }
295 }
296
297
setParent(node v,cluster c)298 void ClusterGraphCopy::setParent(node v, cluster c)
299 {
300 reassignNode(v, c);
301 }
302
303
ExtendedNestingGraph(const ClusterGraph & CG)304 ExtendedNestingGraph::ExtendedNestingGraph(const ClusterGraph &CG) :
305 m_copy(CG),
306 m_topNode(CG),
307 m_bottomNode(CG),
308 m_copyEdge(CG),
309 m_mark(CG, nullptr)
310 {
311 const Graph &G = CG;
312
313 m_origNode.init(*this, nullptr);
314 m_type .init(*this, NodeType::Dummy);
315 m_origEdge.init(*this, nullptr);
316
317 // Create nodes
318 for(node v : G.nodes) {
319 node vH = newNode();
320 m_copy [v] = vH;
321 m_origNode[vH] = v;
322 m_type[vH] = NodeType::Node;
323 }
324
325 m_CGC.init(*this,CG);
326
327 for(cluster c : CG.clusters) {
328 m_type[m_topNode [c] = newNode()] = NodeType::ClusterTop;
329 m_type[m_bottomNode[c] = newNode()] = NodeType::ClusterBottom;
330
331 m_CGC.setParent(m_topNode [c], m_CGC.copy(c));
332 m_CGC.setParent(m_bottomNode[c], m_CGC.copy(c));
333 }
334
335 // Create edges
336 for(node v : G.nodes) {
337 node vH = m_copy[v];
338 cluster c = CG.clusterOf(v);
339
340 newEdge(m_topNode[c], vH);
341 newEdge(vH, m_bottomNode[c]);
342 }
343
344 for(cluster c : CG.clusters) {
345 if(c != CG.rootCluster()) {
346 cluster u = c->parent();
347
348 newEdge(m_topNode[u], m_topNode[c]);
349 newEdge(m_bottomNode[c], m_bottomNode[u]);
350
351 newEdge(m_topNode[c], m_bottomNode[c]);
352 }
353 }
354
355 OGDF_ASSERT(isAcyclic(*this));
356
357
358 // preparation for improved test for cycles
359 m_aeLevel.init(*this, -1);
360 int count = 0;
361 assignAeLevel(CG.rootCluster(), count);
362 m_aeVisited.init(*this, false);
363
364
365 // Add adjacency edges
366 for(edge e : G.edges) {
367 edge eH = addEdge(m_copy[e->source()], m_copy[e->target()], true);
368 m_copyEdge[e].pushBack(eH);
369 m_origEdge[eH] = e;
370 }
371
372 // Add additional edges between nodes and clusters to reflect adjacency hierarchy also
373 // with respect to clusters
374 for(edge e : G.edges) {
375 node u = e->source();
376 node v = e->target();
377
378 // e was reversed?
379 if(m_copyEdge[e].front()->source() != m_copy[e->source()])
380 std::swap(u, v);
381
382 if(CG.clusterOf(u) != CG.clusterOf(v)) {
383 cluster c = lca(u, v);
384 cluster cTo, cFrom;
385
386 if(m_secondPathTo == v) {
387 cTo = m_secondPath;
388 cFrom = m_mark[c];
389 } else {
390 cFrom = m_secondPath;
391 cTo = m_mark[c];
392 }
393
394 // Transfer adjacency relationship to a relationship between clusters
395 // "clusters shall be above each other"
396 edge eH = nullptr;
397 if(cFrom != c && cTo != c)
398 eH = addEdge(m_bottomNode[cFrom], m_topNode[cTo]);
399
400 // if this is not possible, try to relax it to a relationship between node and cluster
401 if(eH == nullptr) {
402 addEdge(m_copy[u], m_topNode[cTo]);
403 addEdge(m_bottomNode[cFrom], m_copy[v]);
404 }
405 }
406 }
407
408 OGDF_ASSERT(isAcyclic(*this));
409
410 // cleanup
411 m_aeVisited.init();
412 m_aeLevel.init();
413
414 // compute ranking and proper hierarchy
415 computeRanking();
416 createDummyNodes();
417 #if 0
418 createVirtualClusters();
419 #endif
420 buildLayers();
421
422 // assign positions on top layer
423 m_pos.init(*this);
424 count = 0;
425 assignPos(m_layer[0].root(), count);
426 }
427
computeRanking()428 void ExtendedNestingGraph::computeRanking()
429 {
430 // Compute ranking
431 OptimalRanking ranking;
432 ranking.separateMultiEdges(false);
433
434 EdgeArray<int> length(*this);
435 EdgeArray<int> cost(*this);
436 for(edge e : edges) {
437 NodeType typeSrc = type(e->source());
438 NodeType typeTgt = type(e->target());
439
440 if(typeSrc == NodeType::Node && typeTgt == NodeType::Node)
441 length[e] = 2; // Node -> Node
442 else if (typeSrc != NodeType::Node && typeTgt != NodeType::Node)
443 length[e] = 2; // Cluster -> Cluster
444 else
445 length[e] = 1; // Node <-> Cluster
446
447 cost[e] = (origEdge(e) != nullptr) ? 2 : 1;
448 }
449
450 ranking.call(*this, length, cost, m_rank);
451
452 // adjust ranks of top / bottom node
453 for(cluster c = m_CGC.firstPostOrderCluster(); c != nullptr; c = c->pSucc())
454 {
455 int t = std::numeric_limits<int>::max();
456 int b = std::numeric_limits<int>::min();
457
458 ListConstIterator<node> itV;
459 for(itV = c->nBegin(); itV.valid(); ++itV) {
460 if(type(*itV) != NodeType::Node)
461 continue;
462
463 int r = m_rank[*itV];
464 if(r-1 < t)
465 t = r-1;
466 if(r+1 > b)
467 b = r+1;
468 }
469
470 for (cluster child : c->children) {
471 int rb = m_rank[bottom(m_CGC.original(child))];
472 if(rb+2 > b)
473 b = rb+2;
474 int rt = m_rank[top(m_CGC.original(child))];
475 if(rt-2 < t)
476 t = rt-2;
477 }
478
479 cluster cOrig = m_CGC.original(c);
480 OGDF_ASSERT(m_rank[top(cOrig)] <= t);
481 OGDF_ASSERT(b <= m_rank[bottom(cOrig)]);
482
483 if(t < std::numeric_limits<int>::max()) {
484 m_rank[top (cOrig)] = t;
485 m_rank[bottom(cOrig)] = b;
486 }
487 }
488
489 // Remove all non-adjacency edges
490 edge eNext;
491 for(edge e = firstEdge(); e != nullptr; e = eNext) {
492 eNext = e->succ();
493 if(m_origEdge[e] == nullptr) {
494 cluster c = originalCluster(e->source());
495 // we do not remove edges from top(c)->bottom(c)
496 if(e->source() != top(c) || e->target() != bottom(c))
497 delEdge(e);
498 }
499 }
500
501 // Remove nodes for root cluster
502 cluster r = getOriginalClusterGraph().rootCluster();
503 int high = m_rank[m_bottomNode[r]];
504 int low = m_rank[m_topNode[r]];
505
506 delNode(m_topNode[r]);
507 delNode(m_bottomNode[r]);
508 m_topNode [r] = nullptr;
509 m_bottomNode[r] = nullptr;
510
511 // Reassign ranks
512 Array<SListPure<node> > levels(low,high);
513
514 for(node v : nodes)
515 levels[m_rank[v]].pushBack(v);
516
517 int currentRank = 0;
518 for(int i = low+1; i < high; ++i)
519 {
520 SListPure<node> &L = levels[i];
521 if(L.empty())
522 continue;
523
524 for(node v : L)
525 m_rank[v] = currentRank;
526
527 ++currentRank;
528 }
529
530 m_numLayers = currentRank;
531 }
532
533
createDummyNodes()534 void ExtendedNestingGraph::createDummyNodes()
535 {
536 const ClusterGraph &CG = getOriginalClusterGraph();
537 const Graph &G = CG;
538
539 for(edge e : G.edges)
540 {
541 edge eH = m_copyEdge[e].front();
542 node uH = eH->source();
543 node vH = eH->target();
544
545 int span = m_rank[vH] - m_rank[uH];
546 OGDF_ASSERT(span >= 1);
547 if(span < 2)
548 continue;
549
550 // find cluster cTop containing both u and v
551 node u = m_origNode[uH];
552 node v = m_origNode[vH];
553
554 cluster cTop = lca(u,v);
555
556 // create split nodes
557 for(int i = m_rank[uH]+1; i < m_rank[vH]; ++i) {
558 eH = split(eH);
559 m_copyEdge[e].pushBack(eH);
560 m_origEdge[eH] = e;
561 m_rank[eH->source()] = i;
562 // assign preliminary cTop to all dummies since this is ok
563 // try to aesthetically improve this later
564 m_CGC.setParent(eH->source(), m_CGC.copy(cTop));
565 }
566
567 // improve cluster assignment
568 cluster c_1 = CG.clusterOf(u);
569 cluster c_2 = CG.clusterOf(v);
570 cluster root = CG.rootCluster();
571
572 if(c_1 == root || c_2 == root || m_rank[m_bottomNode[c_1]] >= m_rank[m_topNode[c_2]]) {
573 if(c_2 != root && m_rank[uH] < m_rank[m_topNode[c_2]])
574 {
575 c_1 = nullptr;
576 while(c_2->parent() != root && m_rank[uH] < m_rank[m_topNode[c_2->parent()]])
577 c_2 = c_2->parent();
578 }
579 else if(c_1 != root && m_rank[vH] > m_rank[m_bottomNode[c_1]])
580 {
581 c_2 = nullptr;
582 while(c_1->parent() != root && m_rank[vH] > m_rank[m_bottomNode[c_1->parent()]])
583 c_1 = c_1->parent();
584
585 } else {
586 continue; // leave all dummies in cTop
587 }
588
589 } else {
590 bool cont;
591 do {
592 cont = false;
593
594 cluster parent = c_1->parent();
595 if(parent != root && m_rank[m_bottomNode[parent]] < m_rank[m_topNode[c_2]]) {
596 c_1 = parent;
597 cont = true;
598 }
599
600 parent = c_2->parent();
601 if(parent != root && m_rank[m_bottomNode[c_1]] < m_rank[m_topNode[parent]]) {
602 c_2 = parent;
603 cont = true;
604 }
605
606 } while(cont);
607 }
608
609 if(c_1 != nullptr) {
610 ListConstIterator<edge> it = m_copyEdge[e].begin();
611 for(cluster c = CG.clusterOf(u); c != c_1->parent(); c = c->parent()) {
612 while(m_rank[(*it)->target()] <= m_rank[m_bottomNode[c]]) {
613 m_CGC.setParent((*it)->target(), m_CGC.copy(c));
614 ++it;
615 }
616 }
617 }
618
619 if(c_2 != nullptr) {
620 ListConstReverseIterator<edge> it = m_copyEdge[e].rbegin();
621 for(cluster c = CG.clusterOf(v); c != c_2->parent(); c = c->parent()) {
622 while(m_rank[(*it)->source()] >= m_rank[m_topNode[c]]) {
623 m_CGC.setParent((*it)->source(), m_CGC.copy(c));
624 ++it;
625 }
626 }
627 }
628 }
629
630 // create dummy nodes for edges top(c)->bottom(c)
631 for(cluster c : CG.clusters)
632 {
633 if(c == CG.rootCluster())
634 continue;
635
636 node vTop = top(c);
637 node vBottom = bottom(c);
638
639 for(adjEntry adj : vTop->adjEntries) {
640 edge e = adj->theEdge();
641 if(e->target() == vBottom) {
642 int span = m_rank[vBottom] - m_rank[vTop];
643 OGDF_ASSERT(span >= 1);
644 if(span < 2)
645 continue;
646
647 // create split nodes
648 edge eH = e;
649 for(int i = m_rank[vTop]+1; i < m_rank[vBottom]; ++i) {
650 eH = split(eH);
651 m_rank[eH->source()] = i;
652 m_type[eH->source()] = NodeType::ClusterTopBottom;
653 m_CGC.setParent(eH->source(), m_CGC.copy(c));
654 }
655 break;
656 }
657 }
658 }
659 }
660
661
createVirtualClusters()662 void ExtendedNestingGraph::createVirtualClusters()
663 {
664 NodeArray <node> vCopy(*this);
665 ClusterArray<node> cCopy(m_CGC);
666
667 createVirtualClusters(m_CGC.rootCluster(), vCopy, cCopy);
668
669 // for each original edge, put the edge segments that are in the same cluster
670 // into a separate cluster
671 for(edge eOrig : m_CGC.getOriginalClusterGraph().constGraph().edges)
672 {
673 const List<edge> &L = m_copyEdge[eOrig];
674 if(L.size() >= 3) {
675 ListConstIterator<edge> it = L.begin().succ();
676 node v = (*it)->source();
677
678 cluster c = parent(v);
679 SList<node> nextCluster;
680 nextCluster.pushBack(v);
681
682 for(++it; it.valid(); ++it) {
683 node u = (*it)->source();
684 cluster cu = parent(u);
685
686 if(cu != c) {
687 if(nextCluster.size() > 1)
688 m_CGC.createCluster(nextCluster, c);
689
690 nextCluster.clear();
691 c = cu;
692 }
693
694 nextCluster.pushBack(u);
695 }
696
697 if(nextCluster.size() > 1)
698 m_CGC.createCluster(nextCluster, c);
699 }
700 }
701 }
702
703
createVirtualClusters(cluster c,NodeArray<node> & vCopy,ClusterArray<node> & cCopy)704 void ExtendedNestingGraph::createVirtualClusters(
705 cluster c,
706 NodeArray<node> &vCopy,
707 ClusterArray<node> &cCopy)
708 {
709 if(c->cCount() >= 1 && c->nCount() >= 1)
710 {
711 // build auxiliaray graph G
712 Graph G;
713
714 ListConstIterator<node> itV;
715 for(itV = c->nBegin(); itV.valid(); ++itV) {
716 vCopy[*itV] = G.newNode();
717 }
718
719 for (cluster child : c->children)
720 cCopy[child] = G.newNode();
721
722 for(itV = c->nBegin(); itV.valid(); ++itV) {
723 node v = *itV;
724 for(adjEntry adj : v->adjEntries) {
725 if(origEdge(adj->theEdge()) == nullptr)
726 continue;
727
728 node w = adj->twinNode();
729 cluster cw = parent(w);
730 if(cw == c)
731 G.newEdge(vCopy[v],vCopy[w]);
732
733 else if(cw->parent() == c) {
734 cluster cwOrig = m_CGC.original(cw);
735 OGDF_ASSERT(cwOrig != nullptr);
736 if(rank(w) == rank(top(cwOrig)) || rank(w) == rank(bottom(cwOrig)))
737 G.newEdge(vCopy[v],cCopy[cw]);
738 }
739 }
740 }
741
742 // find connect components in G
743 NodeArray<int> component(G);
744 int k = connectedComponents(G, component);
745
746 // create virtual clusters
747 if(k > 1) {
748 Array<SList<node > > nodeList(k);
749 Array<SList<cluster> > clusters(k);
750
751 for(itV = c->nBegin(); itV.valid(); ++itV)
752 nodeList[component[vCopy[*itV]]].pushBack(*itV);
753
754 for(cluster child : c->children)
755 clusters[component[cCopy[child]]].pushBack(child);
756
757 for(int i = 0; i < k; ++i) {
758 if(nodeList[i].size() + clusters[i].size() > 1) {
759 cluster cVirt = m_CGC.createCluster(nodeList[i], c);
760 for(cluster ci : clusters[i])
761 m_CGC.moveCluster(ci,cVirt);
762 }
763 }
764 }
765 }
766
767 // recursive call
768 for(cluster child : c->children)
769 createVirtualClusters(child, vCopy, cCopy);
770 }
771
772
buildLayers()773 void ExtendedNestingGraph::buildLayers()
774 {
775 m_layer.init(m_numLayers);
776
777 Array<List<node> > L(m_numLayers);
778
779 for(node v : nodes) {
780 L[rank(v)].pushBack(v);
781 }
782
783 // compute minimum and maximum level of each cluster
784 m_topRank.init(m_CGC,m_numLayers);
785 m_bottomRank.init(m_CGC,0);
786 cluster c;
787 forall_postOrderClusters(c, m_CGC) {
788 ListConstIterator<node> itV;
789 for(itV = c->nBegin(); itV.valid(); ++itV) {
790 int r = rank(*itV);
791 if(r > m_bottomRank[c])
792 m_bottomRank[c] = r;
793 if(r < m_topRank[c])
794 m_topRank[c] = r;
795 }
796 for (cluster child : c->children) {
797 if(m_topRank[child] < m_topRank[c])
798 m_topRank[c] = m_topRank[child];
799 if(m_bottomRank[child] > m_bottomRank[c])
800 m_bottomRank[c] = m_bottomRank[child];
801 }
802 }
803
804 Array<SListPure<cluster> > clusterBegin(m_numLayers);
805 Array<SListPure<cluster> > clusterEnd(m_numLayers);
806
807 for(cluster cl : m_CGC.clusters) {
808 clusterBegin[m_topRank [cl]].pushBack(cl);
809 clusterEnd [m_bottomRank[cl]].pushBack(cl);
810 }
811
812
813 ClusterSetPure activeClusters(m_CGC);
814 activeClusters.insert(m_CGC.rootCluster());
815
816 ClusterArray<LHTreeNode*> clusterToTreeNode(m_CGC, nullptr);
817 ClusterArray<int> numChildren(m_CGC, 0);
818 NodeArray<LHTreeNode*> treeNode(*this, nullptr);
819
820 int i;
821 for(i = 0; i < m_numLayers; ++i) {
822 // identify new clusters on this layer
823 for(node v : L[i]) {
824 ++numChildren[parent(v)];
825 }
826
827 for(cluster cActive : clusterBegin[i])
828 activeClusters.insert(cActive);
829
830 // create compound tree nodes
831 for(cluster cl : activeClusters.clusters()) {
832 clusterToTreeNode[cl] = new LHTreeNode(cl, clusterToTreeNode[cl]);
833 if(cl != m_CGC.rootCluster())
834 ++numChildren[cl->parent()];
835 }
836
837 // initialize child arrays
838 for(cluster cl : activeClusters.clusters()) {
839 clusterToTreeNode[cl]->initChild(numChildren[cl]);
840 }
841
842 // set parent and children of compound tree nodes
843 for(cluster cl : activeClusters.clusters()) {
844 if(cl != m_CGC.rootCluster()) {
845 LHTreeNode *cNode = clusterToTreeNode[cl];
846 LHTreeNode *pNode = clusterToTreeNode[cl->parent()];
847
848 cNode->setParent(pNode);
849 pNode->setChild(--numChildren[cl->parent()], cNode);
850 }
851 }
852
853 // set root of layer
854 m_layer[i].setRoot(clusterToTreeNode[m_CGC.rootCluster()]);
855
856 // create tree nodes for nodes on this layer
857 for(node v : L[i]) {
858 LHTreeNode *cNode = clusterToTreeNode[parent(v)];
859 LHTreeNode::Type type = (m_type[v] == NodeType::ClusterTopBottom) ?
860 LHTreeNode::Type::AuxNode : LHTreeNode::Type::Node;
861 LHTreeNode *vNode = new LHTreeNode(cNode, v, type);
862 treeNode[v] = vNode;
863 cNode->setChild(--numChildren[parent(v)], vNode);
864 }
865
866 // clean-up
867 for(cluster cl : activeClusters.clusters()) {
868 numChildren[cl] = 0;
869 }
870
871 // identify clusters that are not on next layer
872 for(cluster cActive : clusterEnd[i])
873 activeClusters.remove(cActive);
874 }
875
876 // identify adjacencies between nodes and tree nodes
877 for(edge e : edges)
878 {
879 node u = e->source();
880 node v = e->target();
881 bool isTopBottomEdge = (origEdge(e) == nullptr);
882 int weight = (isTopBottomEdge) ? 100 : 1;
883
884 if(isTopBottomEdge)
885 continue;
886
887 LHTreeNode *nd = treeNode[v];
888 LHTreeNode *parent = nd->parent();
889 if(isTopBottomEdge) {
890 nd = parent;
891 parent = parent->parent();
892 }
893
894 while(parent != nullptr) {
895 parent->m_upperAdj.pushBack(LHTreeNode::Adjacency(u,nd,weight));
896
897 nd = parent;
898 parent = parent->parent();
899 }
900
901 nd = treeNode[u];
902 parent = nd->parent();
903 if(isTopBottomEdge) {
904 nd = parent;
905 parent = parent->parent();
906 }
907
908 while(parent != nullptr) {
909 parent->m_lowerAdj.pushBack(LHTreeNode::Adjacency(v,nd,weight));
910
911 nd = parent;
912 parent = parent->parent();
913 }
914 }
915
916 for(i = 0; i < m_numLayers; ++i)
917 m_layer[i].simplifyAdjacencies();
918
919
920 // identify relevant pairs for crossings between top->bottom edges
921 // and foreign edges
922 m_markTree.init(m_CGC,nullptr);
923 ClusterArray<List<tuple<edge,LHTreeNode*,LHTreeNode*> > > edgeArray(m_CGC);
924 ClusterSetSimple C(m_CGC);
925 for(i = 0; i < m_numLayers-1; ++i)
926 {
927 for(node u : L[i]) {
928 for(adjEntry adj : u->adjEntries) {
929 edge e = adj->theEdge();
930 if(origEdge(e) == nullptr)
931 continue;
932 if(e->source() == u) {
933 node v = e->target();
934
935 LHTreeNode *uChild, *vChild;
936 cluster cl = lca(treeNode[u], treeNode[v], &uChild, &vChild)->originalCluster();
937
938 edgeArray[cl].pushBack(std::make_tuple(e,uChild,vChild));
939 C.insert(c);
940 }
941 }
942 }
943
944 for(node u : L[i]) {
945 for(adjEntry adj : u->adjEntries) {
946 edge e = adj->theEdge();
947 if(e->source() == u && origEdge(e) == nullptr) {
948 LHTreeNode *aNode = treeNode[e->target()];
949 cluster ca = aNode->parent()->originalCluster();
950 LHTreeNode *aParent = aNode->parent()->parent();
951
952 for(; aParent != nullptr; aParent = aParent->parent()) {
953 for(const auto &tup : edgeArray[aParent->originalCluster()])
954 {
955 edge e_tup = std::get<0>(tup);
956
957 LHTreeNode *aChild, *vChild, *h1, *h2;
958 LHTreeNode *cNode = lca(aNode, treeNode[e_tup->target()], &aChild, &vChild);
959 if(cNode != aNode->parent() &&
960 lca(aNode,treeNode[e_tup->source()],&h1,&h2)->originalCluster() != ca)
961 cNode->m_upperClusterCrossing.pushBack(
962 LHTreeNode::ClusterCrossing(e->source(), aChild, e_tup->source(), vChild, e_tup));
963 }
964 }
965
966 aNode = treeNode[e->source()];
967 ca = aNode->parent()->originalCluster();
968 aParent = aNode->parent()->parent();
969
970 for(; aParent != nullptr; aParent = aParent->parent()) {
971 for(const auto &tup : edgeArray[aParent->originalCluster()])
972 {
973 edge e_tup = std::get<0>(tup);
974
975 LHTreeNode *aChild, *vChild, *h1, *h2;
976 LHTreeNode *cNode = lca(aNode, treeNode[e_tup->source()],
977 &aChild, &vChild);
978 if(cNode != aNode->parent() &&
979 lca(aNode,treeNode[e_tup->target()],&h1,&h2)->originalCluster() != ca)
980 cNode->m_lowerClusterCrossing.pushBack(
981 LHTreeNode::ClusterCrossing(e->target(), aChild, e_tup->target(), vChild, e_tup));
982 }
983 }
984 }
985 }
986 }
987
988 // get rid of edges in edgeArray[c]
989 for(cluster cl : C.clusters())
990 edgeArray[cl].clear();
991 C.clear();
992 }
993
994 // clean-up
995 m_markTree.init();
996 }
997
998
storeCurrentPos()999 void ExtendedNestingGraph::storeCurrentPos()
1000 {
1001 for(int i = 0; i < m_numLayers; ++i)
1002 m_layer[i].store();
1003 }
1004
1005
restorePos()1006 void ExtendedNestingGraph::restorePos()
1007 {
1008 for(int i = 0; i < m_numLayers; ++i) {
1009 m_layer[i].restore();
1010
1011 int count = 0;
1012 assignPos(m_layer[i].root(), count);
1013 }
1014 }
1015
1016
permute()1017 void ExtendedNestingGraph::permute()
1018 {
1019 for(int i = 0; i < m_numLayers; ++i)
1020 m_layer[i].permute();
1021
1022 int count = 0;
1023 assignPos(m_layer[0].root(), count);
1024 }
1025
1026
reduceCrossings(int i,bool dirTopDown)1027 RCCrossings ExtendedNestingGraph::reduceCrossings(int i, bool dirTopDown)
1028 {
1029 //std::cout << "Layer " << i << ":\n";
1030 LHTreeNode *root = m_layer[i].root();
1031
1032 ArrayBuffer<LHTreeNode*> S;
1033 S.push(root);
1034
1035 RCCrossings numCrossings;
1036 while(!S.empty()) {
1037 LHTreeNode *cNode = S.popRet();
1038 numCrossings += reduceCrossings(cNode, dirTopDown);
1039
1040 for(int j = 0; j < cNode->numberOfChildren(); ++j) {
1041 if(cNode->child(j)->isCompound())
1042 S.push(cNode->child(j));
1043 }
1044 }
1045
1046 // set positions
1047 int count = 0;
1048 assignPos(root, count);
1049
1050 return numCrossings;
1051 }
1052
1053
1054 struct RCEdge
1055 {
RCEdgeogdf::RCEdge1056 RCEdge() { }
RCEdgeogdf::RCEdge1057 RCEdge(node src, node tgt, RCCrossings cr, RCCrossings crReverse)
1058 : m_src(src), m_tgt(tgt), m_cr(cr), m_crReverse(crReverse) { }
1059
weightogdf::RCEdge1060 RCCrossings weight() const { return m_crReverse - m_cr; }
1061
1062 node m_src;
1063 node m_tgt;
1064 RCCrossings m_cr;
1065 RCCrossings m_crReverse;
1066 };
1067
1068
1069 class LocationRelationshipComparer
1070 {
1071 public:
compare(const RCEdge & x,const RCEdge & y)1072 static int compare(const RCEdge &x, const RCEdge &y)
1073 {
1074 return RCCrossings::compare(x.weight(), y.weight());
1075 }
1076 OGDF_AUGMENT_STATICCOMPARER(RCEdge)
1077 };
1078
1079
tryEdge(node u,node v,Graph & G,NodeArray<int> & level)1080 bool ExtendedNestingGraph::tryEdge(node u, node v, Graph &G, NodeArray<int> &level)
1081 {
1082 const int n = G.numberOfNodes();
1083
1084 if(level[u] == -1) {
1085 if(level[v] == -1) {
1086 level[v] = n;
1087 level[u] = n-1;
1088 } else
1089 level[u] = level[v]-1;
1090
1091 } else if(level[v] == -1)
1092 level[v] = level[u]+1;
1093
1094 else if(level[u] >= level[v]) {
1095 SListPure<node> successors;
1096 if(reachable(v, u, successors))
1097 return false;
1098 else {
1099 level[v] = level[u] + 1;
1100 moveDown(v, successors, level);
1101 }
1102 }
1103
1104 G.newEdge(u,v);
1105
1106 return true;
1107 }
1108
1109
reduceCrossings(LHTreeNode * cNode,bool dirTopDown)1110 RCCrossings ExtendedNestingGraph::reduceCrossings(LHTreeNode *cNode, bool dirTopDown)
1111 {
1112 const int n = cNode->numberOfChildren();
1113 if(n < 2)
1114 return RCCrossings(); // nothing to do
1115
1116 cNode->setPos();
1117
1118 // Build
1119 // crossings matrix
1120 Array2D<RCCrossings> cn(0,n-1,0,n-1);
1121
1122 // crossings between adjacency edges
1123 Array<List<LHTreeNode::Adjacency> > adj(n);
1124 ListConstIterator<LHTreeNode::Adjacency> it;
1125 for(it = (dirTopDown) ? cNode->m_upperAdj.begin() : cNode->m_lowerAdj.begin(); it.valid(); ++it)
1126 adj[(*it).m_v->pos()].pushBack(*it);
1127
1128 int j;
1129 for(j = 0; j < n; ++j) {
1130 for (const LHTreeNode::Adjacency &adjJ : adj[j]) {
1131 int posJ = m_pos[(adjJ).m_u];
1132
1133 for(int k = j+1; k < n; ++k) {
1134 for (const LHTreeNode::Adjacency &adjK : adj[k]) {
1135 int posK = m_pos[adjK.m_u];
1136 int weight = adjJ.m_weight * adjK.m_weight;
1137
1138 if(posJ > posK)
1139 cn(j,k).incEdges(weight);
1140 if(posK > posJ)
1141 cn(k,j).incEdges(weight);
1142 }
1143 }
1144 }
1145 }
1146
1147 // crossings between clusters and foreign adjacency edges
1148 ListConstIterator<LHTreeNode::ClusterCrossing> itCC;
1149 for(itCC = (dirTopDown) ?
1150 cNode->m_upperClusterCrossing.begin() : cNode->m_lowerClusterCrossing.begin();
1151 itCC.valid(); ++itCC)
1152 {
1153 /*std::cout << "crossing: C" << m_CGC.clusterOf((*itCC).m_edgeCluster->source()) <<
1154 " e=" << (*itCC).m_edgeCluster << " with edge " << (*itCC).m_edge <<
1155 " cluster: C" << m_CGC.clusterOf((*itCC).m_edge->source()) <<
1156 ", C" << m_CGC.clusterOf((*itCC).m_edge->target()) << "\n";*/
1157
1158 int cPos = (*itCC).m_cNode->pos();
1159 int uPos = (*itCC).m_uNode->pos();
1160
1161 int posJ = m_pos[(*itCC).m_uc];
1162 int posK = m_pos[(*itCC).m_u];
1163
1164 OGDF_ASSERT(cPos != uPos);
1165 OGDF_ASSERT(posJ != posK);
1166
1167 if(posJ > posK)
1168 cn(cPos,uPos).incClusters();
1169 else
1170 cn(uPos,cPos).incClusters();
1171 }
1172
1173
1174 Graph G; // crossing reduction graph
1175 NodeArray<int> level(G,-1);
1176 m_aeVisited.init(G,false);
1177 m_auxDeg.init(G,0);
1178
1179 // create nodes
1180 NodeArray<LHTreeNode*> fromG(G);
1181 Array<node> toG(n);
1182
1183 for(j = 0; j < n; ++j)
1184 fromG[toG[j] = G.newNode()] = cNode->child(j);
1185
1186 // create edges for l-r constraints
1187 const LHTreeNode *neighbourParent = (dirTopDown) ? cNode->up() : cNode->down();
1188 if(neighbourParent != nullptr) {
1189 node src = nullptr;
1190 for(int i = 0; i < neighbourParent->numberOfChildren(); ++i) {
1191 const LHTreeNode *vNode =
1192 (dirTopDown) ?
1193 neighbourParent->child(i)->down() : neighbourParent->child(i)->up();
1194
1195 if(vNode != nullptr) {
1196 node tgt = toG[vNode->pos()];
1197 if(src != nullptr) {
1198 #ifdef OGDF_DEBUG
1199 bool result =
1200 #endif
1201 tryEdge(src, tgt, G, level);
1202 OGDF_ASSERT(result);
1203 }
1204 src = tgt;
1205 }
1206 }
1207 }
1208
1209 // list of location relationships
1210 List<RCEdge> edgeList;
1211 for(j = 0; j < n; ++j)
1212 for(int k = j+1; k < n; ++k) {
1213 if(cn(j,k) <= cn(k,j))
1214 edgeList.pushBack(RCEdge(toG[j], toG[k], cn(j,k), cn(k,j)));
1215 else
1216 edgeList.pushBack(RCEdge(toG[k], toG[j], cn(k,j), cn(j,k)));
1217 }
1218
1219 // sort list according to weights
1220 LocationRelationshipComparer cmp;
1221 edgeList.quicksort(cmp);
1222
1223 // build acyclic graph
1224 RCCrossings numCrossings;
1225 for(const RCEdge &rce : edgeList)
1226 {
1227 node u = rce.m_src;
1228 node v = rce.m_tgt;
1229
1230 if(tryEdge(u, v, G, level)) {
1231 numCrossings += rce.m_cr;
1232
1233 } else {
1234 numCrossings += rce.m_crReverse;
1235 }
1236 }
1237
1238 OGDF_ASSERT(isAcyclic(G));
1239
1240 // sort nodes in G topological
1241 topologicalNumbering(G,level);
1242
1243 // sort children of cNode according to topological numbering
1244 for(node v : G.nodes)
1245 cNode->setChild(level[v], fromG[v]);
1246
1247 #if 0
1248 for(j = 0; j < n; ++j) {
1249 LHTreeNode *vNode = cNode->child(j);
1250 }
1251 #endif
1252
1253 return numCrossings;
1254 }
1255
assignPos(const LHTreeNode * vNode,int & count)1256 void ExtendedNestingGraph::assignPos(const LHTreeNode *vNode, int &count)
1257 {
1258 if(vNode->isCompound()) {
1259 for(int i = 0; i < vNode->numberOfChildren(); ++i)
1260 assignPos(vNode->child(i), count);
1261
1262 } else {
1263 m_pos[vNode->getNode()] = count++;
1264 }
1265 }
1266
1267
removeAuxNodes()1268 void ExtendedNestingGraph::removeAuxNodes()
1269 {
1270 for(int i = 0; i < m_numLayers; ++i)
1271 m_layer[i].removeAuxNodes();
1272 }
1273
1274
removeTopBottomEdges()1275 void ExtendedNestingGraph::removeTopBottomEdges()
1276 {
1277 // compute m_vertical
1278 m_vertical.init(*this);
1279
1280 #if 0
1281 cluster rootOrig = getOriginalClusterGraph().rootCluster();
1282 #endif
1283 for(edge e : edges)
1284 {
1285 if(origEdge(e) == nullptr)
1286 continue;
1287
1288 bool vert = false;
1289 node u = e->source();
1290 node v = e->target();
1291
1292 // if we do not use virtual clusters, cu and cv are simply the
1293 // clusters containing u and v (=> no while-loop required)
1294 cluster cu = parent(u);
1295 while(isVirtual(cu))
1296 cu = cu->parent();
1297 cluster cv = parent(v);
1298 while(isVirtual(cv))
1299 cv = cv->parent();
1300
1301 if(isLongEdgeDummy(u) && isLongEdgeDummy(v)) {
1302 if(cu != cv) {
1303 cluster cuOrig = m_CGC.original(cu);
1304 cluster cvOrig = m_CGC.original(cv);
1305 cluster cuOrigParent = cuOrig->parent();
1306 cluster cvOrigParent = cvOrig->parent();
1307
1308 if((cvOrig == cuOrigParent && rank(u) == rank(bottom(cuOrig))) ||
1309 (cuOrig == cvOrigParent && rank(v) == rank(top (cvOrig))) ||
1310 (cuOrigParent == cvOrigParent &&
1311 rank(u) == rank(bottom(cuOrig)) &&
1312 rank(v) == rank(top (cvOrig))
1313 ))
1314 {
1315 vert = true;
1316 }
1317 } else
1318 vert = true;
1319 }
1320
1321 m_vertical[e] = vert;
1322 }
1323
1324 for(int i = 1; i < m_numLayers; ++i)
1325 {
1326 LHTreeNode *root = m_layer[i].root();
1327
1328 ArrayBuffer<LHTreeNode*> S;
1329 S.push(root);
1330
1331 while(!S.empty()) {
1332 LHTreeNode *cNode = S.popRet();
1333
1334 cNode->setPos();
1335 for (const LHTreeNode::ClusterCrossing &cc : cNode->m_upperClusterCrossing) {
1336 int j = cc.m_cNode->pos();
1337 int k = cc.m_uNode->pos();
1338
1339 int posJ = m_pos[cc.m_uc];
1340 int posK = m_pos[cc.m_u];
1341
1342 OGDF_ASSERT(j != k);
1343 OGDF_ASSERT(posJ != posK);
1344
1345 // do we have a cluster-edge crossing?
1346 if((j < k && posJ > posK) || (j > k && posJ < posK))
1347 m_vertical[cc.m_edge] = false;
1348 }
1349
1350
1351 for(int j = 0; j < cNode->numberOfChildren(); ++j) {
1352 if(cNode->child(j)->isCompound())
1353 S.push(cNode->child(j));
1354 }
1355 }
1356 }
1357
1358 // delete nodes in hierarchy tree
1359 removeAuxNodes();
1360
1361 // delete nodes in graph
1362 node v, vNext;
1363 for(v = firstNode(); v != nullptr; v = vNext) {
1364 vNext = v->succ();
1365 if(type(v) == NodeType::ClusterTopBottom)
1366 delNode(v);
1367 }
1368 }
1369
1370
lca(node u,node v) const1371 cluster ExtendedNestingGraph::lca(node u, node v) const
1372 {
1373 const ClusterGraph &CG = getOriginalClusterGraph();
1374
1375 for(cluster c : m_markedClustersTree)
1376 m_mark[c] = nullptr;
1377 m_markedClustersTree.clear();
1378
1379 cluster c1 = CG.clusterOf(u);
1380 cluster pred1 = c1;
1381 cluster c2 = CG.clusterOf(v);
1382 cluster pred2 = c2;
1383
1384 for( ; ; ) {
1385 if(c1 != nullptr) {
1386 if(m_mark[c1] != nullptr) {
1387 m_secondPath = pred1;
1388 m_secondPathTo = u;
1389 return c1;
1390
1391 } else {
1392 m_mark[c1] = pred1;
1393 pred1 = c1;
1394 m_markedClustersTree.pushBack(c1);
1395 c1 = c1->parent();
1396 }
1397 }
1398 if(c2 != nullptr) {
1399 if(m_mark[c2] != nullptr) {
1400 m_secondPath = pred2;
1401 m_secondPathTo = v;
1402 return c2;
1403
1404 } else {
1405 m_mark[c2] = pred2;
1406 pred2 = c2;
1407 m_markedClustersTree.pushBack(c2);
1408 c2 = c2->parent();
1409 }
1410 }
1411 }
1412 }
1413
1414
lca(LHTreeNode * uNode,LHTreeNode * vNode,LHTreeNode ** uChild,LHTreeNode ** vChild) const1415 LHTreeNode *ExtendedNestingGraph::lca(
1416 LHTreeNode *uNode,
1417 LHTreeNode *vNode,
1418 LHTreeNode **uChild,
1419 LHTreeNode **vChild) const
1420 {
1421 OGDF_ASSERT(!uNode->isCompound());
1422 OGDF_ASSERT(!vNode->isCompound());
1423
1424 for(cluster c : m_markedClusters)
1425 m_markTree[c] = nullptr;
1426 m_markedClusters.clear();
1427
1428 LHTreeNode *cuNode = uNode->parent();
1429 LHTreeNode *cvNode = vNode->parent();
1430
1431 LHTreeNode *uPred = uNode;
1432 LHTreeNode *vPred = vNode;
1433
1434 while(cuNode != nullptr || cvNode != nullptr) {
1435 if(cuNode != nullptr) {
1436 if(m_markTree[cuNode->originalCluster()] != nullptr) {
1437 *uChild = uPred;
1438 *vChild = m_markTree[cuNode->originalCluster()];
1439 return cuNode;
1440
1441 } else {
1442 m_markTree[cuNode->originalCluster()] = uPred;
1443 uPred = cuNode;
1444 m_markedClusters.pushBack(cuNode->originalCluster());
1445 cuNode = cuNode->parent();
1446 }
1447 }
1448 if(cvNode != nullptr) {
1449 if(m_markTree[cvNode->originalCluster()] != nullptr) {
1450 *uChild = m_markTree[cvNode->originalCluster()];
1451 *vChild = vPred;
1452 return cvNode;
1453
1454 } else {
1455 m_markTree[cvNode->originalCluster()] = vPred;
1456 vPred = cvNode;
1457 m_markedClusters.pushBack(cvNode->originalCluster());
1458 cvNode = cvNode->parent();
1459 }
1460 }
1461 }
1462
1463 return nullptr; // error; not found!
1464 }
1465
1466
assignAeLevel(cluster c,int & count)1467 void ExtendedNestingGraph::assignAeLevel(cluster c, int &count)
1468 {
1469 m_aeLevel[m_topNode[c]] = count++;
1470
1471 ListConstIterator<node> itV;
1472 for(itV = c->nBegin(); itV.valid(); ++itV)
1473 m_aeLevel[m_copy[*itV]] = count++;
1474
1475 for(cluster child : c->children)
1476 assignAeLevel(child, count);
1477
1478 m_aeLevel[m_bottomNode[c]] = count++;
1479 }
1480
1481
reachable(node v,node u,SListPure<node> & successors)1482 bool ExtendedNestingGraph::reachable(node v, node u, SListPure<node> &successors)
1483 {
1484 if(u == v)
1485 return true;
1486
1487 SListPure<node> Q;
1488 m_aeVisited[v] = true;
1489 Q.pushBack(v);
1490
1491 while(!Q.empty())
1492 {
1493 node w = Q.popFrontRet();
1494 successors.pushBack(w);
1495
1496 for(adjEntry adj : w->adjEntries) {
1497 edge e = adj->theEdge();
1498 node t = e->target();
1499
1500 if(t == u) {
1501 // we've found u, so we do not need the list of successors
1502 Q.conc(successors);
1503
1504 // reset all visited entries
1505 for(node vi : Q)
1506 m_aeVisited[vi] = false;
1507
1508 return true;
1509 }
1510
1511 if(!m_aeVisited[t]) {
1512 m_aeVisited[t] = true;
1513 Q.pushBack(t);
1514 }
1515 }
1516 }
1517
1518 // reset all visited entries
1519 for(node vi : successors)
1520 m_aeVisited[vi] = false;
1521
1522 return false;
1523 }
1524
1525
moveDown(node v,const SListPure<node> & successors,NodeArray<int> & level)1526 void ExtendedNestingGraph::moveDown(node v, const SListPure<node> &successors, NodeArray<int> &level)
1527 {
1528 for(node vi : successors) {
1529 m_aeVisited[vi] = true;
1530 m_auxDeg[vi] = 0;
1531 }
1532
1533 for(node vi : successors) {
1534 for(adjEntry adj : vi->adjEntries) {
1535 edge e = adj->theEdge();
1536 node s = e->source();
1537 if(s != vi && m_aeVisited[s])
1538 ++m_auxDeg[vi];
1539 }
1540 }
1541
1542 SListPure<node> Q;
1543 for(adjEntry adj : v->adjEntries) {
1544 edge e = adj->theEdge();
1545 node t = e->target();
1546 if (t != v && --m_auxDeg[t] == 0) {
1547 Q.pushBack(t);
1548 }
1549 }
1550
1551 while(!Q.empty())
1552 {
1553 node w = Q.popFrontRet();
1554
1555 int maxLevel = 0;
1556 for(adjEntry adj : w->adjEntries) {
1557 edge e = adj->theEdge();
1558 node s = e->source();
1559 node t = e->target();
1560
1561 if (s != w) {
1562 Math::updateMax(maxLevel, level[s]);
1563 }
1564 if (t != w && --m_auxDeg[t] == 0) {
1565 Q.pushBack(t);
1566 }
1567 }
1568
1569 level[w] = maxLevel+1;
1570 }
1571
1572 for(node vi : successors) {
1573 m_aeVisited[vi] = false;
1574 }
1575 }
1576
1577
addEdge(node u,node v,bool addAlways)1578 edge ExtendedNestingGraph::addEdge(node u, node v, bool addAlways)
1579 {
1580 if(m_aeLevel[u] < m_aeLevel[v])
1581 return newEdge(u,v);
1582
1583 SListPure<node> successors;
1584 if(!reachable(v, u, successors)) {
1585 int d = m_aeLevel[u] - m_aeLevel[v] + 1;
1586 OGDF_ASSERT(d > 0);
1587
1588 for(node vi : successors)
1589 m_aeLevel[vi] += d;
1590
1591 return newEdge(u,v);
1592
1593 } else if(addAlways)
1594 return newEdge(v,u);
1595
1596 return nullptr;
1597 }
1598
1599 }
1600