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