--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/jdk.jdeps/share/classes/com/sun/tools/jdeps/Graph.java Tue Sep 12 19:03:39 2017 +0200
@@ -0,0 +1,338 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.sun.tools.jdeps;
+
+import java.io.PrintWriter;
+import java.lang.module.ModuleDescriptor;
+import java.lang.module.ModuleFinder;
+import java.lang.module.ModuleReference;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+public final class Graph<T> {
+ private final Set<T> nodes;
+ private final Map<T, Set<T>> edges;
+
+ public Graph(Set<T> nodes, Map<T, Set<T>> edges) {
+ this.nodes = Collections.unmodifiableSet(nodes);
+ this.edges = Collections.unmodifiableMap(edges);
+ }
+
+ public Set<T> nodes() {
+ return nodes;
+ }
+
+ public Map<T, Set<T>> edges() {
+ return edges;
+ }
+
+ public Set<T> adjacentNodes(T u) {
+ return edges.get(u);
+ }
+
+ public boolean contains(T u) {
+ return nodes.contains(u);
+ }
+
+ public Set<Edge<T>> edgesFrom(T u) {
+ return edges.get(u).stream()
+ .map(v -> new Edge<T>(u, v))
+ .collect(Collectors.toSet());
+ }
+
+ /**
+ * Returns a new Graph after transitive reduction
+ */
+ public Graph<T> reduce() {
+ Builder<T> builder = new Builder<>();
+ nodes.stream()
+ .forEach(u -> {
+ builder.addNode(u);
+ edges.get(u).stream()
+ .filter(v -> !pathExists(u, v, false))
+ .forEach(v -> builder.addEdge(u, v));
+ });
+ return builder.build();
+ }
+
+ /**
+ * Returns a new Graph after transitive reduction. All edges in
+ * the given g takes precedence over this graph.
+ *
+ * @throw IllegalArgumentException g must be a subgraph this graph
+ */
+ public Graph<T> reduce(Graph<T> g) {
+ boolean subgraph = nodes.containsAll(g.nodes) &&
+ g.edges.keySet().stream()
+ .allMatch(u -> adjacentNodes(u).containsAll(g.adjacentNodes(u)));
+ if (!subgraph) {
+ throw new IllegalArgumentException(g + " is not a subgraph of " + this);
+ }
+
+ Builder<T> builder = new Builder<>();
+ nodes.stream()
+ .forEach(u -> {
+ builder.addNode(u);
+ // filter the edge if there exists a path from u to v in the given g
+ // or there exists another path from u to v in this graph
+ edges.get(u).stream()
+ .filter(v -> !g.pathExists(u, v) && !pathExists(u, v, false))
+ .forEach(v -> builder.addEdge(u, v));
+ });
+
+ // add the overlapped edges from this graph and the given g
+ g.edges().keySet().stream()
+ .forEach(u -> g.adjacentNodes(u).stream()
+ .filter(v -> isAdjacent(u, v))
+ .forEach(v -> builder.addEdge(u, v)));
+ return builder.build().reduce();
+ }
+
+ /**
+ * Returns nodes sorted in topological order.
+ */
+ public Stream<T> orderedNodes() {
+ TopoSorter<T> sorter = new TopoSorter<>(this);
+ return sorter.result.stream();
+ }
+
+ /**
+ * Traverse this graph and performs the given action in topological order
+ */
+ public void ordered(Consumer<T> action) {
+ TopoSorter<T> sorter = new TopoSorter<>(this);
+ sorter.ordered(action);
+ }
+
+ /**
+ * Traverses this graph and performs the given action in reverse topological order
+ */
+ public void reverse(Consumer<T> action) {
+ TopoSorter<T> sorter = new TopoSorter<>(this);
+ sorter.reverse(action);
+ }
+
+ /**
+ * Returns a transposed graph from this graph
+ */
+ public Graph<T> transpose() {
+ Builder<T> builder = new Builder<>();
+ builder.addNodes(nodes);
+ // reverse edges
+ edges.keySet().forEach(u -> {
+ edges.get(u).stream()
+ .forEach(v -> builder.addEdge(v, u));
+ });
+ return builder.build();
+ }
+
+ /**
+ * Returns all nodes reachable from the given set of roots.
+ */
+ public Set<T> dfs(Set<T> roots) {
+ Deque<T> deque = new LinkedList<>(roots);
+ Set<T> visited = new HashSet<>();
+ while (!deque.isEmpty()) {
+ T u = deque.pop();
+ if (!visited.contains(u)) {
+ visited.add(u);
+ if (contains(u)) {
+ adjacentNodes(u).stream()
+ .filter(v -> !visited.contains(v))
+ .forEach(deque::push);
+ }
+ }
+ }
+ return visited;
+ }
+
+ private boolean isAdjacent(T u, T v) {
+ return edges.containsKey(u) && edges.get(u).contains(v);
+ }
+
+ private boolean pathExists(T u, T v) {
+ return pathExists(u, v, true);
+ }
+
+ /**
+ * Returns true if there exists a path from u to v in this graph.
+ * If includeAdjacent is false, it returns true if there exists
+ * another path from u to v of distance > 1
+ */
+ private boolean pathExists(T u, T v, boolean includeAdjacent) {
+ if (!nodes.contains(u) || !nodes.contains(v)) {
+ return false;
+ }
+ if (includeAdjacent && isAdjacent(u, v)) {
+ return true;
+ }
+ Deque<T> stack = new LinkedList<>();
+ Set<T> visited = new HashSet<>();
+ stack.push(u);
+ while (!stack.isEmpty()) {
+ T node = stack.pop();
+ if (node.equals(v)) {
+ return true;
+ }
+ if (!visited.contains(node)) {
+ visited.add(node);
+ edges.get(node).stream()
+ .filter(e -> includeAdjacent || !node.equals(u) || !e.equals(v))
+ .forEach(stack::push);
+ }
+ }
+ assert !visited.contains(v);
+ return false;
+ }
+
+ public void printGraph(PrintWriter out) {
+ out.println("graph for " + nodes);
+ nodes.stream()
+ .forEach(u -> adjacentNodes(u).stream()
+ .forEach(v -> out.format(" %s -> %s%n", u, v)));
+ }
+
+ @Override
+ public String toString() {
+ return nodes.toString();
+ }
+
+ static class Edge<T> {
+ final T u;
+ final T v;
+ Edge(T u, T v) {
+ this.u = u;
+ this.v = v;
+ }
+
+ @Override
+ public String toString() {
+ return String.format("%s -> %s", u, v);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (o == null || !(o instanceof Edge))
+ return false;
+
+ @SuppressWarnings("unchecked")
+ Edge<T> edge = (Edge<T>) o;
+
+ return u.equals(edge.u) && v.equals(edge.v);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = u.hashCode();
+ result = 31 * result + v.hashCode();
+ return result;
+ }
+ }
+
+ static class Builder<T> {
+ final Set<T> nodes = new HashSet<>();
+ final Map<T, Set<T>> edges = new HashMap<>();
+
+ public void addNode(T node) {
+ if (nodes.contains(node)) {
+ return;
+ }
+ nodes.add(node);
+ edges.computeIfAbsent(node, _e -> new HashSet<>());
+ }
+
+ public void addNodes(Set<T> nodes) {
+ this.nodes.addAll(nodes);
+ }
+
+ public void addEdge(T u, T v) {
+ addNode(u);
+ addNode(v);
+ edges.get(u).add(v);
+ }
+
+ public Graph<T> build() {
+ return new Graph<T>(nodes, edges);
+ }
+ }
+
+ /**
+ * Topological sort
+ */
+ static class TopoSorter<T> {
+ final Deque<T> result = new LinkedList<>();
+ final Deque<T> nodes;
+ final Graph<T> graph;
+ TopoSorter(Graph<T> graph) {
+ this.graph = graph;
+ this.nodes = new LinkedList<>(graph.nodes);
+ sort();
+ }
+
+ public void ordered(Consumer<T> action) {
+ result.iterator().forEachRemaining(action);
+ }
+
+ public void reverse(Consumer<T> action) {
+ result.descendingIterator().forEachRemaining(action);
+ }
+
+ private void sort() {
+ Deque<T> visited = new LinkedList<>();
+ Deque<T> done = new LinkedList<>();
+ T node;
+ while ((node = nodes.poll()) != null) {
+ if (!visited.contains(node)) {
+ visit(node, visited, done);
+ }
+ }
+ }
+
+ private void visit(T node, Deque<T> visited, Deque<T> done) {
+ if (visited.contains(node)) {
+ if (!done.contains(node)) {
+ throw new IllegalArgumentException("Cyclic detected: " +
+ node + " " + graph.edges().get(node));
+ }
+ return;
+ }
+ visited.add(node);
+ graph.edges().get(node).stream()
+ .forEach(x -> visit(x, visited, done));
+ done.add(node);
+ result.addLast(node);
+ }
+ }
+}