Graph.java

/*
 * 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) {
            result.iterator().forEachRemaining(action);
        }

        public void reverse(Consumer<T> action) {
            result.descendingIterator().forEachRemaining(action);
        }

        private void sort() {
            Set<T> visited = new HashSet<>();
            Set<T> done = new HashSet<>();
            for (T node : graph.nodes()) {
                if (!visited.contains(node)) {
                    visit(node, visited, done);
                }
            }
        }

        private void visit(T node, Set<T> visited, Set<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);
        }
    }
}