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