Mercurial > hg > truffle

comparison visualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java @ 4512:015fb895586b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved visualizer to new directory.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Tue, 07 Feb 2012 22:41:09 +0100
parents
children
comparison
equal deleted inserted replaced
4511:6cb549627941 4512:015fb895586b
1 /*
2 * Copyright (c) 2008, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24 package com.sun.hotspot.igv.hierarchicallayout;
25
26 import com.sun.hotspot.igv.layout.LayoutGraph;
27 import com.sun.hotspot.igv.layout.LayoutManager;
28 import com.sun.hotspot.igv.layout.Link;
29 import com.sun.hotspot.igv.layout.Vertex;
30 import java.awt.Dimension;
31 import java.awt.Point;
32 import java.util.*;
33
34 /**
35 *
36 * @author Thomas Wuerthinger
37 */
38 public class HierarchicalLayoutManager implements LayoutManager {
39
40 public static final boolean TRACE = false;
41 public static final boolean CHECK = false;
42 public static final int SWEEP_ITERATIONS = 1;
43 public static final int CROSSING_ITERATIONS = 2;
44 public static final int DUMMY_HEIGHT = 1;
45 public static final int DUMMY_WIDTH = 1;
46 public static final int X_OFFSET = 9;
47 public static final int LAYER_OFFSET = 30;
48 public static final int MAX_LAYER_LENGTH = -1;
49 public static final int MIN_LAYER_DIFFERENCE = 1;
50 public static final int VIP_BONUS = 10;
51
52 public enum Combine {
53
54 NONE,
55 SAME_INPUTS,
56 SAME_OUTPUTS
57 }
58 // Options
59 private Combine combine;
60 private int dummyWidth;
61 private int dummyHeight;
62 private int xOffset;
63 private int layerOffset;
64 private int maxLayerLength;
65 private int minLayerDifference;
66 // Algorithm global datastructures
67 private Set<Link> reversedLinks;
68 private List<LayoutNode> nodes;
69 private HashMap<Vertex, LayoutNode> vertexToLayoutNode;
70 private HashMap<Link, List<Point>> reversedLinkStartPoints;
71 private HashMap<Link, List<Point>> reversedLinkEndPoints;
72 private HashMap<LayoutEdge, LayoutEdge> bottomEdgeHash;
73 private HashMap<Link, List<Point>> splitStartPoints;
74 private HashMap<Link, List<Point>> splitEndPoints;
75 private LayoutGraph graph;
76 private List<LayoutNode>[] layers;
77 private int layerCount;
78 private Set<? extends Vertex> firstLayerHint;
79 private Set<? extends Vertex> lastLayerHint;
80 private Set<? extends Link> importantLinks;
81 private Set<Link> linksToFollow;
82
83 private class LayoutNode {
84
85 public int x;
86 public int y;
87 public int width;
88 public int height;
89 public int layer = -1;
90 public int xOffset;
91 public int yOffset;
92 public int bottomYOffset;
93 public Vertex vertex; // Only used for non-dummy nodes, otherwise null
94
95 public List<LayoutEdge> preds = new ArrayList<>();
96 public List<LayoutEdge> succs = new ArrayList<>();
97 public HashMap<Integer, Integer> outOffsets = new HashMap<>();
98 public HashMap<Integer, Integer> inOffsets = new HashMap<>();
99 public int pos = -1; // Position within layer
100
101 public int crossingNumber;
102
103 @Override
104 public String toString() {
105 return "Node " + vertex;
106 }
107 }
108
109 private class LayoutEdge {
110
111 public LayoutNode from;
112 public LayoutNode to;
113 public int relativeFrom;
114 public int relativeTo;
115 public Link link;
116 public boolean vip;
117 }
118
119 private abstract class AlgorithmPart {
120
121 public void start() {
122 if (CHECK) {
123 preCheck();
124 }
125
126 long start = 0;
127 if (TRACE) {
128 System.out.println("##################################################");
129 System.out.println("Starting part " + this.getClass().getName());
130 start = System.currentTimeMillis();
131 }
132 run();
133 if (TRACE) {
134 System.out.println("Timing for " + this.getClass().getName() + " is " + (System.currentTimeMillis() - start));
135 printStatistics();
136 }
137
138 if (CHECK) {
139 postCheck();
140 }
141 }
142
143 protected abstract void run();
144
145 protected void printStatistics() {
146 }
147
148 protected void postCheck() {
149 }
150
151 protected void preCheck() {
152 }
153 }
154
155 public HierarchicalLayoutManager() {
156 this(Combine.NONE);
157 }
158
159 public HierarchicalLayoutManager(Combine b) {
160 this.combine = b;
161 this.dummyWidth = DUMMY_WIDTH;
162 this.dummyHeight = DUMMY_HEIGHT;
163 this.xOffset = X_OFFSET;
164 this.layerOffset = LAYER_OFFSET;
165 this.maxLayerLength = MAX_LAYER_LENGTH;
166 this.minLayerDifference = MIN_LAYER_DIFFERENCE;
167 this.linksToFollow = new HashSet<>();
168 }
169
170 public int getMaxLayerLength() {
171 return maxLayerLength;
172 }
173
174 public void setMaxLayerLength(int v) {
175 maxLayerLength = v;
176 }
177
178 public void setMinLayerDifference(int v) {
179 minLayerDifference = v;
180 }
181
182 @Override
183 public void doLayout(LayoutGraph graph) {
184 doLayout(graph, new HashSet<Vertex>(), new HashSet<Vertex>(), new HashSet<Link>());
185
186 }
187
188 @Override
189 public void doLayout(LayoutGraph graph, Set<? extends Vertex> firstLayerHint, Set<? extends Vertex> lastLayerHint, Set<? extends Link> importantLinks) {
190
191 this.importantLinks = importantLinks;
192 this.graph = graph;
193 this.firstLayerHint = firstLayerHint;
194 this.lastLayerHint = lastLayerHint;
195
196 vertexToLayoutNode = new HashMap<>();
197 reversedLinks = new HashSet<>();
198 reversedLinkStartPoints = new HashMap<>();
199 reversedLinkEndPoints = new HashMap<>();
200 bottomEdgeHash = new HashMap<>();
201 nodes = new ArrayList<>();
202 splitStartPoints = new HashMap<>();
203 splitEndPoints = new HashMap<>();
204
205 // #############################################################
206 // Step 1: Build up data structure
207 new BuildDatastructure().start();
208
209 // #############################################################
210 // STEP 2: Reverse edges, handle backedges
211 new ReverseEdges().start();
212
213 for (LayoutNode n : nodes) {
214 ArrayList<LayoutEdge> tmpArr = new ArrayList<>();
215 for (LayoutEdge e : n.succs) {
216 if (importantLinks.contains(e.link)) {
217 tmpArr.add(e);
218 }
219 }
220
221 for (LayoutEdge e : tmpArr) {
222 //System.out.println("Removed " + e);
223 e.from.succs.remove(e);
224 e.to.preds.remove(e);
225 }
226 }
227
228 // #############################################################
229 // STEP 3: Assign layers
230 new AssignLayers().start();
231
232 // #############################################################
233 // STEP 4: Create dummy nodes
234 new CreateDummyNodes().start();
235
236 // #############################################################
237 // STEP 5: Crossing Reduction
238 new CrossingReduction().start();
239
240 // #############################################################
241 // STEP 7: Assign X coordinates
242 new AssignXCoordinates().start();
243
244 // #############################################################
245 // STEP 6: Assign Y coordinates
246 new AssignYCoordinates().start();
247
248 // #############################################################
249 // STEP 8: Write back to interface
250 new WriteResult().start();
251 }
252
253 private class WriteResult extends AlgorithmPart {
254
255 private int pointCount;
256
257 @Override
258 protected void run() {
259
260 HashMap<Vertex, Point> vertexPositions = new HashMap<>();
261 HashMap<Link, List<Point>> linkPositions = new HashMap<>();
262 for (Vertex v : graph.getVertices()) {
263 LayoutNode n = vertexToLayoutNode.get(v);
264 assert !vertexPositions.containsKey(v);
265 vertexPositions.put(v, new Point(n.x + n.xOffset, n.y + n.yOffset));
266 }
267
268 for (LayoutNode n : nodes) {
269
270 for (LayoutEdge e : n.preds) {
271 if (e.link != null) {
272 ArrayList<Point> points = new ArrayList<>();
273
274 Point p = new Point(e.to.x + e.relativeTo, e.to.y + e.to.yOffset + e.link.getTo().getRelativePosition().y);
275 points.add(p);
276 if (e.to.inOffsets.containsKey(e.relativeTo)) {
277 points.add(new Point(p.x, p.y + e.to.inOffsets.get(e.relativeTo) + e.link.getTo().getRelativePosition().y));
278 }
279
280 LayoutNode cur = e.from;
281 LayoutNode other = e.to;
282 LayoutEdge curEdge = e;
283 while (cur.vertex == null && cur.preds.size() != 0) {
284 if (points.size() > 1 && points.get(points.size() - 1).x == cur.x + cur.width / 2 && points.get(points.size() - 2).x == cur.x + cur.width / 2) {
285 points.remove(points.size() - 1);
286 }
287 points.add(new Point(cur.x + cur.width / 2, cur.y + cur.height));
288 if (points.size() > 1 && points.get(points.size() - 1).x == cur.x + cur.width / 2 && points.get(points.size() - 2).x == cur.x + cur.width / 2) {
289 points.remove(points.size() - 1);
290 }
291 points.add(new Point(cur.x + cur.width / 2, cur.y));
292 assert cur.preds.size() == 1;
293 curEdge = cur.preds.get(0);
294 cur = curEdge.from;
295 }
296
297 p = new Point(cur.x + curEdge.relativeFrom, cur.y + cur.height - cur.bottomYOffset + (curEdge.link == null ? 0 : curEdge.link.getFrom().getRelativePosition().y));
298 if (curEdge.from.outOffsets.containsKey(curEdge.relativeFrom)) {
299 points.add(new Point(p.x, p.y + curEdge.from.outOffsets.get(curEdge.relativeFrom) + (curEdge.link == null ? 0 : curEdge.link.getFrom().getRelativePosition().y)));
300 }
301 points.add(p);
302
303 Collections.reverse(points);
304
305
306
307 if (cur.vertex == null && cur.preds.size() == 0) {
308
309 if (reversedLinkEndPoints.containsKey(e.link)) {
310 for (Point p1 : reversedLinkEndPoints.get(e.link)) {
311 points.add(new Point(p1.x + e.to.x, p1.y + e.to.y));
312 }
313 }
314
315 if (splitStartPoints.containsKey(e.link)) {
316 points.add(0, null);
317 points.addAll(0, splitStartPoints.get(e.link));
318
319 //checkPoints(points);
320 if (reversedLinks.contains(e.link)) {
321 Collections.reverse(points);
322 }
323 assert !linkPositions.containsKey(e.link);
324 linkPositions.put(e.link, points);
325 } else {
326 splitEndPoints.put(e.link, points);
327 }
328
329 } else {
330 if (reversedLinks.contains(e.link)) {
331 Collections.reverse(points);
332 }
333 if (reversedLinkStartPoints.containsKey(e.link)) {
334 for (Point p1 : reversedLinkStartPoints.get(e.link)) {
335 points.add(new Point(p1.x + cur.x, p1.y + cur.y));
336 }
337 }
338
339 if (reversedLinkEndPoints.containsKey(e.link)) {
340 for (Point p1 : reversedLinkEndPoints.get(e.link)) {
341 points.add(0, new Point(p1.x + other.x, p1.y + other.y));
342 }
343 }
344
345 assert !linkPositions.containsKey(e.link);
346 linkPositions.put(e.link, points);
347 }
348 pointCount += points.size();
349
350 // No longer needed!
351 e.link = null;
352 }
353 }
354
355 for (LayoutEdge e : n.succs) {
356 if (e.link != null) {
357 ArrayList<Point> points = new ArrayList<>();
358 Point p = new Point(e.from.x + e.relativeFrom, e.from.y + e.from.height - e.from.bottomYOffset + e.link.getFrom().getRelativePosition().y);
359 points.add(p);
360 if (e.from.outOffsets.containsKey(e.relativeFrom)) {
361 points.add(new Point(p.x, p.y + e.from.outOffsets.get(e.relativeFrom) + e.link.getFrom().getRelativePosition().y));
362 }
363
364 LayoutNode cur = e.to;
365 LayoutNode other = e.from;
366 LayoutEdge curEdge = e;
367 while (cur.vertex == null && cur.succs.size() != 0) {
368 if (points.size() > 1 && points.get(points.size() - 1).x == cur.x + cur.width / 2 && points.get(points.size() - 2).x == cur.x + cur.width / 2) {
369 points.remove(points.size() - 1);
370 }
371 points.add(new Point(cur.x + cur.width / 2, cur.y));
372 if (points.size() > 1 && points.get(points.size() - 1).x == cur.x + cur.width / 2 && points.get(points.size() - 2).x == cur.x + cur.width / 2) {
373 points.remove(points.size() - 1);
374 }
375 points.add(new Point(cur.x + cur.width / 2, cur.y + cur.height));
376 if (cur.succs.size() == 0) {
377 break;
378 }
379 assert cur.succs.size() == 1;
380 curEdge = cur.succs.get(0);
381 cur = curEdge.to;
382 }
383
384
385 p = new Point(cur.x + curEdge.relativeTo, cur.y + cur.yOffset + ((curEdge.link == null) ? 0 : curEdge.link.getTo().getRelativePosition().y));
386 points.add(p);
387 if (curEdge.to.inOffsets.containsKey(curEdge.relativeTo)) {
388 points.add(new Point(p.x, p.y + curEdge.to.inOffsets.get(curEdge.relativeTo) + ((curEdge.link == null) ? 0 : curEdge.link.getTo().getRelativePosition().y)));
389 }
390
391
392 if (cur.succs.size() == 0 && cur.vertex == null) {
393 if (reversedLinkStartPoints.containsKey(e.link)) {
394 for (Point p1 : reversedLinkStartPoints.get(e.link)) {
395 points.add(0, new Point(p1.x + other.x, p1.y + other.y));
396 }
397 }
398
399 if (splitEndPoints.containsKey(e.link)) {
400 points.add(null);
401 points.addAll(splitEndPoints.get(e.link));
402
403 //checkPoints(points);
404 if (reversedLinks.contains(e.link)) {
405 Collections.reverse(points);
406 }
407 assert !linkPositions.containsKey(e.link);
408 linkPositions.put(e.link, points);
409 } else {
410 splitStartPoints.put(e.link, points);
411 }
412 } else {
413
414 if (reversedLinkStartPoints.containsKey(e.link)) {
415 for (Point p1 : reversedLinkStartPoints.get(e.link)) {
416 points.add(0, new Point(p1.x + other.x, p1.y + other.y));
417 }
418 }
419 if (reversedLinkEndPoints.containsKey(e.link)) {
420 for (Point p1 : reversedLinkEndPoints.get(e.link)) {
421 points.add(new Point(p1.x + cur.x, p1.y + cur.y));
422 }
423 }
424 if (reversedLinks.contains(e.link)) {
425 Collections.reverse(points);
426 }
427 //checkPoints(points);
428 assert !linkPositions.containsKey(e.link);
429 linkPositions.put(e.link, points);
430 }
431
432 pointCount += points.size();
433 e.link = null;
434 }
435 }
436 }
437
438 int minX = Integer.MAX_VALUE;
439 int minY = Integer.MAX_VALUE;
440 for (Vertex v : vertexPositions.keySet()) {
441 Point p = vertexPositions.get(v);
442 minX = Math.min(minX, p.x);
443 minY = Math.min(minY, p.y);
444 }
445
446 for (Link l : linkPositions.keySet()) {
447 List<Point> points = linkPositions.get(l);
448 for (Point p : points) {
449 if (p != null) {
450 minX = Math.min(minX, p.x);
451 minY = Math.min(minY, p.y);
452 }
453 }
454
455 }
456
457 for (Vertex v : vertexPositions.keySet()) {
458 Point p = vertexPositions.get(v);
459 p.x -= minX;
460 p.y -= minY;
461 v.setPosition(p);
462 }
463
464 for (Link l : linkPositions.keySet()) {
465 List<Point> points = linkPositions.get(l);
466 for (Point p : points) {
467 if (p != null) {
468 p.x -= minX;
469 p.y -= minY;
470 }
471 }
472 l.setControlPoints(points);
473
474 }
475 }
476
477 @Override
478 protected void printStatistics() {
479 System.out.println("Number of nodes: " + nodes.size());
480 int edgeCount = 0;
481 for (LayoutNode n : nodes) {
482 edgeCount += n.succs.size();
483 }
484 System.out.println("Number of edges: " + edgeCount);
485 System.out.println("Number of points: " + pointCount);
486 }
487 }
488
489 private static class Segment {
490
491 public float d;
492 public int orderNumber = -1;
493 public ArrayList<LayoutNode> nodes = new ArrayList<>();
494 public HashSet<Segment> succs = new HashSet<>();
495 public HashSet<Segment> preds = new HashSet<>();
496 public Region region;
497 }
498 private static final Comparator<Segment> segmentComparator = new Comparator<Segment>() {
499
500 @Override
501 public int compare(Segment s1, Segment s2) {
502 return s1.orderNumber - s2.orderNumber;
503 }
504 };
505
506 private static class Region {
507
508 public float d;
509 public int minOrderNumber;
510 public SortedSet<Segment> segments = new TreeSet<>(segmentComparator);
511 public HashSet<Region> succs = new HashSet<>(4);
512 public HashSet<Region> preds = new HashSet<>(4);
513 }
514 private static final Comparator<Region> regionComparator = new Comparator<Region>() {
515
516 @Override
517 public int compare(Region r1, Region r2) {
518 return r1.minOrderNumber - r2.minOrderNumber;
519 }
520 };
521 private static final Comparator<LayoutNode> nodePositionComparator = new Comparator<LayoutNode>() {
522
523 @Override
524 public int compare(LayoutNode n1, LayoutNode n2) {
525 return n1.pos - n2.pos;
526 }
527 };
528 private static final Comparator<LayoutNode> nodeProcessingDownComparator = new Comparator<LayoutNode>() {
529 @Override
530 public int compare(LayoutNode n1, LayoutNode n2) {
531 if (n1.vertex == null) {
532 if (n2.vertex == null) {
533 return 0;
534 }
535 return -1;
536 }
537 if (n2.vertex == null) {
538 return 1;
539 }
540 return n1.preds.size() - n2.preds.size();
541 }
542 };
543 private static final Comparator<LayoutNode> nodeProcessingUpComparator = new Comparator<LayoutNode>() {
544
545 @Override
546 public int compare(LayoutNode n1, LayoutNode n2) {
547 if (n1.vertex == null) {
548 if (n2.vertex == null) {
549 return 0;
550 }
551 return -1;
552 }
553 if (n2.vertex == null) {
554 return 1;
555 }
556 return n1.succs.size() - n2.succs.size();
557 }
558 };
559
560 private class AssignXCoordinates extends AlgorithmPart {
561
562 private ArrayList<Integer>[] space;
563 private ArrayList<LayoutNode>[] downProcessingOrder;
564 private ArrayList<LayoutNode>[] upProcessingOrder;
565
566 private void initialPositions() {
567 for (LayoutNode n : nodes) {
568 n.x = space[n.layer].get(n.pos);
569 }
570 }
571
572 @SuppressWarnings("unchecked")
573 private void createArrays() {
574 space = new ArrayList[layers.length];
575 downProcessingOrder = new ArrayList[layers.length];
576 upProcessingOrder = new ArrayList[layers.length];
577 }
578
579 @Override
580 protected void run() {
581 createArrays();
582
583 for (int i = 0; i < layers.length; i++) {
584 space[i] = new ArrayList<>();
585 downProcessingOrder[i] = new ArrayList<>();
586 upProcessingOrder[i] = new ArrayList<>();
587
588 int curX = 0;
589 for (LayoutNode n : layers[i]) {
590 space[i].add(curX);
591 curX += n.width + xOffset;
592 downProcessingOrder[i].add(n);
593 upProcessingOrder[i].add(n);
594 }
595
596 Collections.sort(downProcessingOrder[i], nodeProcessingDownComparator);
597 Collections.sort(upProcessingOrder[i], nodeProcessingUpComparator);
598 }
599
600 initialPositions();
601 for (int i = 0; i < SWEEP_ITERATIONS; i++) {
602 sweepDown();
603 sweepUp();
604 }
605
606 sweepDown();
607 //for (int i = 0; i < SWEEP_ITERATIONS; i++) {
608 // doubleSweep();
609 //}
610 }
611
612 private int calculateOptimalDown(LayoutNode n) {
613 int size = n.preds.size();
614 if (size == 0) {
615 return n.x;
616 }
617 int[] values = new int[size];
618 for (int i = 0; i < size; i++) {
619 LayoutEdge e = n.preds.get(i);
620 values[i] = e.from.x + e.relativeFrom - e.relativeTo;
621 if (e.vip) {
622 return values[i];
623 }
624 }
625 return median(values);
626 }
627
628 private int calculateOptimalBoth(LayoutNode n) {
629 if (n.preds.size() == n.succs.size()) {
630 return n.x;
631 }
632
633 int[] values = new int[n.preds.size() + n.succs.size()];
634 int i = 0;
635
636 for (LayoutEdge e : n.preds) {
637 values[i] = e.from.x + e.relativeFrom - e.relativeTo;
638 i++;
639 }
640
641 for (LayoutEdge e : n.succs) {
642 values[i] = e.to.x + e.relativeTo - e.relativeFrom;
643 i++;
644 }
645
646 return median(values);
647 }
648
649 private int calculateOptimalUp(LayoutNode n) {
650 int size = n.succs.size();
651 if (size == 0) {
652 return n.x;
653 }
654 int[] values = new int[size];
655 for (int i = 0; i < size; i++) {
656 LayoutEdge e = n.succs.get(i);
657 values[i] = e.to.x + e.relativeTo - e.relativeFrom;
658 if (e.vip) {
659 return values[i];
660 }
661 }
662 return median(values);
663 }
664
665 private int median(int[] values) {
666 Arrays.sort(values);
667 if (values.length % 2 == 0) {
668 return (values[values.length / 2 - 1] + values[values.length / 2]) / 2;
669 } else {
670 return values[values.length / 2];
671 }
672 }
673
674 private void sweepUp() {
675 for (int i = layers.length - 1; i >= 0; i--) {
676 NodeRow r = new NodeRow(space[i]);
677 for (LayoutNode n : upProcessingOrder[i]) {
678 int optimal = calculateOptimalUp(n);
679 r.insert(n, optimal);
680 }
681 }
682 }
683
684 private void doubleSweep() {
685 for (int i = layers.length - 2; i >= 0; i--) {
686 NodeRow r = new NodeRow(space[i]);
687 for (LayoutNode n : upProcessingOrder[i]) {
688 int optimal = calculateOptimalBoth(n);
689 r.insert(n, optimal);
690 }
691 }
692 }
693
694 private void sweepDown() {
695 for (int i = 1; i < layers.length; i++) {
696 NodeRow r = new NodeRow(space[i]);
697 for (LayoutNode n : downProcessingOrder[i]) {
698 int optimal = calculateOptimalDown(n);
699 r.insert(n, optimal);
700 }
701 }
702 }
703 }
704
705 private static class NodeRow {
706
707 private TreeSet<LayoutNode> treeSet;
708 private ArrayList<Integer> space;
709
710 public NodeRow(ArrayList<Integer> space) {
711 treeSet = new TreeSet<>(nodePositionComparator);
712 this.space = space;
713 }
714
715 public int offset(LayoutNode n1, LayoutNode n2) {
716 int v1 = space.get(n1.pos) + n1.width;
717 int v2 = space.get(n2.pos);
718 return v2 - v1;
719 }
720
721 public void insert(LayoutNode n, int pos) {
722
723 SortedSet<LayoutNode> headSet = treeSet.headSet(n);
724
725 LayoutNode leftNeighbor = null;
726 int minX = Integer.MIN_VALUE;
727 if (!headSet.isEmpty()) {
728 leftNeighbor = headSet.last();
729 minX = leftNeighbor.x + leftNeighbor.width + offset(leftNeighbor, n);
730 }
731
732 if (pos < minX) {
733 n.x = minX;
734 } else {
735
736 LayoutNode rightNeighbor = null;
737 SortedSet<LayoutNode> tailSet = treeSet.tailSet(n);
738 int maxX = Integer.MAX_VALUE;
739 if (!tailSet.isEmpty()) {
740 rightNeighbor = tailSet.first();
741 maxX = rightNeighbor.x - offset(n, rightNeighbor) - n.width;
742 }
743
744 if (pos > maxX) {
745 n.x = maxX;
746 } else {
747 n.x = pos;
748 }
749
750 assert minX <= maxX;
751 }
752
753 treeSet.add(n);
754 }
755 }
756 private static Comparator<LayoutNode> crossingNodeComparator = new Comparator<LayoutNode>() {
757
758 @Override
759 public int compare(LayoutNode n1, LayoutNode n2) {
760 return n1.crossingNumber - n2.crossingNumber;
761 }
762 };
763
764 private class CrossingReduction extends AlgorithmPart {
765
766 @Override
767 public void preCheck() {
768 for (LayoutNode n : nodes) {
769 assert n.layer < layerCount;
770 }
771 }
772
773 @SuppressWarnings("unchecked")
774 private void createLayers() {
775 layers = new List[layerCount];
776
777 for (int i = 0; i < layerCount; i++) {
778 layers[i] = new ArrayList<>();
779 }
780 }
781
782 @Override
783 protected void run() {
784 createLayers();
785
786 // Generate initial ordering
787 HashSet<LayoutNode> visited = new HashSet<>();
788 for (LayoutNode n : nodes) {
789 if (n.layer == 0) {
790 layers[0].add(n);
791 visited.add(n);
792 } else if (n.preds.size() == 0) {
793 layers[n.layer].add(n);
794 visited.add(n);
795 }
796 }
797
798 for (int i = 0; i < layers.length - 1; i++) {
799 for (LayoutNode n : layers[i]) {
800 for (LayoutEdge e : n.succs) {
801 if (!visited.contains(e.to)) {
802 visited.add(e.to);
803 layers[i + 1].add(e.to);
804 }
805 }
806 }
807 }
808
809
810 updatePositions();
811
812 initX();
813
814 // Optimize
815 for (int i = 0; i < CROSSING_ITERATIONS; i++) {
816 downSweep();
817 upSweep();
818 }
819 if (reversedLinks.isEmpty()) {
820 // This graph seems to be a tree or forest.
821 // A final down-sweep will usually give us a better layout.
822 downSweep();
823 }
824 }
825
826 private void initX() {
827
828 for (int i = 0; i < layers.length; i++) {
829 updateXOfLayer(i);
830 }
831 }
832
833 private void updateXOfLayer(int index) {
834 int x = 0;
835
836 for (LayoutNode n : layers[index]) {
837 n.x = x;
838 x += n.width + X_OFFSET;
839 }
840 }
841
842 private void updatePositions() {
843
844 for (int i = 0; i < layers.length; i++) {
845 int z = 0;
846 for (LayoutNode n : layers[i]) {
847 n.pos = z;
848 z++;
849 }
850 }
851 }
852
853 private void downSweep() {
854
855 // Downsweep
856 for (int i = 1; i < layerCount; i++) {
857
858 for (LayoutNode n : layers[i]) {
859 n.crossingNumber = 0;
860 }
861
862 for (LayoutNode n : layers[i]) {
863
864 int sum = 0;
865 int count = 0;
866 for (LayoutEdge e : n.preds) {
867 int cur = e.from.x + e.relativeFrom;
868 int factor = 1;
869 if (e.vip) {
870 factor = VIP_BONUS;
871 }
872 sum += cur*factor;
873 count+=factor;
874 }
875
876 if (count > 0) {
877 sum /= count;
878 n.crossingNumber = sum;
879 }
880 }
881
882
883 updateCrossingNumbers(i, true);
884 Collections.sort(layers[i], crossingNodeComparator);
885 updateXOfLayer(i);
886
887 int z = 0;
888 for (LayoutNode n : layers[i]) {
889 n.pos = z;
890 z++;
891 }
892 }
893 }
894
895 private void updateCrossingNumbers(int index, boolean down) {
896 for (int i = 0; i < layers[index].size(); i++) {
897 LayoutNode n = layers[index].get(i);
898 LayoutNode prev = null;
899 if (i > 0) {
900 prev = layers[index].get(i - 1);
901 }
902 LayoutNode next = null;
903 if (i < layers[index].size() - 1) {
904 next = layers[index].get(i + 1);
905 }
906
907 boolean cond = n.succs.isEmpty();
908 if (down) {
909 cond = n.preds.isEmpty();
910 }
911
912 if (cond) {
913
914 if (prev != null && next != null) {
915 n.crossingNumber = (prev.crossingNumber + next.crossingNumber) / 2;
916 } else if (prev != null) {
917 n.crossingNumber = prev.crossingNumber;
918 } else if (next != null) {
919 n.crossingNumber = next.crossingNumber;
920 }
921 }
922 }
923 }
924
925 private void upSweep() {
926 // Upsweep
927 for (int i = layerCount - 2; i >= 0; i--) {
928
929 for (LayoutNode n : layers[i]) {
930 n.crossingNumber = 0;
931 }
932
933 for (LayoutNode n : layers[i]) {
934
935 int count = 0;
936 int sum = 0;
937 for (LayoutEdge e : n.succs) {
938 int cur = e.to.x + e.relativeTo;
939 int factor = 1;
940 if (e.vip) {
941 factor = VIP_BONUS;
942 }
943 sum += cur*factor;
944 count+=factor;
945 }
946
947 if (count > 0) {
948 sum /= count;
949 n.crossingNumber = sum;
950 }
951
952 }
953
954 updateCrossingNumbers(i, false);
955 Collections.sort(layers[i], crossingNodeComparator);
956 updateXOfLayer(i);
957
958 int z = 0;
959 for (LayoutNode n : layers[i]) {
960 n.pos = z;
961 z++;
962 }
963 }
964 }
965
966 @Override
967 public void postCheck() {
968
969 HashSet<LayoutNode> visited = new HashSet<>();
970 for (int i = 0; i < layers.length; i++) {
971 for (LayoutNode n : layers[i]) {
972 assert !visited.contains(n);
973 assert n.layer == i;
974 visited.add(n);
975 }
976 }
977
978 }
979 }
980
981 private class AssignYCoordinates extends AlgorithmPart {
982
983 @Override
984 protected void run() {
985 int curY = 0;
986
987 for (int i = 0; i < layers.length; i++) {
988 int maxHeight = 0;
989 int baseLine = 0;
990 int bottomBaseLine = 0;
991 for (LayoutNode n : layers[i]) {
992 maxHeight = Math.max(maxHeight, n.height - n.yOffset - n.bottomYOffset);
993 baseLine = Math.max(baseLine, n.yOffset);
994 bottomBaseLine = Math.max(bottomBaseLine, n.bottomYOffset);
995 }
996
997 int maxXOffset = 0;
998 for (LayoutNode n : layers[i]) {
999 if (n.vertex == null) {
1000 // Dummy node
1001 n.y = curY;
1002 n.height = maxHeight + baseLine + bottomBaseLine;
1003
1004 } else {
1005 n.y = curY + baseLine + (maxHeight - (n.height - n.yOffset - n.bottomYOffset)) / 2 - n.yOffset;
1006 }
1007
1008 for (LayoutEdge e : n.succs) {
1009 int curXOffset = Math.abs(n.x - e.to.x);
1010 maxXOffset = Math.max(curXOffset, maxXOffset);
1011 }
1012 }
1013
1014 curY += maxHeight + baseLine + bottomBaseLine;
1015 curY += layerOffset + (int) Math.sqrt(maxXOffset);
1016 }
1017 }
1018 }
1019
1020 private class CreateDummyNodes extends AlgorithmPart {
1021
1022 private int oldNodeCount;
1023
1024 @Override
1025 protected void preCheck() {
1026 for (LayoutNode n : nodes) {
1027 for (LayoutEdge e : n.succs) {
1028 assert e.from != null;
1029 assert e.from == n;
1030 assert e.from.layer < e.to.layer;
1031 }
1032
1033 for (LayoutEdge e : n.preds) {
1034 assert e.to != null;
1035 assert e.to == n;
1036 }
1037 }
1038 }
1039
1040 @Override
1041 protected void run() {
1042 oldNodeCount = nodes.size();
1043
1044
1045 if (combine == Combine.SAME_OUTPUTS) {
1046
1047 Comparator<LayoutEdge> comparator = new Comparator<LayoutEdge>() {
1048
1049 @Override
1050 public int compare(LayoutEdge e1, LayoutEdge e2) {
1051 return e1.to.layer - e2.to.layer;
1052 }
1053 };
1054 HashMap<Integer, List<LayoutEdge>> portHash = new HashMap<>();
1055 ArrayList<LayoutNode> currentNodes = new ArrayList<>(nodes);
1056 for (LayoutNode n : currentNodes) {
1057 portHash.clear();
1058
1059 ArrayList<LayoutEdge> succs = new ArrayList<>(n.succs);
1060 HashMap<Integer, LayoutNode> topNodeHash = new HashMap<>();
1061 HashMap<Integer, HashMap<Integer, LayoutNode>> bottomNodeHash = new HashMap<>();
1062 for (LayoutEdge e : succs) {
1063 assert e.from.layer < e.to.layer;
1064 if (e.from.layer != e.to.layer - 1) {
1065 if (maxLayerLength != -1 && e.to.layer - e.from.layer > maxLayerLength/* && e.to.preds.size() > 1 && e.from.succs.size() > 1*/) {
1066 assert maxLayerLength > 2;
1067 e.to.preds.remove(e);
1068 e.from.succs.remove(e);
1069
1070 LayoutEdge topEdge = null;
1071
1072 if (combine == Combine.SAME_OUTPUTS && topNodeHash.containsKey(e.relativeFrom)) {
1073 LayoutNode topNode = topNodeHash.get(e.relativeFrom);
1074 topEdge = new LayoutEdge();
1075 topEdge.relativeFrom = e.relativeFrom;
1076 topEdge.from = e.from;
1077 topEdge.relativeTo = topNode.width / 2;
1078 topEdge.to = topNode;
1079 topEdge.link = e.link;
1080 topEdge.vip = e.vip;
1081 e.from.succs.add(topEdge);
1082 topNode.preds.add(topEdge);
1083 } else {
1084
1085 LayoutNode topNode = new LayoutNode();
1086 topNode.layer = e.from.layer + 1;
1087 topNode.width = DUMMY_WIDTH;
1088 topNode.height = DUMMY_HEIGHT;
1089 nodes.add(topNode);
1090 topEdge = new LayoutEdge();
1091 topEdge.relativeFrom = e.relativeFrom;
1092 topEdge.from = e.from;
1093 topEdge.relativeTo = topNode.width / 2;
1094 topEdge.to = topNode;
1095 topEdge.link = e.link;
1096 topEdge.vip = e.vip;
1097 e.from.succs.add(topEdge);
1098 topNode.preds.add(topEdge);
1099 topNodeHash.put(e.relativeFrom, topNode);
1100 bottomNodeHash.put(e.relativeFrom, new HashMap<Integer, LayoutNode>());
1101 }
1102
1103 HashMap<Integer, LayoutNode> hash = bottomNodeHash.get(e.relativeFrom);
1104
1105 LayoutNode bottomNode = null;
1106 if (hash.containsKey(e.to.layer)) {
1107 bottomNode = hash.get(e.to.layer);
1108 } else {
1109
1110 bottomNode = new LayoutNode();
1111 bottomNode.layer = e.to.layer - 1;
1112 bottomNode.width = DUMMY_WIDTH;
1113 bottomNode.height = DUMMY_HEIGHT;
1114 nodes.add(bottomNode);
1115 hash.put(e.to.layer, bottomNode);
1116 }
1117
1118 LayoutEdge bottomEdge = new LayoutEdge();
1119 bottomEdge.relativeTo = e.relativeTo;
1120 bottomEdge.to = e.to;
1121 bottomEdge.relativeFrom = bottomNode.width / 2;
1122 bottomEdge.from = bottomNode;
1123 bottomEdge.link = e.link;
1124 bottomEdge.vip = e.vip;
1125 e.to.preds.add(bottomEdge);
1126 bottomEdgeHash.put(topEdge, bottomEdge);
1127 bottomNode.succs.add(bottomEdge);
1128
1129 } else {
1130 Integer i = e.relativeFrom;
1131 if (!portHash.containsKey(i)) {
1132 portHash.put(i, new ArrayList<LayoutEdge>());
1133 }
1134 portHash.get(i).add(e);
1135 }
1136 }
1137 }
1138
1139 succs = new ArrayList<>(n.succs);
1140 for (LayoutEdge e : succs) {
1141
1142 Integer i = e.relativeFrom;
1143 if (portHash.containsKey(i)) {
1144
1145 List<LayoutEdge> list = portHash.get(i);
1146 Collections.sort(list, comparator);
1147
1148 if (list.size() == 1) {
1149 processSingleEdge(list.get(0));
1150 } else {
1151
1152 int maxLayer = list.get(0).to.layer;
1153 for (LayoutEdge curEdge : list) {
1154 maxLayer = Math.max(maxLayer, curEdge.to.layer);
1155 }
1156
1157
1158 int cnt = maxLayer - n.layer - 1;
1159 LayoutEdge[] edges = new LayoutEdge[cnt];
1160 LayoutNode[] nodes = new LayoutNode[cnt];
1161 edges[0] = new LayoutEdge();
1162 edges[0].from = n;
1163 edges[0].relativeFrom = i;
1164 edges[0].vip = e.vip;
1165 n.succs.add(edges[0]);
1166
1167 nodes[0] = new LayoutNode();
1168 nodes[0].width = dummyWidth;
1169 nodes[0].height = dummyHeight;
1170 nodes[0].layer = n.layer + 1;
1171 nodes[0].preds.add(edges[0]);
1172 edges[0].to = nodes[0];
1173 edges[0].relativeTo = nodes[0].width / 2;
1174 for (int j = 1; j < cnt; j++) {
1175 edges[j] = new LayoutEdge();
1176 edges[j].vip = e.vip;
1177 edges[j].from = nodes[j - 1];
1178 edges[j].relativeFrom = nodes[j - 1].width / 2;
1179 nodes[j - 1].succs.add(edges[j]);
1180 nodes[j] = new LayoutNode();
1181 nodes[j].width = dummyWidth;
1182 nodes[j].height = dummyHeight;
1183 nodes[j].layer = n.layer + j + 1;
1184 nodes[j].preds.add(edges[j]);
1185 edges[j].to = nodes[j];
1186 edges[j].relativeTo = nodes[j].width / 2;
1187 }
1188
1189 for (LayoutEdge curEdge : list) {
1190 assert curEdge.to.layer - n.layer - 2 >= 0;
1191 assert curEdge.to.layer - n.layer - 2 < cnt;
1192 LayoutNode anchor = nodes[curEdge.to.layer - n.layer - 2];
1193 anchor.succs.add(curEdge);
1194 curEdge.from = anchor;
1195 curEdge.relativeFrom = anchor.width / 2;
1196 n.succs.remove(curEdge);
1197 }
1198
1199 }
1200
1201 portHash.remove(i);
1202 }
1203 }
1204 }
1205 } else if (combine == Combine.SAME_INPUTS) {
1206 throw new UnsupportedOperationException("Currently not supported");
1207 } else {
1208 ArrayList<LayoutNode> currentNodes = new ArrayList<>(nodes);
1209 for (LayoutNode n : currentNodes) {
1210 for (LayoutEdge e : n.succs) {
1211 processSingleEdge(e);
1212 }
1213 }
1214 }
1215 }
1216
1217 private void processSingleEdge(LayoutEdge e) {
1218 LayoutNode n = e.from;
1219 if (e.to.layer > n.layer + 1) {
1220 LayoutEdge last = e;
1221 for (int i = n.layer + 1; i < last.to.layer; i++) {
1222 last = addBetween(last, i);
1223 }
1224 }
1225 }
1226
1227 private LayoutEdge addBetween(LayoutEdge e, int layer) {
1228 LayoutNode n = new LayoutNode();
1229 n.width = dummyWidth;
1230 n.height = dummyHeight;
1231 n.layer = layer;
1232 n.preds.add(e);
1233 nodes.add(n);
1234 LayoutEdge result = new LayoutEdge();
1235 result.vip = e.vip;
1236 n.succs.add(result);
1237 result.from = n;
1238 result.relativeFrom = n.width / 2;
1239 result.to = e.to;
1240 result.relativeTo = e.relativeTo;
1241 e.relativeTo = n.width / 2;
1242 e.to.preds.remove(e);
1243 e.to.preds.add(result);
1244 e.to = n;
1245 return result;
1246 }
1247
1248 @Override
1249 public void printStatistics() {
1250 System.out.println("Dummy nodes created: " + (nodes.size() - oldNodeCount));
1251 }
1252
1253 @Override
1254 public void postCheck() {
1255 ArrayList<LayoutNode> currentNodes = new ArrayList<>(nodes);
1256 for (LayoutNode n : currentNodes) {
1257 for (LayoutEdge e : n.succs) {
1258 assert e.from.layer == e.to.layer - 1;
1259 }
1260 }
1261
1262 for (int i = 0; i < layers.length; i++) {
1263 assert layers[i].size() > 0;
1264 for (LayoutNode n : layers[i]) {
1265 assert n.layer == i;
1266 }
1267 }
1268 }
1269 }
1270
1271 private class AssignLayers extends AlgorithmPart {
1272
1273 @Override
1274 public void preCheck() {
1275 for (LayoutNode n : nodes) {
1276 assert n.layer == -1;
1277 }
1278 }
1279
1280 @Override
1281 protected void run() {
1282
1283 List<LayoutNode> insertOrder = new ArrayList<>();
1284
1285 HashSet<LayoutNode> set = new HashSet<>();
1286 for (LayoutNode n : nodes) {
1287 if (n.preds.size() == 0) {
1288 set.add(n);
1289 insertOrder.add(n);
1290 n.layer = 0;
1291 }
1292 }
1293
1294 int z = minLayerDifference;
1295 HashSet<LayoutNode> newSet = new HashSet<>();
1296 HashSet<LayoutNode> failed = new HashSet<>();
1297 while (!set.isEmpty()) {
1298
1299 newSet.clear();
1300 failed.clear();
1301
1302 for (LayoutNode n : set) {
1303
1304 for (LayoutEdge se : n.succs) {
1305 LayoutNode s = se.to;
1306 if (!newSet.contains(s) && !failed.contains(s)) {
1307 boolean ok = true;
1308 for (LayoutEdge pe : s.preds) {
1309 LayoutNode p = pe.from;
1310 if (p.layer == -1) {
1311 ok = false;
1312 break;
1313 }
1314 }
1315
1316 if (ok) {
1317 newSet.add(s);
1318 } else {
1319 failed.add(s);
1320 }
1321 }
1322 }
1323
1324 }
1325
1326 for (LayoutNode n : newSet) {
1327 n.layer = z;
1328 insertOrder.add(n);
1329 }
1330
1331 // Swap sets
1332 HashSet<LayoutNode> tmp = set;
1333 set = newSet;
1334 newSet = tmp;
1335 z += minLayerDifference;
1336 }
1337
1338 optimize(insertOrder);
1339
1340 layerCount = z - minLayerDifference;
1341
1342 for (Vertex v : lastLayerHint) {
1343
1344 LayoutNode n = vertexToLayoutNode.get(v);
1345 assert n.succs.size() == 0;
1346 n.layer = layerCount - 1;
1347 }
1348
1349 for (Vertex v : firstLayerHint) {
1350 LayoutNode n = vertexToLayoutNode.get(v);
1351 assert n.preds.size() == 0;
1352 n.layer = 0;
1353 assert n.layer == 0;
1354 }
1355 }
1356
1357 public void optimize(List<LayoutNode> insertOrder) {
1358 for (int i = insertOrder.size() - 1; i >= 0; i--) {
1359 LayoutNode cur = insertOrder.get(i);
1360 if (cur.succs.size() > cur.preds.size()) {
1361 int minLayer = cur.succs.get(0).to.layer;
1362 for (LayoutEdge e : cur.succs) {
1363 minLayer = Math.min(minLayer, e.to.layer);
1364 }
1365 cur.layer = minLayer - 1;
1366 }
1367 }
1368 }
1369
1370 @Override
1371 public void postCheck() {
1372 for (LayoutNode n : nodes) {
1373 assert n.layer >= 0;
1374 assert n.layer < layerCount;
1375 for (LayoutEdge e : n.succs) {
1376 assert e.from.layer < e.to.layer;
1377 }
1378 }
1379 }
1380 }
1381
1382 private class ReverseEdges extends AlgorithmPart {
1383
1384 private HashSet<LayoutNode> visited;
1385 private HashSet<LayoutNode> active;
1386
1387 @Override
1388 protected void run() {
1389
1390 // Remove self-edges
1391 for (LayoutNode node : nodes) {
1392 ArrayList<LayoutEdge> succs = new ArrayList<>(node.succs);
1393 for (LayoutEdge e : succs) {
1394 assert e.from == node;
1395 if (e.to == node) {
1396 node.succs.remove(e);
1397 node.preds.remove(e);
1398 }
1399 }
1400 }
1401
1402 // Reverse inputs of roots
1403 for (LayoutNode node : nodes) {
1404 if (node.vertex.isRoot()) {
1405 boolean ok = true;
1406 for (LayoutEdge e : node.preds) {
1407 if (e.from.vertex.isRoot()) {
1408 ok = false;
1409 break;
1410 }
1411 }
1412 if (ok) {
1413 reverseAllInputs(node);
1414 }
1415 }
1416 }
1417
1418
1419 // Start DFS and reverse back edges
1420 visited = new HashSet<>();
1421 active = new HashSet<>();
1422 for (LayoutNode node : nodes) {
1423 DFS(node);
1424 }
1425
1426
1427 for (LayoutNode node : nodes) {
1428
1429 SortedSet<Integer> reversedDown = new TreeSet<>();
1430
1431 for (LayoutEdge e : node.succs) {
1432 if (reversedLinks.contains(e.link)) {
1433 reversedDown.add(e.relativeFrom);
1434 }
1435 }
1436
1437
1438 SortedSet<Integer> reversedUp = null;
1439 if (reversedDown.size() == 0) {
1440 reversedUp = new TreeSet<>(Collections.reverseOrder());
1441 } else {
1442 reversedUp = new TreeSet<>();
1443 }
1444
1445 for (LayoutEdge e : node.preds) {
1446 if (reversedLinks.contains(e.link)) {
1447 reversedUp.add(e.relativeTo);
1448 }
1449 }
1450
1451 final int offset = X_OFFSET + DUMMY_WIDTH;
1452
1453 int curX = 0;
1454 int curWidth = node.width + reversedDown.size() * offset;
1455 for (int pos : reversedDown) {
1456 ArrayList<LayoutEdge> reversedSuccs = new ArrayList<>();
1457 for (LayoutEdge e : node.succs) {
1458 if (e.relativeFrom == pos && reversedLinks.contains(e.link)) {
1459 reversedSuccs.add(e);
1460 e.relativeFrom = curWidth;
1461 }
1462 }
1463
1464 ArrayList<Point> startPoints = new ArrayList<>();
1465 startPoints.add(new Point(curWidth, curX));
1466 startPoints.add(new Point(pos, curX));
1467 startPoints.add(new Point(pos, reversedDown.size() * offset));
1468 for (LayoutEdge e : reversedSuccs) {
1469 reversedLinkStartPoints.put(e.link, startPoints);
1470 }
1471
1472 node.inOffsets.put(pos, -curX);
1473 curX += offset;
1474 node.height += offset;
1475 node.yOffset += offset;
1476 curWidth -= offset;
1477 }
1478 node.width += reversedDown.size() * offset;
1479
1480 if (reversedDown.size() == 0) {
1481 curX = offset;
1482 } else {
1483 curX = -offset;
1484 }
1485
1486 curX = 0;
1487 int minX = 0;
1488 if (reversedDown.size() != 0) {
1489 minX = -offset * reversedUp.size();
1490 }
1491
1492 int oldNodeHeight = node.height;
1493 for (int pos : reversedUp) {
1494 ArrayList<LayoutEdge> reversedPreds = new ArrayList<>();
1495 for (LayoutEdge e : node.preds) {
1496 if (e.relativeTo == pos && reversedLinks.contains(e.link)) {
1497 if (reversedDown.size() == 0) {
1498 e.relativeTo = node.width + offset;
1499 } else {
1500 e.relativeTo = curX - offset;
1501 }
1502
1503 reversedPreds.add(e);
1504 }
1505 }
1506 node.height += offset;
1507 ArrayList<Point> endPoints = new ArrayList<>();
1508
1509 if (reversedDown.size() == 0) {
1510
1511 curX += offset;
1512 node.width += offset;
1513 endPoints.add(new Point(node.width, node.height));
1514
1515 } else {
1516 curX -= offset;
1517 node.width += offset;
1518 endPoints.add(new Point(curX, node.height));
1519 }
1520
1521 node.outOffsets.put(pos - minX, curX);
1522 curX += offset;
1523 node.bottomYOffset += offset;
1524
1525
1526 endPoints.add(new Point(pos, node.height));
1527 endPoints.add(new Point(pos, oldNodeHeight));
1528 for (LayoutEdge e : reversedPreds) {
1529 reversedLinkEndPoints.put(e.link, endPoints);
1530 }
1531 }
1532
1533
1534 if (minX < 0) {
1535 for (LayoutEdge e : node.preds) {
1536 e.relativeTo -= minX;
1537 }
1538
1539 for (LayoutEdge e : node.succs) {
1540 e.relativeFrom -= minX;
1541 }
1542
1543 node.xOffset = -minX;
1544 node.width += -minX;
1545 }
1546 }
1547
1548 }
1549
1550 private void DFS(LayoutNode startNode) {
1551 if (visited.contains(startNode)) {
1552 return;
1553 }
1554
1555 Stack<LayoutNode> stack = new Stack<>();
1556 stack.push(startNode);
1557
1558 while (!stack.empty()) {
1559 LayoutNode node = stack.pop();
1560
1561 if (visited.contains(node)) {
1562 // Node no longer active
1563 active.remove(node);
1564 continue;
1565 }
1566
1567 // Repush immediately to know when no longer active
1568 stack.push(node);
1569 visited.add(node);
1570 active.add(node);
1571
1572 ArrayList<LayoutEdge> succs = new ArrayList<>(node.succs);
1573 for (LayoutEdge e : succs) {
1574 if (active.contains(e.to)) {
1575 assert visited.contains(e.to);
1576 // Encountered back edge
1577 reverseEdge(e);
1578 } else if (!visited.contains(e.to) && (linksToFollow.size() == 0 || linksToFollow.contains(e.link))) {
1579 stack.push(e.to);
1580 }
1581 }
1582 }
1583 }
1584
1585 private void reverseAllInputs(LayoutNode node) {
1586 for (LayoutEdge e : node.preds) {
1587 assert !reversedLinks.contains(e.link);
1588 reversedLinks.add(e.link);
1589 node.succs.add(e);
1590 e.from.preds.add(e);
1591 e.from.succs.remove(e);
1592 int oldRelativeFrom = e.relativeFrom;
1593 int oldRelativeTo = e.relativeTo;
1594 e.to = e.from;
1595 e.from = node;
1596 e.relativeFrom = oldRelativeTo;
1597 e.relativeTo = oldRelativeFrom;
1598 }
1599 node.preds.clear();
1600 }
1601
1602 private void reverseEdge(LayoutEdge e) {
1603 assert !reversedLinks.contains(e.link);
1604 reversedLinks.add(e.link);
1605
1606 LayoutNode oldFrom = e.from;
1607 LayoutNode oldTo = e.to;
1608 int oldRelativeFrom = e.relativeFrom;
1609 int oldRelativeTo = e.relativeTo;
1610
1611 e.from = oldTo;
1612 e.to = oldFrom;
1613 e.relativeFrom = oldRelativeTo;
1614 e.relativeTo = oldRelativeFrom;
1615
1616 oldFrom.succs.remove(e);
1617 oldFrom.preds.add(e);
1618 oldTo.preds.remove(e);
1619 oldTo.succs.add(e);
1620 }
1621
1622 @Override
1623 public void postCheck() {
1624
1625 for (LayoutNode n : nodes) {
1626
1627 HashSet<LayoutNode> curVisited = new HashSet<>();
1628 Queue<LayoutNode> queue = new LinkedList<>();
1629 for (LayoutEdge e : n.succs) {
1630 LayoutNode s = e.to;
1631 queue.add(s);
1632 curVisited.add(s);
1633 }
1634
1635 while (!queue.isEmpty()) {
1636 LayoutNode curNode = queue.remove();
1637
1638 for (LayoutEdge e : curNode.succs) {
1639 assert e.to != n;
1640 if (!curVisited.contains(e.to)) {
1641 queue.add(e.to);
1642 curVisited.add(e.to);
1643 }
1644 }
1645 }
1646 }
1647 }
1648 }
1649 private Comparator<Link> linkComparator = new Comparator<Link>() {
1650
1651 @Override
1652 public int compare(Link l1, Link l2) {
1653
1654 int result = l1.getFrom().getVertex().compareTo(l2.getFrom().getVertex());
1655 if (result != 0) {
1656 return result;
1657 }
1658 result = l1.getTo().getVertex().compareTo(l2.getTo().getVertex());
1659 if (result != 0) {
1660 return result;
1661 }
1662 result = l1.getFrom().getRelativePosition().x - l2.getFrom().getRelativePosition().x;
1663 if (result != 0) {
1664 return result;
1665 }
1666 result = l1.getTo().getRelativePosition().x - l2.getTo().getRelativePosition().x;
1667 return result;
1668 }
1669 };
1670
1671 private class BuildDatastructure extends AlgorithmPart {
1672
1673 @Override
1674 protected void run() {
1675 // Set up nodes
1676 List<Vertex> vertices = new ArrayList<>(graph.getVertices());
1677 Collections.sort(vertices);
1678
1679 for (Vertex v : vertices) {
1680 LayoutNode node = new LayoutNode();
1681 Dimension size = v.getSize();
1682 node.width = (int) size.getWidth();
1683 node.height = (int) size.getHeight();
1684 node.vertex = v;
1685 nodes.add(node);
1686 vertexToLayoutNode.put(v, node);
1687 }
1688
1689 // Set up edges
1690 List<Link> links = new ArrayList<>(graph.getLinks());
1691 Collections.sort(links, linkComparator);
1692 for (Link l : links) {
1693 LayoutEdge edge = new LayoutEdge();
1694 assert vertexToLayoutNode.containsKey(l.getFrom().getVertex());
1695 assert vertexToLayoutNode.containsKey(l.getTo().getVertex());
1696 edge.from = vertexToLayoutNode.get(l.getFrom().getVertex());
1697 edge.to = vertexToLayoutNode.get(l.getTo().getVertex());
1698 edge.relativeFrom = l.getFrom().getRelativePosition().x;
1699 edge.relativeTo = l.getTo().getRelativePosition().x;
1700 edge.link = l;
1701 edge.from.succs.add(edge);
1702 edge.to.preds.add(edge);
1703 edge.vip = l.isVIP();
1704 //assert edge.from != edge.to; // No self-loops allowed
1705 }
1706
1707 for (Link l : importantLinks) {
1708 if (!vertexToLayoutNode.containsKey(l.getFrom().getVertex()) ||
1709 vertexToLayoutNode.containsKey(l.getTo().getVertex())) {
1710 continue;
1711 }
1712 LayoutNode from = vertexToLayoutNode.get(l.getFrom().getVertex());
1713 LayoutNode to = vertexToLayoutNode.get(l.getTo().getVertex());
1714 for (LayoutEdge e : from.succs) {
1715 if (e.to == to) {
1716 linksToFollow.add(e.link);
1717 }
1718 }
1719 }
1720 }
1721
1722 @Override
1723 public void postCheck() {
1724
1725 assert vertexToLayoutNode.keySet().size() == nodes.size();
1726 assert nodes.size() == graph.getVertices().size();
1727
1728 for (Vertex v : graph.getVertices()) {
1729
1730 LayoutNode node = vertexToLayoutNode.get(v);
1731 assert node != null;
1732
1733 for (LayoutEdge e : node.succs) {
1734 assert e.from == node;
1735 }
1736
1737 for (LayoutEdge e : node.preds) {
1738 assert e.to == node;
1739 }
1740
1741 }
1742 }
1743 }
1744
1745 @Override
1746 public void doRouting(LayoutGraph graph) {
1747 // Do nothing for now
1748 }
1749 }