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"
70#include "ortools/base/macros.h"
73
74namespace 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.
79ABSL_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.
84ABSL_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.
94ABSL_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.
99template <typename T>
100ABSL_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);
103template <typename T>
104ABSL_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.
110inline std::vector<int> DenseIntTopologicalSortOrDie(
111 int num_nodes, const std::vector<std::pair<int, int>>& arcs);
112inline std::vector<int> DenseIntStableTopologicalSortOrDie(
113 int num_nodes, const std::vector<std::pair<int, int>>& arcs);
114template <typename T>
115std::vector<T> TopologicalSortOrDie(const std::vector<T>& nodes,
116 const std::vector<std::pair<T, T>>& arcs);
117template <typename T>
118std::vector<T> StableTopologicalSortOrDie(
119 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs);
120
121namespace internal {
122// Internal wrapper around the *TopologicalSort classes.
123template <typename T, typename Sorter>
124ABSL_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)).
140template <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
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
223extern template class DenseIntTopologicalSorterTpl<false>;
224extern 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.
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).
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).
264template <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) {
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).
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().
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
382namespace 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).
385template <typename T, typename Sorter>
386ABSL_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
402template <bool stable_sort = false>
403ABSL_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
411template <typename T, bool stable_sort = false>
412ABSL_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.
424template <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
433template <bool stable_sort = false>
435 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
437 return RunTopologicalSorterOrDie(&sorter, arcs);
438}
439
440template <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
466template <typename T>
467bool 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
474template <typename T>
475bool 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
481inline 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
487 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
488 return internal::DenseIntTopologicalSortOrDieImpl<true>(num_nodes, arcs);
489}
490
491template <typename T>
492std::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
497template <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.
511template <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
518namespace util {
519namespace graph {
520inline std::vector<int> DenseIntTopologicalSortOrDie(
521 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
523}
525 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {
527}
528template <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
void STLClearHashIfBig(T *obj, size_t limit)
Definition: stl_util.h:180
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
auto LogContainer(const ContainerT &container, const PolicyT &policy) -> decltype(gtl::LogRange(container.begin(), container.end(), policy))
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 > StableTopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &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< int > DenseIntTopologicalSortOrDieImpl(int num_nodes, const std::vector< std::pair< int, int > > &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< T > RunTopologicalSorterOrDie(Sorter *sorter, const std::vector< std::pair< T, T > > &arcs)
std::vector< T > TopologicalSortOrDieImpl(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
uint64 Hash(uint64 num, uint64 c)
Definition: hash.h:150
std::vector< T > TopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
ABSL_MUST_USE_RESULT bool TopologicalSort(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)
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)
::util::internal::DenseIntTopologicalSorterTpl< true > DenseIntStableTopologicalSorter
std::vector< int > FindCycleInDenseIntGraph(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 > StableTopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &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)
::util::internal::DenseIntTopologicalSorterTpl< false > DenseIntTopologicalSorter
ABSL_MUST_USE_RESULT bool DenseIntStableTopologicalSort(int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)
::util::DenseIntStableTopologicalSorter DenseIntStableTopologicalSorter
::util::DenseIntTopologicalSorter DenseIntTopologicalSorter