1 /*

     2  * Copyright (c) 2014, 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 

    26 package build.tools.jigsaw;

    27 

    28 import java.io.PrintStream;

    29 import java.util.Deque;

    30 import java.util.HashMap;

    31 import java.util.HashSet;

    32 import java.util.LinkedList;

    33 import java.util.Map;

    34 import java.util.Set;

    35 

    36 public class Graph<T> {

    37     private static boolean traceOn = Boolean.getBoolean("build.tools.module.trace");

    38     private final Set<T> nodes;

    39     private final Map<T, Set<T>> edges;

    40     private Graph(Set<T> nodes, Map<T, Set<T>> edges) {

    41         this.nodes = nodes;

    42         this.edges = edges;

    43     }

    44 

    45     public Set<T> nodes() {

    46         return nodes;

    47     }

    48 

    49     public Map<T, Set<T>> edges() {

    50         return edges;

    51     }

    52 

    53     public Set<T> adjacentNodes(T u) {

    54         return edges.get(u);

    55     }

    56 

    57     /**

    58      * Returns a new Graph after transitive reduction

    59      */

    60     public Graph<T> reduce() {

    61         Graph.Builder<T> builder = new Builder<>();

    62         nodes.stream()

    63              .forEach(u -> {

    64                  builder.addNode(u);

    65                  edges.get(u).stream()

    66                          .filter(v -> !pathExists(u, v, false))

    67                          .forEach(v -> builder.addEdge(u, v));

    68              });

    69         return builder.build();

    70     }

    71 

    72     /**

    73      * Returns a new Graph after transitive reduction.  All edges in

    74      * the given g takes precedence over this graph.

    75      *

    76      * @throw IllegalArgumentException g must be a subgraph this graph

    77      */

    78     public Graph<T> reduce(Graph<T> g) {

    79         boolean subgraph = nodes.containsAll(g.nodes) && g.edges.keySet().stream()

    80                .allMatch(u -> adjacentNodes(u).containsAll(g.adjacentNodes(u)));

    81         if (!subgraph) {

    82             throw new IllegalArgumentException("the given argument is not a subgraph of this graph");

    83         }

    84 

    85         Graph.Builder<T> builder = new Builder<>();

    86         nodes.stream()

    87              .forEach(u -> {

    88                  builder.addNode(u);

    89                  // filter the edge if there exists a path from u to v in the given g

    90                  // or there exists another path from u to v in this graph

    91                  edges.get(u).stream()

    92                       .filter(v -> !g.pathExists(u, v) && !pathExists(u, v, false))

    93                       .forEach(v -> builder.addEdge(u, v));

    94              });

    95 

    96         // add the overlapped edges from this graph and the given g

    97         g.edges().keySet().stream()

    98                  .forEach(u -> g.adjacentNodes(u).stream()

    99                          .filter(v -> isAdjacent(u, v))

   100                          .forEach(v -> builder.addEdge(u, v)));

   101         return builder.build();

   102     }

   103 

   104     private boolean isAdjacent(T u, T v) {

   105         return edges.containsKey(u) && edges.get(u).contains(v);

   106     }

   107 

   108     private boolean pathExists(T u, T v) {

   109         return pathExists(u, v, true);

   110     }

   111 

   112     /**

   113      * Returns true if there exists a path from u to v in this graph.

   114      * If includeAdjacent is false, it returns true if there exists

   115      * another path from u to v of distance > 1

   116      */

   117     private boolean pathExists(T u, T v, boolean includeAdjacent) {

   118         if (!nodes.contains(u) || !nodes.contains(v)) {

   119             return false;

   120         }

   121         if (includeAdjacent && isAdjacent(u, v)) {

   122             return true;

   123         }

   124         Deque<T> stack = new LinkedList<>();

   125         Set<T> visited = new HashSet<>();

   126         stack.push(u);

   127         while (!stack.isEmpty()) {

   128             T node = stack.pop();

   129             if (node.equals(v)) {

   130                 if (traceOn) {

   131                     System.out.format("Edge %s -> %s removed%n", u, v);

   132                 }

   133                 return true;

   134             }

   135             if (!visited.contains(node)) {

   136                 visited.add(node);

   137                 edges.get(node).stream()

   138                      .filter(e -> includeAdjacent || !node.equals(u) || !e.equals(v))

   139                      .forEach(e -> stack.push(e));

   140             }

   141         }

   142         assert !visited.contains(v);

   143         return false;

   144     }

   145 

   146     void printGraph(PrintStream out) {

   147         nodes.stream()

   148              .forEach(u -> adjacentNodes(u).stream()

   149                      .forEach(v -> out.format("%s -> %s%n", u, v)));

   150     }

   151 

   152     public static class Builder<T> {

   153         final Set<T> nodes = new HashSet<>();

   154         final Map<T, Set<T>> edges = new HashMap<>();

   155         public void addNode(T node) {

   156             if (nodes.contains(node)) {

   157                 return;

   158             }

   159             nodes.add(node);

   160             edges.computeIfAbsent(node, _e -> new HashSet<>());

   161         }

   162         public void addEdge(T u, T v) {

   163             addNode(u);

   164             addNode(v);

   165             edges.get(u).add(v);

   166         }

   167         public Graph<T> build() {

   168             return new Graph<>(nodes, edges);

   169         }

   170     }

   171 }