util::internal Namespace Reference

Classes
class	DenseIntTopologicalSorterTpl

Functions
template<typename T , typename Sorter >
ABSL_MUST_USE_RESULT bool	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	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	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	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 >	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 >	DenseIntTopologicalSortOrDieImpl (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
template<typename T , bool stable_sort = false>
std::vector< T >	TopologicalSortOrDieImpl (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)

Variables
static const int	kLazyDuplicateDetectionSizeThreshold = 16

Function Documentation

DenseIntTopologicalSortImpl()

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 )

Definition at line 466 of file topologicalsorter.h.

DenseIntTopologicalSortOrDieImpl()

template<bool stable_sort = false>

std::vector< int > util::internal::DenseIntTopologicalSortOrDieImpl	(	int	num_nodes,
		const std::vector< std::pair< int, int > > &	arcs )

Definition at line 499 of file topologicalsorter.h.

RunTopologicalSorter() [1/2]

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 )

If successful, returns true and outputs the order in "topological_order". If not, returns false and outputs a cycle in "cycle" (if not null).

Definition at line 451 of file topologicalsorter.h.

RunTopologicalSorter() [2/2]

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.

RunTopologicalSorterOrDie()

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.

Definition at line 489 of file topologicalsorter.h.

TopologicalSortImpl()

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 )

Definition at line 476 of file topologicalsorter.h.

TopologicalSortOrDieImpl()

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 )

Definition at line 506 of file topologicalsorter.h.

Variable Documentation

kLazyDuplicateDetectionSizeThreshold

const int util::internal::kLazyDuplicateDetectionSizeThreshold = 16

static

Up to a point, we detect duplicates up front and do not insert them. Then we switch to using RemoveDuplicates(), see below.

Note(user): I did benchmarks on this in November 2011, and while 32 seemed too large, I did not see very significant performance differences with 0, 4, 8 or 16. But since larger values of this threshold mean that there will be slightly less space used up by small adjacency lists in case there are repeated edges, I picked 16.

Definition at line 66 of file topologicalsorter.cc.