1 /*

     2  * Copyright (c) 2016, 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 package com.sun.tools.jdeps;

    26 

    27 import java.io.PrintWriter;

    28 import java.lang.module.ModuleDescriptor;

    29 import java.lang.module.ModuleFinder;

    30 import java.lang.module.ModuleReference;

    31 import java.util.Collections;

    32 import java.util.Deque;

    33 import java.util.HashMap;

    34 import java.util.HashSet;

    35 import java.util.LinkedList;

    36 import java.util.Map;

    37 import java.util.Set;

    38 import java.util.function.Consumer;

    39 import java.util.function.Predicate;

    40 import java.util.stream.Collectors;

    41 import java.util.stream.Stream;

    42 

    43 public final class Graph<T> {

    44     private final Set<T> nodes;

    45     private final Map<T, Set<T>> edges;

    46 

    47     public Graph(Set<T> nodes, Map<T, Set<T>> edges) {

    48         this.nodes = Collections.unmodifiableSet(nodes);

    49         this.edges = Collections.unmodifiableMap(edges);

    50     }

    51 

    52     public Set<T> nodes() {

    53         return nodes;

    54     }

    55 

    56     public Map<T, Set<T>> edges() {

    57         return edges;

    58     }

    59 

    60     public Set<T> adjacentNodes(T u) {

    61         return edges.get(u);

    62     }

    63 

    64     public boolean contains(T u) {

    65         return nodes.contains(u);

    66     }

    67 

    68     public Set<Edge<T>> edgesFrom(T u) {

    69         return edges.get(u).stream()

    70                     .map(v -> new Edge<T>(u, v))

    71                     .collect(Collectors.toSet());

    72     }

    73 

    74     /**

    75      * Returns a new Graph after transitive reduction

    76      */

    77     public Graph<T> reduce() {

    78         Builder<T> builder = new Builder<>();

    79         nodes.stream()

    80                 .forEach(u -> {

    81                     builder.addNode(u);

    82                     edges.get(u).stream()

    83                          .filter(v -> !pathExists(u, v, false))

    84                          .forEach(v -> builder.addEdge(u, v));

    85                 });

    86         return builder.build();

    87     }

    88 

    89     /**

    90      * Returns a new Graph after transitive reduction.  All edges in

    91      * the given g takes precedence over this graph.

    92      *

    93      * @throw IllegalArgumentException g must be a subgraph this graph

    94      */

    95     public Graph<T> reduce(Graph<T> g) {

    96         boolean subgraph = nodes.containsAll(g.nodes) &&

    97                 g.edges.keySet().stream()

    98                        .allMatch(u -> adjacentNodes(u).containsAll(g.adjacentNodes(u)));

    99         if (!subgraph) {

   100             throw new IllegalArgumentException(g + " is not a subgraph of " + this);

   101         }

   102 

   103         Builder<T> builder = new Builder<>();

   104         nodes.stream()

   105                 .forEach(u -> {

   106                     builder.addNode(u);

   107                     // filter the edge if there exists a path from u to v in the given g

   108                     // or there exists another path from u to v in this graph

   109                     edges.get(u).stream()

   110                          .filter(v -> !g.pathExists(u, v) && !pathExists(u, v, false))

   111                          .forEach(v -> builder.addEdge(u, v));

   112                 });

   113 

   114         // add the overlapped edges from this graph and the given g

   115         g.edges().keySet().stream()

   116                 .forEach(u -> g.adjacentNodes(u).stream()

   117                                 .filter(v -> isAdjacent(u, v))

   118                                 .forEach(v -> builder.addEdge(u, v)));

   119         return builder.build().reduce();

   120     }

   121 

   122     /**

   123      * Returns nodes sorted in topological order.

   124      */

   125     public Stream<T> orderedNodes() {

   126         TopoSorter<T> sorter = new TopoSorter<>(this);

   127         return sorter.result.stream();

   128     }

   129 

   130     /**

   131      * Traverse this graph and performs the given action in topological order

   132      */

   133     public void ordered(Consumer<T> action) {

   134         TopoSorter<T> sorter = new TopoSorter<>(this);

   135         sorter.ordered(action);

   136     }

   137 

   138     /**

   139      * Traverses this graph and performs the given action in reverse topological order

   140      */

   141     public void reverse(Consumer<T> action) {

   142         TopoSorter<T> sorter = new TopoSorter<>(this);

   143         sorter.reverse(action);

   144     }

   145 

   146     /**

   147      * Returns a transposed graph from this graph

   148      */

   149     public Graph<T> transpose() {

   150         Builder<T> builder = new Builder<>();

   151         builder.addNodes(nodes);

   152         // reverse edges

   153         edges.keySet().forEach(u -> {

   154             edges.get(u).stream()

   155                 .forEach(v -> builder.addEdge(v, u));

   156         });

   157         return builder.build();

   158     }

   159 

   160     /**

   161      * Returns all nodes reachable from the given set of roots.

   162      */

   163     public Set<T> dfs(Set<T> roots) {

   164         Deque<T> deque = new LinkedList<>(roots);

   165         Set<T> visited = new HashSet<>();

   166         while (!deque.isEmpty()) {

   167             T u = deque.pop();

   168             if (!visited.contains(u)) {

   169                 visited.add(u);

   170                 if (contains(u)) {

   171                     adjacentNodes(u).stream()

   172                         .filter(v -> !visited.contains(v))

   173                         .forEach(deque::push);

   174                 }

   175             }

   176         }

   177         return visited;

   178     }

   179 

   180     private boolean isAdjacent(T u, T v) {

   181         return edges.containsKey(u) && edges.get(u).contains(v);

   182     }

   183 

   184     private boolean pathExists(T u, T v) {

   185         return pathExists(u, v, true);

   186     }

   187 

   188     /**

   189      * Returns true if there exists a path from u to v in this graph.

   190      * If includeAdjacent is false, it returns true if there exists

   191      * another path from u to v of distance > 1

   192      */

   193     private boolean pathExists(T u, T v, boolean includeAdjacent) {

   194         if (!nodes.contains(u) || !nodes.contains(v)) {

   195             return false;

   196         }

   197         if (includeAdjacent && isAdjacent(u, v)) {

   198             return true;

   199         }

   200         Deque<T> stack = new LinkedList<>();

   201         Set<T> visited = new HashSet<>();

   202         stack.push(u);

   203         while (!stack.isEmpty()) {

   204             T node = stack.pop();

   205             if (node.equals(v)) {

   206                 return true;

   207             }

   208             if (!visited.contains(node)) {

   209                 visited.add(node);

   210                 edges.get(node).stream()

   211                      .filter(e -> includeAdjacent || !node.equals(u) || !e.equals(v))

   212                      .forEach(stack::push);

   213             }

   214         }

   215         assert !visited.contains(v);

   216         return false;

   217     }

   218 

   219     public void printGraph(PrintWriter out) {

   220         out.println("graph for " + nodes);

   221         nodes.stream()

   222              .forEach(u -> adjacentNodes(u).stream()

   223                                .forEach(v -> out.format("  %s -> %s%n", u, v)));

   224     }

   225 

   226     @Override

   227     public String toString() {

   228         return nodes.toString();

   229     }

   230 

   231     static class Edge<T> {

   232         final T u;

   233         final T v;

   234         Edge(T u, T v) {

   235             this.u = u;

   236             this.v = v;

   237         }

   238 

   239         @Override

   240         public String toString() {

   241             return String.format("%s -> %s", u, v);

   242         }

   243 

   244         @Override

   245         public boolean equals(Object o) {

   246             if (this == o) return true;

   247             if (o == null || !(o instanceof Edge))

   248                 return false;

   249 

   250             @SuppressWarnings("unchecked")

   251             Edge<T> edge = (Edge<T>) o;

   252 

   253             return u.equals(edge.u) && v.equals(edge.v);

   254         }

   255 

   256         @Override

   257         public int hashCode() {

   258             int result = u.hashCode();

   259             result = 31 * result + v.hashCode();

   260             return result;

   261         }

   262     }

   263 

   264     static class Builder<T> {

   265         final Set<T> nodes = new HashSet<>();

   266         final Map<T, Set<T>> edges = new HashMap<>();

   267 

   268         public void addNode(T node) {

   269             if (nodes.contains(node)) {

   270                 return;

   271             }

   272             nodes.add(node);

   273             edges.computeIfAbsent(node, _e -> new HashSet<>());

   274         }

   275 

   276         public void addNodes(Set<T> nodes) {

   277             this.nodes.addAll(nodes);

   278         }

   279 

   280         public void addEdge(T u, T v) {

   281             addNode(u);

   282             addNode(v);

   283             edges.get(u).add(v);

   284         }

   285 

   286         public Graph<T> build() {

   287             return new Graph<T>(nodes, edges);

   288         }

   289     }

   290 

   291     /**

   292      * Topological sort

   293      */

   294     static class TopoSorter<T> {

   295         final Deque<T> result = new LinkedList<>();

   296         final Deque<T> nodes;

   297         final Graph<T> graph;

   298         TopoSorter(Graph<T> graph) {

   299             this.graph = graph;

   300             this.nodes = new LinkedList<>(graph.nodes);

   301             sort();

   302         }

   303 

   304         public void ordered(Consumer<T> action) {

   305             result.iterator().forEachRemaining(action);

   306         }

   307 

   308         public void reverse(Consumer<T> action) {

   309             result.descendingIterator().forEachRemaining(action);

   310         }

   311 

   312         private void sort() {

   313             Deque<T> visited = new LinkedList<>();

   314             Deque<T> done = new LinkedList<>();

   315             T node;

   316             while ((node = nodes.poll()) != null) {

   317                 if (!visited.contains(node)) {

   318                     visit(node, visited, done);

   319                 }

   320             }

   321         }

   322 

   323         private void visit(T node, Deque<T> visited, Deque<T> done) {

   324             if (visited.contains(node)) {

   325                 if (!done.contains(node)) {

   326                     throw new IllegalArgumentException("Cyclic detected: " +

   327                         node + " " + graph.edges().get(node));

   328                 }

   329                 return;

   330             }

   331             visited.add(node);

   332             graph.edges().get(node).stream()

   333                 .forEach(x -> visit(x, visited, done));

   334             done.add(node);

   335             result.addLast(node);

   336         }

   337     }

   338 }