topologicalsorter.h File Reference

#include <cstddef>
#include <functional>
#include <limits>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>
#include "absl/base/attributes.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/inlined_vector.h"
#include "absl/status/status.h"
#include "absl/status/statusor.h"
#include "absl/strings/str_format.h"
#include "absl/types/span.h"
#include "ortools/base/container_logging.h"
#include "ortools/base/logging.h"
#include "ortools/base/map_util.h"
#include "ortools/base/status_builder.h"
#include "ortools/base/stl_util.h"
#include "ortools/graph/graph.h"

Go to the source code of this file.

Classes
class	util::internal::DenseIntTopologicalSorterTpl< stable_sort >
class	util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >
class	TopologicalSorter< T, stable_sort, Hash, KeyEqual >

Namespaces
namespace	util
	A collections of i/o utilities for the Graph classes in ./graph.h.
namespace	util::graph
namespace	util::internal

Typedefs
typedef ::util::internal::DenseIntTopologicalSorterTpl< true >	util::DenseIntStableTopologicalSorter
typedef ::util::internal::DenseIntTopologicalSorterTpl< false >	util::DenseIntTopologicalSorter
typedef ::util::DenseIntStableTopologicalSorter	DenseIntStableTopologicalSorter
typedef ::util::DenseIntTopologicalSorter	DenseIntTopologicalSorter

Functions
template<class AdjacencyLists>
absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > >	util::graph::FastTopologicalSort (const AdjacencyLists &adj)
template<class AdjacencyLists>
absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > >	util::graph::FindCycleInGraph (const AdjacencyLists &adj)
template<typename T>
ABSL_MUST_USE_RESULT bool	util::TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)
template<typename T>
ABSL_MUST_USE_RESULT bool	util::TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order, std::vector< T > *cycle)
	Override of the above that outputs the detected cycle.
template<typename T>
std::vector< T >	util::TopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
	OrDie() variant of the above.
template<typename T>
ABSL_MUST_USE_RESULT bool	util::StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)
template<typename T>
ABSL_MUST_USE_RESULT bool	util::StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order, std::vector< T > *cycle)
	Override of the above that outputs the detected cycle.
template<typename T>
std::vector< T >	util::StableTopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
	OrDie() variant of the above.
ABSL_MUST_USE_RESULT std::vector< int >	util::FindCycleInDenseIntGraph (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
	______________________ END OF THE RECOMMENDED API ___________________________
ABSL_MUST_USE_RESULT bool	util::DenseIntTopologicalSort (int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)
	Implementations of the "simple API" functions declared at the top.
std::vector< int >	util::DenseIntStableTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
ABSL_MUST_USE_RESULT bool	util::DenseIntStableTopologicalSort (int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)
std::vector< int >	util::DenseIntTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
template<typename T, typename Sorter>
ABSL_MUST_USE_RESULT bool	util::internal::RunTopologicalSorter (Sorter *sorter, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order_or_cycle)
	Internal wrapper around the *TopologicalSort classes.
template<typename T, typename Sorter>
ABSL_MUST_USE_RESULT bool	util::internal::RunTopologicalSorter (Sorter *sorter, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order, std::vector< T > *cycle)
template<bool stable_sort = false>
ABSL_MUST_USE_RESULT bool	util::internal::DenseIntTopologicalSortImpl (int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)
template<typename T, bool stable_sort = false>
ABSL_MUST_USE_RESULT bool	util::internal::TopologicalSortImpl (absl::Span< const T > nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order, std::vector< T > *cycle)
template<typename T, typename Sorter>
std::vector< T >	util::internal::RunTopologicalSorterOrDie (Sorter *sorter, int num_nodes, const std::vector< std::pair< T, T > > &arcs)
	Now, the OrDie() versions, which directly return the topological order.
template<bool stable_sort = false>
std::vector< int >	util::internal::DenseIntTopologicalSortOrDieImpl (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
template<typename T, bool stable_sort = false>
std::vector< T >	util::internal::TopologicalSortOrDieImpl (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
template<typename T>
bool	util::TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)
template<typename T>
bool	util::TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order, std::vector< T > *cycle)
	Override of the above that outputs the detected cycle.
template<typename T>
bool	util::StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)
template<typename T>
bool	util::StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order, std::vector< T > *cycle)
	Override of the above that outputs the detected cycle.
std::vector< int >	util::graph::DenseIntTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
std::vector< int >	util::graph::DenseIntStableTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
template<typename T>
std::vector< T >	util::graph::StableTopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
template<class AdjacencyLists>
absl::StatusOr< std::vector< typename GraphTraits< AdjacencyLists >::NodeIndex > >	util::graph::FastTopologicalSort (const AdjacencyLists &adj)

Typedef Documentation

DenseIntStableTopologicalSorter

typedef ::util::DenseIntStableTopologicalSorter DenseIntStableTopologicalSorter

BACKWARDS COMPATIBILITY Some of the classes or functions have been exposed under the global namespace or the util::graph:: namespace. Until all clients are fixed to use the util:: namespace, we keep those versions around.

Definition at line 595 of file topologicalsorter.h.

DenseIntTopologicalSorter

typedef ::util::DenseIntTopologicalSorter DenseIntTopologicalSorter

Definition at line 596 of file topologicalsorter.h.