1 /** \file
2 * \brief Implementation of the FastSimpleHierarchyLayout
3 * (third phase of sugiyama)
4 *
5 * \author Till Schäfer, 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/FastSimpleHierarchyLayout.h>
35
36
37 namespace ogdf {
38
FastSimpleHierarchyLayout()39 FastSimpleHierarchyLayout::FastSimpleHierarchyLayout()
40 {
41 m_minXSep = LayoutStandards::defaultNodeSeparation();
42 m_ySep = 1.5 * LayoutStandards::defaultNodeSeparation();
43
44 m_balanced = true;
45 m_downward = true;
46 m_leftToRight = true;
47 }
48
49
FastSimpleHierarchyLayout(const FastSimpleHierarchyLayout & fshl)50 FastSimpleHierarchyLayout::FastSimpleHierarchyLayout(const FastSimpleHierarchyLayout &fshl)
51 {
52 m_minXSep = fshl.m_minXSep;
53 m_ySep = fshl.m_ySep;
54 m_balanced = fshl.m_balanced;
55 m_downward = fshl.m_downward;
56 m_leftToRight = fshl.m_leftToRight;
57 }
58
59
operator =(const FastSimpleHierarchyLayout & fshl)60 FastSimpleHierarchyLayout &FastSimpleHierarchyLayout::operator=(const FastSimpleHierarchyLayout &fshl)
61 {
62 m_minXSep = fshl.m_minXSep;
63 m_ySep = fshl.m_ySep;
64 m_balanced = fshl.m_balanced;
65 m_downward = fshl.m_downward;
66 m_leftToRight = fshl.m_leftToRight;
67
68 return *this;
69 }
70
71
doCall(const HierarchyLevelsBase & levels,GraphAttributes & AGC)72 void FastSimpleHierarchyLayout::doCall(const HierarchyLevelsBase &levels, GraphAttributes &AGC)
73 {
74 const Hierarchy &H = levels.hierarchy();
75 const GraphCopy &GC = H;
76
77 if (GC.numberOfNodes() == 0) {
78 return;
79 }
80
81 NodeArray<node> align(GC);
82
83 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
84 for(int i = 0; i <= levels.high(); ++i) {
85 std::cout << "level " << i << ": ";
86 const LevelBase &level = levels[i];
87 for(int j = 0; j <= level.high(); ++j)
88 std::cout << level[j] << " ";
89 std::cout << std::endl;
90 }
91 #endif
92
93 if (m_balanced) {
94 // the x positions; x = -infinity <=> x is undefined
95 NodeArray<double> x[4];
96 NodeArray<double> blockWidth[4];
97 NodeArray<node> root[4];
98 double width[4];
99 double min[4];
100 double max[4];
101 int minWidthLayout = 0;
102
103 // initializing
104 for (int i = 0; i < 4; i++) {
105 min[i] = std::numeric_limits<double>::max();
106 max[i] = std::numeric_limits<double>::lowest();
107 }
108
109 // calc the layout for down/up and leftToRight/rightToLeft
110 for (int downward = 0; downward <= 1; downward++) {
111 NodeArray<NodeArray<bool> > type1Conflicts(GC);
112 markType1Conflicts(levels, downward == 0, type1Conflicts);
113 for (int leftToRight = 0; leftToRight <= 1; leftToRight++) {
114 int k = 2 * downward + leftToRight;
115 root[k].init(GC);
116 verticalAlignment(levels, root[k], align, type1Conflicts, downward == 0, leftToRight == 0);
117 computeBlockWidths(GC, AGC, root[k], blockWidth[k]);
118 horizontalCompactation(align, levels, root[k], blockWidth[k], x[k], leftToRight == 0, downward == 0);
119 }
120 }
121
122 /*
123 * - calc min/max x coordinate for each layout
124 * - calc x-width for each layout
125 * - find the layout with the minimal width
126 */
127 for (int i = 0; i < 4; i++) {
128 for(node v : GC.nodes) {
129 double bw = 0.5 * blockWidth[i][root[i][v]];
130 double xp = x[i][v] - bw;
131 if (min[i] > xp) {
132 min[i] = xp;
133 }
134 xp = x[i][v] + bw;
135 if (max[i] < xp) {
136 max[i] = xp;
137 }
138 }
139 width[i] = max[i] - min[i];
140 if (width[minWidthLayout] > width[i]) {
141 minWidthLayout = i;
142 }
143 }
144
145 /*
146 * shift the layout so that they align with the minimum width layout
147 * - leftToRight: align minimum coordinate
148 * - rightToLeft: align maximum coordinate
149 */
150 double shift[4];
151 for (int i = 0; i < 4; i++) {
152 if (i % 2 == 0) {
153 // for leftToRight layouts
154 shift[i] = min[minWidthLayout] - min[i];
155 } else {
156 // for rightToLeft layouts
157 shift[i] = max[minWidthLayout] - max[i];
158 }
159 }
160
161 /*
162 * shift the layouts and use the
163 * median average coordinate for each node
164 */
165 Array<double> sorting(4);
166 for(node v : GC.nodes) {
167 for (int i = 0; i < 4; i++) {
168 sorting[i] = x[i][v] + shift[i];
169 }
170 sorting.quicksort();
171 AGC.x(v) = 0.5 * (sorting[1] + sorting[2]);
172 }
173
174 } else {
175 NodeArray<double> x;
176 NodeArray<NodeArray<bool> > type1Conflicts(GC);
177 markType1Conflicts(levels, m_downward, type1Conflicts);
178 NodeArray<double> blockWidth; // the width of each block (max width of node in block)
179
180 NodeArray<node> root(GC);
181 verticalAlignment(levels, root, align, type1Conflicts, m_downward, m_leftToRight);
182 computeBlockWidths(GC, AGC, root, blockWidth);
183 horizontalCompactation(align, levels, root, blockWidth, x, m_leftToRight, m_downward);
184 for(node v : GC.nodes) {
185 AGC.x(v) = x[v];
186 }
187 }
188
189 // compute y-coordinates
190 const int k = levels.size();
191
192 // compute height of each layer
193 Array<double> height(0,k-1,0.0);
194
195 for(int i = 0; i < k; ++i) {
196 const LevelBase &level = levels[i];
197 for(int j = 0; j < level.size(); ++j) {
198 double h = getHeight(AGC, levels, level[j]);
199 if(h > height[i])
200 height[i] = h;
201 }
202 }
203
204 // assign y-coordinates
205 double yPos = 0.5 * height[0];
206
207 for(int i = 0; ; ++i)
208 {
209 const LevelBase &level = levels[i];
210 for(int j = 0; j < level.size(); ++j)
211 AGC.y(level[j]) = yPos;
212
213 if(i == k-1)
214 break;
215
216 yPos += m_ySep + 0.5 * (height[i] + height[i+1]);
217 }
218 }
219
220
markType1Conflicts(const HierarchyLevelsBase & levels,const bool downward,NodeArray<NodeArray<bool>> & type1Conflicts)221 void FastSimpleHierarchyLayout::markType1Conflicts(const HierarchyLevelsBase &levels, const bool downward, NodeArray<NodeArray<bool> > &type1Conflicts)
222 {
223 const GraphCopy& GC = levels.hierarchy();
224
225 for(node v : GC.nodes) {
226 type1Conflicts[v].init(GC,false);
227 }
228
229 if (levels.size() >= 4) {
230 int upper, lower; // iteration bounds
231 int k1; // node position boundaries of closest inner segments
232 HierarchyLevelsBase::TraversingDir relupward; // upward relativ to the direction from downward
233
234 if (downward) {
235 lower = 1;
236 upper = levels.high() - 2;
237
238 relupward = HierarchyLevelsBase::TraversingDir::downward;
239 }
240 else {
241 lower = levels.high() - 1;
242 upper = 2;
243
244 relupward = HierarchyLevelsBase::TraversingDir::upward;
245 }
246
247 /*
248 * iterate level[2..h-2] in the given direction
249 *
250 * availible levels: 1 to h
251 */
252 for (int i = lower; (downward && i <= upper) || (!downward && i >= upper); i = downward ? i + 1 : i - 1)
253 {
254 int k0 = 0;
255 int firstIndex = 0; // index of first node on layer
256 const LevelBase ¤tLevel = levels[i];
257 const LevelBase &nextLevel = downward ? levels[i+1] : levels[i-1];
258
259 // for all nodes on next level
260 for (int l1 = 0; l1 <= nextLevel.high(); l1++) {
261 const node virtualTwin = virtualTwinNode(levels, nextLevel[l1], relupward);
262
263 if (l1 == nextLevel.high() || virtualTwin != nullptr) {
264 k1 = currentLevel.high();
265
266 if (virtualTwin != nullptr) {
267 k1 = levels.pos(virtualTwin);
268 }
269
270 for (; firstIndex <= l1; firstIndex++) {
271 const Array<node> &upperNeighbours = levels.adjNodes(nextLevel[l1], relupward);
272
273 for (auto currentNeighbour : upperNeighbours) {
274 /*
275 * XXX: < 0 in first iteration is still ok for indizes starting
276 * with 0 because no index can be smaller than 0
277 */
278 if (levels.pos(currentNeighbour) < k0 || levels.pos(currentNeighbour) > k1) {
279 type1Conflicts[nextLevel[l1]][currentNeighbour] = true;
280 }
281 }
282 }
283 k0 = k1;
284 }
285 }
286 }
287 }
288 }
289
290
verticalAlignment(const HierarchyLevelsBase & levels,NodeArray<node> & root,NodeArray<node> & align,const NodeArray<NodeArray<bool>> & type1Conflicts,bool downward,const bool leftToRight)291 void FastSimpleHierarchyLayout::verticalAlignment(
292 const HierarchyLevelsBase &levels,
293 NodeArray<node> &root,
294 NodeArray<node> &align,
295 const NodeArray<NodeArray<bool> > &type1Conflicts,
296 bool downward,
297 const bool leftToRight)
298 {
299 const GraphCopy& GC = levels.hierarchy();
300 HierarchyLevelsBase::TraversingDir relupward; // upward relativ to the direction from downward
301
302 relupward = downward ? HierarchyLevelsBase::TraversingDir::downward : HierarchyLevelsBase::TraversingDir::upward;
303
304 // initialize root and align
305 for(node v : GC.nodes) {
306 root[v] = v;
307 align[v] = v;
308 }
309
310 // for all Level
311 for (int i = downward ? 0 : levels.high();
312 (downward && i <= levels.high()) || (!downward && i >= 0);
313 i = downward ? i + 1 : i - 1)
314 {
315 const LevelBase ¤tLevel = levels[i];
316 int r = leftToRight ? -1 : std::numeric_limits<int>::max();
317
318 // for all nodes on Level i (with direction leftToRight)
319 for (int j = leftToRight ? 0 : currentLevel.high();
320 (leftToRight && j <= currentLevel.high()) || (!leftToRight && j >= 0);
321 leftToRight ? j++ : j--)
322 {
323 node v = currentLevel[j];
324 // the first median
325 int median = (int)floor((levels.adjNodes(v, relupward).size() + 1) / 2.0);
326
327 int medianCount = (levels.adjNodes(v, relupward).size() % 2 == 1) ? 1 : 2;
328 if (levels.adjNodes(v, relupward).size() == 0) {
329 medianCount = 0;
330 }
331
332 // for all median neighbours in direction of H
333 for (int count = 0; count < medianCount; count++) {
334 node u = levels.adjNodes(v, relupward)[median + count - 1];
335
336 if (align[v] == v
337 // if segment (u,v) not marked by type1 conflicts AND ...
338 && !type1Conflicts[v][u]
339 && ((leftToRight && r < levels.pos(u))
340 || (!leftToRight && r > levels.pos(u)))) {
341 align[u] = v;
342 root[v] = root[u];
343 align[v] = root[v];
344 r = levels.pos(u);
345 }
346 }
347 }
348 }
349
350 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
351 for(node v : GC.nodes) {
352 std::cout
353 << "node: " << GC.original(v) << "/" << v
354 << ", root: " << GC.original(root[v]) << "/" << root[v]
355 << ", alignment: " << GC.original(align[v]) << "/" << align[v] << std::endl;
356 }
357 #endif
358 }
359
360
computeBlockWidths(const GraphCopy & GC,const GraphAttributes & GCA,NodeArray<node> & root,NodeArray<double> & blockWidth)361 void FastSimpleHierarchyLayout::computeBlockWidths(
362 const GraphCopy &GC,
363 const GraphAttributes &GCA,
364 NodeArray<node> &root,
365 NodeArray<double> &blockWidth)
366 {
367 blockWidth.init(GC, 0.0);
368 for(node v : GC.nodes) {
369 if (!GC.isDummy(v)) {
370 Math::updateMax(blockWidth[root[v]], GCA.width(v));
371 }
372 }
373 }
374
375
horizontalCompactation(const NodeArray<node> & align,const HierarchyLevelsBase & levels,const NodeArray<node> & root,const NodeArray<double> & blockWidth,NodeArray<double> & x,const bool leftToRight,bool downward)376 void FastSimpleHierarchyLayout::horizontalCompactation(
377 const NodeArray<node> &align,
378 const HierarchyLevelsBase &levels,
379 const NodeArray<node> &root,
380 const NodeArray<double> &blockWidth,
381 NodeArray<double> &x,
382 const bool leftToRight, bool downward)
383 {
384 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
385 std::cout << "-------- Horizontal Compactation --------" << std::endl;
386 #endif
387
388 const GraphCopy& GC = levels.hierarchy();
389
390 NodeArray<node> sink(GC);
391 NodeArray<double> shift(GC, std::numeric_limits<double>::max());
392
393 x.init(GC, std::numeric_limits<double>::lowest());
394
395 for(node v : GC.nodes) {
396 sink[v] = v;
397 }
398
399 // calculate class relative coordinates for all roots
400 for (int i = downward ? 0 : levels.high();
401 (downward && i <= levels.high()) || (!downward && i >= 0);
402 i = downward ? i + 1 : i - 1)
403 {
404 const LevelBase ¤tLevel = levels[i];
405
406 for (int j = leftToRight ? 0 : currentLevel.high();
407 (leftToRight && j <= currentLevel.high()) || (!leftToRight && j >= 0);
408 leftToRight ? j++ : j--)
409 {
410 node v = currentLevel[j];
411 if (root[v] == v) {
412 placeBlock(v, sink, shift, x, align, levels, blockWidth, root, leftToRight);
413 }
414 }
415 }
416
417 double d = 0;
418 for (int i = downward ? 0 : levels.high();
419 (downward && i <= levels.high()) || (!downward && i >= 0);
420 i = downward ? i + 1 : i - 1)
421 {
422 const LevelBase ¤tLevel = levels[i];
423
424 node v = currentLevel[leftToRight ? 0 : currentLevel.high()];
425
426 if(v == sink[root[v]]) {
427 double oldShift = shift[v];
428 if(oldShift < std::numeric_limits<double>::max()) {
429 shift[v] += d;
430 d += oldShift;
431 } else
432 shift[v] = 0;
433 }
434 }
435
436 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
437 std::cout << "------- Sinks ----------" << std::endl;
438 #endif
439 // apply root coordinates for all aligned nodes
440 // (place block did this only for the roots)
441 for(node v : GC.nodes) {
442 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
443 if (sink[root[v]] == v) {
444 std::cout << "Topmost Root von Senke!: " << GC.original(v) << std::endl;
445 std::cout << "-> Shift: " << shift[v] << std::endl;
446 std::cout << "-> x: " << x[v] << std::endl;
447 }
448 #endif
449 x[v] = x[root[v]];
450 }
451
452 // apply shift for each class
453 for(node v : GC.nodes) {
454 x[v] += shift[sink[root[v]]];
455 }
456 }
457
458
placeBlock(node v,NodeArray<node> & sink,NodeArray<double> & shift,NodeArray<double> & x,const NodeArray<node> & align,const HierarchyLevelsBase & levels,const NodeArray<double> & blockWidth,const NodeArray<node> & root,const bool leftToRight)459 void FastSimpleHierarchyLayout::placeBlock(
460 node v,
461 NodeArray<node> &sink,
462 NodeArray<double> &shift,
463 NodeArray<double> &x,
464 const NodeArray<node> &align,
465 const HierarchyLevelsBase &levels,
466 const NodeArray<double> &blockWidth,
467 const NodeArray<node> &root,
468 const bool leftToRight)
469 {
470 const Hierarchy &H = levels.hierarchy();
471
472 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
473 const GraphCopy& GC = H;
474 #endif
475
476 if (x[v] == std::numeric_limits<double>::lowest()) {
477 x[v] = 0;
478 node w = v;
479 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
480 std::cout << "---placeblock: " << GC.original(v) << " ---" << std::endl;
481 #endif
482 do {
483 // if not first node on layer
484 if ((leftToRight && levels.pos(w) > 0) || (!leftToRight && levels.pos(w) < levels[H.rank(w)].high())) {
485 node u = root[pred(w, levels, leftToRight)];
486 placeBlock(u, sink, shift, x, align, levels, blockWidth, root, leftToRight);
487 if (sink[v] == v) {
488 sink[v] = sink[u];
489 }
490 if (sink[v] != sink[u]) {
491 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
492 std::cout << "old shift " << GC.original(sink[u]) << ": " << shift[sink[u]] << "<>" << x[v] - x[u] - m_minXSep << std::endl;
493 #endif
494 if (leftToRight) {
495 shift[sink[u]] = min<double>(shift[sink[u]], x[v] - x[u] - m_minXSep - 0.5 * (blockWidth[u] + blockWidth[v]));
496 } else {
497 shift[sink[u]] = max<double>(shift[sink[u]], x[v] - x[u] + m_minXSep + 0.5 * (blockWidth[u] + blockWidth[v]));
498 }
499 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
500 std::cout << "-> new shift: " << shift[sink[u]] << std::endl;
501 #endif
502 }
503 else {
504 if (leftToRight) {
505 x[v] = max<double>(x[v], x[u] + m_minXSep + 0.5 * (blockWidth[u] + blockWidth[v]));
506 } else {
507 x[v] = min<double>(x[v], x[u] - m_minXSep - 0.5 * (blockWidth[u] + blockWidth[v]));
508 }
509 }
510 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
511 std::cout << "placing w: " << GC.original(w) << "; predecessor: " << GC.original(pred(w, levels, leftToRight)) <<
512 "; root(w)=v: " << GC.original(v) << "; root(pred(u)): " << GC.original(u) <<
513 "; sink(v): " << GC.original(sink[v]) << "; sink(u): " << GC.original(sink[u]) << std::endl;
514 std::cout << "x(v): " << x[v] << std::endl;
515 } else {
516 std::cout << "not placing w: " << GC.original(w) << " because at beginning of layer" << std::endl;
517 #endif
518 }
519 w = align[w];
520 } while (w != v);
521 #ifdef OGDF_FAST_SIMPLE_HIERARCHY_LAYOUT_LOGGING
522 std::cout << "---END placeblock: " << GC.original(v) << " ---" << std::endl;
523 #endif
524 }
525 }
526
527
virtualTwinNode(const HierarchyLevelsBase & levels,const node v,const HierarchyLevelsBase::TraversingDir dir) const528 node FastSimpleHierarchyLayout::virtualTwinNode(const HierarchyLevelsBase &levels, const node v, const HierarchyLevelsBase::TraversingDir dir) const
529 {
530 const Hierarchy &H = levels.hierarchy();
531
532 if (!H.isLongEdgeDummy(v) || levels.adjNodes(v, dir).size() == 0) {
533 return nullptr;
534 }
535
536 if (levels.adjNodes(v, dir).size() > 1) {
537 // since v is a dummy there sould be only one upper neighbour
538 throw AlgorithmFailureException("FastSimpleHierarchyLayout.cpp");
539 }
540
541 return *levels.adjNodes(v, dir).begin();
542 }
543
544
pred(const node v,const HierarchyLevelsBase & levels,const bool leftToRight)545 node FastSimpleHierarchyLayout::pred(const node v, const HierarchyLevelsBase &levels, const bool leftToRight)
546 {
547 const Hierarchy &H = levels.hierarchy();
548
549 int pos = levels.pos(v);
550 int rank = H.rank(v);
551
552 const LevelBase &level = levels[rank];
553 if ((leftToRight && pos != 0) || (!leftToRight && pos != level.high())) {
554 return level[leftToRight ? pos - 1 : pos + 1];
555 }
556 return nullptr;
557 }
558
559 }
560