Mercurial > hg > truffle
view visualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java @ 5199:b968b71e22a4
Allow tracking nodes responsible for a non-empty liveIn in LinearScan
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Fri, 06 Apr 2012 14:41:10 +0200 |
parents | 015fb895586b |
children |
line wrap: on
line source
/* * Copyright (c) 2008, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ package com.sun.hotspot.igv.hierarchicallayout; import com.sun.hotspot.igv.layout.LayoutGraph; import com.sun.hotspot.igv.layout.LayoutManager; import com.sun.hotspot.igv.layout.Link; import com.sun.hotspot.igv.layout.Vertex; import java.awt.Dimension; import java.awt.Point; import java.util.*; /** * * @author Thomas Wuerthinger */ public class HierarchicalLayoutManager implements LayoutManager { public static final boolean TRACE = false; public static final boolean CHECK = false; public static final int SWEEP_ITERATIONS = 1; public static final int CROSSING_ITERATIONS = 2; public static final int DUMMY_HEIGHT = 1; public static final int DUMMY_WIDTH = 1; public static final int X_OFFSET = 9; public static final int LAYER_OFFSET = 30; public static final int MAX_LAYER_LENGTH = -1; public static final int MIN_LAYER_DIFFERENCE = 1; public static final int VIP_BONUS = 10; public enum Combine { NONE, SAME_INPUTS, SAME_OUTPUTS } // Options private Combine combine; private int dummyWidth; private int dummyHeight; private int xOffset; private int layerOffset; private int maxLayerLength; private int minLayerDifference; // Algorithm global datastructures private Set<Link> reversedLinks; private List<LayoutNode> nodes; private HashMap<Vertex, LayoutNode> vertexToLayoutNode; private HashMap<Link, List<Point>> reversedLinkStartPoints; private HashMap<Link, List<Point>> reversedLinkEndPoints; private HashMap<LayoutEdge, LayoutEdge> bottomEdgeHash; private HashMap<Link, List<Point>> splitStartPoints; private HashMap<Link, List<Point>> splitEndPoints; private LayoutGraph graph; private List<LayoutNode>[] layers; private int layerCount; private Set<? extends Vertex> firstLayerHint; private Set<? extends Vertex> lastLayerHint; private Set<? extends Link> importantLinks; private Set<Link> linksToFollow; private class LayoutNode { public int x; public int y; public int width; public int height; public int layer = -1; public int xOffset; public int yOffset; public int bottomYOffset; public Vertex vertex; // Only used for non-dummy nodes, otherwise null public List<LayoutEdge> preds = new ArrayList<>(); public List<LayoutEdge> succs = new ArrayList<>(); public HashMap<Integer, Integer> outOffsets = new HashMap<>(); public HashMap<Integer, Integer> inOffsets = new HashMap<>(); public int pos = -1; // Position within layer public int crossingNumber; @Override public String toString() { return "Node " + vertex; } } private class LayoutEdge { public LayoutNode from; public LayoutNode to; public int relativeFrom; public int relativeTo; public Link link; public boolean vip; } private abstract class AlgorithmPart { public void start() { if (CHECK) { preCheck(); } long start = 0; if (TRACE) { System.out.println("##################################################"); System.out.println("Starting part " + this.getClass().getName()); start = System.currentTimeMillis(); } run(); if (TRACE) { System.out.println("Timing for " + this.getClass().getName() + " is " + (System.currentTimeMillis() - start)); printStatistics(); } if (CHECK) { postCheck(); } } protected abstract void run(); protected void printStatistics() { } protected void postCheck() { } protected void preCheck() { } } public HierarchicalLayoutManager() { this(Combine.NONE); } public HierarchicalLayoutManager(Combine b) { this.combine = b; this.dummyWidth = DUMMY_WIDTH; this.dummyHeight = DUMMY_HEIGHT; this.xOffset = X_OFFSET; this.layerOffset = LAYER_OFFSET; this.maxLayerLength = MAX_LAYER_LENGTH; this.minLayerDifference = MIN_LAYER_DIFFERENCE; this.linksToFollow = new HashSet<>(); } public int getMaxLayerLength() { return maxLayerLength; } public void setMaxLayerLength(int v) { maxLayerLength = v; } public void setMinLayerDifference(int v) { minLayerDifference = v; } @Override public void doLayout(LayoutGraph graph) { doLayout(graph, new HashSet<Vertex>(), new HashSet<Vertex>(), new HashSet<Link>()); } @Override public void doLayout(LayoutGraph graph, Set<? extends Vertex> firstLayerHint, Set<? extends Vertex> lastLayerHint, Set<? extends Link> importantLinks) { this.importantLinks = importantLinks; this.graph = graph; this.firstLayerHint = firstLayerHint; this.lastLayerHint = lastLayerHint; vertexToLayoutNode = new HashMap<>(); reversedLinks = new HashSet<>(); reversedLinkStartPoints = new HashMap<>(); reversedLinkEndPoints = new HashMap<>(); bottomEdgeHash = new HashMap<>(); nodes = new ArrayList<>(); splitStartPoints = new HashMap<>(); splitEndPoints = new HashMap<>(); // ############################################################# // Step 1: Build up data structure new BuildDatastructure().start(); // ############################################################# // STEP 2: Reverse edges, handle backedges new ReverseEdges().start(); for (LayoutNode n : nodes) { ArrayList<LayoutEdge> tmpArr = new ArrayList<>(); for (LayoutEdge e : n.succs) { if (importantLinks.contains(e.link)) { tmpArr.add(e); } } for (LayoutEdge e : tmpArr) { //System.out.println("Removed " + e); e.from.succs.remove(e); e.to.preds.remove(e); } } // ############################################################# // STEP 3: Assign layers new AssignLayers().start(); // ############################################################# // STEP 4: Create dummy nodes new CreateDummyNodes().start(); // ############################################################# // STEP 5: Crossing Reduction new CrossingReduction().start(); // ############################################################# // STEP 7: Assign X coordinates new AssignXCoordinates().start(); // ############################################################# // STEP 6: Assign Y coordinates new AssignYCoordinates().start(); // ############################################################# // STEP 8: Write back to interface new WriteResult().start(); } private class WriteResult extends AlgorithmPart { private int pointCount; @Override protected void run() { HashMap<Vertex, Point> vertexPositions = new HashMap<>(); HashMap<Link, List<Point>> linkPositions = new HashMap<>(); for (Vertex v : graph.getVertices()) { LayoutNode n = vertexToLayoutNode.get(v); assert !vertexPositions.containsKey(v); vertexPositions.put(v, new Point(n.x + n.xOffset, n.y + n.yOffset)); } for (LayoutNode n : nodes) { for (LayoutEdge e : n.preds) { if (e.link != null) { ArrayList<Point> points = new ArrayList<>(); Point p = new Point(e.to.x + e.relativeTo, e.to.y + e.to.yOffset + e.link.getTo().getRelativePosition().y); points.add(p); if (e.to.inOffsets.containsKey(e.relativeTo)) { points.add(new Point(p.x, p.y + e.to.inOffsets.get(e.relativeTo) + e.link.getTo().getRelativePosition().y)); } LayoutNode cur = e.from; LayoutNode other = e.to; LayoutEdge curEdge = e; while (cur.vertex == null && cur.preds.size() != 0) { 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) { points.remove(points.size() - 1); } points.add(new Point(cur.x + cur.width / 2, cur.y + cur.height)); 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) { points.remove(points.size() - 1); } points.add(new Point(cur.x + cur.width / 2, cur.y)); assert cur.preds.size() == 1; curEdge = cur.preds.get(0); cur = curEdge.from; } p = new Point(cur.x + curEdge.relativeFrom, cur.y + cur.height - cur.bottomYOffset + (curEdge.link == null ? 0 : curEdge.link.getFrom().getRelativePosition().y)); if (curEdge.from.outOffsets.containsKey(curEdge.relativeFrom)) { points.add(new Point(p.x, p.y + curEdge.from.outOffsets.get(curEdge.relativeFrom) + (curEdge.link == null ? 0 : curEdge.link.getFrom().getRelativePosition().y))); } points.add(p); Collections.reverse(points); if (cur.vertex == null && cur.preds.size() == 0) { if (reversedLinkEndPoints.containsKey(e.link)) { for (Point p1 : reversedLinkEndPoints.get(e.link)) { points.add(new Point(p1.x + e.to.x, p1.y + e.to.y)); } } if (splitStartPoints.containsKey(e.link)) { points.add(0, null); points.addAll(0, splitStartPoints.get(e.link)); //checkPoints(points); if (reversedLinks.contains(e.link)) { Collections.reverse(points); } assert !linkPositions.containsKey(e.link); linkPositions.put(e.link, points); } else { splitEndPoints.put(e.link, points); } } else { if (reversedLinks.contains(e.link)) { Collections.reverse(points); } if (reversedLinkStartPoints.containsKey(e.link)) { for (Point p1 : reversedLinkStartPoints.get(e.link)) { points.add(new Point(p1.x + cur.x, p1.y + cur.y)); } } if (reversedLinkEndPoints.containsKey(e.link)) { for (Point p1 : reversedLinkEndPoints.get(e.link)) { points.add(0, new Point(p1.x + other.x, p1.y + other.y)); } } assert !linkPositions.containsKey(e.link); linkPositions.put(e.link, points); } pointCount += points.size(); // No longer needed! e.link = null; } } for (LayoutEdge e : n.succs) { if (e.link != null) { ArrayList<Point> points = new ArrayList<>(); Point p = new Point(e.from.x + e.relativeFrom, e.from.y + e.from.height - e.from.bottomYOffset + e.link.getFrom().getRelativePosition().y); points.add(p); if (e.from.outOffsets.containsKey(e.relativeFrom)) { points.add(new Point(p.x, p.y + e.from.outOffsets.get(e.relativeFrom) + e.link.getFrom().getRelativePosition().y)); } LayoutNode cur = e.to; LayoutNode other = e.from; LayoutEdge curEdge = e; while (cur.vertex == null && cur.succs.size() != 0) { 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) { points.remove(points.size() - 1); } points.add(new Point(cur.x + cur.width / 2, cur.y)); 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) { points.remove(points.size() - 1); } points.add(new Point(cur.x + cur.width / 2, cur.y + cur.height)); if (cur.succs.size() == 0) { break; } assert cur.succs.size() == 1; curEdge = cur.succs.get(0); cur = curEdge.to; } p = new Point(cur.x + curEdge.relativeTo, cur.y + cur.yOffset + ((curEdge.link == null) ? 0 : curEdge.link.getTo().getRelativePosition().y)); points.add(p); if (curEdge.to.inOffsets.containsKey(curEdge.relativeTo)) { points.add(new Point(p.x, p.y + curEdge.to.inOffsets.get(curEdge.relativeTo) + ((curEdge.link == null) ? 0 : curEdge.link.getTo().getRelativePosition().y))); } if (cur.succs.size() == 0 && cur.vertex == null) { if (reversedLinkStartPoints.containsKey(e.link)) { for (Point p1 : reversedLinkStartPoints.get(e.link)) { points.add(0, new Point(p1.x + other.x, p1.y + other.y)); } } if (splitEndPoints.containsKey(e.link)) { points.add(null); points.addAll(splitEndPoints.get(e.link)); //checkPoints(points); if (reversedLinks.contains(e.link)) { Collections.reverse(points); } assert !linkPositions.containsKey(e.link); linkPositions.put(e.link, points); } else { splitStartPoints.put(e.link, points); } } else { if (reversedLinkStartPoints.containsKey(e.link)) { for (Point p1 : reversedLinkStartPoints.get(e.link)) { points.add(0, new Point(p1.x + other.x, p1.y + other.y)); } } if (reversedLinkEndPoints.containsKey(e.link)) { for (Point p1 : reversedLinkEndPoints.get(e.link)) { points.add(new Point(p1.x + cur.x, p1.y + cur.y)); } } if (reversedLinks.contains(e.link)) { Collections.reverse(points); } //checkPoints(points); assert !linkPositions.containsKey(e.link); linkPositions.put(e.link, points); } pointCount += points.size(); e.link = null; } } } int minX = Integer.MAX_VALUE; int minY = Integer.MAX_VALUE; for (Vertex v : vertexPositions.keySet()) { Point p = vertexPositions.get(v); minX = Math.min(minX, p.x); minY = Math.min(minY, p.y); } for (Link l : linkPositions.keySet()) { List<Point> points = linkPositions.get(l); for (Point p : points) { if (p != null) { minX = Math.min(minX, p.x); minY = Math.min(minY, p.y); } } } for (Vertex v : vertexPositions.keySet()) { Point p = vertexPositions.get(v); p.x -= minX; p.y -= minY; v.setPosition(p); } for (Link l : linkPositions.keySet()) { List<Point> points = linkPositions.get(l); for (Point p : points) { if (p != null) { p.x -= minX; p.y -= minY; } } l.setControlPoints(points); } } @Override protected void printStatistics() { System.out.println("Number of nodes: " + nodes.size()); int edgeCount = 0; for (LayoutNode n : nodes) { edgeCount += n.succs.size(); } System.out.println("Number of edges: " + edgeCount); System.out.println("Number of points: " + pointCount); } } private static class Segment { public float d; public int orderNumber = -1; public ArrayList<LayoutNode> nodes = new ArrayList<>(); public HashSet<Segment> succs = new HashSet<>(); public HashSet<Segment> preds = new HashSet<>(); public Region region; } private static final Comparator<Segment> segmentComparator = new Comparator<Segment>() { @Override public int compare(Segment s1, Segment s2) { return s1.orderNumber - s2.orderNumber; } }; private static class Region { public float d; public int minOrderNumber; public SortedSet<Segment> segments = new TreeSet<>(segmentComparator); public HashSet<Region> succs = new HashSet<>(4); public HashSet<Region> preds = new HashSet<>(4); } private static final Comparator<Region> regionComparator = new Comparator<Region>() { @Override public int compare(Region r1, Region r2) { return r1.minOrderNumber - r2.minOrderNumber; } }; private static final Comparator<LayoutNode> nodePositionComparator = new Comparator<LayoutNode>() { @Override public int compare(LayoutNode n1, LayoutNode n2) { return n1.pos - n2.pos; } }; private static final Comparator<LayoutNode> nodeProcessingDownComparator = new Comparator<LayoutNode>() { @Override public int compare(LayoutNode n1, LayoutNode n2) { if (n1.vertex == null) { if (n2.vertex == null) { return 0; } return -1; } if (n2.vertex == null) { return 1; } return n1.preds.size() - n2.preds.size(); } }; private static final Comparator<LayoutNode> nodeProcessingUpComparator = new Comparator<LayoutNode>() { @Override public int compare(LayoutNode n1, LayoutNode n2) { if (n1.vertex == null) { if (n2.vertex == null) { return 0; } return -1; } if (n2.vertex == null) { return 1; } return n1.succs.size() - n2.succs.size(); } }; private class AssignXCoordinates extends AlgorithmPart { private ArrayList<Integer>[] space; private ArrayList<LayoutNode>[] downProcessingOrder; private ArrayList<LayoutNode>[] upProcessingOrder; private void initialPositions() { for (LayoutNode n : nodes) { n.x = space[n.layer].get(n.pos); } } @SuppressWarnings("unchecked") private void createArrays() { space = new ArrayList[layers.length]; downProcessingOrder = new ArrayList[layers.length]; upProcessingOrder = new ArrayList[layers.length]; } @Override protected void run() { createArrays(); for (int i = 0; i < layers.length; i++) { space[i] = new ArrayList<>(); downProcessingOrder[i] = new ArrayList<>(); upProcessingOrder[i] = new ArrayList<>(); int curX = 0; for (LayoutNode n : layers[i]) { space[i].add(curX); curX += n.width + xOffset; downProcessingOrder[i].add(n); upProcessingOrder[i].add(n); } Collections.sort(downProcessingOrder[i], nodeProcessingDownComparator); Collections.sort(upProcessingOrder[i], nodeProcessingUpComparator); } initialPositions(); for (int i = 0; i < SWEEP_ITERATIONS; i++) { sweepDown(); sweepUp(); } sweepDown(); //for (int i = 0; i < SWEEP_ITERATIONS; i++) { // doubleSweep(); //} } private int calculateOptimalDown(LayoutNode n) { int size = n.preds.size(); if (size == 0) { return n.x; } int[] values = new int[size]; for (int i = 0; i < size; i++) { LayoutEdge e = n.preds.get(i); values[i] = e.from.x + e.relativeFrom - e.relativeTo; if (e.vip) { return values[i]; } } return median(values); } private int calculateOptimalBoth(LayoutNode n) { if (n.preds.size() == n.succs.size()) { return n.x; } int[] values = new int[n.preds.size() + n.succs.size()]; int i = 0; for (LayoutEdge e : n.preds) { values[i] = e.from.x + e.relativeFrom - e.relativeTo; i++; } for (LayoutEdge e : n.succs) { values[i] = e.to.x + e.relativeTo - e.relativeFrom; i++; } return median(values); } private int calculateOptimalUp(LayoutNode n) { int size = n.succs.size(); if (size == 0) { return n.x; } int[] values = new int[size]; for (int i = 0; i < size; i++) { LayoutEdge e = n.succs.get(i); values[i] = e.to.x + e.relativeTo - e.relativeFrom; if (e.vip) { return values[i]; } } return median(values); } private int median(int[] values) { Arrays.sort(values); if (values.length % 2 == 0) { return (values[values.length / 2 - 1] + values[values.length / 2]) / 2; } else { return values[values.length / 2]; } } private void sweepUp() { for (int i = layers.length - 1; i >= 0; i--) { NodeRow r = new NodeRow(space[i]); for (LayoutNode n : upProcessingOrder[i]) { int optimal = calculateOptimalUp(n); r.insert(n, optimal); } } } private void doubleSweep() { for (int i = layers.length - 2; i >= 0; i--) { NodeRow r = new NodeRow(space[i]); for (LayoutNode n : upProcessingOrder[i]) { int optimal = calculateOptimalBoth(n); r.insert(n, optimal); } } } private void sweepDown() { for (int i = 1; i < layers.length; i++) { NodeRow r = new NodeRow(space[i]); for (LayoutNode n : downProcessingOrder[i]) { int optimal = calculateOptimalDown(n); r.insert(n, optimal); } } } } private static class NodeRow { private TreeSet<LayoutNode> treeSet; private ArrayList<Integer> space; public NodeRow(ArrayList<Integer> space) { treeSet = new TreeSet<>(nodePositionComparator); this.space = space; } public int offset(LayoutNode n1, LayoutNode n2) { int v1 = space.get(n1.pos) + n1.width; int v2 = space.get(n2.pos); return v2 - v1; } public void insert(LayoutNode n, int pos) { SortedSet<LayoutNode> headSet = treeSet.headSet(n); LayoutNode leftNeighbor = null; int minX = Integer.MIN_VALUE; if (!headSet.isEmpty()) { leftNeighbor = headSet.last(); minX = leftNeighbor.x + leftNeighbor.width + offset(leftNeighbor, n); } if (pos < minX) { n.x = minX; } else { LayoutNode rightNeighbor = null; SortedSet<LayoutNode> tailSet = treeSet.tailSet(n); int maxX = Integer.MAX_VALUE; if (!tailSet.isEmpty()) { rightNeighbor = tailSet.first(); maxX = rightNeighbor.x - offset(n, rightNeighbor) - n.width; } if (pos > maxX) { n.x = maxX; } else { n.x = pos; } assert minX <= maxX; } treeSet.add(n); } } private static Comparator<LayoutNode> crossingNodeComparator = new Comparator<LayoutNode>() { @Override public int compare(LayoutNode n1, LayoutNode n2) { return n1.crossingNumber - n2.crossingNumber; } }; private class CrossingReduction extends AlgorithmPart { @Override public void preCheck() { for (LayoutNode n : nodes) { assert n.layer < layerCount; } } @SuppressWarnings("unchecked") private void createLayers() { layers = new List[layerCount]; for (int i = 0; i < layerCount; i++) { layers[i] = new ArrayList<>(); } } @Override protected void run() { createLayers(); // Generate initial ordering HashSet<LayoutNode> visited = new HashSet<>(); for (LayoutNode n : nodes) { if (n.layer == 0) { layers[0].add(n); visited.add(n); } else if (n.preds.size() == 0) { layers[n.layer].add(n); visited.add(n); } } for (int i = 0; i < layers.length - 1; i++) { for (LayoutNode n : layers[i]) { for (LayoutEdge e : n.succs) { if (!visited.contains(e.to)) { visited.add(e.to); layers[i + 1].add(e.to); } } } } updatePositions(); initX(); // Optimize for (int i = 0; i < CROSSING_ITERATIONS; i++) { downSweep(); upSweep(); } if (reversedLinks.isEmpty()) { // This graph seems to be a tree or forest. // A final down-sweep will usually give us a better layout. downSweep(); } } private void initX() { for (int i = 0; i < layers.length; i++) { updateXOfLayer(i); } } private void updateXOfLayer(int index) { int x = 0; for (LayoutNode n : layers[index]) { n.x = x; x += n.width + X_OFFSET; } } private void updatePositions() { for (int i = 0; i < layers.length; i++) { int z = 0; for (LayoutNode n : layers[i]) { n.pos = z; z++; } } } private void downSweep() { // Downsweep for (int i = 1; i < layerCount; i++) { for (LayoutNode n : layers[i]) { n.crossingNumber = 0; } for (LayoutNode n : layers[i]) { int sum = 0; int count = 0; for (LayoutEdge e : n.preds) { int cur = e.from.x + e.relativeFrom; int factor = 1; if (e.vip) { factor = VIP_BONUS; } sum += cur*factor; count+=factor; } if (count > 0) { sum /= count; n.crossingNumber = sum; } } updateCrossingNumbers(i, true); Collections.sort(layers[i], crossingNodeComparator); updateXOfLayer(i); int z = 0; for (LayoutNode n : layers[i]) { n.pos = z; z++; } } } private void updateCrossingNumbers(int index, boolean down) { for (int i = 0; i < layers[index].size(); i++) { LayoutNode n = layers[index].get(i); LayoutNode prev = null; if (i > 0) { prev = layers[index].get(i - 1); } LayoutNode next = null; if (i < layers[index].size() - 1) { next = layers[index].get(i + 1); } boolean cond = n.succs.isEmpty(); if (down) { cond = n.preds.isEmpty(); } if (cond) { if (prev != null && next != null) { n.crossingNumber = (prev.crossingNumber + next.crossingNumber) / 2; } else if (prev != null) { n.crossingNumber = prev.crossingNumber; } else if (next != null) { n.crossingNumber = next.crossingNumber; } } } } private void upSweep() { // Upsweep for (int i = layerCount - 2; i >= 0; i--) { for (LayoutNode n : layers[i]) { n.crossingNumber = 0; } for (LayoutNode n : layers[i]) { int count = 0; int sum = 0; for (LayoutEdge e : n.succs) { int cur = e.to.x + e.relativeTo; int factor = 1; if (e.vip) { factor = VIP_BONUS; } sum += cur*factor; count+=factor; } if (count > 0) { sum /= count; n.crossingNumber = sum; } } updateCrossingNumbers(i, false); Collections.sort(layers[i], crossingNodeComparator); updateXOfLayer(i); int z = 0; for (LayoutNode n : layers[i]) { n.pos = z; z++; } } } @Override public void postCheck() { HashSet<LayoutNode> visited = new HashSet<>(); for (int i = 0; i < layers.length; i++) { for (LayoutNode n : layers[i]) { assert !visited.contains(n); assert n.layer == i; visited.add(n); } } } } private class AssignYCoordinates extends AlgorithmPart { @Override protected void run() { int curY = 0; for (int i = 0; i < layers.length; i++) { int maxHeight = 0; int baseLine = 0; int bottomBaseLine = 0; for (LayoutNode n : layers[i]) { maxHeight = Math.max(maxHeight, n.height - n.yOffset - n.bottomYOffset); baseLine = Math.max(baseLine, n.yOffset); bottomBaseLine = Math.max(bottomBaseLine, n.bottomYOffset); } int maxXOffset = 0; for (LayoutNode n : layers[i]) { if (n.vertex == null) { // Dummy node n.y = curY; n.height = maxHeight + baseLine + bottomBaseLine; } else { n.y = curY + baseLine + (maxHeight - (n.height - n.yOffset - n.bottomYOffset)) / 2 - n.yOffset; } for (LayoutEdge e : n.succs) { int curXOffset = Math.abs(n.x - e.to.x); maxXOffset = Math.max(curXOffset, maxXOffset); } } curY += maxHeight + baseLine + bottomBaseLine; curY += layerOffset + (int) Math.sqrt(maxXOffset); } } } private class CreateDummyNodes extends AlgorithmPart { private int oldNodeCount; @Override protected void preCheck() { for (LayoutNode n : nodes) { for (LayoutEdge e : n.succs) { assert e.from != null; assert e.from == n; assert e.from.layer < e.to.layer; } for (LayoutEdge e : n.preds) { assert e.to != null; assert e.to == n; } } } @Override protected void run() { oldNodeCount = nodes.size(); if (combine == Combine.SAME_OUTPUTS) { Comparator<LayoutEdge> comparator = new Comparator<LayoutEdge>() { @Override public int compare(LayoutEdge e1, LayoutEdge e2) { return e1.to.layer - e2.to.layer; } }; HashMap<Integer, List<LayoutEdge>> portHash = new HashMap<>(); ArrayList<LayoutNode> currentNodes = new ArrayList<>(nodes); for (LayoutNode n : currentNodes) { portHash.clear(); ArrayList<LayoutEdge> succs = new ArrayList<>(n.succs); HashMap<Integer, LayoutNode> topNodeHash = new HashMap<>(); HashMap<Integer, HashMap<Integer, LayoutNode>> bottomNodeHash = new HashMap<>(); for (LayoutEdge e : succs) { assert e.from.layer < e.to.layer; if (e.from.layer != e.to.layer - 1) { if (maxLayerLength != -1 && e.to.layer - e.from.layer > maxLayerLength/* && e.to.preds.size() > 1 && e.from.succs.size() > 1*/) { assert maxLayerLength > 2; e.to.preds.remove(e); e.from.succs.remove(e); LayoutEdge topEdge = null; if (combine == Combine.SAME_OUTPUTS && topNodeHash.containsKey(e.relativeFrom)) { LayoutNode topNode = topNodeHash.get(e.relativeFrom); topEdge = new LayoutEdge(); topEdge.relativeFrom = e.relativeFrom; topEdge.from = e.from; topEdge.relativeTo = topNode.width / 2; topEdge.to = topNode; topEdge.link = e.link; topEdge.vip = e.vip; e.from.succs.add(topEdge); topNode.preds.add(topEdge); } else { LayoutNode topNode = new LayoutNode(); topNode.layer = e.from.layer + 1; topNode.width = DUMMY_WIDTH; topNode.height = DUMMY_HEIGHT; nodes.add(topNode); topEdge = new LayoutEdge(); topEdge.relativeFrom = e.relativeFrom; topEdge.from = e.from; topEdge.relativeTo = topNode.width / 2; topEdge.to = topNode; topEdge.link = e.link; topEdge.vip = e.vip; e.from.succs.add(topEdge); topNode.preds.add(topEdge); topNodeHash.put(e.relativeFrom, topNode); bottomNodeHash.put(e.relativeFrom, new HashMap<Integer, LayoutNode>()); } HashMap<Integer, LayoutNode> hash = bottomNodeHash.get(e.relativeFrom); LayoutNode bottomNode = null; if (hash.containsKey(e.to.layer)) { bottomNode = hash.get(e.to.layer); } else { bottomNode = new LayoutNode(); bottomNode.layer = e.to.layer - 1; bottomNode.width = DUMMY_WIDTH; bottomNode.height = DUMMY_HEIGHT; nodes.add(bottomNode); hash.put(e.to.layer, bottomNode); } LayoutEdge bottomEdge = new LayoutEdge(); bottomEdge.relativeTo = e.relativeTo; bottomEdge.to = e.to; bottomEdge.relativeFrom = bottomNode.width / 2; bottomEdge.from = bottomNode; bottomEdge.link = e.link; bottomEdge.vip = e.vip; e.to.preds.add(bottomEdge); bottomEdgeHash.put(topEdge, bottomEdge); bottomNode.succs.add(bottomEdge); } else { Integer i = e.relativeFrom; if (!portHash.containsKey(i)) { portHash.put(i, new ArrayList<LayoutEdge>()); } portHash.get(i).add(e); } } } succs = new ArrayList<>(n.succs); for (LayoutEdge e : succs) { Integer i = e.relativeFrom; if (portHash.containsKey(i)) { List<LayoutEdge> list = portHash.get(i); Collections.sort(list, comparator); if (list.size() == 1) { processSingleEdge(list.get(0)); } else { int maxLayer = list.get(0).to.layer; for (LayoutEdge curEdge : list) { maxLayer = Math.max(maxLayer, curEdge.to.layer); } int cnt = maxLayer - n.layer - 1; LayoutEdge[] edges = new LayoutEdge[cnt]; LayoutNode[] nodes = new LayoutNode[cnt]; edges[0] = new LayoutEdge(); edges[0].from = n; edges[0].relativeFrom = i; edges[0].vip = e.vip; n.succs.add(edges[0]); nodes[0] = new LayoutNode(); nodes[0].width = dummyWidth; nodes[0].height = dummyHeight; nodes[0].layer = n.layer + 1; nodes[0].preds.add(edges[0]); edges[0].to = nodes[0]; edges[0].relativeTo = nodes[0].width / 2; for (int j = 1; j < cnt; j++) { edges[j] = new LayoutEdge(); edges[j].vip = e.vip; edges[j].from = nodes[j - 1]; edges[j].relativeFrom = nodes[j - 1].width / 2; nodes[j - 1].succs.add(edges[j]); nodes[j] = new LayoutNode(); nodes[j].width = dummyWidth; nodes[j].height = dummyHeight; nodes[j].layer = n.layer + j + 1; nodes[j].preds.add(edges[j]); edges[j].to = nodes[j]; edges[j].relativeTo = nodes[j].width / 2; } for (LayoutEdge curEdge : list) { assert curEdge.to.layer - n.layer - 2 >= 0; assert curEdge.to.layer - n.layer - 2 < cnt; LayoutNode anchor = nodes[curEdge.to.layer - n.layer - 2]; anchor.succs.add(curEdge); curEdge.from = anchor; curEdge.relativeFrom = anchor.width / 2; n.succs.remove(curEdge); } } portHash.remove(i); } } } } else if (combine == Combine.SAME_INPUTS) { throw new UnsupportedOperationException("Currently not supported"); } else { ArrayList<LayoutNode> currentNodes = new ArrayList<>(nodes); for (LayoutNode n : currentNodes) { for (LayoutEdge e : n.succs) { processSingleEdge(e); } } } } private void processSingleEdge(LayoutEdge e) { LayoutNode n = e.from; if (e.to.layer > n.layer + 1) { LayoutEdge last = e; for (int i = n.layer + 1; i < last.to.layer; i++) { last = addBetween(last, i); } } } private LayoutEdge addBetween(LayoutEdge e, int layer) { LayoutNode n = new LayoutNode(); n.width = dummyWidth; n.height = dummyHeight; n.layer = layer; n.preds.add(e); nodes.add(n); LayoutEdge result = new LayoutEdge(); result.vip = e.vip; n.succs.add(result); result.from = n; result.relativeFrom = n.width / 2; result.to = e.to; result.relativeTo = e.relativeTo; e.relativeTo = n.width / 2; e.to.preds.remove(e); e.to.preds.add(result); e.to = n; return result; } @Override public void printStatistics() { System.out.println("Dummy nodes created: " + (nodes.size() - oldNodeCount)); } @Override public void postCheck() { ArrayList<LayoutNode> currentNodes = new ArrayList<>(nodes); for (LayoutNode n : currentNodes) { for (LayoutEdge e : n.succs) { assert e.from.layer == e.to.layer - 1; } } for (int i = 0; i < layers.length; i++) { assert layers[i].size() > 0; for (LayoutNode n : layers[i]) { assert n.layer == i; } } } } private class AssignLayers extends AlgorithmPart { @Override public void preCheck() { for (LayoutNode n : nodes) { assert n.layer == -1; } } @Override protected void run() { List<LayoutNode> insertOrder = new ArrayList<>(); HashSet<LayoutNode> set = new HashSet<>(); for (LayoutNode n : nodes) { if (n.preds.size() == 0) { set.add(n); insertOrder.add(n); n.layer = 0; } } int z = minLayerDifference; HashSet<LayoutNode> newSet = new HashSet<>(); HashSet<LayoutNode> failed = new HashSet<>(); while (!set.isEmpty()) { newSet.clear(); failed.clear(); for (LayoutNode n : set) { for (LayoutEdge se : n.succs) { LayoutNode s = se.to; if (!newSet.contains(s) && !failed.contains(s)) { boolean ok = true; for (LayoutEdge pe : s.preds) { LayoutNode p = pe.from; if (p.layer == -1) { ok = false; break; } } if (ok) { newSet.add(s); } else { failed.add(s); } } } } for (LayoutNode n : newSet) { n.layer = z; insertOrder.add(n); } // Swap sets HashSet<LayoutNode> tmp = set; set = newSet; newSet = tmp; z += minLayerDifference; } optimize(insertOrder); layerCount = z - minLayerDifference; for (Vertex v : lastLayerHint) { LayoutNode n = vertexToLayoutNode.get(v); assert n.succs.size() == 0; n.layer = layerCount - 1; } for (Vertex v : firstLayerHint) { LayoutNode n = vertexToLayoutNode.get(v); assert n.preds.size() == 0; n.layer = 0; assert n.layer == 0; } } public void optimize(List<LayoutNode> insertOrder) { for (int i = insertOrder.size() - 1; i >= 0; i--) { LayoutNode cur = insertOrder.get(i); if (cur.succs.size() > cur.preds.size()) { int minLayer = cur.succs.get(0).to.layer; for (LayoutEdge e : cur.succs) { minLayer = Math.min(minLayer, e.to.layer); } cur.layer = minLayer - 1; } } } @Override public void postCheck() { for (LayoutNode n : nodes) { assert n.layer >= 0; assert n.layer < layerCount; for (LayoutEdge e : n.succs) { assert e.from.layer < e.to.layer; } } } } private class ReverseEdges extends AlgorithmPart { private HashSet<LayoutNode> visited; private HashSet<LayoutNode> active; @Override protected void run() { // Remove self-edges for (LayoutNode node : nodes) { ArrayList<LayoutEdge> succs = new ArrayList<>(node.succs); for (LayoutEdge e : succs) { assert e.from == node; if (e.to == node) { node.succs.remove(e); node.preds.remove(e); } } } // Reverse inputs of roots for (LayoutNode node : nodes) { if (node.vertex.isRoot()) { boolean ok = true; for (LayoutEdge e : node.preds) { if (e.from.vertex.isRoot()) { ok = false; break; } } if (ok) { reverseAllInputs(node); } } } // Start DFS and reverse back edges visited = new HashSet<>(); active = new HashSet<>(); for (LayoutNode node : nodes) { DFS(node); } for (LayoutNode node : nodes) { SortedSet<Integer> reversedDown = new TreeSet<>(); for (LayoutEdge e : node.succs) { if (reversedLinks.contains(e.link)) { reversedDown.add(e.relativeFrom); } } SortedSet<Integer> reversedUp = null; if (reversedDown.size() == 0) { reversedUp = new TreeSet<>(Collections.reverseOrder()); } else { reversedUp = new TreeSet<>(); } for (LayoutEdge e : node.preds) { if (reversedLinks.contains(e.link)) { reversedUp.add(e.relativeTo); } } final int offset = X_OFFSET + DUMMY_WIDTH; int curX = 0; int curWidth = node.width + reversedDown.size() * offset; for (int pos : reversedDown) { ArrayList<LayoutEdge> reversedSuccs = new ArrayList<>(); for (LayoutEdge e : node.succs) { if (e.relativeFrom == pos && reversedLinks.contains(e.link)) { reversedSuccs.add(e); e.relativeFrom = curWidth; } } ArrayList<Point> startPoints = new ArrayList<>(); startPoints.add(new Point(curWidth, curX)); startPoints.add(new Point(pos, curX)); startPoints.add(new Point(pos, reversedDown.size() * offset)); for (LayoutEdge e : reversedSuccs) { reversedLinkStartPoints.put(e.link, startPoints); } node.inOffsets.put(pos, -curX); curX += offset; node.height += offset; node.yOffset += offset; curWidth -= offset; } node.width += reversedDown.size() * offset; if (reversedDown.size() == 0) { curX = offset; } else { curX = -offset; } curX = 0; int minX = 0; if (reversedDown.size() != 0) { minX = -offset * reversedUp.size(); } int oldNodeHeight = node.height; for (int pos : reversedUp) { ArrayList<LayoutEdge> reversedPreds = new ArrayList<>(); for (LayoutEdge e : node.preds) { if (e.relativeTo == pos && reversedLinks.contains(e.link)) { if (reversedDown.size() == 0) { e.relativeTo = node.width + offset; } else { e.relativeTo = curX - offset; } reversedPreds.add(e); } } node.height += offset; ArrayList<Point> endPoints = new ArrayList<>(); if (reversedDown.size() == 0) { curX += offset; node.width += offset; endPoints.add(new Point(node.width, node.height)); } else { curX -= offset; node.width += offset; endPoints.add(new Point(curX, node.height)); } node.outOffsets.put(pos - minX, curX); curX += offset; node.bottomYOffset += offset; endPoints.add(new Point(pos, node.height)); endPoints.add(new Point(pos, oldNodeHeight)); for (LayoutEdge e : reversedPreds) { reversedLinkEndPoints.put(e.link, endPoints); } } if (minX < 0) { for (LayoutEdge e : node.preds) { e.relativeTo -= minX; } for (LayoutEdge e : node.succs) { e.relativeFrom -= minX; } node.xOffset = -minX; node.width += -minX; } } } private void DFS(LayoutNode startNode) { if (visited.contains(startNode)) { return; } Stack<LayoutNode> stack = new Stack<>(); stack.push(startNode); while (!stack.empty()) { LayoutNode node = stack.pop(); if (visited.contains(node)) { // Node no longer active active.remove(node); continue; } // Repush immediately to know when no longer active stack.push(node); visited.add(node); active.add(node); ArrayList<LayoutEdge> succs = new ArrayList<>(node.succs); for (LayoutEdge e : succs) { if (active.contains(e.to)) { assert visited.contains(e.to); // Encountered back edge reverseEdge(e); } else if (!visited.contains(e.to) && (linksToFollow.size() == 0 || linksToFollow.contains(e.link))) { stack.push(e.to); } } } } private void reverseAllInputs(LayoutNode node) { for (LayoutEdge e : node.preds) { assert !reversedLinks.contains(e.link); reversedLinks.add(e.link); node.succs.add(e); e.from.preds.add(e); e.from.succs.remove(e); int oldRelativeFrom = e.relativeFrom; int oldRelativeTo = e.relativeTo; e.to = e.from; e.from = node; e.relativeFrom = oldRelativeTo; e.relativeTo = oldRelativeFrom; } node.preds.clear(); } private void reverseEdge(LayoutEdge e) { assert !reversedLinks.contains(e.link); reversedLinks.add(e.link); LayoutNode oldFrom = e.from; LayoutNode oldTo = e.to; int oldRelativeFrom = e.relativeFrom; int oldRelativeTo = e.relativeTo; e.from = oldTo; e.to = oldFrom; e.relativeFrom = oldRelativeTo; e.relativeTo = oldRelativeFrom; oldFrom.succs.remove(e); oldFrom.preds.add(e); oldTo.preds.remove(e); oldTo.succs.add(e); } @Override public void postCheck() { for (LayoutNode n : nodes) { HashSet<LayoutNode> curVisited = new HashSet<>(); Queue<LayoutNode> queue = new LinkedList<>(); for (LayoutEdge e : n.succs) { LayoutNode s = e.to; queue.add(s); curVisited.add(s); } while (!queue.isEmpty()) { LayoutNode curNode = queue.remove(); for (LayoutEdge e : curNode.succs) { assert e.to != n; if (!curVisited.contains(e.to)) { queue.add(e.to); curVisited.add(e.to); } } } } } } private Comparator<Link> linkComparator = new Comparator<Link>() { @Override public int compare(Link l1, Link l2) { int result = l1.getFrom().getVertex().compareTo(l2.getFrom().getVertex()); if (result != 0) { return result; } result = l1.getTo().getVertex().compareTo(l2.getTo().getVertex()); if (result != 0) { return result; } result = l1.getFrom().getRelativePosition().x - l2.getFrom().getRelativePosition().x; if (result != 0) { return result; } result = l1.getTo().getRelativePosition().x - l2.getTo().getRelativePosition().x; return result; } }; private class BuildDatastructure extends AlgorithmPart { @Override protected void run() { // Set up nodes List<Vertex> vertices = new ArrayList<>(graph.getVertices()); Collections.sort(vertices); for (Vertex v : vertices) { LayoutNode node = new LayoutNode(); Dimension size = v.getSize(); node.width = (int) size.getWidth(); node.height = (int) size.getHeight(); node.vertex = v; nodes.add(node); vertexToLayoutNode.put(v, node); } // Set up edges List<Link> links = new ArrayList<>(graph.getLinks()); Collections.sort(links, linkComparator); for (Link l : links) { LayoutEdge edge = new LayoutEdge(); assert vertexToLayoutNode.containsKey(l.getFrom().getVertex()); assert vertexToLayoutNode.containsKey(l.getTo().getVertex()); edge.from = vertexToLayoutNode.get(l.getFrom().getVertex()); edge.to = vertexToLayoutNode.get(l.getTo().getVertex()); edge.relativeFrom = l.getFrom().getRelativePosition().x; edge.relativeTo = l.getTo().getRelativePosition().x; edge.link = l; edge.from.succs.add(edge); edge.to.preds.add(edge); edge.vip = l.isVIP(); //assert edge.from != edge.to; // No self-loops allowed } for (Link l : importantLinks) { if (!vertexToLayoutNode.containsKey(l.getFrom().getVertex()) || vertexToLayoutNode.containsKey(l.getTo().getVertex())) { continue; } LayoutNode from = vertexToLayoutNode.get(l.getFrom().getVertex()); LayoutNode to = vertexToLayoutNode.get(l.getTo().getVertex()); for (LayoutEdge e : from.succs) { if (e.to == to) { linksToFollow.add(e.link); } } } } @Override public void postCheck() { assert vertexToLayoutNode.keySet().size() == nodes.size(); assert nodes.size() == graph.getVertices().size(); for (Vertex v : graph.getVertices()) { LayoutNode node = vertexToLayoutNode.get(v); assert node != null; for (LayoutEdge e : node.succs) { assert e.from == node; } for (LayoutEdge e : node.preds) { assert e.to == node; } } } } @Override public void doRouting(LayoutGraph graph) { // Do nothing for now } }