1 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 2 // -*- mode: C++ -*- 3 // 4 // Copyright 2020-2022 Google LLC 5 // 6 // Licensed under the Apache License v2.0 with LLVM Exceptions (the 7 // "License"); you may not use this file except in compliance with the 8 // License. You may obtain a copy of the License at 9 // 10 // https://llvm.org/LICENSE.txt 11 // 12 // Unless required by applicable law or agreed to in writing, software 13 // distributed under the License is distributed on an "AS IS" BASIS, 14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 // See the License for the specific language governing permissions and 16 // limitations under the License. 17 // 18 // Author: Giuliano Procida 19 20 #ifndef STG_SCC_H_ 21 #define STG_SCC_H_ 22 23 #include <cstddef> 24 #include <iterator> 25 #include <memory> 26 #include <optional> 27 #include <unordered_map> 28 #include <utility> 29 #include <vector> 30 31 #include "error.h" 32 33 namespace stg { 34 35 /* 36 * This is a streamlined Strongly-Connected Component finder for use with 37 * procedurally generated or explored graphs, where the nodes and edges are not 38 * known a priori. 39 * 40 * REQUIREMENTS 41 * 42 * The Node type must be copyable and have a suitable hash function. 43 * 44 * The user code must take the form of a Depth First Search which can be 45 * repeatedly invoked on unvisited nodes until the whole graph has been 46 * traversed. 47 * 48 * The user code must always follow edges to child nodes, even if it knows the 49 * node has already been visited. The SCC finder needs to know about all edges. 50 * 51 * The user code must ensure that nodes are not re-examined once they have been 52 * assigned to an SCC. The finder does not maintain any state for such nodes. 53 * 54 * GUARANTEES 55 * 56 * The SCC finder will ensure each node is examined exactly once. 57 * 58 * The SCCs will be presented in a topological order, leaves first. 59 * 60 * Note that within each SCC, nodes will be presented in DFS traversal order, 61 * roots first. However, this is just an implementation detail, not a guarantee. 62 * 63 * USAGE 64 * 65 * Before examining a node, check it's not been assigned to an SCC already and 66 * then call Open. If the node is already "open" (i.e., is already waiting to be 67 * assigned to an SCC), this will return an empty optional value and the node 68 * should not be examined. If Open succeeds, a numerical node handle will be 69 * returned and the node will be recorded as waiting to be assigned to an SCC. 70 * 71 * Now examine the node, making recursive calls to follow edges to other nodes. 72 * Information about the node can be stored provisionally, but must NOT be used 73 * to make decisions about whether to revisit it - that is Open's job. 74 * 75 * Once the examination is done, call Close, passing in the handle. If the node 76 * has been identified as the "root" of an SCC, the whole SCC will be returned 77 * as a vector of nodes. If any processing needs to be done (such as recording 78 * the nodes as visited), this should be done now. Otherwise, an empty vector 79 * will be returned. 80 * 81 * After a top-level DFS has completed, the SCC finder should be carrying no 82 * state. This can be verified by calling Empty. 83 */ 84 template <typename Node, typename Hash = std::hash<Node>> 85 class SCC { 86 public: Empty()87 bool Empty() const { 88 return open_.empty() && is_open_.empty() && root_index_.empty(); 89 } 90 Open(const Node & node)91 std::optional<size_t> Open(const Node& node) { 92 // Insertion will fail if the node is already open. 93 auto [it, inserted] = is_open_.insert({node, is_open_.size()}); 94 auto ix = it->second; 95 if (!inserted) { 96 // Pop indices to nodes which cannot be the root of their SCC. 97 while (root_index_.back() > ix) { 98 root_index_.pop_back(); 99 } 100 return {}; 101 } 102 // Unvisited, record open node and record root index. 103 open_.push_back(node); 104 root_index_.push_back(ix); 105 return {ix}; 106 } 107 Close(size_t ix)108 std::vector<Node> Close(size_t ix) { 109 std::vector<Node> scc; 110 Check(ix < open_.size()) << "internal error: illegal SCC node index"; 111 if (ix == root_index_.back()) { 112 // Close SCC. 113 root_index_.pop_back(); 114 const auto begin = open_.begin() + ix; 115 const auto end = open_.end(); 116 for (auto it = begin; it != end; ++it) { 117 is_open_.erase(*it); 118 } 119 scc.reserve(end - begin); 120 std::move(begin, end, std::back_inserter(scc)); 121 open_.erase(begin, end); 122 } 123 return scc; 124 } 125 126 private: 127 std::vector<Node> open_; // index to node 128 std::unordered_map<Node, size_t, Hash> is_open_; // node to index 129 std::vector<size_t> root_index_; 130 }; 131 132 } // namespace stg 133 134 #endif // STG_SCC_H_ 135