1 /* 2 * Copyright (C) 2021 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.base; 18 19 import static com.google.common.base.Preconditions.checkState; 20 import static java.lang.Math.min; 21 22 import com.google.common.collect.ImmutableCollection; 23 import com.google.common.collect.ImmutableList; 24 import com.google.common.collect.ImmutableSet; 25 import com.google.common.collect.Maps; 26 import com.google.common.collect.Sets; 27 import com.google.common.graph.SuccessorsFunction; 28 import java.util.ArrayDeque; 29 import java.util.ArrayList; 30 import java.util.Deque; 31 import java.util.List; 32 import java.util.Map; 33 import java.util.Set; 34 35 /** 36 * An implementation of Tarjan's algorithm for finding the SCC of a graph. This is based on the 37 * psuedo code algorithm here: 38 * http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm 39 */ 40 public final class TarjanSCCs { 41 42 /** Returns the set of strongly connected components in reverse topological order. */ compute( ImmutableCollection<NodeT> nodes, SuccessorsFunction<NodeT> successorsFunction)43 public static <NodeT> ImmutableList<ImmutableSet<NodeT>> compute( 44 ImmutableCollection<NodeT> nodes, SuccessorsFunction<NodeT> successorsFunction) { 45 return new TarjanSCC<>(nodes, successorsFunction).compute(); 46 } 47 48 private static class TarjanSCC<NodeT> { 49 private final ImmutableCollection<NodeT> nodes; 50 private final SuccessorsFunction<NodeT> successorsFunction; 51 private final Deque<NodeT> stack; 52 private final Set<NodeT> onStack; 53 private final Map<NodeT, Integer> indexes; 54 private final Map<NodeT, Integer> lowLinks; 55 private final List<ImmutableSet<NodeT>> stronglyConnectedComponents = new ArrayList<>(); 56 TarjanSCC(ImmutableCollection<NodeT> nodes, SuccessorsFunction<NodeT> successorsFunction)57 TarjanSCC(ImmutableCollection<NodeT> nodes, SuccessorsFunction<NodeT> successorsFunction) { 58 this.nodes = nodes; 59 this.successorsFunction = successorsFunction; 60 this.stack = new ArrayDeque<>(nodes.size()); 61 this.onStack = Sets.newHashSetWithExpectedSize(nodes.size()); 62 this.indexes = Maps.newHashMapWithExpectedSize(nodes.size()); 63 this.lowLinks = Maps.newHashMapWithExpectedSize(nodes.size()); 64 } 65 compute()66 private ImmutableList<ImmutableSet<NodeT>> compute() { 67 checkState(indexes.isEmpty(), "TarjanSCC#compute() can only be called once per instance!"); 68 for (NodeT node : nodes) { 69 if (!indexes.containsKey(node)) { 70 stronglyConnect(node); 71 } 72 } 73 return ImmutableList.copyOf(stronglyConnectedComponents); 74 } 75 stronglyConnect(NodeT node)76 private void stronglyConnect(NodeT node) { 77 // Set the index and lowLink for node to the smallest unused index and add it to the stack 78 lowLinks.put(node, indexes.size()); 79 indexes.put(node, indexes.size()); 80 stack.push(node); 81 onStack.add(node); 82 83 for (NodeT successor : successorsFunction.successors(node)) { 84 if (!indexes.containsKey(successor)) { 85 // Successor has not been processed. 86 stronglyConnect(successor); 87 lowLinks.put(node, min(lowLinks.get(node), lowLinks.get(successor))); 88 } else if (onStack.contains(successor)) { 89 // Successor is on the stack and hence in the current SCC. 90 lowLinks.put(node, min(lowLinks.get(node), indexes.get(successor))); 91 } else { 92 // Successor is not on the stack and hence in an already processed SCC, so ignore. 93 } 94 } 95 96 // If node is the root of the SCC, pop the stack until reaching the root to get all SCC nodes. 97 if (lowLinks.get(node).equals(indexes.get(node))) { 98 ImmutableSet.Builder<NodeT> scc = ImmutableSet.builder(); 99 NodeT currNode; 100 do { 101 currNode = stack.pop(); 102 onStack.remove(currNode); 103 scc.add(currNode); 104 } while (!node.equals(currNode)); 105 stronglyConnectedComponents.add(scc.build()); 106 } 107 } 108 } 109 TarjanSCCs()110 private TarjanSCCs() {} 111 } 112