Mercurial > hg > graal-compiler
view src/share/tools/IdealGraphVisualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/OldHierarchicalLayoutManager.java @ 1552:c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
Summary: Change all the Sun copyrights to Oracle copyright
Reviewed-by: ohair
author | trims |
---|---|
date | Thu, 27 May 2010 19:08:38 -0700 |
parents | 30369db7f5d2 |
children | 53ddfe305645 |
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 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; } }