Mercurial > jdk8-mips64-public > langtools / file comparison
comparison: src/share/classes/com/sun/tools/javac/util/GraphUtils.java
src/share/classes/com/sun/tools/javac/util/GraphUtils.java
- changeset 1562
- 2154ed9ff6c8
- child 2000
- 4a6acc42c3a1
equal
deleted
inserted
replaced
| 1561:073696f59241 | 1562:2154ed9ff6c8 |
|---|---|
| 1 /* | |
| 2 * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved. | |
| 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. Oracle designates this | |
| 8 * particular file as subject to the "Classpath" exception as provided | |
| 9 * by Oracle in the LICENSE file that accompanied this code. | |
| 10 * | |
| 11 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 14 * version 2 for more details (a copy is included in the LICENSE file that | |
| 15 * accompanied this code). | |
| 16 * | |
| 17 * You should have received a copy of the GNU General Public License version | |
| 18 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 20 * | |
| 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| 22 * or visit www.oracle.com if you need additional information or have any | |
| 23 * questions. | |
| 24 */ | |
| 25 | |
| 26 package com.sun.tools.javac.util; | |
| 27 | |
| 28 /** <p><b>This is NOT part of any supported API. | |
| 29 * If you write code that depends on this, you do so at your own risk. | |
| 30 * This code and its internal interfaces are subject to change or | |
| 31 * deletion without notice.</b> | |
| 32 */ | |
| 33 public class GraphUtils { | |
| 34 | |
| 35 /** | |
| 36 * This class is a basic abstract class for representing a node. | |
| 37 * A node is associated with a given data. | |
| 38 */ | |
| 39 public static abstract class Node<D> { | |
| 40 public final D data; | |
| 41 | |
| 42 public Node(D data) { | |
| 43 this.data = data; | |
| 44 } | |
| 45 | |
| 46 public abstract Iterable<? extends Node<D>> getDependencies(); | |
| 47 | |
| 48 public abstract String printDependency(Node<D> to); | |
| 49 | |
| 50 @Override | |
| 51 public String toString() { | |
| 52 return data.toString(); | |
| 53 } | |
| 54 } | |
| 55 | |
| 56 /** | |
| 57 * This class specialized Node, by adding elements that are required in order | |
| 58 * to perform Tarjan computation of strongly connected components. | |
| 59 */ | |
| 60 public static abstract class TarjanNode<D> extends Node<D> implements Comparable<TarjanNode<D>> { | |
| 61 int index = -1; | |
| 62 int lowlink; | |
| 63 boolean active; | |
| 64 | |
| 65 public TarjanNode(D data) { | |
| 66 super(data); | |
| 67 } | |
| 68 | |
| 69 public abstract Iterable<? extends TarjanNode<D>> getDependencies(); | |
| 70 | |
| 71 public int compareTo(TarjanNode<D> o) { | |
| 72 return (index < o.index) ? -1 : (index == o.index) ? 0 : 1; | |
| 73 } | |
| 74 } | |
| 75 | |
| 76 /** | |
| 77 * Tarjan's algorithm to determine strongly connected components of a | |
| 78 * directed graph in linear time. Works on TarjanNode. | |
| 79 */ | |
| 80 public static <D, N extends TarjanNode<D>> List<? extends List<? extends N>> tarjan(Iterable<? extends N> nodes) { | |
| 81 ListBuffer<List<N>> cycles = ListBuffer.lb(); | |
| 82 ListBuffer<N> stack = ListBuffer.lb(); | |
| 83 int index = 0; | |
| 84 for (N node: nodes) { | |
| 85 if (node.index == -1) { | |
| 86 index += tarjan(node, index, stack, cycles); | |
| 87 } | |
| 88 } | |
| 89 return cycles.toList(); | |
| 90 } | |
| 91 | |
| 92 private static <D, N extends TarjanNode<D>> int tarjan(N v, int index, ListBuffer<N> stack, ListBuffer<List<N>> cycles) { | |
| 93 v.index = index; | |
| 94 v.lowlink = index; | |
| 95 index++; | |
| 96 stack.prepend(v); | |
| 97 v.active = true; | |
| 98 for (TarjanNode<D> nd: v.getDependencies()) { | |
| 99 @SuppressWarnings("unchecked") | |
| 100 N n = (N)nd; | |
| 101 if (n.index == -1) { | |
| 102 tarjan(n, index, stack, cycles); | |
| 103 v.lowlink = Math.min(v.lowlink, n.lowlink); | |
| 104 } else if (stack.contains(n)) { | |
| 105 v.lowlink = Math.min(v.lowlink, n.index); | |
| 106 } | |
| 107 } | |
| 108 if (v.lowlink == v.index) { | |
| 109 N n; | |
| 110 ListBuffer<N> cycle = ListBuffer.lb(); | |
| 111 do { | |
| 112 n = stack.remove(); | |
| 113 n.active = false; | |
| 114 cycle.add(n); | |
| 115 } while (n != v); | |
| 116 cycles.add(cycle.toList()); | |
| 117 } | |
| 118 return index; | |
| 119 } | |
| 120 | |
| 121 /** | |
| 122 * Debugging: dot representation of a set of connected nodes. The resulting | |
| 123 * dot representation will use {@code Node.toString} to display node labels | |
| 124 * and {@code Node.printDependency} to display edge labels. The resulting | |
| 125 * representation is also customizable with a graph name and a header. | |
| 126 */ | |
| 127 public static <D> String toDot(Iterable<? extends TarjanNode<D>> nodes, String name, String header) { | |
| 128 StringBuilder buf = new StringBuilder(); | |
| 129 buf.append(String.format("digraph %s {\n", name)); | |
| 130 buf.append(String.format("label = \"%s\";\n", header)); | |
| 131 //dump nodes | |
| 132 for (TarjanNode<D> n : nodes) { | |
| 133 buf.append(String.format("%s [label = \"%s\"];\n", n.hashCode(), n.toString())); | |
| 134 } | |
| 135 //dump arcs | |
| 136 for (TarjanNode<D> from : nodes) { | |
| 137 for (TarjanNode<D> to : from.getDependencies()) { | |
| 138 buf.append(String.format("%s -> %s [label = \" %s \"];\n", | |
| 139 from.hashCode(), to.hashCode(), from.printDependency(to))); | |
| 140 } | |
| 141 } | |
| 142 buf.append("}\n"); | |
| 143 return buf.toString(); | |
| 144 } | |
| 145 } |
