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 }