content: /*
   * 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 openjdk.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);
          }
      }
  }
  