| /* |
| * 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 java.awt.Point; |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.HashMap; |
| import java.util.HashSet; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Set; |
| 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.Port; |
| import com.sun.hotspot.igv.layout.Vertex; |
| |
| /** |
| * |
| * @author Thomas Wuerthinger |
| */ |
| public class OldHierarchicalLayoutManager implements LayoutManager { |
| |
| public static final int DUMMY_WIDTH = 0; |
| public static final int DUMMY_HEIGHT = 0; |
| public static final int LAYER_OFFSET = 50; |
| public static final int OFFSET = 8; |
| public static final boolean VERTICAL_LAYOUT = true; |
| public static final boolean ASSERT = false; |
| public static final boolean TRACE = false; |
| public static final Timing initTiming = new Timing("init"); |
| public static final Timing removeCyclesTiming = new Timing("removeCycles"); |
| public static final Timing reversedEdgesTiming = new Timing("reversedEdges"); |
| public static final Timing assignLayersTiming = new Timing("assignLayers"); |
| public static final Timing dummyNodesTiming = new Timing("dummyNodes"); |
| public static final Timing crossingReductionTiming = new Timing("crossingReduction"); |
| public static final Timing assignCoordinatesTiming = new Timing("assignCoordinates"); |
| public static final Timing assignRealTiming = new Timing("assignReal"); |
| public static final Timing rootVertexTiming = new Timing("rootVertex"); |
| public static final Timing createEdgesTiming = new Timing("createEdges"); |
| public static final Timing optimizeMedianTiming = new Timing("optimizeMedian"); |
| private Combine combine; |
| |
| public enum Combine { |
| |
| NONE, |
| SAME_INPUTS, |
| SAME_OUTPUTS |
| } |
| |
| private class NodeData { |
| |
| private Map<Port, Integer> reversePositions; |
| private Vertex node; |
| private Link edge; |
| private int layer; |
| private int x; |
| private int y; |
| private int width; |
| |
| public NodeData(Vertex node) { |
| reversePositions = new HashMap<Port, Integer>(); |
| layer = -1; |
| this.node = node; |
| assert node != null; |
| |
| if (VERTICAL_LAYOUT) { |
| width = node.getSize().width; |
| } else { |
| width = node.getSize().height; |
| } |
| } |
| |
| public NodeData(Link edge) { |
| layer = -1; |
| this.edge = edge; |
| assert edge != null; |
| |
| if (VERTICAL_LAYOUT) { |
| width = DUMMY_WIDTH; |
| } else { |
| width = DUMMY_HEIGHT; |
| } |
| } |
| |
| public Vertex getNode() { |
| return node; |
| } |
| |
| public Link getEdge() { |
| return edge; |
| } |
| |
| public int getCoordinate() { |
| return x; |
| } |
| |
| public void setCoordinate(int x) { |
| this.x = x; |
| } |
| |
| public int getX() { |
| if (VERTICAL_LAYOUT) { |
| return x; |
| } else { |
| return y; |
| } |
| } |
| |
| public int getY() { |
| if (VERTICAL_LAYOUT) { |
| return y; |
| } else { |
| return x; |
| } |
| } |
| |
| public void setLayerCoordinate(int y) { |
| this.y = y; |
| } |
| |
| public void setLayer(int x) { |
| layer = x; |
| } |
| |
| public int getLayer() { |
| return layer; |
| } |
| |
| public boolean isDummy() { |
| return edge != null; |
| } |
| |
| public int getWidth() { |
| return width; |
| } |
| |
| public void addReversedStartEdge(Edge<NodeData, EdgeData> e) { |
| assert e.getData().isReversed(); |
| Port port = e.getData().getEdge().getTo(); |
| int pos = addReversedPort(port); |
| Point start = e.getData().getRelativeStart(); |
| e.getData().addStartPoint(start); |
| int yCoord = node.getSize().height + width - node.getSize().width; |
| e.getData().addStartPoint(new Point(start.x, yCoord)); |
| e.getData().addStartPoint(new Point(pos, yCoord)); |
| e.getData().setRelativeStart(new Point(pos, 0)); |
| } |
| |
| private int addReversedPort(Port p) { |
| if (reversePositions.containsKey(p)) { |
| return reversePositions.get(p); |
| } else { |
| width += OFFSET; |
| reversePositions.put(p, width); |
| return width; |
| } |
| } |
| |
| public void addReversedEndEdge(Edge<NodeData, EdgeData> e) { |
| assert e.getData().isReversed(); |
| int pos = addReversedPort(e.getData().getEdge().getFrom()); |
| Point end = e.getData().getRelativeEnd(); |
| e.getData().setRelativeEnd(new Point(pos, node.getSize().height)); |
| int yCoord = 0 - width + node.getSize().width; |
| e.getData().addEndPoint(new Point(pos, yCoord)); |
| e.getData().addEndPoint(new Point(end.x, yCoord)); |
| e.getData().addEndPoint(end); |
| } |
| |
| public int getHeight() { |
| if (isDummy()) { |
| if (VERTICAL_LAYOUT) { |
| return DUMMY_HEIGHT; |
| } else { |
| return DUMMY_WIDTH; |
| } |
| |
| } else { |
| if (VERTICAL_LAYOUT) { |
| return node.getSize().height; |
| } else { |
| return node.getSize().width; |
| } |
| } |
| } |
| |
| @Override |
| public String toString() { |
| if (isDummy()) { |
| return edge.toString() + "(layer=" + layer + ")"; |
| } else { |
| return node.toString() + "(layer=" + layer + ")"; |
| } |
| } |
| } |
| |
| private class EdgeData { |
| |
| private Point relativeEnd; |
| private Point relativeStart; |
| private List<Point> startPoints; |
| private List<Point> endPoints; |
| private boolean important; |
| private boolean reversed; |
| private Link edge; |
| |
| public EdgeData(Link edge) { |
| this(edge, false); |
| } |
| |
| public EdgeData(Link edge, boolean rev) { |
| this.edge = edge; |
| reversed = rev; |
| relativeStart = edge.getFrom().getRelativePosition(); |
| relativeEnd = edge.getTo().getRelativePosition(); |
| assert relativeStart.x >= 0 && relativeStart.x <= edge.getFrom().getVertex().getSize().width; |
| assert relativeStart.y >= 0 && relativeStart.y <= edge.getFrom().getVertex().getSize().height; |
| assert relativeEnd.x >= 0 && relativeEnd.x <= edge.getTo().getVertex().getSize().width; |
| assert relativeEnd.y >= 0 && relativeEnd.y <= edge.getTo().getVertex().getSize().height; |
| startPoints = new ArrayList<Point>(); |
| endPoints = new ArrayList<Point>(); |
| this.important = true; |
| } |
| |
| public boolean isImportant() { |
| return important; |
| } |
| |
| public void setImportant(boolean b) { |
| this.important = b; |
| } |
| |
| public List<Point> getStartPoints() { |
| return startPoints; |
| } |
| |
| public List<Point> getEndPoints() { |
| return endPoints; |
| } |
| |
| public List<Point> getAbsoluteEndPoints() { |
| if (endPoints.size() == 0) { |
| return endPoints; |
| } |
| |
| List<Point> result = new ArrayList<Point>(); |
| Point point = edge.getTo().getVertex().getPosition(); |
| for (Point p : endPoints) { |
| Point p2 = new Point(p.x + point.x, p.y + point.y); |
| result.add(p2); |
| } |
| |
| return result; |
| } |
| |
| public List<Point> getAbsoluteStartPoints() { |
| if (startPoints.size() == 0) { |
| return startPoints; |
| } |
| |
| List<Point> result = new ArrayList<Point>(); |
| Point point = edge.getFrom().getVertex().getPosition(); |
| for (Point p : startPoints) { |
| Point p2 = new Point(p.x + point.x, p.y + point.y); |
| result.add(p2); |
| } |
| |
| return result; |
| } |
| |
| public void addEndPoint(Point p) { |
| endPoints.add(p); |
| } |
| |
| public void addStartPoint(Point p) { |
| startPoints.add(p); |
| } |
| |
| public Link getEdge() { |
| return edge; |
| } |
| |
| public void setRelativeEnd(Point p) { |
| relativeEnd = p; |
| } |
| |
| public void setRelativeStart(Point p) { |
| relativeStart = p; |
| } |
| |
| public Point getRelativeEnd() { |
| return relativeEnd; |
| } |
| |
| public Point getRelativeStart() { |
| return relativeStart; |
| } |
| |
| public boolean isReversed() { |
| return reversed; |
| } |
| |
| public void setReversed(boolean b) { |
| reversed = b; |
| } |
| |
| @Override |
| public String toString() { |
| return "EdgeData[reversed=" + reversed + "]"; |
| } |
| } |
| private Graph<NodeData, EdgeData> graph; |
| private Map<Vertex, Node<NodeData, EdgeData>> nodeMap; |
| private int layerOffset; |
| |
| /** Creates a new instance of HierarchicalPositionManager */ |
| public OldHierarchicalLayoutManager(Combine combine) { |
| this(combine, LAYER_OFFSET); |
| } |
| |
| public OldHierarchicalLayoutManager(Combine combine, int layerOffset) { |
| this.combine = combine; |
| this.layerOffset = layerOffset; |
| } |
| |
| public void doRouting(LayoutGraph graph) { |
| } |
| |
| //public void setPositions(PositionedNode rootNode, List<? extends PositionedNode> nodes, List<? extends PositionedEdge> edges) { |
| public void doLayout(LayoutGraph layoutGraph) { |
| doLayout(layoutGraph, new HashSet<Vertex>(), new HashSet<Vertex>()); |
| } |
| |
| public void doLayout(LayoutGraph layoutGraph, Set<? extends Vertex> firstLayerHint, Set<? extends Vertex> lastLayerHint) { |
| doLayout(layoutGraph, firstLayerHint, lastLayerHint, new HashSet<Link>()); |
| } |
| |
| public void doLayout(LayoutGraph layoutGraph, Set<? extends Vertex> firstLayerHint, Set<? extends Vertex> lastLayerHint, Set<? extends Link> importantLinksHint) { |
| |
| if (TRACE) { |
| System.out.println("HierarchicalPositionManager.doLayout called"); |
| System.out.println("Vertex count = " + layoutGraph.getVertices().size() + " Link count = " + layoutGraph.getLinks().size()); |
| } |
| |
| // Nothing to do => quit immediately |
| if (layoutGraph.getVertices().size() == 0) { |
| return; |
| } |
| |
| initTiming.start(); |
| |
| // Mapping vertex to Node in graph |
| nodeMap = new HashMap<Vertex, Node<NodeData, EdgeData>>(); |
| |
| graph = new Graph<NodeData, EdgeData>(); |
| |
| Set<Node<NodeData, EdgeData>> rootNodes = new HashSet<Node<NodeData, EdgeData>>(); |
| Set<Vertex> startRootVertices = new HashSet<Vertex>(); |
| |
| for (Vertex v : layoutGraph.getVertices()) { |
| if (v.isRoot()) { |
| startRootVertices.add(v); |
| } |
| } |
| |
| rootVertexTiming.start(); |
| Set<Vertex> rootVertices = layoutGraph.findRootVertices(startRootVertices); |
| rootVertexTiming.stop(); |
| |
| |
| for (Vertex node : layoutGraph.getVertices()) { |
| |
| NodeData data = new NodeData(node); |
| Node<NodeData, EdgeData> n = graph.createNode(data, node); |
| nodeMap.put(node, n); |
| |
| if (rootVertices.contains(node)) { |
| rootNodes.add(n); |
| } |
| } |
| |
| Set<? extends Link> links = layoutGraph.getLinks(); |
| Link[] linkArr = new Link[links.size()]; |
| links.toArray(linkArr); |
| |
| List<Link> linkList = new ArrayList<Link>(); |
| for (Link l : linkArr) { |
| linkList.add(l); |
| } |
| |
| createEdgesTiming.start(); |
| Collections.sort(linkList, new Comparator<Link>() { |
| |
| public int compare(Link o1, Link o2) { |
| int result = o1.getFrom().getVertex().compareTo(o2.getFrom().getVertex()); |
| if (result == 0) { |
| return o1.getTo().getVertex().compareTo(o2.getTo().getVertex()); |
| } else { |
| return result; |
| } |
| } |
| }); |
| |
| for (Link edge : linkList) { |
| EdgeData data = new EdgeData(edge); |
| graph.createEdge(graph.getNode(edge.getFrom().getVertex()), graph.getNode(edge.getTo().getVertex()), data, data); |
| if (importantLinksHint.size() > 0 && !importantLinksHint.contains(edge)) { |
| data.setImportant(false); |
| } |
| } |
| createEdgesTiming.stop(); |
| |
| initTiming.stop(); |
| |
| removeCyclesTiming.start(); |
| |
| // STEP 1: Remove cycles! |
| removeCycles(rootNodes); |
| if (ASSERT) { |
| assert checkRemoveCycles(); |
| } |
| |
| removeCyclesTiming.stop(); |
| |
| reversedEdgesTiming.start(); |
| |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| List<Edge<NodeData, EdgeData>> edges = new ArrayList<Edge<NodeData, EdgeData>>(n.getOutEdges()); |
| Collections.sort(edges, new Comparator<Edge<NodeData, EdgeData>>() { |
| |
| public int compare(Edge<NodeData, EdgeData> o1, Edge<NodeData, EdgeData> o2) { |
| return o2.getData().getRelativeEnd().x - o1.getData().getRelativeEnd().x; |
| } |
| }); |
| |
| |
| for (Edge<NodeData, EdgeData> e : edges) { |
| |
| if (e.getData().isReversed()) { |
| e.getSource().getData().addReversedEndEdge(e); |
| } |
| } |
| } |
| |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| List<Edge<NodeData, EdgeData>> edges = new ArrayList<Edge<NodeData, EdgeData>>(n.getInEdges()); |
| Collections.sort(edges, new Comparator<Edge<NodeData, EdgeData>>() { |
| |
| public int compare(Edge<NodeData, EdgeData> o1, Edge<NodeData, EdgeData> o2) { |
| return o2.getData().getRelativeStart().x - o1.getData().getRelativeStart().x; |
| } |
| }); |
| |
| |
| for (Edge<NodeData, EdgeData> e : edges) { |
| if (e.getData().isReversed()) { |
| e.getDest().getData().addReversedStartEdge(e); |
| } |
| } |
| } |
| |
| reversedEdgesTiming.stop(); |
| |
| assignLayersTiming.start(); |
| // STEP 2: Assign layers! |
| int maxLayer = assignLayers(rootNodes, firstLayerHint, lastLayerHint); |
| if (ASSERT) { |
| assert checkAssignLayers(); |
| } |
| |
| // Put into layer array |
| //int maxLayer = 0; |
| //for(Node<NodeData, EdgeData> n : graph.getNodes()) { |
| // maxLayer = Math.max(maxLayer, n.getData().getLayer()); |
| //} |
| |
| |
| ArrayList<Node<NodeData, EdgeData>> layers[] = new ArrayList[maxLayer + 1]; |
| int layerSizes[] = new int[maxLayer + 1]; |
| for (int i = 0; i < maxLayer + 1; i++) { |
| layers[i] = new ArrayList<Node<NodeData, EdgeData>>(); |
| } |
| |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| int curLayer = n.getData().getLayer(); |
| layers[curLayer].add(n); |
| } |
| |
| assignLayersTiming.stop(); |
| |
| // STEP 3: Insert dummy nodes! |
| dummyNodesTiming.start(); |
| insertDummyNodes(layers); |
| if (ASSERT) { |
| assert checkDummyNodes(); |
| } |
| dummyNodesTiming.stop(); |
| |
| crossingReductionTiming.start(); |
| // STEP 4: Assign Y coordinates |
| assignLayerCoordinates(layers, layerSizes); |
| |
| // STEP 5: Crossing reduction |
| crossingReduction(layers); |
| crossingReductionTiming.stop(); |
| |
| // STEP 6: Assign Y coordinates |
| assignCoordinatesTiming.start(); |
| assignCoordinates(layers); |
| assignCoordinatesTiming.stop(); |
| |
| assignRealTiming.start(); |
| |
| // Assign coordinates of nodes to real objects |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| if (!n.getData().isDummy()) { |
| |
| Vertex node = n.getData().getNode(); |
| node.setPosition(new Point(n.getData().getX(), n.getData().getY())); |
| } |
| } |
| |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| if (!n.getData().isDummy()) { |
| |
| Vertex node = n.getData().getNode(); |
| |
| List<Edge<NodeData, EdgeData>> outEdges = n.getOutEdges(); |
| for (Edge<NodeData, EdgeData> e : outEdges) { |
| Node<NodeData, EdgeData> succ = e.getDest(); |
| if (succ.getData().isDummy()) { |
| //PositionedEdge edge = succ.getData().getEdge(); |
| List<Point> points = new ArrayList<Point>(); |
| assignToRealObjects(layerSizes, succ, points); |
| } else { |
| List<Point> points = new ArrayList<Point>(); |
| |
| EdgeData otherEdgeData = e.getData(); |
| points.addAll(otherEdgeData.getAbsoluteStartPoints()); |
| Link otherEdge = otherEdgeData.getEdge(); |
| Point relFrom = new Point(otherEdgeData.getRelativeStart()); |
| Point from = otherEdge.getFrom().getVertex().getPosition(); |
| relFrom.move(relFrom.x + from.x, relFrom.y + from.y); |
| points.add(relFrom); |
| |
| Point relTo = new Point(otherEdgeData.getRelativeEnd()); |
| Point to = otherEdge.getTo().getVertex().getPosition(); |
| relTo.move(relTo.x + to.x, relTo.y + to.y); |
| assert from != null; |
| assert to != null; |
| points.add(relTo); |
| points.addAll(otherEdgeData.getAbsoluteEndPoints()); |
| e.getData().getEdge().setControlPoints(points); |
| } |
| } |
| } |
| } |
| |
| assignRealTiming.stop(); |
| |
| initTiming.print(); |
| removeCyclesTiming.print(); |
| reversedEdgesTiming.print(); |
| assignLayersTiming.print(); |
| dummyNodesTiming.print(); |
| crossingReductionTiming.print(); |
| assignCoordinatesTiming.print(); |
| assignRealTiming.print(); |
| rootVertexTiming.print(); |
| createEdgesTiming.print(); |
| optimizeMedianTiming.print(); |
| } |
| |
| public boolean onOneLine(Point p1, Point p2, Point p3) { |
| int xoff1 = p1.x - p2.x; |
| int yoff1 = p1.y - p2.y; |
| int xoff2 = p3.x - p2.x; |
| int yoff2 = p3.y - p2.x; |
| |
| return (xoff1 * yoff2 - yoff1 * xoff2 == 0); |
| } |
| |
| private void assignToRealObjects(int layerSizes[], Node<NodeData, EdgeData> cur, List<Point> points) { |
| assert cur.getData().isDummy(); |
| |
| ArrayList<Point> otherPoints = new ArrayList<Point>(points); |
| |
| int size = layerSizes[cur.getData().getLayer()]; |
| otherPoints.add(new Point(cur.getData().getX(), cur.getData().getY() - size / 2)); |
| if (otherPoints.size() >= 3 && onOneLine(otherPoints.get(otherPoints.size() - 1), otherPoints.get(otherPoints.size() - 2), otherPoints.get(otherPoints.size() - 3))) { |
| otherPoints.remove(otherPoints.size() - 2); |
| } |
| otherPoints.add(new Point(cur.getData().getX(), cur.getData().getY() + size / 2)); |
| if (otherPoints.size() >= 3 && onOneLine(otherPoints.get(otherPoints.size() - 1), otherPoints.get(otherPoints.size() - 2), otherPoints.get(otherPoints.size() - 3))) { |
| otherPoints.remove(otherPoints.size() - 2); |
| } |
| |
| for (int i = 0; i < cur.getOutEdges().size(); i++) { |
| Node<NodeData, EdgeData> otherSucc = cur.getOutEdges().get(i).getDest(); |
| |
| if (otherSucc.getData().isDummy()) { |
| assignToRealObjects(layerSizes, otherSucc, otherPoints); |
| } else { |
| EdgeData otherEdgeData = cur.getOutEdges().get(i).getData(); |
| Link otherEdge = otherEdgeData.getEdge(); |
| |
| List<Point> middlePoints = new ArrayList<Point>(otherPoints); |
| if (cur.getOutEdges().get(i).getData().isReversed()) { |
| Collections.reverse(middlePoints); |
| } |
| |
| ArrayList<Point> copy = new ArrayList<Point>(); |
| Point relFrom = new Point(otherEdgeData.getRelativeStart()); |
| Point from = otherEdge.getFrom().getVertex().getPosition(); |
| //int moveUp = (size - otherEdge.getFrom().getVertex().getSize().height) / 2; |
| relFrom.move(relFrom.x + from.x, relFrom.y + from.y); |
| copy.addAll(otherEdgeData.getAbsoluteStartPoints()); |
| copy.add(relFrom); |
| copy.addAll(middlePoints); |
| |
| Point relTo = new Point(otherEdgeData.getRelativeEnd()); |
| Point to = otherEdge.getTo().getVertex().getPosition(); |
| relTo.move(relTo.x + to.x, relTo.y + to.y); |
| copy.add(relTo); |
| |
| copy.addAll(otherEdgeData.getAbsoluteEndPoints()); |
| |
| |
| otherEdge.setControlPoints(copy); |
| } |
| } |
| } |
| |
| private boolean checkDummyNodes() { |
| for (Edge<NodeData, EdgeData> e : graph.getEdges()) { |
| if (e.getSource().getData().getLayer() != e.getDest().getData().getLayer() - 1) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| private void insertDummyNodes(ArrayList<Node<NodeData, EdgeData>> layers[]) { |
| |
| int sum = 0; |
| List<Node<NodeData, EdgeData>> nodes = new ArrayList<Node<NodeData, EdgeData>>(graph.getNodes()); |
| int edgeCount = 0; |
| int innerMostLoop = 0; |
| |
| for (Node<NodeData, EdgeData> n : nodes) { |
| List<Edge<NodeData, EdgeData>> edges = new ArrayList<Edge<NodeData, EdgeData>>(n.getOutEdges()); |
| for (Edge<NodeData, EdgeData> e : edges) { |
| |
| edgeCount++; |
| Link edge = e.getData().getEdge(); |
| Node<NodeData, EdgeData> destNode = e.getDest(); |
| Node<NodeData, EdgeData> lastNode = n; |
| Edge<NodeData, EdgeData> lastEdge = e; |
| |
| boolean searchForNode = (combine != Combine.NONE); |
| for (int i = n.getData().getLayer() + 1; i < destNode.getData().getLayer(); i++) { |
| |
| Node<NodeData, EdgeData> foundNode = null; |
| if (searchForNode) { |
| for (Node<NodeData, EdgeData> sameLayerNode : layers[i]) { |
| innerMostLoop++; |
| |
| if (combine == Combine.SAME_OUTPUTS) { |
| if (sameLayerNode.getData().isDummy() && sameLayerNode.getData().getEdge().getFrom() == edge.getFrom()) { |
| foundNode = sameLayerNode; |
| break; |
| } |
| } else if (combine == Combine.SAME_INPUTS) { |
| if (sameLayerNode.getData().isDummy() && sameLayerNode.getData().getEdge().getTo() == edge.getTo()) { |
| foundNode = sameLayerNode; |
| break; |
| } |
| } |
| } |
| } |
| |
| if (foundNode == null) { |
| searchForNode = false; |
| NodeData intermediateData = new NodeData(edge); |
| Node<NodeData, EdgeData> curNode = graph.createNode(intermediateData, null); |
| curNode.getData().setLayer(i); |
| layers[i].add(0, curNode); |
| sum++; |
| lastEdge.remove(); |
| graph.createEdge(lastNode, curNode, e.getData(), null); |
| assert lastNode.getData().getLayer() == curNode.getData().getLayer() - 1; |
| lastEdge = graph.createEdge(curNode, destNode, e.getData(), null); |
| lastNode = curNode; |
| } else { |
| lastEdge.remove(); |
| lastEdge = graph.createEdge(foundNode, destNode, e.getData(), null); |
| lastNode = foundNode; |
| } |
| |
| } |
| } |
| } |
| |
| if (TRACE) { |
| System.out.println("Number of edges: " + edgeCount); |
| } |
| if (TRACE) { |
| System.out.println("Dummy nodes inserted: " + sum); |
| } |
| } |
| |
| private void assignLayerCoordinates(ArrayList<Node<NodeData, EdgeData>> layers[], int layerSizes[]) { |
| int cur = 0; |
| for (int i = 0; i < layers.length; i++) { |
| int maxHeight = 0; |
| for (Node<NodeData, EdgeData> n : layers[i]) { |
| maxHeight = Math.max(maxHeight, n.getData().getHeight()); |
| } |
| |
| layerSizes[i] = maxHeight; |
| for (Node<NodeData, EdgeData> n : layers[i]) { |
| int curCoordinate = cur + (maxHeight - n.getData().getHeight()) / 2; |
| n.getData().setLayerCoordinate(curCoordinate); |
| } |
| cur += maxHeight + layerOffset; |
| |
| } |
| } |
| |
| private void assignCoordinates(ArrayList<Node<NodeData, EdgeData>> layers[]) { |
| |
| // TODO: change this |
| for (int i = 0; i < layers.length; i++) { |
| ArrayList<Node<NodeData, EdgeData>> curArray = layers[i]; |
| int curY = 0; |
| for (Node<NodeData, EdgeData> n : curArray) { |
| |
| n.getData().setCoordinate(curY); |
| if (!n.getData().isDummy()) { |
| curY += n.getData().getWidth(); |
| } |
| curY += OFFSET; |
| |
| } |
| } |
| |
| int curSol = evaluateSolution(); |
| if (TRACE) { |
| System.out.println("First coordinate solution found: " + curSol); |
| } |
| |
| // Sort to correct order |
| for (int i = 0; i < layers.length; i++) { |
| Collections.sort(layers[i], new Comparator<Node<NodeData, EdgeData>>() { |
| |
| public int compare(Node<NodeData, EdgeData> o1, Node<NodeData, EdgeData> o2) { |
| if (o2.getData().isDummy()) { |
| return 1; |
| } else if (o1.getData().isDummy()) { |
| return -1; |
| } |
| return o2.getInEdges().size() + o2.getOutEdges().size() - o1.getInEdges().size() - o1.getOutEdges().size(); |
| } |
| }); |
| } |
| |
| |
| optimizeMedianTiming.start(); |
| for (int i = 0; i < 2; i++) { |
| optimizeMedian(layers); |
| curSol = evaluateSolution(); |
| if (TRACE) { |
| System.out.println("Current coordinate solution found: " + curSol); |
| } |
| } |
| optimizeMedianTiming.stop(); |
| normalizeCoordinate(); |
| |
| } |
| |
| private void normalizeCoordinate() { |
| |
| int min = Integer.MAX_VALUE; |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| min = Math.min(min, n.getData().getCoordinate()); |
| } |
| |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| n.getData().setCoordinate(n.getData().getCoordinate() - min); |
| } |
| |
| } |
| |
| private void optimizeMedian(ArrayList<Node<NodeData, EdgeData>> layers[]) { |
| |
| // Downsweep |
| for (int i = 1; i < layers.length; i++) { |
| |
| ArrayList<Node<NodeData, EdgeData>> processingList = layers[i]; |
| ArrayList<Node<NodeData, EdgeData>> alreadyAssigned = new ArrayList<Node<NodeData, EdgeData>>(); |
| for (Node<NodeData, EdgeData> n : processingList) { |
| |
| |
| ArrayList<Node<NodeData, EdgeData>> preds = new ArrayList<Node<NodeData, EdgeData>>(n.getPredecessors()); |
| int pos = n.getData().getCoordinate(); |
| if (preds.size() > 0) { |
| |
| Collections.sort(preds, new Comparator<Node<NodeData, EdgeData>>() { |
| |
| public int compare(Node<NodeData, EdgeData> o1, Node<NodeData, EdgeData> o2) { |
| return o1.getData().getCoordinate() - o2.getData().getCoordinate(); |
| } |
| }); |
| |
| if (preds.size() % 2 == 0) { |
| assert preds.size() >= 2; |
| pos = (preds.get(preds.size() / 2).getData().getCoordinate() - calcRelativeCoordinate(preds.get(preds.size() / 2), n) + preds.get(preds.size() / 2 - 1).getData().getCoordinate() - calcRelativeCoordinate(preds.get(preds.size() / 2 - 1), n)) / 2; |
| } else { |
| assert preds.size() >= 1; |
| pos = preds.get(preds.size() / 2).getData().getCoordinate() - calcRelativeCoordinate(preds.get(preds.size() / 2), n); |
| } |
| } |
| |
| tryAdding(alreadyAssigned, n, pos); |
| } |
| } |
| // Upsweep |
| for (int i = layers.length - 2; i >= 0; i--) { |
| ArrayList<Node<NodeData, EdgeData>> processingList = layers[i]; |
| ArrayList<Node<NodeData, EdgeData>> alreadyAssigned = new ArrayList<Node<NodeData, EdgeData>>(); |
| for (Node<NodeData, EdgeData> n : processingList) { |
| |
| ArrayList<Node<NodeData, EdgeData>> succs = new ArrayList<Node<NodeData, EdgeData>>(n.getSuccessors()); |
| int pos = n.getData().getCoordinate(); |
| if (succs.size() > 0) { |
| |
| Collections.sort(succs, new Comparator<Node<NodeData, EdgeData>>() { |
| |
| public int compare(Node<NodeData, EdgeData> o1, Node<NodeData, EdgeData> o2) { |
| return o1.getData().getCoordinate() - o2.getData().getCoordinate(); |
| } |
| }); |
| |
| if (succs.size() % 2 == 0) { |
| assert succs.size() >= 2; |
| pos = (succs.get(succs.size() / 2).getData().getCoordinate() - calcRelativeCoordinate(n, succs.get(succs.size() / 2)) + succs.get(succs.size() / 2 - 1).getData().getCoordinate() - calcRelativeCoordinate(n, succs.get(succs.size() / 2 - 1))) / 2; |
| } else { |
| assert succs.size() >= 1; |
| pos = succs.get(succs.size() / 2).getData().getCoordinate() - calcRelativeCoordinate(n, succs.get(succs.size() / 2)); |
| } |
| } |
| |
| tryAdding(alreadyAssigned, n, pos); |
| } |
| } |
| } |
| |
| private int median(ArrayList<Integer> arr) { |
| assert arr.size() > 0; |
| Collections.sort(arr); |
| if (arr.size() % 2 == 0) { |
| return (arr.get(arr.size() / 2) + arr.get(arr.size() / 2 - 1)) / 2; |
| } else { |
| return arr.get(arr.size() / 2); |
| } |
| } |
| |
| private int calcRelativeCoordinate(Node<NodeData, EdgeData> n, Node<NodeData, EdgeData> succ) { |
| |
| if (n.getData().isDummy() && succ.getData().isDummy()) { |
| return 0; |
| } |
| |
| int pos = 0; |
| int pos2 = 0; |
| ArrayList<Integer> coords2 = new ArrayList<Integer>(); |
| ArrayList<Integer> coords = new ArrayList<Integer>(); |
| /*if(!n.getData().isDummy())*/ { |
| for (Edge<NodeData, EdgeData> e : n.getOutEdges()) { |
| |
| //System.out.println("reversed: " + e.getData().isReversed()); |
| if (e.getDest() == succ) { |
| |
| if (e.getData().isReversed()) { |
| if (!n.getData().isDummy()) { |
| coords.add(e.getData().getRelativeEnd().x); |
| } |
| |
| if (!succ.getData().isDummy()) { |
| coords2.add(e.getData().getRelativeStart().x); |
| } |
| } else { |
| if (!n.getData().isDummy()) { |
| coords.add(e.getData().getRelativeStart().x); |
| } |
| |
| if (!succ.getData().isDummy()) { |
| coords2.add(e.getData().getRelativeEnd().x); |
| } |
| } |
| } |
| } |
| |
| // assert coords.size() > 0; |
| if (!n.getData().isDummy()) { |
| pos = median(coords); |
| } |
| |
| if (!succ.getData().isDummy()) { |
| pos2 = median(coords2); |
| } |
| } |
| //System.out.println("coords=" + coords); |
| //System.out.println("coords2=" + coords2); |
| |
| return pos - pos2; |
| } |
| |
| private boolean intersect(int v1, int w1, int v2, int w2) { |
| if (v1 >= v2 && v1 < v2 + w2) { |
| return true; |
| } |
| if (v1 + w1 > v2 && v1 + w1 < v2 + w2) { |
| return true; |
| } |
| if (v1 < v2 && v1 + w1 > v2) { |
| return true; |
| } |
| return false; |
| } |
| |
| private boolean intersect(Node<NodeData, EdgeData> n1, Node<NodeData, EdgeData> n2) { |
| return intersect(n1.getData().getCoordinate(), n1.getData().getWidth() + OFFSET, n2.getData().getCoordinate(), n2.getData().getWidth() + OFFSET); |
| } |
| |
| private void tryAdding(List<Node<NodeData, EdgeData>> alreadyAssigned, Node<NodeData, EdgeData> node, int pos) { |
| |
| boolean doesIntersect = false; |
| node.getData().setCoordinate(pos); |
| for (Node<NodeData, EdgeData> n : alreadyAssigned) { |
| if (n.getData().getCoordinate() + n.getData().getWidth() < pos) { |
| break; |
| } else if (intersect(node, n)) { |
| doesIntersect = true; |
| break; |
| } |
| |
| } |
| |
| if (!doesIntersect) { |
| |
| // Everything fine, just place the node |
| int z = 0; |
| for (Node<NodeData, EdgeData> n : alreadyAssigned) { |
| if (pos > n.getData().getCoordinate()) { |
| break; |
| } |
| z++; |
| } |
| |
| if (z == -1) { |
| z = alreadyAssigned.size(); |
| } |
| |
| |
| if (ASSERT) { |
| assert !findOverlap(alreadyAssigned, node); |
| } |
| alreadyAssigned.add(z, node); |
| |
| } else { |
| |
| assert alreadyAssigned.size() > 0; |
| |
| // Search for alternative location |
| int minOffset = Integer.MAX_VALUE; |
| int minIndex = -1; |
| int minPos = 0; |
| int w = node.getData().getWidth() + OFFSET; |
| |
| // Try top-most |
| minIndex = 0; |
| minPos = alreadyAssigned.get(0).getData().getCoordinate() + alreadyAssigned.get(0).getData().getWidth() + OFFSET; |
| minOffset = Math.abs(minPos - pos); |
| |
| // Try bottom-most |
| Node<NodeData, EdgeData> lastNode = alreadyAssigned.get(alreadyAssigned.size() - 1); |
| int lastPos = lastNode.getData().getCoordinate() - w; |
| int lastOffset = Math.abs(lastPos - pos); |
| if (lastOffset < minOffset) { |
| minPos = lastPos; |
| minOffset = lastOffset; |
| minIndex = alreadyAssigned.size(); |
| } |
| |
| // Try between |
| for (int i = 0; i < alreadyAssigned.size() - 1; i++) { |
| Node<NodeData, EdgeData> curNode = alreadyAssigned.get(i); |
| Node<NodeData, EdgeData> nextNode = alreadyAssigned.get(i + 1); |
| |
| int start = nextNode.getData().getCoordinate() + nextNode.getData().getWidth() + OFFSET; |
| int end = curNode.getData().getCoordinate() - OFFSET; |
| |
| int bestPoss = end - node.getData().getWidth(); |
| if (bestPoss < pos && pos - bestPoss > minOffset) { |
| // No better solution possible => break |
| break; |
| } |
| |
| if (end - start >= node.getData().getWidth()) { |
| // Node could fit here |
| int cand1 = start; |
| int cand2 = end - node.getData().getWidth(); |
| int off1 = Math.abs(cand1 - pos); |
| int off2 = Math.abs(cand2 - pos); |
| if (off1 < minOffset) { |
| minPos = cand1; |
| minOffset = off1; |
| minIndex = i + 1; |
| } |
| |
| if (off2 < minOffset) { |
| minPos = cand2; |
| minOffset = off2; |
| minIndex = i + 1; |
| } |
| } |
| } |
| |
| assert minIndex != -1; |
| node.getData().setCoordinate(minPos); |
| if (ASSERT) { |
| assert !findOverlap(alreadyAssigned, node); |
| } |
| alreadyAssigned.add(minIndex, node); |
| } |
| |
| } |
| |
| private boolean findOverlap(List<Node<NodeData, EdgeData>> nodes, Node<NodeData, EdgeData> node) { |
| |
| for (Node<NodeData, EdgeData> n1 : nodes) { |
| if (intersect(n1, node)) { |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| private int evaluateSolution() { |
| |
| int sum = 0; |
| for (Edge<NodeData, EdgeData> e : graph.getEdges()) { |
| Node<NodeData, EdgeData> source = e.getSource(); |
| Node<NodeData, EdgeData> dest = e.getDest(); |
| int offset = 0; |
| offset = Math.abs(source.getData().getCoordinate() - dest.getData().getCoordinate()); |
| sum += offset; |
| } |
| |
| return sum; |
| } |
| |
| private void crossingReduction(ArrayList<Node<NodeData, EdgeData>> layers[]) { |
| |
| for (int i = 0; i < layers.length - 1; i++) { |
| |
| ArrayList<Node<NodeData, EdgeData>> curNodes = layers[i]; |
| ArrayList<Node<NodeData, EdgeData>> nextNodes = layers[i + 1]; |
| for (Node<NodeData, EdgeData> n : curNodes) { |
| for (Node<NodeData, EdgeData> succ : n.getSuccessors()) { |
| if (ASSERT) { |
| assert nextNodes.contains(succ); |
| } |
| nextNodes.remove(succ); |
| nextNodes.add(succ); |
| } |
| } |
| |
| } |
| |
| } |
| |
| private void removeCycles(Set<Node<NodeData, EdgeData>> rootNodes) { |
| final List<Edge<NodeData, EdgeData>> reversedEdges = new ArrayList<Edge<NodeData, EdgeData>>(); |
| |
| |
| int removedCount = 0; |
| int reversedCount = 0; |
| |
| Graph.DFSTraversalVisitor visitor = graph.new DFSTraversalVisitor() { |
| |
| @Override |
| public boolean visitEdge(Edge<NodeData, EdgeData> e, boolean backEdge) { |
| if (backEdge) { |
| if (ASSERT) { |
| assert !reversedEdges.contains(e); |
| } |
| reversedEdges.add(e); |
| e.getData().setReversed(!e.getData().isReversed()); |
| } |
| |
| return e.getData().isImportant(); |
| } |
| }; |
| Set<Node<NodeData, EdgeData>> nodes = new HashSet<Node<NodeData, EdgeData>>(); |
| nodes.addAll(rootNodes); |
| |
| assert nodes.size() > 0; |
| |
| this.graph.traverseDFS(nodes, visitor); |
| |
| for (Edge<NodeData, EdgeData> e : reversedEdges) { |
| if (e.isSelfLoop()) { |
| e.remove(); |
| removedCount++; |
| } else { |
| e.reverse(); |
| reversedCount++; |
| } |
| } |
| } |
| |
| private boolean checkRemoveCycles() { |
| return !graph.hasCycles(); |
| } |
| // Only used by assignLayers |
| private int maxLayerTemp; |
| |
| private int assignLayers(Set<Node<NodeData, EdgeData>> rootNodes, Set<? extends Vertex> firstLayerHints, |
| Set<? extends Vertex> lastLayerHints) { |
| this.maxLayerTemp = -1; |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| n.getData().setLayer(-1); |
| } |
| |
| Graph.BFSTraversalVisitor traverser = graph.new BFSTraversalVisitor() { |
| |
| @Override |
| public void visitNode(Node<NodeData, EdgeData> n, int depth) { |
| if (depth > n.getData().getLayer()) { |
| n.getData().setLayer(depth); |
| maxLayerTemp = Math.max(maxLayerTemp, depth); |
| } |
| } |
| }; |
| |
| for (Node<NodeData, EdgeData> n : rootNodes) { |
| if (n.getData().getLayer() == -1) { |
| this.graph.traverseBFS(n, traverser, true); |
| } |
| } |
| |
| for (Vertex v : firstLayerHints) { |
| assert nodeMap.containsKey(v); |
| nodeMap.get(v).getData().setLayer(0); |
| } |
| |
| for (Vertex v : lastLayerHints) { |
| assert nodeMap.containsKey(v); |
| nodeMap.get(v).getData().setLayer(maxLayerTemp); |
| } |
| |
| return maxLayerTemp; |
| } |
| |
| private boolean checkAssignLayers() { |
| |
| for (Edge<NodeData, EdgeData> e : graph.getEdges()) { |
| Node<NodeData, EdgeData> source = e.getSource(); |
| Node<NodeData, EdgeData> dest = e.getDest(); |
| |
| |
| if (source.getData().getLayer() >= dest.getData().getLayer()) { |
| return false; |
| } |
| } |
| int maxLayer = 0; |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| assert n.getData().getLayer() >= 0; |
| if (n.getData().getLayer() > maxLayer) { |
| maxLayer = n.getData().getLayer(); |
| } |
| } |
| |
| int countPerLayer[] = new int[maxLayer + 1]; |
| for (Node<NodeData, EdgeData> n : graph.getNodes()) { |
| countPerLayer[n.getData().getLayer()]++; |
| } |
| |
| if (TRACE) { |
| System.out.println("Number of layers: " + maxLayer); |
| } |
| return true; |
| } |
| } |