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
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);
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 }
|
1 /*
2 * Copyright (c) 2016, 2017, 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.util.ArrayDeque;
29 import java.util.Collections;
30 import java.util.Deque;
31 import java.util.HashMap;
32 import java.util.HashSet;
33 import java.util.Map;
34 import java.util.Set;
35 import java.util.function.Consumer;
36 import java.util.stream.Collectors;
37 import java.util.stream.Stream;
38
39 public final class Graph<T> {
40 private final Set<T> nodes;
41 private final Map<T, Set<T>> edges;
42
43 public Graph(Set<T> nodes, Map<T, Set<T>> edges) {
44 this.nodes = Collections.unmodifiableSet(nodes);
45 this.edges = Collections.unmodifiableMap(edges);
46 }
47
48 public Set<T> nodes() {
49 return nodes;
50 }
51
52 public Map<T, Set<T>> edges() {
53 return edges;
54 }
55
140 }
141
142 /**
143 * Returns a transposed graph from this graph
144 */
145 public Graph<T> transpose() {
146 Builder<T> builder = new Builder<>();
147 builder.addNodes(nodes);
148 // reverse edges
149 edges.keySet().forEach(u -> {
150 edges.get(u).stream()
151 .forEach(v -> builder.addEdge(v, u));
152 });
153 return builder.build();
154 }
155
156 /**
157 * Returns all nodes reachable from the given set of roots.
158 */
159 public Set<T> dfs(Set<T> roots) {
160 Deque<T> deque = new ArrayDeque<>(roots);
161 Set<T> visited = new HashSet<>();
162 while (!deque.isEmpty()) {
163 T u = deque.pop();
164 if (!visited.contains(u)) {
165 visited.add(u);
166 if (contains(u)) {
167 adjacentNodes(u).stream()
168 .filter(v -> !visited.contains(v))
169 .forEach(deque::push);
170 }
171 }
172 }
173 return visited;
174 }
175
176 private boolean isAdjacent(T u, T v) {
177 return edges.containsKey(u) && edges.get(u).contains(v);
178 }
179
180 private boolean pathExists(T u, T v) {
181 return pathExists(u, v, true);
182 }
183
184 /**
185 * Returns true if there exists a path from u to v in this graph.
186 * If includeAdjacent is false, it returns true if there exists
187 * another path from u to v of distance > 1
188 */
189 private boolean pathExists(T u, T v, boolean includeAdjacent) {
190 if (!nodes.contains(u) || !nodes.contains(v)) {
191 return false;
192 }
193 if (includeAdjacent && isAdjacent(u, v)) {
194 return true;
195 }
196 Deque<T> stack = new ArrayDeque<>();
197 Set<T> visited = new HashSet<>();
198 stack.push(u);
199 while (!stack.isEmpty()) {
200 T node = stack.pop();
201 if (node.equals(v)) {
202 return true;
203 }
204 if (!visited.contains(node)) {
205 visited.add(node);
206 edges.get(node).stream()
207 .filter(e -> includeAdjacent || !node.equals(u) || !e.equals(v))
208 .forEach(stack::push);
209 }
210 }
211 assert !visited.contains(v);
212 return false;
213 }
214
215 public void printGraph(PrintWriter out) {
216 out.println("graph for " + nodes);
271
272 public void addNodes(Set<T> nodes) {
273 this.nodes.addAll(nodes);
274 }
275
276 public void addEdge(T u, T v) {
277 addNode(u);
278 addNode(v);
279 edges.get(u).add(v);
280 }
281
282 public Graph<T> build() {
283 return new Graph<T>(nodes, edges);
284 }
285 }
286
287 /**
288 * Topological sort
289 */
290 static class TopoSorter<T> {
291 final Deque<T> result = new ArrayDeque<>();
292 final Graph<T> graph;
293 TopoSorter(Graph<T> graph) {
294 this.graph = graph;
295 sort();
296 }
297
298 public void ordered(Consumer<T> action) {
299 result.iterator().forEachRemaining(action);
300 }
301
302 public void reverse(Consumer<T> action) {
303 result.descendingIterator().forEachRemaining(action);
304 }
305
306 private void sort() {
307 Set<T> visited = new HashSet<>();
308 Set<T> done = new HashSet<>();
309 for (T node : graph.nodes()) {
310 if (!visited.contains(node)) {
311 visit(node, visited, done);
312 }
313 }
314 }
315
316 private void visit(T node, Set<T> visited, Set<T> done) {
317 if (visited.contains(node)) {
318 if (!done.contains(node)) {
319 throw new IllegalArgumentException("Cyclic detected: " +
320 node + " " + graph.edges().get(node));
321 }
322 return;
323 }
324 visited.add(node);
325 graph.edges().get(node).stream()
326 .forEach(x -> visit(x, visited, done));
327 done.add(node);
328 result.addLast(node);
329 }
330 }
331 }
|