OR-Tools  8.2
topologicalsorter.h
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 
14 // TopologicalSorter provides topologically sorted traversal of the
15 // nodes of a directed acyclic graph (DAG) with up to INT_MAX nodes.
16 // It sorts ancestor nodes before their descendants.
17 //
18 // If your graph is not a DAG and you're reading this, you are probably
19 // looking for ortools/graph/strongly_connected_components.h which does
20 // the topological decomposition of a directed graph.
21 //
22 // EXAMPLE:
23 //
24 // vector<int> result;
25 // vector<string> nodes = {"a", "b", "c"};
26 // vector<pair<string, string>> arcs = {{"a", "c"}, {"a", "b"}, {"b", "c"}};
27 // if (util::StableTopologicalSort(num_nodes, arcs, &result)) {
28 // LOG(INFO) << "The topological order is: " << gtl::LogContainer(result);
29 // } else {
30 // LOG(INFO) << "The graph is cyclic.";
31 // // Note: you can extract a cycle with the TopologicalSorter class, or
32 // // with the API defined in circularity_detector.h.
33 // }
34 // // This will be successful and result will be equal to {"a", "b", "c"}.
35 //
36 // There are 8 flavors of topological sort, from these 3 bits:
37 // - There are OrDie() versions that directly return the topological order, or
38 // crash if a cycle is detected (and LOG the cycle).
39 // - There are type-generic versions that can take any node type (including
40 // non-dense integers), but slower, or the "dense int" versions which requires
41 // nodes to be a dense interval [0..num_nodes-1]. Note that the type must
42 // be compatible with LOG << T if you're using the OrDie() version.
43 // - The sorting can be either stable or not. "Stable" essentially means that it
44 // will preserve the order of nodes, if possible. More precisely, the returned
45 // topological order will be the lexicographically minimal valid order, where
46 // "lexicographic" applies to the indices of the nodes.
47 //
48 // TopologicalSort()
49 // TopologicalSortOrDie()
50 // StableTopologicalSort()
51 // StableTopologicalSortOrDie()
52 // DenseIntTopologicalSort()
53 // DenseIntTopologicalSortOrDie()
54 // DenseIntStableTopologicalSort()
55 // DenseIntStableTopologicalSortOrDie()
56 //
57 // If you need more control, or a step-by-step topological sort, see the
58 // TopologicalSorter classes below.
59 
60 #ifndef UTIL_GRAPH_TOPOLOGICALSORTER_H__
61 #define UTIL_GRAPH_TOPOLOGICALSORTER_H__
62 
63 #include <queue>
64 #include <type_traits>
65 #include <vector>
66 
67 #include "absl/container/flat_hash_map.h"
69 #include "ortools/base/logging.h"
70 #include "ortools/base/macros.h"
71 #include "ortools/base/map_util.h"
72 #include "ortools/base/stl_util.h"
73 
74 namespace util {
75 
76 // Returns true if the graph was a DAG, and outputs the topological order in
77 // "topological_order". Returns false if the graph is cyclic.
78 // Works in O(num_nodes + arcs.size()), and is pretty fast.
79 ABSL_MUST_USE_RESULT inline bool DenseIntTopologicalSort(
80  int num_nodes, const std::vector<std::pair<int, int>>& arcs,
81  std::vector<int>* topological_order);
82 
83 // Like DenseIntTopologicalSort, but stable.
84 ABSL_MUST_USE_RESULT inline bool DenseIntStableTopologicalSort(
85  int num_nodes, const std::vector<std::pair<int, int>>& arcs,
86  std::vector<int>* topological_order);
87 
88 // Finds a cycle in the directed graph given as argument: nodes are dense
89 // integers in 0..num_nodes-1, and (directed) arcs are pairs of nodes
90 // {from, to}.
91 // The returned cycle is a list of nodes that form a cycle, eg. {1, 4, 3}
92 // if the cycle 1->4->3->1 exists.
93 // If the graph is acyclic, returns an empty vector.
94 ABSL_MUST_USE_RESULT std::vector<int> FindCycleInDenseIntGraph(
95  int num_nodes, const std::vector<std::pair<int, int>>& arcs);
96 
97 // Like the two above, but with generic node types. The nodes must be provided.
98 // Can be significantly slower, but still linear.
99 template <typename T>
100 ABSL_MUST_USE_RESULT bool TopologicalSort(
101  const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs,
102  std::vector<T>* topological_order);
103 template <typename T>
104 ABSL_MUST_USE_RESULT bool StableTopologicalSort(
105  const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs,
106  std::vector<T>* topological_order);
107 
108 // "OrDie()" versions of the 4 functions above. Those directly return the
109 // topological order, which makes their API even simpler.
110 inline std::vector<int> DenseIntTopologicalSortOrDie(
111  int num_nodes, const std::vector<std::pair<int, int>>& arcs);
112 inline std::vector<int> DenseIntStableTopologicalSortOrDie(
113  int num_nodes, const std::vector<std::pair<int, int>>& arcs);
114 template <typename T>
115 std::vector<T> TopologicalSortOrDie(const std::vector<T>& nodes,
116  const std::vector<std::pair<T, T>>& arcs);
117 template <typename T>
118 std::vector<T> StableTopologicalSortOrDie(
119  const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs);
120 
121 namespace internal {
122 // Internal wrapper around the *TopologicalSort classes.
123 template <typename T, typename Sorter>
124 ABSL_MUST_USE_RESULT bool RunTopologicalSorter(
125  Sorter* sorter, const std::vector<std::pair<T, T>>& arcs,
126  std::vector<T>* topological_order_or_cycle);
127 
128 // Do not use the templated class directly, instead use one of the
129 // typedefs DenseIntTopologicalSorter or DenseIntStableTopologicalSorter.
130 //
131 // The equivalent of a TopologicalSorter<int> which nodes are the
132 // N integers from 0 to N-1 (see the toplevel comment). The API is
133 // exactly similar to that of TopologicalSorter, please refer to the
134 // TopologicalSorter class below for more detailed comments.
135 //
136 // If the template parameter is true then the sort will be stable.
137 // This means that the order of the nodes will be maintained as much as
138 // possible. A non-stable sort is more efficient, since the complexity
139 // of getting the next node is O(1) rather than O(log(Nodes)).
140 template <bool stable_sort = false>
142  public:
143  // To store the adjacency lists efficiently.
144  typedef std::vector<int> AdjacencyList;
145 
146  // For efficiency, it is best to specify how many nodes are required
147  // by using the next constructor.
149  : traversal_started_(false),
150  num_edges_(0),
151  num_edges_added_since_last_duplicate_removal_(0) {}
152 
153  // One may also construct a DenseIntTopologicalSorterTpl with a predefined
154  // number of empty nodes. One can thus bypass the AddNode() API,
155  // which may yield a lower memory usage.
156  explicit DenseIntTopologicalSorterTpl(int num_nodes)
157  : adjacency_lists_(num_nodes),
158  traversal_started_(false),
159  num_edges_(0),
160  num_edges_added_since_last_duplicate_removal_(0) {}
161 
162  // Performs in constant amortized time. Calling this will make all
163  // node indices in [0 .. node_index] be valid node indices. If you
164  // can avoid using AddNode(), you should! If you know the number of
165  // nodes in advance, you should specify that at construction time --
166  // it will be faster and use less memory.
167  void AddNode(int node_index);
168 
169  // Performs in constant amortized time. Calling this will make all
170  // node indices in [0, max(from, to)] be valid node indices.
171  void AddEdge(int from, int to);
172 
173  // Performs in O(average degree) in average. If a cycle is detected
174  // and "output_cycle_nodes" isn't NULL, it will require an additional
175  // O(number of edges + number of nodes in the graph) time.
176  bool GetNext(int* next_node_index, bool* cyclic,
177  std::vector<int>* output_cycle_nodes = NULL);
178 
180  StartTraversal();
181  return nodes_with_zero_indegree_.size();
182  }
183 
184  void StartTraversal();
185 
186  bool TraversalStarted() const { return traversal_started_; }
187 
188  // Given a vector<AdjacencyList> of size n such that elements of the
189  // AdjacencyList are in [0, n-1], remove the duplicates within each
190  // AdjacencyList of size greater or equal to skip_lists_smaller_than,
191  // in linear time. Returns the total number of duplicates removed.
192  // This method is exposed for unit testing purposes only.
193  static int RemoveDuplicates(std::vector<AdjacencyList>* lists,
194  int skip_lists_smaller_than);
195 
196  // To extract a cycle. When there is no cycle, cycle_nodes will be empty.
197  void ExtractCycle(std::vector<int>* cycle_nodes) const;
198 
199  private:
200  // Outgoing adjacency lists.
201  std::vector<AdjacencyList> adjacency_lists_;
202 
203  bool traversal_started_;
204 
205  // Only valid after a traversal started.
206  int num_nodes_left_;
207  typename std::conditional<
208  stable_sort,
209  // We use greater<int> so that the lowest elements gets popped first.
210  std::priority_queue<int, std::vector<int>, std::greater<int>>,
211  std::queue<int>>::type nodes_with_zero_indegree_;
212  std::vector<int> indegree_;
213 
214  // Used internally by AddEdge() to decide whether to trigger
215  // RemoveDuplicates(). See the .cc.
216  int num_edges_; // current total number of edges.
217  int num_edges_added_since_last_duplicate_removal_;
218 
219  private:
220  DISALLOW_COPY_AND_ASSIGN(DenseIntTopologicalSorterTpl);
221 };
222 
223 extern template class DenseIntTopologicalSorterTpl<false>;
224 extern template class DenseIntTopologicalSorterTpl<true>;
225 
226 } // namespace internal
227 
228 // Recommended version for general usage. The stability makes it more
229 // deterministic, and its behavior is guaranteed to never change.
230 typedef ::util::internal::DenseIntTopologicalSorterTpl<
231  /*stable_sort=*/true>
233 
234 // Use this version if you are certain you don't care about the
235 // tie-breaking order and need the 5 to 10% performance gain. The
236 // performance gain can be more significant for large graphs with large
237 // numbers of source nodes (for example 2 Million nodes with 2 Million
238 // random edges sees a factor of 0.7 difference in completion time).
239 typedef ::util::internal::DenseIntTopologicalSorterTpl<
240  /*stable_sort=*/false>
242 
243 // A copy of each Node is stored internally. Duplicated edges are allowed,
244 // and discarded lazily so that AddEdge() keeps an amortized constant
245 // time, yet the total memory usage remains O(number of different edges +
246 // number of nodes).
247 //
248 // DenseIntTopologicalSorter implements the core topological sort
249 // algorithm. For greater efficiency it can be used directly
250 // (TopologicalSorter<int> is about 1.5-3x slower).
251 //
252 // TopologicalSorter requires that all nodes and edges be added before
253 // traversing the nodes, otherwise it will die with a fatal error.
254 //
255 //
256 // Note(user): since all the real work is done by
257 // DenseIntTopologicalSorterTpl, and this class is a template, we inline
258 // every function here in the .h.
259 //
260 // If stable_sort is true then the topological sort will preserve the
261 // original order of the nodes as much as possible. Note, the order
262 // which is preserved is the order in which the nodes are added (if you
263 // use AddEdge it will add the first argument and then the second).
264 template <typename T, bool stable_sort = false,
265  typename Hash = typename absl::flat_hash_map<T, int>::hasher,
266  typename KeyEqual =
267  typename absl::flat_hash_map<T, int, Hash>::key_equal>
269  public:
272 
273  // Adds a node to the graph, if it has not already been added via
274  // previous calls to AddNode()/AddEdge(). If no edges are later
275  // added connecting this node, then it remains an isolated node in
276  // the graph. AddNode() only exists to support isolated nodes. There
277  // is no requirement (nor is it an error) to call AddNode() for the
278  // endpoints used in a call to AddEdge(). Dies with a fatal error if
279  // called after a traversal has been started (see TraversalStarted()),
280  // or if more than INT_MAX nodes are being added.
281  void AddNode(const T& node) { int_sorter_.AddNode(LookupOrInsertNode(node)); }
282 
283  // Adds a directed edge with the given endpoints to the graph. There
284  // is no requirement (nor is it an error) to call AddNode() for the
285  // endpoints. Dies with a fatal error if called after a traversal
286  // has been started (see TraversalStarted()).
287  void AddEdge(const T& from, const T& to) {
288  // The lookups are not inlined into AddEdge because we need to ensure that
289  // "from" is inserted before "to".
290  const int from_int = LookupOrInsertNode(from);
291  const int to_int = LookupOrInsertNode(to);
292  int_sorter_.AddEdge(from_int, to_int);
293  }
294 
295  // Visits the least node in topological order over the current set of
296  // nodes and edges, and marks that node as visited, so that repeated
297  // calls to GetNext() will visit all nodes in order. Writes the newly
298  // visited node in *node and returns true with *cyclic set to false
299  // (assuming the graph has not yet been discovered to be cyclic).
300  // Returns false if all nodes have been visited, or if the graph is
301  // discovered to be cyclic, in which case *cyclic is also set to true.
302  //
303  // If you set the optional argument "output_cycle_nodes" to non-NULL and
304  // a cycle is detected, it will dump an arbitrary cycle of the graph
305  // (whose length will be between 1 and #number_of_nodes, inclusive),
306  // in the natural order: for example if "output_cycle_nodes" is filled
307  // with ["A", "C", "B"], it means that A->C->B->A is a directed cycle
308  // of the graph.
309  //
310  // This starts a traversal (if not started already). Note that the
311  // graph can only be traversed once.
312  bool GetNext(T* node, bool* cyclic_ptr,
313  std::vector<T>* output_cycle_nodes = NULL) {
314  StartTraversal();
315  int node_index;
316  if (!int_sorter_.GetNext(&node_index, cyclic_ptr,
317  output_cycle_nodes ? &cycle_int_nodes_ : NULL)) {
318  if (*cyclic_ptr && output_cycle_nodes != NULL) {
319  output_cycle_nodes->clear();
320  for (const int int_node : cycle_int_nodes_) {
321  output_cycle_nodes->push_back(nodes_[int_node]);
322  }
323  }
324  return false;
325  }
326  *node = nodes_[node_index];
327  return true;
328  }
329 
330  // Returns the number of nodes that currently have zero indegree.
331  // This starts a traversal (if not started already).
333  StartTraversal();
334  return int_sorter_.GetCurrentFringeSize();
335  }
336 
337  // Start a traversal. See TraversalStarted(). This initializes the
338  // various data structures of the sorter. Since this takes O(num_nodes
339  // + num_edges) time, users may want to call this at their convenience,
340  // instead of making it happen with the first GetNext().
341  void StartTraversal() {
342  if (TraversalStarted()) return;
343  nodes_.resize(node_to_index_.size());
344  // We move elements from the absl::flat_hash_map to this vector, without
345  // extra copy (if they are movable).
346  for (auto& node_and_index : node_to_index_) {
347  nodes_[node_and_index.second] = std::move(node_and_index.first);
348  }
349  gtl::STLClearHashIfBig(&node_to_index_, 1 << 16);
350  int_sorter_.StartTraversal();
351  }
352 
353  // Whether a traversal has started. If true, AddNode() and AddEdge()
354  // can no longer be called.
355  bool TraversalStarted() const { return int_sorter_.TraversalStarted(); }
356 
357  private:
358  // A simple mapping from node to their dense index, in 0..num_nodes-1,
359  // which will be their index in nodes_[]. Cleared when a traversal
360  // starts, and replaced by nodes_[].
361  absl::flat_hash_map<T, int, Hash, KeyEqual> node_to_index_;
362 
363  // Stores all the nodes as soon as a traversal starts.
364  std::vector<T> nodes_;
365 
366  // An internal DenseIntTopologicalSorterTpl that does all the real work.
368 
369  // Used internally to extract cycles from the underlying
370  // DenseIntTopologicalSorterTpl.
371  std::vector<int> cycle_int_nodes_;
372 
373  // Lookup an existing node's index, or add the node and return the
374  // new index that was assigned to it.
375  int LookupOrInsertNode(const T& node) {
376  return gtl::LookupOrInsert(&node_to_index_, node, node_to_index_.size());
377  }
378 
379  DISALLOW_COPY_AND_ASSIGN(TopologicalSorter);
380 };
381 
382 namespace internal {
383 // If successful, returns true and outputs the order in "topological_order".
384 // If not, returns false and outputs a cycle in "cycle" (if not null).
385 template <typename T, typename Sorter>
386 ABSL_MUST_USE_RESULT bool RunTopologicalSorter(
387  Sorter* sorter, const std::vector<std::pair<T, T>>& arcs,
388  std::vector<T>* topological_order, std::vector<T>* cycle) {
389  topological_order->clear();
390  for (const auto& arc : arcs) {
391  sorter->AddEdge(arc.first, arc.second);
392  }
393  bool cyclic = false;
394  sorter->StartTraversal();
395  T next;
396  while (sorter->GetNext(&next, &cyclic, cycle)) {
397  topological_order->push_back(next);
398  }
399  return !cyclic;
400 }
401 
402 template <bool stable_sort = false>
403 ABSL_MUST_USE_RESULT bool DenseIntTopologicalSortImpl(
404  int num_nodes, const std::vector<std::pair<int, int>>& arcs,
405  std::vector<int>* topological_order) {
407  return RunTopologicalSorter<int, decltype(sorter)>(
408  &sorter, arcs, topological_order, nullptr);
409 }
410 
411 template <typename T, bool stable_sort = false>
412 ABSL_MUST_USE_RESULT bool TopologicalSortImpl(
413  const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs,
414  std::vector<T>* topological_order) {
416  for (const T& node : nodes) {
417  sorter.AddNode(node);
418  }
419  return RunTopologicalSorter<T, decltype(sorter)>(&sorter, arcs,
420  topological_order, nullptr);
421 }
422 
423 // Now, the OrDie() versions, which directly return the topological order.
424 template <typename T, typename Sorter>
426  Sorter* sorter, const std::vector<std::pair<T, T>>& arcs) {
427  std::vector<T> topo_order;
428  CHECK(RunTopologicalSorter(sorter, arcs, &topo_order, &topo_order))
429  << "Found cycle: " << gtl::LogContainer(topo_order);
430  return topo_order;
431 }
432 
433 template <bool stable_sort = false>
435  int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
437  return RunTopologicalSorterOrDie(&sorter, arcs);
438 }
439 
440 template <typename T, bool stable_sort = false>
442  const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs) {
444  for (const T& node : nodes) {
445  sorter.AddNode(node);
446  }
447  return RunTopologicalSorterOrDie(&sorter, arcs);
448 }
449 } // namespace internal
450 
451 // Implementations of the "simple API" functions declared at the top.
453  int num_nodes, const std::vector<std::pair<int, int>>& arcs,
454  std::vector<int>* topological_order) {
455  return internal::DenseIntTopologicalSortImpl<false>(num_nodes, arcs,
456  topological_order);
457 }
458 
460  int num_nodes, const std::vector<std::pair<int, int>>& arcs,
461  std::vector<int>* topological_order) {
462  return internal::DenseIntTopologicalSortImpl<true>(num_nodes, arcs,
463  topological_order);
464 }
465 
466 template <typename T>
467 bool TopologicalSort(const std::vector<T>& nodes,
468  const std::vector<std::pair<T, T>>& arcs,
469  std::vector<T>* topological_order) {
470  return internal::TopologicalSortImpl<T, false>(nodes, arcs,
471  topological_order);
472 }
473 
474 template <typename T>
475 bool StableTopologicalSort(const std::vector<T>& nodes,
476  const std::vector<std::pair<T, T>>& arcs,
477  std::vector<T>* topological_order) {
478  return internal::TopologicalSortImpl<T, true>(nodes, arcs, topological_order);
479 }
480 
481 inline std::vector<int> DenseIntTopologicalSortOrDie(
482  int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
483  return internal::DenseIntTopologicalSortOrDieImpl<false>(num_nodes, arcs);
484 }
485 
486 inline std::vector<int> DenseIntStableTopologicalSortOrDie(
487  int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
488  return internal::DenseIntTopologicalSortOrDieImpl<true>(num_nodes, arcs);
489 }
490 
491 template <typename T>
492 std::vector<T> TopologicalSortOrDie(const std::vector<T>& nodes,
493  const std::vector<std::pair<T, T>>& arcs) {
494  return internal::TopologicalSortOrDieImpl<T, false>(nodes, arcs);
495 }
496 
497 template <typename T>
499  const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs) {
500  return internal::TopologicalSortOrDieImpl<T, true>(nodes, arcs);
501 }
502 
503 } // namespace util
504 
505 // BACKWARDS COMPATIBILITY
506 // Some of the classes or functions have been exposed under the global namespace
507 // or the util::graph:: namespace. Until all clients are fixed to use the
508 // util:: namespace, we keep those versions around.
511 template <typename T, bool stable_sort = false,
512  typename Hash = typename absl::flat_hash_map<T, int>::hasher,
513  typename KeyEqual =
514  typename absl::flat_hash_map<T, int, Hash>::key_equal>
516  : public ::util::TopologicalSorter<T, stable_sort, Hash, KeyEqual> {};
517 
518 namespace util {
519 namespace graph {
520 inline std::vector<int> DenseIntTopologicalSortOrDie(
521  int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
523 }
524 inline std::vector<int> DenseIntStableTopologicalSortOrDie(
525  int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
527 }
528 template <typename T>
530  const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs) {
531  return ::util::StableTopologicalSortOrDie<T>(nodes, arcs);
532 }
533 
534 } // namespace graph
535 } // namespace util
536 
537 #endif // UTIL_GRAPH_TOPOLOGICALSORTER_H__
#define CHECK(condition)
Definition: base/logging.h:495
void AddEdge(const T &from, const T &to)
bool GetNext(T *node, bool *cyclic_ptr, std::vector< T > *output_cycle_nodes=NULL)
void AddNode(const T &node)
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)
Block * next
auto LogContainer(const ContainerT &container, const PolicyT &policy) -> decltype(gtl::LogRange(container.begin(), container.end(), policy))
Collection::value_type::second_type & LookupOrInsert(Collection *const collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:207
void STLClearHashIfBig(T *obj, size_t limit)
Definition: stl_util.h:180
std::vector< T > StableTopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs)
std::vector< int > DenseIntStableTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int >> &arcs)
std::vector< int > DenseIntTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int >> &arcs)
std::vector< T > TopologicalSortOrDieImpl(const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs)
ABSL_MUST_USE_RESULT bool RunTopologicalSorter(Sorter *sorter, const std::vector< std::pair< T, T >> &arcs, std::vector< T > *topological_order_or_cycle)
ABSL_MUST_USE_RESULT bool TopologicalSortImpl(const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs, std::vector< T > *topological_order)
std::vector< int > DenseIntTopologicalSortOrDieImpl(int num_nodes, const std::vector< std::pair< int, int >> &arcs)
ABSL_MUST_USE_RESULT bool DenseIntTopologicalSortImpl(int num_nodes, const std::vector< std::pair< int, int >> &arcs, std::vector< int > *topological_order)
std::vector< T > RunTopologicalSorterOrDie(Sorter *sorter, const std::vector< std::pair< T, T >> &arcs)
uint64 Hash(uint64 num, uint64 c)
Definition: hash.h:150
ABSL_MUST_USE_RESULT bool DenseIntStableTopologicalSort(int num_nodes, const std::vector< std::pair< int, int >> &arcs, std::vector< int > *topological_order)
::util::internal::DenseIntTopologicalSorterTpl< true > DenseIntStableTopologicalSorter
std::vector< int > FindCycleInDenseIntGraph(int num_nodes, const std::vector< std::pair< int, int >> &arcs)
ABSL_MUST_USE_RESULT bool DenseIntTopologicalSort(int num_nodes, const std::vector< std::pair< int, int >> &arcs, std::vector< int > *topological_order)
std::vector< int > DenseIntStableTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int >> &arcs)
ABSL_MUST_USE_RESULT bool StableTopologicalSort(const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs, std::vector< T > *topological_order)
std::vector< T > TopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs)
::util::internal::DenseIntTopologicalSorterTpl< false > DenseIntTopologicalSorter
ABSL_MUST_USE_RESULT bool TopologicalSort(const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs, std::vector< T > *topological_order)
std::vector< int > DenseIntTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int >> &arcs)
std::vector< T > StableTopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs)
::util::DenseIntStableTopologicalSorter DenseIntStableTopologicalSorter
::util::DenseIntTopologicalSorter DenseIntTopologicalSorter