jdk8-mips64-public/langtools: src/share/classes/com/sun/tools/javac/util/GraphUtils.java@959103a6100f

Initial load
http://hg.openjdk.java.net/jdk8u/jdk8u/langtools/
changeset: 2573:53ca196be1ae
tag: jdk8u25-b17

     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  */

    26 package com.sun.tools.javac.util;

    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 {

    35     /**

    36      * Basic interface for defining various dependency kinds. All dependency kinds

    37      * must at least support basic capabilities to tell the DOT engine how to render them.

    38      */

    39     public interface DependencyKind {

    40         /**

    41          * Returns the DOT representation (to be used in a {@code style} attribute

    42          * that's most suited for this dependency kind.

    43          */

    44         String getDotStyle();

    45     }

    47     /**

    48      * This class is a basic abstract class for representing a node.

    49      * A node is associated with a given data.

    50      */

    51     public static abstract class Node<D> {

    52         public final D data;

    54         public Node(D data) {

    55             this.data = data;

    56         }

    58         /**

    59          * Get an array of the dependency kinds supported by this node.

    60          */

    61         public abstract DependencyKind[] getSupportedDependencyKinds();

    63         /**

    64          * Get all dependencies, regardless of their kind.

    65          */

    66         public abstract Iterable<? extends Node<D>> getAllDependencies();

    68         /**

    69          * Get a name for the dependency (of given kind) linking this node to a given node

    70          */

    71         public abstract String getDependencyName(Node<D> to, DependencyKind dk);

    73         @Override

    74         public String toString() {

    75             return data.toString();

    76         }

    77     }

    79     /**

    80      * This class specialized Node, by adding elements that are required in order

    81      * to perform Tarjan computation of strongly connected components.

    82      */

    83     public static abstract class TarjanNode<D> extends Node<D> implements Comparable<TarjanNode<D>> {

    84         int index = -1;

    85         int lowlink;

    86         boolean active;

    88         public TarjanNode(D data) {

    89             super(data);

    90         }

    92         public abstract Iterable<? extends TarjanNode<D>> getAllDependencies();

    94         public abstract Iterable<? extends TarjanNode<D>> getDependenciesByKind(DependencyKind dk);

    96         public int compareTo(TarjanNode<D> o) {

    97             return (index < o.index) ? -1 : (index == o.index) ? 0 : 1;

    98         }

    99     }

   101     /**

   102      * Tarjan's algorithm to determine strongly connected components of a

   103      * directed graph in linear time. Works on TarjanNode.

   104      */

   105     public static <D, N extends TarjanNode<D>> List<? extends List<? extends N>> tarjan(Iterable<? extends N> nodes) {

   106         ListBuffer<List<N>> cycles = new ListBuffer<>();

   107         ListBuffer<N> stack = new ListBuffer<>();

   108         int index = 0;

   109         for (N node: nodes) {

   110             if (node.index == -1) {

   111                 index += tarjan(node, index, stack, cycles);

   112             }

   113         }

   114         return cycles.toList();

   115     }

   117     private static <D, N extends TarjanNode<D>> int tarjan(N v, int index, ListBuffer<N> stack, ListBuffer<List<N>> cycles) {

   118         v.index = index;

   119         v.lowlink = index;

   120         index++;

   121         stack.prepend(v);

   122         v.active = true;

   123         for (TarjanNode<D> nd: v.getAllDependencies()) {

   124             @SuppressWarnings("unchecked")

   125             N n = (N)nd;

   126             if (n.index == -1) {

   127                 tarjan(n, index, stack, cycles);

   128                 v.lowlink = Math.min(v.lowlink, n.lowlink);

   129             } else if (stack.contains(n)) {

   130                 v.lowlink = Math.min(v.lowlink, n.index);

   131             }

   132         }

   133         if (v.lowlink == v.index) {

   134             N n;

   135             ListBuffer<N> cycle = new ListBuffer<>();

   136             do {

   137                 n = stack.remove();

   138                 n.active = false;

   139                 cycle.add(n);

   140             } while (n != v);

   141             cycles.add(cycle.toList());

   142         }

   143         return index;

   144     }

   146     /**

   147      * Debugging: dot representation of a set of connected nodes. The resulting

   148      * dot representation will use {@code Node.toString} to display node labels

   149      * and {@code Node.printDependency} to display edge labels. The resulting

   150      * representation is also customizable with a graph name and a header.

   151      */

   152     public static <D> String toDot(Iterable<? extends TarjanNode<D>> nodes, String name, String header) {

   153         StringBuilder buf = new StringBuilder();

   154         buf.append(String.format("digraph %s {\n", name));

   155         buf.append(String.format("label = \"%s\";\n", header));

   156         //dump nodes

   157         for (TarjanNode<D> n : nodes) {

   158             buf.append(String.format("%s [label = \"%s\"];\n", n.hashCode(), n.toString()));

   159         }

   160         //dump arcs

   161         for (TarjanNode<D> from : nodes) {

   162             for (DependencyKind dk : from.getSupportedDependencyKinds()) {

   163                 for (TarjanNode<D> to : from.getDependenciesByKind(dk)) {

   164                     buf.append(String.format("%s -> %s [label = \" %s \" style = %s ];\n",

   165                             from.hashCode(), to.hashCode(), from.getDependencyName(to, dk), dk.getDotStyle()));

   166                 }

   167             }

   168         }

   169         buf.append("}\n");

   170         return buf.toString();

   171     }

   172 }

Mercurial > jdk8-mips64-public > langtools / file revision