Graph.java revision 3827:44bdefe64114
176273Sbrian/* 276273Sbrian * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. 376273Sbrian * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 476273Sbrian * 576273Sbrian * This code is free software; you can redistribute it and/or modify it 676273Sbrian * under the terms of the GNU General Public License version 2 only, as 776273Sbrian * published by the Free Software Foundation. Oracle designates this 876273Sbrian * particular file as subject to the "Classpath" exception as provided 976273Sbrian * by Oracle in the LICENSE file that accompanied this code. 1076273Sbrian * 1176273Sbrian * This code is distributed in the hope that it will be useful, but WITHOUT 1276273Sbrian * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1376273Sbrian * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1476273Sbrian * version 2 for more details (a copy is included in the LICENSE file that 1576273Sbrian * accompanied this code). 1676273Sbrian * 1776273Sbrian * You should have received a copy of the GNU General Public License version 1876273Sbrian * 2 along with this work; if not, write to the Free Software Foundation, 1976273Sbrian * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2076273Sbrian * 2176273Sbrian * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2276273Sbrian * or visit www.oracle.com if you need additional information or have any 2376273Sbrian * questions. 2476273Sbrian */ 2576273Sbrianpackage com.sun.tools.jdeps; 2676273Sbrian 2776273Sbrianimport java.io.PrintWriter; 2876273Sbrianimport java.lang.module.ModuleDescriptor; 2976273Sbrianimport java.lang.module.ModuleFinder; 3076273Sbrianimport java.lang.module.ModuleReference; 3176273Sbrianimport java.util.Collections; 3276273Sbrianimport java.util.Deque; 3376273Sbrianimport java.util.HashMap; 3476273Sbrianimport java.util.HashSet; 3576273Sbrianimport java.util.LinkedList; 3676273Sbrianimport java.util.Map; 3776273Sbrianimport java.util.Set; 38189168Sdasimport java.util.function.Consumer; 3976273Sbrianimport java.util.function.Predicate; 4076273Sbrianimport java.util.stream.Collectors; 4197337Stjrimport java.util.stream.Stream; 4276273Sbrian 4376273Sbrianpublic final class Graph<T> { 4476273Sbrian private final Set<T> nodes; 4576273Sbrian private final Map<T, Set<T>> edges; 4676273Sbrian 4776273Sbrian public Graph(Set<T> nodes, Map<T, Set<T>> edges) { 4876273Sbrian this.nodes = Collections.unmodifiableSet(nodes); 4976273Sbrian this.edges = Collections.unmodifiableMap(edges); 50132078Stjr } 5176273Sbrian 5276273Sbrian public Set<T> nodes() { 5376273Sbrian return nodes; 5476273Sbrian } 5576273Sbrian 5676273Sbrian public Map<T, Set<T>> edges() { 5776273Sbrian return edges; 5876273Sbrian } 5976273Sbrian 6076273Sbrian public Set<T> adjacentNodes(T u) { 6176273Sbrian return edges.get(u); 6276273Sbrian } 6376273Sbrian 6476273Sbrian public boolean contains(T u) { 6576273Sbrian return nodes.contains(u); 6676273Sbrian } 6776273Sbrian 6876273Sbrian public Set<Edge<T>> edgesFrom(T u) { 6976273Sbrian return edges.get(u).stream() 7076273Sbrian .map(v -> new Edge<T>(u, v)) 7176273Sbrian .collect(Collectors.toSet()); 7276273Sbrian } 7376273Sbrian 7476273Sbrian /** 7576273Sbrian * Returns a new Graph after transitive reduction 76226362Sed */ 77226362Sed public Graph<T> reduce() { 78226362Sed Builder<T> builder = new Builder<>(); 7976273Sbrian nodes.stream() 8076273Sbrian .forEach(u -> { 8176273Sbrian builder.addNode(u); 8276273Sbrian edges.get(u).stream() 8376273Sbrian .filter(v -> !pathExists(u, v, false)) 8476273Sbrian .forEach(v -> builder.addEdge(u, v)); 8576273Sbrian }); 8676273Sbrian return builder.build(); 8776273Sbrian } 8876273Sbrian 8976273Sbrian /** 9092921Simp * Returns a new Graph after transitive reduction. All edges in 9192921Simp * the given g takes precedence over this graph. 9292921Simp * 9376273Sbrian * @throw IllegalArgumentException g must be a subgraph this graph 9476273Sbrian */ 9576273Sbrian public Graph<T> reduce(Graph<T> g) { 9676273Sbrian boolean subgraph = nodes.containsAll(g.nodes) && 9776273Sbrian g.edges.keySet().stream() 9876273Sbrian .allMatch(u -> adjacentNodes(u).containsAll(g.adjacentNodes(u))); 99132078Stjr if (!subgraph) { 100132078Stjr throw new IllegalArgumentException(g + " is not a subgraph of " + this); 101132078Stjr } 102132078Stjr 10376273Sbrian Builder<T> builder = new Builder<>(); 10476273Sbrian nodes.stream() 10576273Sbrian .forEach(u -> { 10676273Sbrian builder.addNode(u); 10776273Sbrian // filter the edge if there exists a path from u to v in the given g 10876273Sbrian // or there exists another path from u to v in this graph 10976273Sbrian edges.get(u).stream() 11076273Sbrian .filter(v -> !g.pathExists(u, v) && !pathExists(u, v, false)) 11176273Sbrian .forEach(v -> builder.addEdge(u, v)); 11276273Sbrian }); 11376273Sbrian 11476273Sbrian // add the overlapped edges from this graph and the given g 11576273Sbrian g.edges().keySet().stream() 11676273Sbrian .forEach(u -> g.adjacentNodes(u).stream() 11776273Sbrian .filter(v -> isAdjacent(u, v)) 11876273Sbrian .forEach(v -> builder.addEdge(u, v))); 11976273Sbrian return builder.build(); 12076273Sbrian } 12176273Sbrian 12276273Sbrian /** 12376273Sbrian * Returns nodes sorted in topological order. 12476273Sbrian */ 12576273Sbrian public Stream<T> orderedNodes() { 12676273Sbrian TopoSorter<T> sorter = new TopoSorter<>(this); 12776273Sbrian return sorter.result.stream(); 12876273Sbrian } 12976273Sbrian 13076273Sbrian /** 131226362Sed * Traverse this graph and performs the given action in topological order 13276273Sbrian */ 133144840Sstefanf public void ordered(Consumer<T> action) { 13476273Sbrian TopoSorter<T> sorter = new TopoSorter<>(this); 13576273Sbrian sorter.ordered(action); 13676273Sbrian } 137132078Stjr 138132078Stjr /** 139132078Stjr * Traverses this graph and performs the given action in reverse topological order 14076273Sbrian */ 14176273Sbrian public void reverse(Consumer<T> action) { 14276273Sbrian TopoSorter<T> sorter = new TopoSorter<>(this); 14376273Sbrian sorter.reverse(action); 14476273Sbrian } 14576273Sbrian 14676273Sbrian /** 14776273Sbrian * Returns a transposed graph from this graph 14876273Sbrian */ 14976273Sbrian public Graph<T> transpose() { 15076273Sbrian Builder<T> builder = new Builder<>(); 15176273Sbrian builder.addNodes(nodes); 152132078Stjr // reverse edges 153132078Stjr edges.keySet().forEach(u -> { 154132078Stjr edges.get(u).stream() 155132078Stjr .forEach(v -> builder.addEdge(v, u)); 156132078Stjr }); 157132078Stjr return builder.build(); 158132078Stjr } 159132078Stjr 160132078Stjr /** 161132078Stjr * Returns all nodes reachable from the given set of roots. 162132078Stjr */ 163132078Stjr public Set<T> dfs(Set<T> roots) { 164132078Stjr Deque<T> deque = new LinkedList<>(roots); 165132078Stjr Set<T> visited = new HashSet<>(); 166132078Stjr while (!deque.isEmpty()) { 167132078Stjr T u = deque.pop(); 168132078Stjr if (!visited.contains(u)) { 169132078Stjr visited.add(u); 17076273Sbrian if (contains(u)) { 17176273Sbrian adjacentNodes(u).stream() 17276273Sbrian .filter(v -> !visited.contains(v)) 17376273Sbrian .forEach(deque::push); 17476273Sbrian } 17576273Sbrian } 17676273Sbrian } 17776273Sbrian return visited; 17876273Sbrian } 17976273Sbrian 18076273Sbrian private boolean isAdjacent(T u, T v) { 18176273Sbrian return edges.containsKey(u) && edges.get(u).contains(v); 18297338Stjr } 18397338Stjr 18497338Stjr private boolean pathExists(T u, T v) { 18576273Sbrian return pathExists(u, v, true); 18676273Sbrian } 18776273Sbrian 18876273Sbrian /** 18976273Sbrian * Returns true if there exists a path from u to v in this graph. 19076273Sbrian * If includeAdjacent is false, it returns true if there exists 19197338Stjr * another path from u to v of distance > 1 19297338Stjr */ 19397338Stjr private boolean pathExists(T u, T v, boolean includeAdjacent) { 19476273Sbrian if (!nodes.contains(u) || !nodes.contains(v)) { 19576273Sbrian return false; 19676273Sbrian } 19776273Sbrian if (includeAdjacent && isAdjacent(u, v)) { 19876273Sbrian return true; 19976273Sbrian } 20076273Sbrian Deque<T> stack = new LinkedList<>(); 20176273Sbrian Set<T> visited = new HashSet<>(); 20276273Sbrian stack.push(u); 20397338Stjr while (!stack.isEmpty()) { 20497338Stjr T node = stack.pop(); 20597338Stjr if (node.equals(v)) { 20676273Sbrian return true; 20776273Sbrian } 20876273Sbrian if (!visited.contains(node)) { 20976273Sbrian visited.add(node); 21076273Sbrian edges.get(node).stream() 21176273Sbrian .filter(e -> includeAdjacent || !node.equals(u) || !e.equals(v)) 21276273Sbrian .forEach(stack::push); 21376273Sbrian } 21497338Stjr } 21597338Stjr assert !visited.contains(v); 21697338Stjr return false; 21776273Sbrian } 21876273Sbrian 21976273Sbrian public void printGraph(PrintWriter out) { 22076273Sbrian out.println("graph for " + nodes); 22176273Sbrian nodes.stream() 22276273Sbrian .forEach(u -> adjacentNodes(u).stream() 22397338Stjr .forEach(v -> out.format(" %s -> %s%n", u, v))); 22497338Stjr } 22597338Stjr 22676273Sbrian @Override 22797338Stjr public String toString() { 22897338Stjr return nodes.toString(); 22997338Stjr } 23076273Sbrian 23176273Sbrian static class Edge<T> { 23276273Sbrian final T u; 23376273Sbrian final T v; 23476273Sbrian Edge(T u, T v) { 23576273Sbrian this.u = u; 23676273Sbrian this.v = v; 23776273Sbrian } 23876273Sbrian 23976273Sbrian @Override 24076273Sbrian public String toString() { 24176273Sbrian return String.format("%s -> %s", u, v); 24276273Sbrian } 24376273Sbrian 24476273Sbrian @Override 24597337Stjr public boolean equals(Object o) { 24697337Stjr if (this == o) return true; 24776273Sbrian if (o == null || !(o instanceof Edge)) 24876273Sbrian return false; 24976273Sbrian 25076273Sbrian @SuppressWarnings("unchecked") 25176273Sbrian Edge<T> edge = (Edge<T>) o; 25276273Sbrian 253132078Stjr return u.equals(edge.u) && v.equals(edge.v); 254132078Stjr } 255132078Stjr 256132078Stjr @Override 257132078Stjr public int hashCode() { 25876273Sbrian int result = u.hashCode(); 259226362Sed result = 31 * result + v.hashCode(); 26097337Stjr return result; 26197337Stjr } 26276273Sbrian } 26376273Sbrian 26476273Sbrian static class Builder<T> { 26576273Sbrian final Set<T> nodes = new HashSet<>(); 26676273Sbrian final Map<T, Set<T>> edges = new HashMap<>(); 26776273Sbrian 26876273Sbrian public void addNode(T node) { 26976273Sbrian if (nodes.contains(node)) { 27076273Sbrian return; 271226362Sed } 27276273Sbrian nodes.add(node); 273189168Sdas edges.computeIfAbsent(node, _e -> new HashSet<>()); 274189168Sdas } 275189168Sdas 27676273Sbrian public void addNodes(Set<T> nodes) { 27776273Sbrian nodes.addAll(nodes); 27876273Sbrian } 27976273Sbrian 280165462Simp public void addEdge(T u, T v) { 28176273Sbrian addNode(u); 28276273Sbrian addNode(v); 28376273Sbrian edges.get(u).add(v); 28476273Sbrian } 28576273Sbrian 286189168Sdas public Graph<T> build() { 287189168Sdas return new Graph<T>(nodes, edges); 288189168Sdas } 28976273Sbrian } 29076273Sbrian 291189168Sdas /** 292189168Sdas * Topological sort 293132078Stjr */ 294189168Sdas static class TopoSorter<T> { 29576273Sbrian final Deque<T> result = new LinkedList<>(); 296189168Sdas final Deque<T> nodes; 297189168Sdas final Graph<T> graph; 298189168Sdas TopoSorter(Graph<T> graph) { 299189168Sdas this.graph = graph; 300189168Sdas this.nodes = new LinkedList<>(graph.nodes); 301189168Sdas sort(); 302189168Sdas } 30376273Sbrian 30476273Sbrian public void ordered(Consumer<T> action) { 30576273Sbrian result.iterator().forEachRemaining(action); 30676273Sbrian } 30776273Sbrian 30876273Sbrian public void reverse(Consumer<T> action) { 30976273Sbrian result.descendingIterator().forEachRemaining(action); 31076273Sbrian } 31176273Sbrian 31276273Sbrian private void sort() { 31376273Sbrian Deque<T> visited = new LinkedList<>(); 31476273Sbrian Deque<T> done = new LinkedList<>(); 31576273Sbrian T node; 31676273Sbrian while ((node = nodes.poll()) != null) { 31776273Sbrian if (!visited.contains(node)) { 31876273Sbrian visit(node, visited, done); 31976273Sbrian } 32076273Sbrian } 32176273Sbrian } 32276273Sbrian 32376273Sbrian private void visit(T node, Deque<T> visited, Deque<T> done) { 32476273Sbrian if (visited.contains(node)) { 32576273Sbrian if (!done.contains(node)) { 32676273Sbrian throw new IllegalArgumentException("Cyclic detected: " + 32776273Sbrian node + " " + graph.edges().get(node)); 32876273Sbrian } 32976273Sbrian return; 33076273Sbrian } 33176273Sbrian visited.add(node); 33276273Sbrian graph.edges().get(node).stream() 33376273Sbrian .forEach(x -> visit(x, visited, done)); 33476273Sbrian done.add(node); 33576273Sbrian result.addLast(node); 33676273Sbrian } 33776273Sbrian } 33876273Sbrian 33976273Sbrian public static class DotGraph { 340189168Sdas static final String ORANGE = "#e76f00"; 341189168Sdas static final String BLUE = "#437291"; 34276273Sbrian static final String GRAY = "#dddddd"; 34397337Stjr 34497337Stjr static final String REEXPORTS = ""; 34576273Sbrian static final String REQUIRES = "style=\"dashed\""; 34676273Sbrian static final String REQUIRES_BASE = "color=\"" + GRAY + "\""; 34776273Sbrian 34876273Sbrian static final Set<String> javaModules = modules(name -> 34997337Stjr (name.startsWith("java.") && !name.equals("java.smartcardio"))); 35097337Stjr static final Set<String> jdkModules = modules(name -> 351189168Sdas (name.startsWith("java.") || 352189168Sdas name.startsWith("jdk.") || 35376273Sbrian name.startsWith("javafx.")) && !javaModules.contains(name)); 35476273Sbrian 35576273Sbrian private static Set<String> modules(Predicate<String> predicate) { 35676273Sbrian return ModuleFinder.ofSystem().findAll() 35776273Sbrian .stream() 35876273Sbrian .map(ModuleReference::descriptor) 35976273Sbrian .map(ModuleDescriptor::name) 360226362Sed .filter(predicate) 36176273Sbrian .collect(Collectors.toSet()); 36276273Sbrian } 36376273Sbrian 36476273Sbrian static void printAttributes(PrintWriter out) { 36576273Sbrian out.format(" size=\"25,25\";%n"); 36676273Sbrian out.format(" nodesep=.5;%n"); 36776273Sbrian out.format(" ranksep=1.5;%n"); 36876273Sbrian out.format(" pencolor=transparent;%n"); 36976273Sbrian out.format(" node [shape=plaintext, fontname=\"DejaVuSans\", fontsize=36, margin=\".2,.2\"];%n"); 37076273Sbrian out.format(" edge [penwidth=4, color=\"#999999\", arrowhead=open, arrowsize=2];%n"); 37176273Sbrian } 37276273Sbrian 37376273Sbrian static void printNodes(PrintWriter out, Graph<String> graph) { 37476273Sbrian out.format(" subgraph se {%n"); 37576273Sbrian graph.nodes().stream() 37676273Sbrian .filter(javaModules::contains) 37776273Sbrian .forEach(mn -> out.format(" \"%s\" [fontcolor=\"%s\", group=%s];%n", 37876273Sbrian mn, ORANGE, "java")); 37976273Sbrian out.format(" }%n"); 38076273Sbrian graph.nodes().stream() 38176273Sbrian .filter(jdkModules::contains) 38276273Sbrian .forEach(mn -> out.format(" \"%s\" [fontcolor=\"%s\", group=%s];%n", 38376273Sbrian mn, BLUE, "jdk")); 38476273Sbrian 38576273Sbrian graph.nodes().stream() 38676273Sbrian .filter(mn -> !javaModules.contains(mn) && !jdkModules.contains(mn)) 38776273Sbrian .forEach(mn -> out.format(" \"%s\";%n", mn)); 38897338Stjr } 38997338Stjr 39076273Sbrian static void printEdges(PrintWriter out, Graph<String> graph, 39176273Sbrian String node, Set<String> requiresTransitive) { 39276273Sbrian graph.adjacentNodes(node).forEach(dn -> { 39376273Sbrian String attr = dn.equals("java.base") ? REQUIRES_BASE 39476273Sbrian : (requiresTransitive.contains(dn) ? REEXPORTS : REQUIRES); 39597338Stjr out.format(" \"%s\" -> \"%s\" [%s];%n", node, dn, attr); 39697338Stjr }); 39776273Sbrian } 39876273Sbrian } 39976273Sbrian 40076273Sbrian 40176273Sbrian} 402226362Sed