/*
* Copyright (c) 2016, 2017, 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.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;
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 ArrayDeque<>(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 ArrayDeque<>();
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 ArrayDeque<>();
final Graph<T> graph;
TopoSorter(Graph<T> graph) {
this.graph = graph;
sort();
}
public void ordered(Consumer<T> action) {
/**代码未完, 请加载全部代码(NowJava.com).**/