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 
23 #include "ortools/base/map_util.h"
24 #include "ortools/base/stl_util.h"
25 
26 namespace util {
27 namespace internal {
28 
29 namespace {
30 template <typename IntQueue>
31 inline void PopTop(IntQueue* q, int* top) {
32  *top = q->front();
33  q->pop();
34 }
35 
36 template <typename C, typename F>
37 void PopTop(std::priority_queue<int, C, F>* q, int* top) {
38  *top = q->top();
39  q->pop();
40 }
41 } // namespace
42 
43 template <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 
63 template <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 
94 template <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 
135 template <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
168 template <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;
193  }
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.
218 template <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 
290 std::vector<int> FindCycleInDenseIntGraph(
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
bool GetNext(int *next_node_index, bool *cyclic, std::vector< int > *output_cycle_nodes=NULL)
static int RemoveDuplicates(std::vector< AdjacencyList > *lists, int skip_lists_smaller_than)
unsigned int uint32
static const int kLazyDuplicateDetectionSizeThreshold
std::vector< int > FindCycleInDenseIntGraph(int num_nodes, const std::vector< std::pair< int, int >> &arcs)