--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/visualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java	Tue Feb 07 22:41:09 2012 +0100
@@ -0,0 +1,1749 @@
+/*
+ * 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
+    }
+}