42 #ifndef UTIL_GRAPH_STRONGLY_CONNECTED_COMPONENTS_H_
43 #define UTIL_GRAPH_STRONGLY_CONNECTED_COMPONENTS_H_
48 #include "ortools/base/logging.h"
49 #include "ortools/base/macros.h"
71 template <
typename NodeIndex,
typename Graph,
typename SccOutput>
73 const Graph& graph, SccOutput* components);
81 template <
typename NodeIndex>
102 template <
typename NodeIndex,
typename Graph,
typename SccOutput>
107 SccOutput* components) {
110 scc_start_index_.clear();
111 node_index_.assign(num_nodes, 0);
112 node_to_process_.clear();
120 for (
NodeIndex base_node = 0; base_node < num_nodes; ++base_node) {
121 if (node_index_[base_node] != 0)
continue;
122 DCHECK_EQ(0, node_to_process_.size());
123 node_to_process_.push_back(base_node);
125 const NodeIndex node = node_to_process_.back();
126 const NodeIndex index = node_index_[node];
129 scc_stack_.push_back(node);
130 current_scc_start = scc_stack_.size();
131 node_index_[node] = current_scc_start;
132 scc_start_index_.push_back(current_scc_start);
135 NodeIndex min_head_index = kSettledIndex;
136 for (
const NodeIndex head : graph[node]) {
137 const NodeIndex head_index = node_index_[head];
138 if (head_index == 0) {
139 node_to_process_.push_back(head);
142 min_head_index = std::min(min_head_index, head_index);
150 while (current_scc_start > min_head_index) {
151 scc_start_index_.pop_back();
152 current_scc_start = scc_start_index_.back();
155 node_to_process_.pop_back();
156 if (current_scc_start == index) {
158 components->emplace_back(&scc_stack_[current_scc_start - 1],
159 &scc_stack_[0] + scc_stack_.size());
160 for (
int i = current_scc_start - 1; i < scc_stack_.size(); ++i) {
161 node_index_[scc_stack_[i]] = kSettledIndex;
163 scc_stack_.resize(current_scc_start - 1);
164 scc_start_index_.pop_back();
166 scc_start_index_.empty() ? 0 : scc_start_index_.back();
169 }
while (!node_to_process_.empty());
177 return node_index_[node] > 0 && node_index_[node] < kSettledIndex;
181 static constexpr
NodeIndex kSettledIndex =
182 std::numeric_limits<NodeIndex>::max();
187 std::vector<NodeIndex> scc_stack_;
193 std::vector<NodeIndex> scc_start_index_;
201 std::vector<NodeIndex> node_index_;
206 std::vector<NodeIndex> node_to_process_;
210 template <
typename NodeIndex,
typename Graph,
typename SccOutput>
213 SccOutput* components) {
218 #endif // UTIL_GRAPH_STRONGLY_CONNECTED_COMPONENTS_H_