Graph.java revision 3827:44bdefe64114
10Sduke/* 29302Sdholmes * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. 30Sduke * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 40Sduke * 50Sduke * This code is free software; you can redistribute it and/or modify it 60Sduke * under the terms of the GNU General Public License version 2 only, as 70Sduke * published by the Free Software Foundation. Oracle designates this 80Sduke * particular file as subject to the "Classpath" exception as provided 90Sduke * by Oracle in the LICENSE file that accompanied this code. 100Sduke * 110Sduke * This code is distributed in the hope that it will be useful, but WITHOUT 120Sduke * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 130Sduke * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 140Sduke * version 2 for more details (a copy is included in the LICENSE file that 150Sduke * accompanied this code). 160Sduke * 170Sduke * You should have received a copy of the GNU General Public License version 180Sduke * 2 along with this work; if not, write to the Free Software Foundation, 191472Strims * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 201472Strims * 211472Strims * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 220Sduke * or visit www.oracle.com if you need additional information or have any 230Sduke * questions. 240Sduke */ 251879Sstefankpackage com.sun.tools.jdeps; 261879Sstefank 271879Sstefankimport java.io.PrintWriter; 281879Sstefankimport java.lang.module.ModuleDescriptor; 290Sdukeimport java.lang.module.ModuleFinder; 300Sdukeimport java.lang.module.ModuleReference; 310Sdukeimport java.util.Collections; 320Sdukeimport java.util.Deque; 330Sdukeimport java.util.HashMap; 340Sdukeimport java.util.HashSet; 350Sdukeimport java.util.LinkedList; 360Sdukeimport java.util.Map; 370Sdukeimport java.util.Set; 380Sdukeimport java.util.function.Consumer; 390Sdukeimport java.util.function.Predicate; 400Sdukeimport java.util.stream.Collectors; 410Sdukeimport java.util.stream.Stream; 420Sduke 430Sdukepublic final class Graph<T> { 440Sduke private final Set<T> nodes; 450Sduke private final Map<T, Set<T>> edges; 460Sduke 470Sduke public Graph(Set<T> nodes, Map<T, Set<T>> edges) { 480Sduke this.nodes = Collections.unmodifiableSet(nodes); 490Sduke this.edges = Collections.unmodifiableMap(edges); 500Sduke } 510Sduke 520Sduke public Set<T> nodes() { 530Sduke return nodes; 540Sduke } 550Sduke 560Sduke public Map<T, Set<T>> edges() { 570Sduke return edges; 580Sduke } 590Sduke 600Sduke public Set<T> adjacentNodes(T u) { 610Sduke return edges.get(u); 620Sduke } 630Sduke 640Sduke public boolean contains(T u) { 650Sduke return nodes.contains(u); 660Sduke } 670Sduke 680Sduke public Set<Edge<T>> edgesFrom(T u) { 690Sduke return edges.get(u).stream() 700Sduke .map(v -> new Edge<T>(u, v)) 710Sduke .collect(Collectors.toSet()); 720Sduke } 730Sduke 740Sduke /** 750Sduke * Returns a new Graph after transitive reduction 760Sduke */ 770Sduke public Graph<T> reduce() { 780Sduke Builder<T> builder = new Builder<>(); 790Sduke nodes.stream() 800Sduke .forEach(u -> { 810Sduke builder.addNode(u); 820Sduke edges.get(u).stream() 830Sduke .filter(v -> !pathExists(u, v, false)) 840Sduke .forEach(v -> builder.addEdge(u, v)); 850Sduke }); 860Sduke return builder.build(); 870Sduke } 880Sduke 890Sduke /** 900Sduke * Returns a new Graph after transitive reduction. All edges in 910Sduke * the given g takes precedence over this graph. 920Sduke * 930Sduke * @throw IllegalArgumentException g must be a subgraph this graph 940Sduke */ 950Sduke public Graph<T> reduce(Graph<T> g) { 960Sduke boolean subgraph = nodes.containsAll(g.nodes) && 970Sduke g.edges.keySet().stream() 980Sduke .allMatch(u -> adjacentNodes(u).containsAll(g.adjacentNodes(u))); 990Sduke if (!subgraph) { 1000Sduke throw new IllegalArgumentException(g + " is not a subgraph of " + this); 1010Sduke } 1020Sduke 1030Sduke Builder<T> builder = new Builder<>(); 1040Sduke nodes.stream() 1050Sduke .forEach(u -> { 1060Sduke builder.addNode(u); 1070Sduke // filter the edge if there exists a path from u to v in the given g 1080Sduke // 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(); 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 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 339 public static class DotGraph { 340 static final String ORANGE = "#e76f00"; 341 static final String BLUE = "#437291"; 342 static final String GRAY = "#dddddd"; 343 344 static final String REEXPORTS = ""; 345 static final String REQUIRES = "style=\"dashed\""; 346 static final String REQUIRES_BASE = "color=\"" + GRAY + "\""; 347 348 static final Set<String> javaModules = modules(name -> 349 (name.startsWith("java.") && !name.equals("java.smartcardio"))); 350 static final Set<String> jdkModules = modules(name -> 351 (name.startsWith("java.") || 352 name.startsWith("jdk.") || 353 name.startsWith("javafx.")) && !javaModules.contains(name)); 354 355 private static Set<String> modules(Predicate<String> predicate) { 356 return ModuleFinder.ofSystem().findAll() 357 .stream() 358 .map(ModuleReference::descriptor) 359 .map(ModuleDescriptor::name) 360 .filter(predicate) 361 .collect(Collectors.toSet()); 362 } 363 364 static void printAttributes(PrintWriter out) { 365 out.format(" size=\"25,25\";%n"); 366 out.format(" nodesep=.5;%n"); 367 out.format(" ranksep=1.5;%n"); 368 out.format(" pencolor=transparent;%n"); 369 out.format(" node [shape=plaintext, fontname=\"DejaVuSans\", fontsize=36, margin=\".2,.2\"];%n"); 370 out.format(" edge [penwidth=4, color=\"#999999\", arrowhead=open, arrowsize=2];%n"); 371 } 372 373 static void printNodes(PrintWriter out, Graph<String> graph) { 374 out.format(" subgraph se {%n"); 375 graph.nodes().stream() 376 .filter(javaModules::contains) 377 .forEach(mn -> out.format(" \"%s\" [fontcolor=\"%s\", group=%s];%n", 378 mn, ORANGE, "java")); 379 out.format(" }%n"); 380 graph.nodes().stream() 381 .filter(jdkModules::contains) 382 .forEach(mn -> out.format(" \"%s\" [fontcolor=\"%s\", group=%s];%n", 383 mn, BLUE, "jdk")); 384 385 graph.nodes().stream() 386 .filter(mn -> !javaModules.contains(mn) && !jdkModules.contains(mn)) 387 .forEach(mn -> out.format(" \"%s\";%n", mn)); 388 } 389 390 static void printEdges(PrintWriter out, Graph<String> graph, 391 String node, Set<String> requiresTransitive) { 392 graph.adjacentNodes(node).forEach(dn -> { 393 String attr = dn.equals("java.base") ? REQUIRES_BASE 394 : (requiresTransitive.contains(dn) ? REEXPORTS : REQUIRES); 395 out.format(" \"%s\" -> \"%s\" [%s];%n", node, dn, attr); 396 }); 397 } 398 } 399 400 401} 402