OR-Tools  8.2
topologicalsorter.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include <algorithm>
17#include <cstddef>
18#include <map>
19#include <queue>
20#include <string>
21#include <vector>
22
25
26namespace util {
27namespace internal {
28
29namespace {
30template <typename IntQueue>
31inline void PopTop(IntQueue* q, int* top) {
32 *top = q->front();
33 q->pop();
34}
35
36template <typename C, typename F>
37void PopTop(std::priority_queue<int, C, F>* q, int* top) {
38 *top = q->top();
39 q->pop();
40}
41} // namespace
42
43template <bool stable_sort>
45 CHECK(!TraversalStarted()) << "Cannot add nodes after starting traversal";
46 CHECK_GE(node_index, 0) << "Index must not be negative";
47
48 if (static_cast<std::size_t>(node_index) >= adjacency_lists_.size()) {
49 adjacency_lists_.resize(node_index + 1);
50 }
51}
52
53// Up to a point, we detect duplicates up front and do not insert them.
54// Then we switch to using RemoveDuplicates(), see below.
55//
56// Note(user): I did benchmarks on this in November 2011, and while
57// 32 seemed too large, I did not see very significant performance
58// differences with 0, 4, 8 or 16. But since larger values of this
59// threshold mean that there will be slightly less space used up by
60// small adjacency lists in case there are repeated edges, I picked 16.
62
63template <bool stable_sort>
65 CHECK(!TraversalStarted()) << "Cannot add edges after starting traversal";
66
67 AddNode(std::max(from, to));
68
69 AdjacencyList& adj_list = adjacency_lists_[from];
70 const uint32 adj_list_size = adj_list.size();
71 if (adj_list_size <= kLazyDuplicateDetectionSizeThreshold) {
72 for (AdjacencyList::const_iterator it = adj_list.begin();
73 it != adj_list.end(); ++it) {
74 if (*it == to) {
75 return;
76 }
77 }
78 adj_list.push_back(to);
79 ++num_edges_;
80 } else {
81 adj_list.push_back(to);
82 if (++num_edges_added_since_last_duplicate_removal_ > ++num_edges_ / 2) {
83 num_edges_added_since_last_duplicate_removal_ = 0;
84 // We remove all duplicates at once, but skip lists for which the
85 // number of duplicates can't be too large, i.e. lists smaller than
86 // kLazyDuplicateDetectionSizeThreshold * 2. The overall ratio of
87 // duplicate edges remains bounded by 2/3 in the worst case.
88 num_edges_ -= RemoveDuplicates(&adjacency_lists_,
90 }
91 }
92}
93
94template <bool stable_sort>
96 int* next_node_index, bool* cyclic, std::vector<int>* output_cycle_nodes) {
97 if (!TraversalStarted()) {
98 StartTraversal();
99 }
100
101 *cyclic = false;
102 if (num_nodes_left_ == 0) {
103 return false;
104 }
105 if (nodes_with_zero_indegree_.empty()) {
106 VLOG(2) << "Not all nodes have been visited (" << num_nodes_left_
107 << " nodes left), but there aren't any zero-indegree nodes"
108 << " available. This graph is cyclic! Use ExtractCycle() for"
109 << " more information.";
110 *cyclic = true;
111 if (output_cycle_nodes != NULL) {
112 ExtractCycle(output_cycle_nodes);
113 }
114 return false;
115 }
116
117 // Pop one orphan node.
118 --num_nodes_left_;
119 PopTop(&nodes_with_zero_indegree_, next_node_index);
120
121 // Swap out the adjacency list, since we won't need it afterwards,
122 // to decrease memory usage.
123 AdjacencyList adj_list;
124 adj_list.swap(adjacency_lists_[*next_node_index]);
125
126 // Add new orphan nodes to nodes_with_zero_indegree_.
127 for (std::size_t i = 0; i < adj_list.size(); ++i) {
128 if (--indegree_[adj_list[i]] == 0) {
129 nodes_with_zero_indegree_.push(adj_list[i]);
130 }
131 }
132 return true;
133}
134
135template <bool stable_sort>
137 if (TraversalStarted()) {
138 return;
139 }
140
141 const int num_nodes = adjacency_lists_.size();
142 indegree_.assign(num_nodes, 0);
143
144 // Iterate over all adjacency lists, and fill the indegree[] vector.
145 // Note that we don't bother removing duplicates: there can't be
146 // too many, since we removed them progressively, and it is actually
147 // cheaper to keep them at this point.
148 for (int from = 0; from < num_nodes; ++from) {
149 AdjacencyList& adj_list = adjacency_lists_[from];
150 for (AdjacencyList::const_iterator it = adj_list.begin();
151 it != adj_list.end(); ++it) {
152 ++indegree_[*it];
153 }
154 }
155
156 // Initialize the nodes_with_zero_indegree_ vector.
157 for (int node = 0; node < num_nodes; ++node) {
158 if (indegree_[node] == 0) {
159 nodes_with_zero_indegree_.push(node);
160 }
161 }
162
163 num_nodes_left_ = num_nodes;
164 traversal_started_ = true;
165}
166
167// static
168template <bool stable_sort>
170 std::vector<AdjacencyList>* lists, int skip_lists_smaller_than) {
171 // We can always skip lists with less than 2 elements.
172 if (skip_lists_smaller_than < 2) {
173 skip_lists_smaller_than = 2;
174 }
175 const int n = lists->size();
176 std::vector<bool> visited(n, false);
177 int num_duplicates_removed = 0;
178 for (std::vector<AdjacencyList>::iterator list = lists->begin();
179 list != lists->end(); ++list) {
180 if (list->size() < static_cast<std::size_t>(skip_lists_smaller_than)) {
181 continue;
182 }
183 num_duplicates_removed += list->size();
184 // To optimize the duplicate removal loop, we split it in two:
185 // first, find the first duplicate, then copy the rest of the shifted
186 // adjacency list as we keep detecting duplicates.
187 AdjacencyList::iterator it = list->begin();
188 DCHECK(it != list->end());
189 while (!visited[*it]) {
190 visited[*(it++)] = true;
191 if (it == list->end()) {
192 break;
194 }
195 // Skip the shifted copy if there were no duplicates at all.
196 if (it != list->end()) {
197 AdjacencyList::iterator it2 = it;
198 while (++it != list->end()) {
199 if (!visited[*it]) {
200 visited[*it] = true;
201 *(it2++) = *it;
202 }
203 }
204 list->erase(it2, list->end());
205 }
206 for (it = list->begin(); it != list->end(); ++it) {
207 visited[*it] = false;
208 }
209 num_duplicates_removed -= list->size();
210 }
211 return num_duplicates_removed;
212}
213
214// Note(user): as of 2012-09, this implementation works in
215// O(number of edges + number of nodes), which is the theoretical best.
216// It could probably be optimized to gain a significant constant speed-up;
217// but at the cost of more code complexity.
218template <bool stable_sort>
220 std::vector<int>* cycle_nodes) const {
221 const int num_nodes = adjacency_lists_.size();
222 cycle_nodes->clear();
223 // To find a cycle, we start a DFS from each yet-unvisited node and
224 // try to find a cycle, if we don't find it then we know for sure that
225 // no cycle is reachable from any of the explored nodes (so, we don't
226 // explore them in later DFSs).
227 std::vector<bool> no_cycle_reachable_from(num_nodes, false);
228 // The DFS stack will contain a chain of nodes, from the root of the
229 // DFS to the current leaf.
230 struct DfsState {
231 int node;
232 // Points at the first child node that we did *not* yet look at.
233 std::size_t adj_list_index;
234 explicit DfsState(int _node) : node(_node), adj_list_index(0) {}
235 };
236 std::vector<DfsState> dfs_stack;
237 std::vector<bool> in_cur_stack(num_nodes, false);
238 for (int start_node = 0; start_node < num_nodes; ++start_node) {
239 if (no_cycle_reachable_from[start_node]) {
240 continue;
241 }
242 // Start the DFS.
243 dfs_stack.push_back(DfsState(start_node));
244 in_cur_stack[start_node] = true;
245 while (!dfs_stack.empty()) {
246 DfsState* cur_state = &dfs_stack.back();
247 if (cur_state->adj_list_index >=
248 adjacency_lists_[cur_state->node].size()) {
249 no_cycle_reachable_from[cur_state->node] = true;
250 in_cur_stack[cur_state->node] = false;
251 dfs_stack.pop_back();
252 continue;
253 }
254 // Look at the current child, and increase the current state's
255 // adj_list_index.
256 const int child =
257 adjacency_lists_[cur_state->node][cur_state->adj_list_index];
258 ++(cur_state->adj_list_index);
259 if (no_cycle_reachable_from[child]) {
260 continue;
261 }
262 if (in_cur_stack[child]) {
263 // We detected a cycle! Fill it and return.
264 for (;;) {
265 cycle_nodes->push_back(dfs_stack.back().node);
266 if (dfs_stack.back().node == child) {
267 std::reverse(cycle_nodes->begin(), cycle_nodes->end());
268 return;
269 }
270 dfs_stack.pop_back();
271 }
272 }
273 // Push the child onto the stack.
274 dfs_stack.push_back(DfsState(child));
275 in_cur_stack[child] = true;
276 }
277 }
278 // If we're here, then all the DFS stopped, and they never encountered
279 // a cycle (otherwise, we would have returned). Just exit; the output
280 // vector has been cleared already.
281}
282
283// Generate the templated code. Including these definitions allows us
284// to have templated code inside the .cc file and not incur linker errors.
287
288} // namespace internal
289
291 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
292 std::vector<int> cycle;
293 if (num_nodes < 1) {
294 return cycle;
295 }
296 internal::DenseIntTopologicalSorterTpl</* stable= */ false> sorter(num_nodes);
297 for (const auto& arc : arcs) {
298 sorter.AddEdge(arc.first, arc.second);
299 }
300 sorter.ExtractCycle(&cycle);
301 return cycle;
302}
303} // namespace util
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define DCHECK(condition)
Definition: base/logging.h:884
#define VLOG(verboselevel)
Definition: base/logging.h:978
void ExtractCycle(std::vector< int > *cycle_nodes) const
unsigned int uint32
static const int kLazyDuplicateDetectionSizeThreshold
std::vector< int > FindCycleInDenseIntGraph(int num_nodes, const std::vector< std::pair< int, int > > &arcs)