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 <exception> 25 #include <functional> 26 #include <iterator> 27 #include <optional> 28 #include <unordered_map> 29 #include <utility> 30 #include <vector> 31 32 #include "error.h" 33 34 namespace stg { 35 36 /* 37 * This is a streamlined Strongly-Connected Component finder for use with 38 * procedurally generated or explored graphs, where the nodes and edges are not 39 * known a priori. 40 * 41 * REQUIREMENTS 42 * 43 * The Node type must be copyable and have a suitable hash function. 44 * 45 * The user code must take the form of a Depth First Search which can be 46 * repeatedly invoked on unvisited nodes until the whole graph has been 47 * traversed. 48 * 49 * The user code must always follow edges to child nodes, even if it knows the 50 * node has already been visited. The SCC finder needs to know about all edges. 51 * 52 * The user code must ensure that nodes are not re-examined once they have been 53 * assigned to an SCC. The finder does not maintain any state for such nodes. 54 * 55 * GUARANTEES 56 * 57 * The SCC finder will ensure each node is examined exactly once. 58 * 59 * The SCCs will be presented in a topological order, leaves first. 60 * 61 * Note that within each SCC, nodes will be presented in DFS traversal order, 62 * roots first. However, this is just an implementation detail, not a guarantee. 63 * 64 * USAGE 65 * 66 * Create an SCC finder with a lifetime bracketing a top-level DFS invocation. 67 * 68 * Before examining a node, check it's not been assigned to an SCC already and 69 * then call Open. If the node is already "open" (i.e., is already waiting to be 70 * assigned to an SCC), this will return an empty optional value and the node 71 * should not be examined. If Open succeeds, a numerical node handle will be 72 * returned and the node will be recorded as waiting to be assigned to an SCC. 73 * 74 * Now examine the node, making recursive calls to follow edges to other nodes. 75 * Information about the node can be stored provisionally, but must NOT be used 76 * to make decisions about whether to revisit it - that is Open's job. 77 * 78 * Once the examination is done, call Close, passing in the handle. If the node 79 * has been identified as the "root" of an SCC, the whole SCC will be returned 80 * as a vector of nodes. If any processing needs to be done (such as recording 81 * the nodes as visited), this should be done now. Otherwise, an empty vector 82 * will be returned. 83 * 84 * On destruction, after a top-level DFS invocation has completed, the SCC 85 * finder will check that it is carrying no state. 86 */ 87 template <typename Node, typename Hash = std::hash<Node>> 88 class SCC { 89 public: ~SCC()90 ~SCC() noexcept(false) { 91 if (std::uncaught_exceptions() == 0) { 92 Check(open_.empty() && is_open_.empty() && root_index_.empty()) 93 << "internal error: SCC state broken"; 94 } 95 } 96 Open(const Node & node)97 std::optional<size_t> Open(const Node& node) { 98 // Insertion will fail if the node is already open. 99 auto [it, inserted] = is_open_.insert({node, is_open_.size()}); 100 auto ix = it->second; 101 if (!inserted) { 102 // Pop indices to nodes which cannot be the root of their SCC. 103 while (root_index_.back() > ix) { 104 root_index_.pop_back(); 105 } 106 return {}; 107 } 108 // Unvisited, record open node and record root index. 109 open_.push_back(node); 110 root_index_.push_back(ix); 111 return {ix}; 112 } 113 Close(size_t ix)114 std::vector<Node> Close(size_t ix) { 115 std::vector<Node> scc; 116 Check(ix < open_.size()) << "internal error: illegal SCC node index"; 117 if (ix == root_index_.back()) { 118 // Close SCC. 119 root_index_.pop_back(); 120 const auto begin = open_.begin() + ix; 121 const auto end = open_.end(); 122 for (auto it = begin; it != end; ++it) { 123 is_open_.erase(*it); 124 } 125 scc.reserve(end - begin); 126 std::move(begin, end, std::back_inserter(scc)); 127 open_.erase(begin, end); 128 } 129 return scc; 130 } 131 132 private: 133 std::vector<Node> open_; // index to node 134 std::unordered_map<Node, size_t, Hash> is_open_; // node to index 135 std::vector<size_t> root_index_; 136 }; 137 138 } // namespace stg 139 140 #endif // STG_SCC_H_ 141