60#ifndef UTIL_GRAPH_TOPOLOGICALSORTER_H__
61#define UTIL_GRAPH_TOPOLOGICALSORTER_H__
67#include "absl/container/flat_hash_map.h"
80 int num_nodes,
const std::vector<std::pair<int, int>>& arcs,
81 std::vector<int>* topological_order);
85 int num_nodes,
const std::vector<std::pair<int, int>>& arcs,
86 std::vector<int>* topological_order);
95 int num_nodes,
const std::vector<std::pair<int, int>>& arcs);
101 const std::vector<T>& nodes,
const std::vector<std::pair<T, T>>& arcs,
102 std::vector<T>* topological_order);
105 const std::vector<T>& nodes,
const std::vector<std::pair<T, T>>& arcs,
106 std::vector<T>* topological_order);
111 int num_nodes,
const std::vector<std::pair<int, int>>& arcs);
113 int num_nodes,
const std::vector<std::pair<int, int>>& arcs);
116 const std::vector<std::pair<T, T>>& arcs);
119 const std::vector<T>& nodes,
const std::vector<std::pair<T, T>>& arcs);
123template <
typename T,
typename Sorter>
125 Sorter* sorter,
const std::vector<std::pair<T, T>>& arcs,
126 std::vector<T>* topological_order_or_cycle);
140template <
bool stable_sort = false>
149 : traversal_started_(false),
151 num_edges_added_since_last_duplicate_removal_(0) {}
157 : adjacency_lists_(num_nodes),
158 traversal_started_(false),
160 num_edges_added_since_last_duplicate_removal_(0) {}
171 void AddEdge(
int from,
int to);
176 bool GetNext(
int* next_node_index,
bool* cyclic,
177 std::vector<int>* output_cycle_nodes = NULL);
181 return nodes_with_zero_indegree_.size();
194 int skip_lists_smaller_than);
201 std::vector<AdjacencyList> adjacency_lists_;
203 bool traversal_started_;
207 typename std::conditional<
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_;
217 int num_edges_added_since_last_duplicate_removal_;
223extern template class DenseIntTopologicalSorterTpl<false>;
224extern template class DenseIntTopologicalSorterTpl<true>;
264template <
typename T,
bool stable_sort =
false,
265 typename Hash =
typename absl::flat_hash_map<T, int>::hasher,
267 typename absl::flat_hash_map<T, int, Hash>::key_equal>
290 const int from_int = LookupOrInsertNode(from);
291 const int to_int = LookupOrInsertNode(to);
292 int_sorter_.
AddEdge(from_int, to_int);
313 std::vector<T>* output_cycle_nodes = NULL) {
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]);
326 *node = nodes_[node_index];
343 nodes_.resize(node_to_index_.size());
346 for (
auto& node_and_index : node_to_index_) {
347 nodes_[node_and_index.second] = std::move(node_and_index.first);
361 absl::flat_hash_map<T, int, Hash, KeyEqual> node_to_index_;
364 std::vector<T> nodes_;
371 std::vector<int> cycle_int_nodes_;
375 int LookupOrInsertNode(
const T& node) {
385template <
typename T,
typename Sorter>
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);
394 sorter->StartTraversal();
396 while (sorter->GetNext(&
next, &cyclic, cycle)) {
397 topological_order->push_back(
next);
402template <
bool stable_sort = false>
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);
411template <
typename T,
bool stable_sort = false>
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) {
419 return RunTopologicalSorter<T, decltype(sorter)>(&sorter, arcs,
420 topological_order,
nullptr);
424template <
typename T,
typename Sorter>
426 Sorter* sorter,
const std::vector<std::pair<T, T>>& arcs) {
427 std::vector<T> topo_order;
433template <
bool stable_sort = false>
435 int num_nodes,
const std::vector<std::pair<int, int>>& arcs) {
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) {
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,
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,
468 const std::vector<std::pair<T, T>>& arcs,
469 std::vector<T>* topological_order) {
470 return internal::TopologicalSortImpl<T, false>(nodes, arcs,
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);
482 int num_nodes,
const std::vector<std::pair<int, int>>& arcs) {
483 return internal::DenseIntTopologicalSortOrDieImpl<false>(num_nodes, arcs);
487 int num_nodes,
const std::vector<std::pair<int, int>>& arcs) {
488 return internal::DenseIntTopologicalSortOrDieImpl<true>(num_nodes, arcs);
493 const std::vector<std::pair<T, T>>& arcs) {
494 return internal::TopologicalSortOrDieImpl<T, false>(nodes, arcs);
499 const std::vector<T>& nodes,
const std::vector<std::pair<T, T>>& arcs) {
500 return internal::TopologicalSortOrDieImpl<T, true>(nodes, arcs);
511template <
typename T,
bool stable_sort =
false,
512 typename Hash =
typename absl::flat_hash_map<T, int>::hasher,
514 typename absl::flat_hash_map<T, int, Hash>::key_equal>
521 int num_nodes,
const std::vector<std::pair<int, int>>& arcs) {
525 int num_nodes,
const std::vector<std::pair<int, int>>& arcs) {
530 const std::vector<T>& nodes,
const std::vector<std::pair<T, T>>& arcs) {
531 return ::util::StableTopologicalSortOrDie<T>(nodes, arcs);
void AddEdge(const T &from, const T &to)
bool GetNext(T *node, bool *cyclic_ptr, std::vector< T > *output_cycle_nodes=NULL)
int GetCurrentFringeSize()
bool TraversalStarted() const
void AddNode(const T &node)
void ExtractCycle(std::vector< int > *cycle_nodes) const
void AddEdge(int from, int to)
void AddNode(int node_index)
DenseIntTopologicalSorterTpl(int num_nodes)
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)
DenseIntTopologicalSorterTpl()
int GetCurrentFringeSize()
std::vector< int > AdjacencyList
bool TraversalStarted() const
void STLClearHashIfBig(T *obj, size_t limit)
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)
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)
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