1 /** \file
2 * \brief Implementation of the optimal third phase of the
3 * sugiyama algorithm for cluster graphs
4 *
5 * \author Carsten Gutwenger
6 *
7 * \par License:
8 * This file is part of the Open Graph Drawing Framework (OGDF).
9 *
10 * \par
11 * Copyright (C)<br>
12 * See README.md in the OGDF root directory for details.
13 *
14 * \par
15 * This program is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU General Public License
17 * Version 2 or 3 as published by the Free Software Foundation;
18 * see the file LICENSE.txt included in the packaging of this file
19 * for details.
20 *
21 * \par
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU General Public License for more details.
26 *
27 * \par
28 * You should have received a copy of the GNU General Public
29 * License along with this program; if not, see
30 * http://www.gnu.org/copyleft/gpl.html
31 */
32
33
34 #include <ogdf/layered/OptimalHierarchyClusterLayout.h>
35 #include <ogdf/lpsolver/LPSolver.h>
36 #include <ogdf/basic/Array2D.h>
37
38 namespace ogdf {
39
checkSolution(Array<int> & matrixBegin,Array<int> & matrixCount,Array<int> & matrixIndex,Array<double> & matrixValue,Array<double> & rightHandSide,Array<char> & equationSense,Array<double> & lowerBound,Array<double> & upperBound,Array<double> & x)40 int checkSolution(
41 Array<int> &matrixBegin, // matrixBegin[i] = begin of column i
42 Array<int> &matrixCount, // matrixCount[i] = number of nonzeroes in column i
43 Array<int> &matrixIndex, // matrixIndex[n] = index of matrixValue[n] in its column
44 Array<double> &matrixValue, // matrixValue[n] = non-zero value in matrix
45 Array<double> &rightHandSide, // right-hand side of LP constraints
46 Array<char> &equationSense, // 'E' == 'G' >= 'L' <=
47 Array<double> &lowerBound, // lower bound of x[i]
48 Array<double> &upperBound, // upper bound of x[i]
49 Array<double> &x) // x-vector of optimal solution (if result is Optimal)
50 {
51 const double zeroeps = 1.0E-7;
52
53 const int nCols = matrixBegin.size();
54 const int nRows = rightHandSide.size();
55
56 Array2D<double> M(0,nCols-1, 0,nRows-1, 0.0);
57
58 int i;
59 for(i = 0; i < nCols; ++i)
60 {
61 for(int j = 0; j < matrixCount[i]; ++j)
62 {
63 int k = matrixBegin[i] + j;
64 M(i,matrixIndex[k]) = matrixValue[k];
65 }
66 }
67
68 // check inequations
69 for(i = 0; i < nRows; ++i)
70 {
71 double val = 0.0;
72 for(int j = 0; j < nCols; ++j)
73 val += M(j,i) * x[j];
74
75 switch(equationSense[i]) {
76 case 'E':
77 if(fabs(val - rightHandSide[i]) > zeroeps)
78 return i;
79 break;
80 case 'G':
81 if(val+zeroeps < rightHandSide[i])
82 return i;
83 break;
84 case 'L':
85 if(val-zeroeps > rightHandSide[i])
86 return i;
87 break;
88 default:
89 return -2;
90 }
91 }
92
93 return -1;
94 }
95
96
OptimalHierarchyClusterLayout()97 OptimalHierarchyClusterLayout::OptimalHierarchyClusterLayout()
98 {
99 m_nodeDistance = 3;
100 m_layerDistance = 3;
101 m_fixedLayerDistance = false;
102 m_weightSegments = 2.0;
103 m_weightBalancing = 0.1;
104 m_weightClusters = 0.05;
105 }
106
107
OptimalHierarchyClusterLayout(const OptimalHierarchyClusterLayout & ohl)108 OptimalHierarchyClusterLayout::OptimalHierarchyClusterLayout(
109 const OptimalHierarchyClusterLayout &ohl)
110 {
111 m_nodeDistance = ohl.nodeDistance();
112 m_layerDistance = ohl.layerDistance();
113 m_fixedLayerDistance = ohl.fixedLayerDistance();
114 m_weightSegments = ohl.weightSegments();
115 m_weightBalancing = ohl.weightBalancing();
116 m_weightClusters = ohl.weightClusters();
117 }
118
119
operator =(const OptimalHierarchyClusterLayout & ohl)120 OptimalHierarchyClusterLayout &OptimalHierarchyClusterLayout::operator=(
121 const OptimalHierarchyClusterLayout &ohl)
122 {
123 m_nodeDistance = ohl.nodeDistance();
124 m_layerDistance = ohl.layerDistance();
125 m_fixedLayerDistance = ohl.fixedLayerDistance();
126 m_weightSegments = ohl.weightSegments();
127 m_weightBalancing = ohl.weightBalancing();
128 m_weightClusters = ohl.weightClusters();
129
130 return *this;
131 }
132
133
134 // Call for Cluster Graphs
doCall(const ExtendedNestingGraph & H,ClusterGraphCopyAttributes & ACGC)135 void OptimalHierarchyClusterLayout::doCall(
136 const ExtendedNestingGraph &H,
137 ClusterGraphCopyAttributes &ACGC)
138 {
139 // trivial cases
140 const int n = H.numberOfNodes();
141
142 if(n == 0)
143 return; // nothing to do
144
145 if(n == 1) {
146 node v = H.firstNode();
147 ACGC.x(v) = 0;
148 ACGC.y(v) = 0;
149 return;
150 }
151
152 m_pH = &H;
153 m_pACGC = &ACGC;
154
155 // actual computation
156 computeXCoordinates(H,ACGC);
157 computeYCoordinates(H,ACGC);
158 }
159
160
161 // Compute x-coordinates (LP-based approach) (for cluster graphs)
computeXCoordinates(const ExtendedNestingGraph & H,ClusterGraphCopyAttributes & AGC)162 void OptimalHierarchyClusterLayout::computeXCoordinates(
163 const ExtendedNestingGraph& H,
164 ClusterGraphCopyAttributes &AGC)
165 {
166 const ClusterGraphCopy &CG = H.getClusterGraph();
167
168 const int k = H.numberOfLayers();
169
170 //
171 // preprocessing: determine nodes that are considered as virtual
172 //
173 m_isVirtual.init(H);
174
175 int i;
176 for(i = 0; i < k; ++i)
177 {
178 int last = -1;
179
180 // Process nodes on layer i from left to right
181 ArrayBuffer<const LHTreeNode*> S;
182 S.push(H.layerHierarchyTree(i));
183 while(!S.empty())
184 {
185 const LHTreeNode *vNode = S.popRet();
186
187 if(vNode->isCompound()) {
188 for(int j = vNode->numberOfChildren()-1; j >= 0; --j)
189 S.push(vNode->child(j));
190
191 } else {
192 node v = vNode->getNode();
193
194 if(H.isLongEdgeDummy(v)) {
195 m_isVirtual[v] = true;
196
197 edge e = v->firstAdj()->theEdge();
198 if(e->target() == v)
199 e = v->lastAdj()->theEdge();
200 node u = e->target();
201
202 if(!H.verticalSegment(e))
203 continue;
204
205 if(H.isLongEdgeDummy(u)) {
206 int down = H.pos(u);
207 if(last != -1 && last > down) {
208 m_isVirtual[v] = false;
209 } else {
210 last = down;
211 }
212 }
213 } else {
214 m_isVirtual[v] = false;
215 }
216 }
217 }
218 }
219
220 //
221 // determine variables of LP
222 //
223 int nSegments = 0; // number of vertical segments
224 int nRealVertices = 0; // number of real vertices
225 int nEdges = 0; // number of edges not in vertical segments
226 int nBalanced = 0; // number of real vertices with deg > 1 for which balancing constraints may be applied
227
228 m_vIndex.init(H,-1); // for real node: index of x[v] for dummy: index of corresponding segment
229 NodeArray<int> bIndex(H,-1); // (relative) index of b[v]
230 EdgeArray<int> eIndex(H,-1); // for edge not in vertical segment: its index
231 Array<int> count(H.numberOfEdges()); // counts the number of dummy vertices in corresponding segment that are not at position 0
232
233 int nSpacingConstraints = 0;
234 for(i = 0; i < k; ++i)
235 {
236 ArrayBuffer<const LHTreeNode*> S;
237 S.push(H.layerHierarchyTree(i));
238 while(!S.empty())
239 {
240 const LHTreeNode *vNode = S.popRet();
241
242 if(vNode->isCompound()) {
243 cluster c = vNode->originalCluster();
244
245 if(!H.isVirtual(c))
246 nSpacingConstraints += (c == CG.rootCluster()) ? 1 : 2;
247
248 for(int j = vNode->numberOfChildren()-1; j >= 0; --j)
249 S.push(vNode->child(j));
250
251 } else {
252 node v = vNode->getNode();
253
254 // ignore dummy nodes and nodes representing cluster
255 // (top or bottom) border
256 if(H.type(v) == ExtendedNestingGraph::NodeType::ClusterBottom || H.type(v) == ExtendedNestingGraph::NodeType::ClusterTop)
257 continue;
258
259 ++nSpacingConstraints;
260
261 // ignore dummy nodes
262 if(m_isVirtual[v])
263 continue;
264
265 // we've found a real vertex
266 m_vIndex[v] = nRealVertices++;
267 if(v->degree() > 1)
268 bIndex[v] = nBalanced++;
269
270 // consider all outgoing edges
271 for(adjEntry adj : v->adjEntries) {
272 edge e = adj->theEdge();
273 node w = e->target();
274 if(w == v)
275 continue;
276
277 // we've found an edge not belonging to a vetical segment
278 eIndex[e] = nEdges++;
279
280 if(!m_isVirtual[w])
281 continue;
282
283 do {
284 // we've found a vertical segment
285 count[nSegments] = 0;
286 do {
287 m_vIndex[w] = nSegments;
288 count[nSegments] += 2;
289
290 // next edge / dummy in segment
291 e = e->adjTarget()->cyclicSucc()->theEdge();
292 w = e->target();
293 } while(m_isVirtual[w] && H.verticalSegment(e));
294
295 ++nSegments;
296
297 // edge following vertical segment
298 eIndex[e] = nEdges++;
299
300 } while(m_isVirtual[w]);
301 }
302 }
303 }
304 }
305
306 // Assign indices to clusters
307 int nClusters = 0;
308 m_cIndex.init(CG,-1);
309
310 for(cluster c : CG.clusters)
311 if(!H.isVirtual(c))
312 m_cIndex[c] = nClusters++;
313
314
315 // assignment of variables to matrix columns
316 // d_e 0, ..., nEdges-1
317 // x_v vertexOffset, ..., vertexOffset + nRealVertices-1
318 // x_s segmentOffset, ..., segmentOffset + nSegments-1
319 // b_v balancedOffset, ..., balancedOffset + nBalanced-1
320 // l_c clusterLefOffset, ..., clusterLeftOffset + nClusters-1
321 // r_c clusterRightOffset, ..., clusterRightOffset+ nClusters-1
322 LPSolver solver;
323
324 if(m_weightBalancing <= 0.0)
325 nBalanced = 0; // no balancing
326
327 const int nCols = nEdges + nRealVertices + nSegments + nBalanced + 2*nClusters;
328 const int nRows = 2*nEdges + nSpacingConstraints + 2*nBalanced;
329
330 m_vertexOffset = nEdges;
331 m_segmentOffset = nEdges + nRealVertices;
332 const int balancedOffset = m_segmentOffset + nSegments;
333 m_clusterLeftOffset = balancedOffset + nBalanced;
334 m_clusterRightOffset = m_clusterLeftOffset + nClusters;
335
336 // allocation of matrix
337 Array<int> matrixCount(0,nCols-1,0);
338
339 for(i = 0; i < nEdges; ++i) {
340 matrixCount[i] = 2;
341 }
342
343 for(int jj = 0; jj < k; ++jj) {
344 const LHTreeNode *layerRoot = H.layerHierarchyTree(jj);
345
346 ArrayBuffer<const LHTreeNode*> S;
347 S.push(layerRoot);
348 while(!S.empty())
349 {
350 const LHTreeNode *vNode = S.popRet();
351
352 if(vNode->isCompound()) {
353 i = m_cIndex[vNode->originalCluster()];
354
355 if(i >= 0) {
356 int cnt = (vNode == layerRoot) ? 1 : 2;
357
358 matrixCount[m_clusterLeftOffset + i] += cnt;
359 matrixCount[m_clusterRightOffset + i] += cnt;
360 }
361
362 for(int j = vNode->numberOfChildren()-1; j >= 0; --j)
363 S.push(vNode->child(j));
364
365 } else {
366 node v = vNode->getNode();
367
368 // ignore nodes representing cluster (top or bottom) border
369 if(H.type(v) == ExtendedNestingGraph::NodeType::ClusterBottom ||
370 H.type(v) == ExtendedNestingGraph::NodeType::ClusterTop)
371 continue;
372
373 if(!m_isVirtual[v]) {
374 i = m_vertexOffset + m_vIndex[v];
375
376 int cnt = 2 + 2*v->degree();
377 if(nBalanced > 0) {
378 if(v->degree() > 1)
379 cnt += 2;
380 for(adjEntry adj : v->adjEntries) {
381 node w = adj->twinNode();
382 if(bIndex[w] != -1)
383 cnt += 2;
384 }
385 }
386
387 matrixCount[i] = cnt;
388
389 } else if (nBalanced > 0) {
390 i = m_vIndex[v];
391 for(adjEntry adj : v->adjEntries) {
392 node w = adj->twinNode();
393 if(bIndex[w] != -1)
394 count[i] += 2;
395 }
396 }
397 }
398 }
399 }
400
401 for(i = 0; i < nSegments; ++i) {
402 matrixCount[m_segmentOffset+i] = count[i] + 4;
403 }
404
405 for(i = 0; i < nBalanced; ++i) {
406 matrixCount[balancedOffset+i] = 2;
407 }
408
409
410 // Computation of matrixBegin[i] from given matrixCount values
411 Array<int> matrixBegin(nCols);
412
413 int nNonZeroes = 0;
414 for(i = 0; i < nCols; ++i) {
415 matrixBegin[i] = nNonZeroes;
416 nNonZeroes += matrixCount[i];
417 }
418
419
420 int debugNonZeroCount = 0; // for debugging only
421
422 //
423 // constraints
424 //
425 Array<int> matrixIndex(nNonZeroes);
426 Array<double> matrixValue(nNonZeroes);
427 Array<char> equationSense(nRows);
428 Array<double> rightHandSide(nRows);
429
430 int currentRow = 0;
431 Array<int> currentCol(nCols);
432 for(i = 0; i < nCols; ++i)
433 currentCol[i] = matrixBegin[i];
434
435 // Constraints:
436 // d_(u,v) - x_u + x_v >= 0
437 // d_(u,v) + x_u - x_v >= 0
438 for(edge e : H.edges)
439 {
440 int dCol = eIndex[e];
441 if(dCol >= 0) {
442 node u = e->source();
443 int uCol = m_vIndex[u];
444 uCol += (m_isVirtual[u]) ? m_segmentOffset : m_vertexOffset;
445
446 node v = e->target();
447 int vCol = m_vIndex[v];
448 vCol += (m_isVirtual[v]) ? m_segmentOffset : m_vertexOffset;
449
450 // d_(u,v) - x_u + x_v >= 0
451
452 matrixValue[currentCol[dCol]] = 1.0;
453 matrixIndex[currentCol[dCol]] = currentRow;
454 ++currentCol[dCol];
455 debugNonZeroCount++;
456
457 matrixValue[currentCol[uCol]] = -1.0;
458 matrixIndex[currentCol[uCol]] = currentRow;
459 ++currentCol[uCol];
460 debugNonZeroCount++;
461
462 matrixValue[currentCol[vCol]] = 1.0;
463 matrixIndex[currentCol[vCol]] = currentRow;
464 ++currentCol[vCol];
465 debugNonZeroCount++;
466
467 equationSense[currentRow] = 'G';
468 rightHandSide[currentRow] = 0.0;
469
470 ++currentRow;
471
472 // d_(u,v) + x_u - x_v >= 0
473
474 matrixValue[currentCol[dCol]] = 1.0;
475 matrixIndex[currentCol[dCol]] = currentRow;
476 ++currentCol[dCol];
477 debugNonZeroCount++;
478
479 matrixValue[currentCol[uCol]] = 1.0;
480 matrixIndex[currentCol[uCol]] = currentRow;
481 ++currentCol[uCol];
482 debugNonZeroCount++;
483
484 matrixValue[currentCol[vCol]] = -1.0;
485 matrixIndex[currentCol[vCol]] = currentRow;
486 ++currentCol[vCol];
487 debugNonZeroCount++;
488
489 equationSense[currentRow] = 'G';
490 rightHandSide[currentRow] = 0.0;
491
492 ++currentRow;
493 }
494 }
495
496
497 // Constraints:
498 // x[v_i] - x[v_(i-1)] >= nodeDistance + 0.5*(width(v_i)+width(v_(i-1))
499 for(i = 0; i < k; ++i)
500 {
501 List<Tuple2<int,double> > L;
502 buildLayerList(H.layerHierarchyTree(i), L);
503
504 if(L.size() < 2)
505 continue;
506
507 ListConstIterator<Tuple2<int,double> > it1 = L.begin();
508 for(ListConstIterator<Tuple2<int,double> > it2 = it1.succ();
509 it2.valid(); it1 = it2, ++it2)
510 {
511 int uCol = (*it1).x1();
512 double uWidth = (*it1).x2();
513
514 int vCol = (*it2).x1();
515 double vWidth = (*it2).x2();
516
517 // x_v - x_u >= nodeDistance + 0.5*(width(v)+width(u))
518 matrixValue[currentCol[uCol]] = -1.0;
519 matrixIndex[currentCol[uCol]] = currentRow;
520 ++currentCol[uCol];
521 debugNonZeroCount++;
522
523 matrixValue[currentCol[vCol]] = 1.0;
524 matrixIndex[currentCol[vCol]] = currentRow;
525 ++currentCol[vCol];
526 debugNonZeroCount++;
527
528 equationSense[currentRow] = 'G';
529 rightHandSide[currentRow] =
530 m_nodeDistance + 0.5*(uWidth + vWidth);
531
532 ++currentRow;
533 }
534 }
535
536 // Constraints:
537 // b[v] - x[v] + 1/deg(v) * sum_{u in Adj(v)} x[u] >= 0
538 // b[v] + x[v] - 1/deg(v) * sum_{u in Adj(v)} x[u] >= 0
539 if(nBalanced > 0) {
540 for(node v : H.nodes)
541 {
542 int bCol = bIndex[v];
543 if(bCol == -1)
544 continue;
545 bCol += balancedOffset;
546
547 int vCol = m_vertexOffset+m_vIndex[v];
548
549 // b[v] - x[v] + 1/deg(v) * sum_{u in Adj(v)} x[u] >= 0
550 matrixValue[currentCol[bCol]] = 1.0;
551 matrixIndex[currentCol[bCol]] = currentRow;
552 ++currentCol[bCol];
553 debugNonZeroCount++;
554
555 matrixValue[currentCol[vCol]] = -1.0;
556 matrixIndex[currentCol[vCol]] = currentRow;
557 ++currentCol[vCol];
558 debugNonZeroCount++;
559
560 double f = 1.0 / v->degree();
561 for(adjEntry adj : v->adjEntries) {
562 node u = adj->twinNode();
563 int uCol = m_vIndex[u];
564 uCol += (m_isVirtual[u]) ? m_segmentOffset : m_vertexOffset;
565
566 matrixValue[currentCol[uCol]] = f;
567 matrixIndex[currentCol[uCol]] = currentRow;
568 ++currentCol[uCol];
569 debugNonZeroCount++;
570 }
571
572 equationSense[currentRow] = 'G';
573 rightHandSide[currentRow] = 0.0;
574
575 ++currentRow;
576
577 // b[v] + x[v] - 1/deg(v) * sum_{u in Adj(v)} x[u] >= 0
578 matrixValue[currentCol[bCol]] = 1.0;
579 matrixIndex[currentCol[bCol]] = currentRow;
580 ++currentCol[bCol];
581 debugNonZeroCount++;
582
583 matrixValue[currentCol[vCol]] = 1.0;
584 matrixIndex[currentCol[vCol]] = currentRow;
585 ++currentCol[vCol];
586 debugNonZeroCount++;
587
588 f = -1.0 / v->degree();
589 for(adjEntry adj : v->adjEntries) {
590 node u = adj->twinNode();
591 int uCol = m_vIndex[u];
592 uCol += (m_isVirtual[u]) ? m_segmentOffset : m_vertexOffset;
593
594 matrixValue[currentCol[uCol]] = f;
595 matrixIndex[currentCol[uCol]] = currentRow;
596 ++currentCol[uCol];
597 debugNonZeroCount++;
598 }
599
600 equationSense[currentRow] = 'G';
601 rightHandSide[currentRow] = 0.0;
602
603 ++currentRow;
604 }
605 }
606
607 OGDF_ASSERT(nNonZeroes == debugNonZeroCount);
608
609 // lower and upper bounds
610 Array<double> lowerBound(nCols);
611 Array<double> upperBound(nCols);
612
613 for(i = 0; i < nCols; ++i) {
614 lowerBound[i] = 0.0;
615 upperBound[i] = solver.infinity();
616 }
617
618
619 // objective function
620 Array<double> obj(nCols);
621 for(edge e : H.edges) {
622 i = eIndex[e];
623 if(i >= 0) {
624 // edge segments connecting to a vertical segment
625 // (i.e. the original edge is represented by at least
626 // three edges in H) get a special weight; all others
627 // have weight 1.0
628 int sz = H.chain(H.origEdge(e)).size();
629 if(sz >= 2) {
630 node uOrig = H.origNode(e->source());
631 node vOrig = H.origNode(e->target());
632 if((uOrig && uOrig->outdeg() == 1) || (vOrig && vOrig->indeg() == 1))
633 obj[i] = 1.2*m_weightSegments;
634 else
635 obj[i] = (sz >= 3) ? m_weightSegments : 1.0;
636 } else
637 obj[i] = 1.0;
638
639 if(!m_isVirtual[e->source()] && e->source()->degree() == 1)
640 obj[i] += m_weightBalancing;
641 if(!m_isVirtual[e->target()] && e->target()->degree() == 1)
642 obj[i] += m_weightBalancing;
643 }
644 }
645
646 for(i = nEdges; i < balancedOffset; ++i)
647 obj[i] = 0.0; // all x_v and x_s do not contribute
648
649 for(; i < m_clusterLeftOffset; ++i)
650 obj[i] = m_weightBalancing;
651
652 for(; i < m_clusterRightOffset; ++i)
653 obj[i] = -m_weightClusters;
654
655 for(; i < nCols; ++i)
656 obj[i] = +m_weightClusters;
657
658 // solve LP
659 double optimum;
660 Array<double> x(nCols);
661
662 #ifdef OGDF_DEBUG
663 LPSolver::Status status =
664 #endif
665 solver.optimize(LPSolver::OptimizationGoal::Minimize, obj,
666 matrixBegin, matrixCount, matrixIndex, matrixValue,
667 rightHandSide, equationSense,
668 lowerBound, upperBound, optimum, x);
669
670 OGDF_ASSERT(status == LPSolver::Status::Optimal);
671 #ifdef OGDF_DEBUG
672 int checkResult =
673 #endif
674 checkSolution(matrixBegin, matrixCount, matrixIndex, matrixValue,
675 rightHandSide, equationSense, lowerBound, upperBound, x);
676 OGDF_ASSERT(checkResult == -1);
677
678 // assign x coordinates
679 for(node v : H.nodes)
680 {
681 ExtendedNestingGraph::NodeType t = H.type(v);
682 if(t == ExtendedNestingGraph::NodeType::Node || t == ExtendedNestingGraph::NodeType::Dummy)
683 {
684 if(m_isVirtual[v])
685 AGC.x(v) = x[m_segmentOffset + m_vIndex[v]];
686 else
687 AGC.x(v) = x[m_vertexOffset + m_vIndex[v]];
688 }
689 }
690
691 for(cluster c : CG.getOriginalClusterGraph().clusters)
692 {
693 int indexC = m_cIndex[CG.copy(c)];
694 OGDF_ASSERT(indexC >= 0);
695
696 AGC.setClusterLeftRight(c,
697 x[m_clusterLeftOffset+indexC], x[m_clusterRightOffset+indexC]);
698 }
699
700
701 // clean-up
702 m_isVirtual.init();
703 m_vIndex .init();
704 m_cIndex .init();
705 }
706
707
buildLayerList(const LHTreeNode * vNode,List<Tuple2<int,double>> & L)708 void OptimalHierarchyClusterLayout::buildLayerList(
709 const LHTreeNode *vNode,
710 List<Tuple2<int,double> > &L)
711 {
712 if(vNode->isCompound())
713 {
714 int i = m_cIndex[vNode->originalCluster()];
715
716 if(i >= 0)
717 L.pushBack(Tuple2<int,double>(m_clusterLeftOffset + i, 0));
718
719 for(int j = 0; j < vNode->numberOfChildren(); ++j)
720 buildLayerList(vNode->child(j), L);
721
722 if(i >= 0)
723 L.pushBack(Tuple2<int,double>(m_clusterRightOffset + i, 0));
724
725 } else {
726 node v = vNode->getNode();
727 ExtendedNestingGraph::NodeType t = m_pH->type(v);
728
729 if(t != ExtendedNestingGraph::NodeType::ClusterBottom &&
730 t != ExtendedNestingGraph::NodeType::ClusterTop)
731 {
732 int i = m_vIndex[v];
733 i += (m_isVirtual[v]) ? m_segmentOffset : m_vertexOffset;
734
735 L.pushBack(Tuple2<int,double>(i, m_pACGC->getWidth(v)));
736 }
737 }
738 }
739
740
741 // Compute y-coordinates for cluster graphs
computeYCoordinates(const ExtendedNestingGraph & H,ClusterGraphCopyAttributes & AGC)742 void OptimalHierarchyClusterLayout::computeYCoordinates(
743 const ExtendedNestingGraph& H,
744 ClusterGraphCopyAttributes &AGC)
745 {
746 const int k = H.numberOfLayers();
747
748 Array<double> y(k);
749
750 double prevHeight = 0;
751 for(int i = 0; i < k; ++i)
752 {
753 // Compute height of layer i and dy (if required)
754 double height = 0; // height[i]
755 double dy = m_layerDistance; // dy[i]
756
757 ArrayBuffer<const LHTreeNode*> S;
758 S.push(H.layerHierarchyTree(i));
759 while(!S.empty())
760 {
761 const LHTreeNode *vNode = S.popRet();
762
763 if(vNode->isCompound()) {
764 for(int j = vNode->numberOfChildren()-1; j >= 0; --j)
765 S.push(vNode->child(j));
766
767 } else {
768 node v = vNode->getNode();
769
770 if(H.type(v) == ExtendedNestingGraph::NodeType::Node) {
771 double h = AGC.getHeight(v);
772 if(h > height)
773 height = h;
774 }
775
776 if(!m_fixedLayerDistance) {
777 for(adjEntry adj : v->adjEntries) {
778 edge e = adj->theEdge();
779 node w = e->source();
780 if(w != v) {
781 double dwv = fabs(AGC.x(w) - AGC.x(v)) / 3.0;
782 if(dwv > dy)
783 dy = dwv;
784 }
785 }
786 }
787 }
788 }
789
790 if(dy > 10*m_layerDistance)
791 dy = 10*m_layerDistance;
792
793 y[i] = (i > 0) ? y[i-1] + dy +0.5*(height+prevHeight) : 0.5*height;
794
795 prevHeight = height;
796 }
797
798 // set y-ccordinates of nodes
799 for(node v : H.nodes) {
800 ExtendedNestingGraph::NodeType t = H.type(v);
801 if(t == ExtendedNestingGraph::NodeType::Node || t == ExtendedNestingGraph::NodeType::Dummy)
802 {
803 AGC.y(v) = y[H.rank(v)];
804 }
805 }
806
807 // set y-coordinates of clusters
808 const ClusterGraph &CG = H.getOriginalClusterGraph();
809
810 const double yUnit = m_layerDistance;
811
812 cluster c;
813 forall_postOrderClusters(c,CG)
814 {
815 if(c == CG.rootCluster())
816 continue;
817
818 double contentMin = std::numeric_limits<double>::max();
819 double contentMax = std::numeric_limits<double>::lowest();
820
821 ListConstIterator<node> itV;
822 for(itV = c->nBegin(); itV.valid(); ++itV) {
823 node v = H.copy(*itV);
824 double t = AGC.y(v) - 0.5*AGC.getHeight(v);
825 double b = AGC.y(v) + 0.5*AGC.getHeight(v);
826 OGDF_ASSERT(t <= b);
827
828 if(t < contentMin) contentMin = t;
829 if(b > contentMax) contentMax = b;
830 }
831
832 for(cluster child : c->children) {
833 double t = AGC.top(child);
834 double b = AGC.bottom(child);
835 OGDF_ASSERT(t <= b);
836
837 if(t < contentMin) contentMin = t;
838 if(b > contentMax) contentMax = b;
839 }
840
841 double currentTop = y[H.rank(H.top(c))];
842 double currentBottom = y[H.rank(H.bottom(c))];
843
844 if(contentMin != std::numeric_limits<double>::max())
845 {
846 int kt = int(((contentMin-m_layerDistance) - currentTop) / yUnit);
847 if(kt >= 1)
848 currentTop += kt*yUnit;
849
850 int kb = int((currentBottom - (contentMax+m_layerDistance)) / yUnit);
851 if(kb >= 1)
852 currentBottom -= kb*yUnit;
853 }
854
855 AGC.setClusterTopBottom(c, currentTop, currentBottom);
856 }
857 }
858
859 }
860