1 /* 2 * Copyright (C) 2018 The Dagger Authors. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package dagger.internal.codegen.extension; 18 19 import static com.google.common.collect.Sets.difference; 20 import static com.google.common.graph.Graphs.reachableNodes; 21 22 import com.google.common.collect.ImmutableList; 23 import com.google.common.collect.ImmutableSet; 24 import com.google.common.graph.Graph; 25 import com.google.common.graph.SuccessorsFunction; 26 import java.util.ArrayDeque; 27 import java.util.HashMap; 28 import java.util.Map; 29 import java.util.Queue; 30 import java.util.Set; 31 32 /** Utility methods for {@link com.google.common.graph} types. */ 33 public final class DaggerGraphs { 34 /** 35 * Returns a shortest path from {@code nodeU} to {@code nodeV} in {@code graph} as a list of the 36 * nodes visited in sequence, including both {@code nodeU} and {@code nodeV}. (Note that there may 37 * be many possible shortest paths.) 38 * 39 * <p>If {@code nodeV} is not {@link 40 * com.google.common.graph.Graphs#reachableNodes(com.google.common.graph.Graph, Object) reachable} 41 * from {@code nodeU}, the list returned is empty. 42 * 43 * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not present in {@code 44 * graph} 45 */ shortestPath(SuccessorsFunction<N> graph, N nodeU, N nodeV)46 public static <N> ImmutableList<N> shortestPath(SuccessorsFunction<N> graph, N nodeU, N nodeV) { 47 if (nodeU.equals(nodeV)) { 48 return ImmutableList.of(nodeU); 49 } 50 Set<N> successors = ImmutableSet.copyOf(graph.successors(nodeU)); 51 if (successors.contains(nodeV)) { 52 return ImmutableList.of(nodeU, nodeV); 53 } 54 55 Map<N, N> visitedNodeToPathPredecessor = new HashMap<>(); // encodes shortest path tree 56 for (N node : successors) { 57 visitedNodeToPathPredecessor.put(node, nodeU); 58 } 59 Queue<N> currentNodes = new ArrayDeque<N>(successors); 60 Queue<N> nextNodes = new ArrayDeque<N>(); 61 62 // Perform a breadth-first traversal starting with the successors of nodeU. 63 while (!currentNodes.isEmpty()) { 64 while (!currentNodes.isEmpty()) { 65 N currentNode = currentNodes.remove(); 66 for (N nextNode : graph.successors(currentNode)) { 67 if (visitedNodeToPathPredecessor.containsKey(nextNode)) { 68 continue; // we already have a shortest path to nextNode 69 } 70 visitedNodeToPathPredecessor.put(nextNode, currentNode); 71 if (nextNode.equals(nodeV)) { 72 ImmutableList.Builder<N> builder = ImmutableList.builder(); 73 N node = nodeV; 74 builder.add(node); 75 while (!node.equals(nodeU)) { 76 node = visitedNodeToPathPredecessor.get(node); 77 builder.add(node); 78 } 79 return builder.build().reverse(); 80 } 81 nextNodes.add(nextNode); 82 } 83 } 84 Queue<N> emptyQueue = currentNodes; 85 currentNodes = nextNodes; 86 nextNodes = emptyQueue; // reusing empty queue faster than allocating new one 87 } 88 89 return ImmutableList.of(); 90 } 91 92 /** Returns the nodes in a graph that are not reachable from a node. */ unreachableNodes(Graph<N> graph, N node)93 public static <N> ImmutableSet<N> unreachableNodes(Graph<N> graph, N node) { 94 return ImmutableSet.copyOf(difference(graph.nodes(), reachableNodes(graph, node))); 95 } 96 DaggerGraphs()97 private DaggerGraphs() {} 98 } 99