--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/visualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/Graph.java	Tue Feb 07 22:41:09 2012 +0100
@@ -0,0 +1,292 @@
+/*
+ * 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.util.*;
+
+/**
+ *
+ * @author Thomas Wuerthinger
+ */
+public class Graph<N, E> {
+
+    private HashMap<Object, Node<N, E>> nodes;
+    private HashMap<Object, Edge<N, E>> edges;
+    private List<Node<N, E>> nodeList;
+
+    public Graph() {
+        nodes = new HashMap<>();
+        edges = new HashMap<>();
+        nodeList = new ArrayList<>();
+    }
+
+    public Node<N, E> createNode(N data, Object key) {
+        Node<N, E> n = new Node<>(this, data);
+        assert key == null || !nodes.containsKey(key);
+        if (key != null) {
+            nodes.put(key, n);
+        }
+        nodeList.add(n);
+        return n;
+    }
+
+    public Edge<N, E> createEdge(Node<N, E> source, Node<N, E> dest, E data, Object key) {
+        Edge<N, E> e = new Edge<>(this, source, dest, data);
+        source.addOutEdge(e);
+        dest.addInEdge(e);
+        if (key != null) {
+            edges.put(key, e);
+        }
+        return e;
+    }
+
+    public Node<N, E> getNode(Object key) {
+        return nodes.get(key);
+    }
+
+    public Edge<N, E> getEdge(Object key) {
+        return edges.get(key);
+    }
+
+    public Collection<Edge<N, E>> getEdges() {
+        return Collections.unmodifiableCollection(edges.values());
+    }
+
+    public Collection<Node<N, E>> getNodes() {
+        return Collections.unmodifiableList(nodeList);
+    }
+
+    public void removeEdge(Edge<N, E> e, Object key) {
+        assert key == null || edges.containsKey(key);
+        if (key != null) {
+            edges.remove(key);
+        }
+        e.getSource().removeOutEdge(e);
+        e.getDest().removeInEdge(e);
+    }
+
+    public class DFSTraversalVisitor {
+
+        public void visitNode(Node<N, E> n) {
+        }
+
+        public boolean visitEdge(Edge<N, E> e, boolean backEdge) {
+            return true;
+        }
+    }
+
+    public class BFSTraversalVisitor {
+
+        public void visitNode(Node<N, E> n, int depth) {
+        }
+    }
+
+    public List<Node<N, E>> getNodesWithInDegree(int x) {
+        return getNodesWithInDegree(x, true);
+    }
+
+    public List<Node<N, E>> getNodesWithInDegree(int x, boolean countSelfLoops) {
+
+        List<Node<N, E>> result = new ArrayList<>();
+        for (Node<N, E> n : getNodes()) {
+            if (n.getInDegree(countSelfLoops) == x) {
+                result.add(n);
+            }
+        }
+
+        return result;
+
+    }
+
+    private void markReachable(Node<N, E> startingNode) {
+        ArrayList<Node<N, E>> arr = new ArrayList<>();
+        arr.add(startingNode);
+        for (Node<N, E> n : getNodes()) {
+            n.setReachable(false);
+        }
+        traverseDFS(arr, new DFSTraversalVisitor() {
+
+            @Override
+            public void visitNode(Node<N, E> n) {
+                n.setReachable(true);
+            }
+        });
+    }
+
+    public void traverseBFS(Node<N, E> startingNode, BFSTraversalVisitor tv, boolean longestPath) {
+
+        if (longestPath) {
+            markReachable(startingNode);
+        }
+
+        for (Node<N, E> n : getNodes()) {
+            n.setVisited(false);
+            n.setActive(false);
+        }
+
+        Queue<Node<N, E>> queue = new LinkedList<>();
+        queue.add(startingNode);
+        startingNode.setVisited(true);
+        int layer = 0;
+        Node<N, E> lastOfLayer = startingNode;
+        Node<N, E> lastAdded = null;
+
+        while (!queue.isEmpty()) {
+
+            Node<N, E> current = queue.poll();
+            tv.visitNode(current, layer);
+            current.setActive(false);
+
+
+            for (Edge<N, E> e : current.getOutEdges()) {
+                if (!e.getDest().isVisited()) {
+
+                    boolean allow = true;
+                    if (longestPath) {
+                        for (Node<N, E> pred : e.getDest().getPredecessors()) {
+                            if ((!pred.isVisited() || pred.isActive()) && pred.isReachable()) {
+                                allow = false;
+                                break;
+                            }
+                        }
+                    }
+
+                    if (allow) {
+                        queue.offer(e.getDest());
+                        lastAdded = e.getDest();
+                        e.getDest().setVisited(true);
+                        e.getDest().setActive(true);
+                    }
+                }
+            }
+
+            if (current == lastOfLayer && !queue.isEmpty()) {
+                lastOfLayer = lastAdded;
+                layer++;
+            }
+        }
+    }
+
+    public void traverseDFS(DFSTraversalVisitor tv) {
+        traverseDFS(getNodes(), tv);
+    }
+
+    public void traverseDFS(Collection<Node<N, E>> startingNodes, DFSTraversalVisitor tv) {
+
+        for (Node<N, E> n : getNodes()) {
+            n.setVisited(false);
+            n.setActive(false);
+        }
+
+        boolean result = false;
+        for (Node<N, E> n : startingNodes) {
+            traverse(tv, n);
+        }
+    }
+
+    private void traverse(DFSTraversalVisitor tv, Node<N, E> n) {
+
+        if (!n.isVisited()) {
+            n.setVisited(true);
+            n.setActive(true);
+            tv.visitNode(n);
+
+            for (Edge<N, E> e : n.getOutEdges()) {
+
+                Node<N, E> next = e.getDest();
+                if (next.isActive()) {
+                    tv.visitEdge(e, true);
+                } else {
+                    if (tv.visitEdge(e, false)) {
+                        traverse(tv, next);
+                    }
+                }
+            }
+
+            n.setActive(false);
+        }
+
+    }
+
+    public boolean hasCycles() {
+
+        for (Node<N, E> n : getNodes()) {
+            n.setVisited(false);
+            n.setActive(false);
+        }
+
+        boolean result = false;
+        for (Node<N, E> n : getNodes()) {
+            result |= checkCycles(n);
+            if (result) {
+                break;
+            }
+        }
+        return result;
+    }
+
+    private boolean checkCycles(Node<N, E> n) {
+
+        if (n.isActive()) {
+            return true;
+        }
+
+        if (!n.isVisited()) {
+
+            n.setVisited(true);
+            n.setActive(true);
+
+            for (Node<N, E> succ : n.getSuccessors()) {
+                if (checkCycles(succ)) {
+                    return true;
+                }
+            }
+
+            n.setActive(false);
+
+        }
+
+        return false;
+    }
+
+    @Override
+    public String toString() {
+
+        StringBuilder s = new StringBuilder();
+        s.append("Nodes: ");
+        for (Node<N, E> n : getNodes()) {
+            s.append(n.toString());
+            s.append("\n");
+        }
+
+        s.append("Edges: ");
+
+        for (Edge<N, E> e : getEdges()) {
+            s.append(e.toString());
+            s.append("\n");
+        }
+
+        return s.toString();
+    }
+}