#include <topologicalsorter.h>

Public Types
typedef absl::InlinedVector< int, 4 >	AdjacencyList
	To store the adjacency lists efficiently.

Public Member Functions
	DenseIntTopologicalSorterTpl ()

	DenseIntTopologicalSorterTpl (int num_nodes)

	DenseIntTopologicalSorterTpl (const DenseIntTopologicalSorterTpl &)=delete
	This type is neither copyable nor movable.

DenseIntTopologicalSorterTpl &	operator= (const DenseIntTopologicalSorterTpl &)=delete

void	AddNode (int node_index)

void	AddEdges (absl::Span< const std::pair< int, int > > edges)
	Performs AddEdge() in bulk. Much faster if you add all edges at once.

void	AddEdge (int from, int to)

bool	GetNext (int next_node_index, bool cyclic, std::vector< int > *output_cycle_nodes=nullptr)

int	GetCurrentFringeSize ()

void	StartTraversal ()

bool	TraversalStarted () const

void	ExtractCycle (std::vector< int > *cycle_nodes) const
	To extract a cycle. When there is no cycle, cycle_nodes will be empty.

Static Public Member Functions
static int	RemoveDuplicates (std::vector< AdjacencyList > *lists, int skip_lists_smaller_than)
	static

Detailed Description

template<bool stable_sort = false>
class util::internal::DenseIntTopologicalSorterTpl< stable_sort >

Do not use the templated class directly, instead use one of the typedefs DenseIntTopologicalSorter or DenseIntStableTopologicalSorter.

The equivalent of a TopologicalSorter<int> which nodes are the N integers from 0 to N-1 (see the toplevel comment). The API is exactly similar to that of TopologicalSorter, please refer to the TopologicalSorter class below for more detailed comments.

If the template parameter is true then the sort will be stable. This means that the order of the nodes will be maintained as much as possible. A non-stable sort is more efficient, since the complexity of getting the next node is O(1) rather than O(log(Nodes)).

Definition at line 190 of file topologicalsorter.h.

Member Typedef Documentation

◆ AdjacencyList

template<bool stable_sort = false>

absl::InlinedVector<int, 4> util::internal::DenseIntTopologicalSorterTpl< stable_sort >::AdjacencyList

To store the adjacency lists efficiently.

Definition at line 193 of file topologicalsorter.h.

Constructor & Destructor Documentation

◆ DenseIntTopologicalSorterTpl() [1/3]

template<bool stable_sort = false>

util::internal::DenseIntTopologicalSorterTpl< stable_sort >::DenseIntTopologicalSorterTpl ( )

inline

For efficiency, it is best to specify how many nodes are required by using the next constructor.

Definition at line 197 of file topologicalsorter.h.

◆ DenseIntTopologicalSorterTpl() [2/3]

template<bool stable_sort = false>

util::internal::DenseIntTopologicalSorterTpl< stable_sort >::DenseIntTopologicalSorterTpl ( int num_nodes )

inlineexplicit

One may also construct a DenseIntTopologicalSorterTpl with a predefined number of empty nodes. One can thus bypass the AddNode() API, which may yield a lower memory usage.

Definition at line 205 of file topologicalsorter.h.

◆ DenseIntTopologicalSorterTpl() [3/3]

template<bool stable_sort = false>

util::internal::DenseIntTopologicalSorterTpl< stable_sort >::DenseIntTopologicalSorterTpl ( const DenseIntTopologicalSorterTpl< stable_sort > & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddEdge()

template<bool stable_sort>

void util::internal::DenseIntTopologicalSorterTpl< stable_sort >::AddEdge	(	int	from,
		int	to )

Performs in constant amortized time. Calling this will make all node indices in [0, max(from, to)] be valid node indices. THIS IS MUCH SLOWER than calling AddEdges() if you already have all the edges.

We remove all duplicates at once, but skip lists for which the number of duplicates can't be too large, i.e. lists smaller than kLazyDuplicateDetectionSizeThreshold * 2. The overall ratio of duplicate edges remains bounded by 2/3 in the worst case.

Definition at line 98 of file topologicalsorter.cc.

◆ AddEdges()

template<bool stable_sort>

void util::internal::DenseIntTopologicalSorterTpl< stable_sort >::AddEdges ( absl::Span< const std::pair< int, int > > edges )

Performs AddEdge() in bulk. Much faster if you add all edges at once.

Make a first pass to detect the number of nodes.

Make a second pass to reserve the adjacency list sizes. We use indegree_ as temporary node buffer to store the node out-degrees, since it isn't being used yet.

Finally, add edges to the adjacency lists in a third pass. Don't bother doing the duplicate detection: in the bulk API, we assume that there isn't much edge duplication.

Definition at line 69 of file topologicalsorter.cc.

◆ AddNode()

template<bool stable_sort>

void util::internal::DenseIntTopologicalSorterTpl< stable_sort >::AddNode ( int node_index )

Performs in constant amortized time. Calling this will make all node indices in [0 .. node_index] be valid node indices. If you can avoid using AddNode(), you should! If you know the number of nodes in advance, you should specify that at construction time – it will be faster and use less memory.

Definition at line 49 of file topologicalsorter.cc.

◆ ExtractCycle()

template<bool stable_sort>

void util::internal::DenseIntTopologicalSorterTpl< stable_sort >::ExtractCycle ( std::vector< int > * cycle_nodes ) const

To extract a cycle. When there is no cycle, cycle_nodes will be empty.

Note(user): as of 2012-09, this implementation works in O(number of edges + number of nodes), which is the theoretical best. It could probably be optimized to gain a significant constant speed-up; but at the cost of more code complexity.

Definition at line 253 of file topologicalsorter.cc.

◆ GetCurrentFringeSize()

template<bool stable_sort = false>

int util::internal::DenseIntTopologicalSorterTpl< stable_sort >::GetCurrentFringeSize ( )

inline

Definition at line 238 of file topologicalsorter.h.

◆ GetNext()

template<bool stable_sort>

bool util::internal::DenseIntTopologicalSorterTpl< stable_sort >::GetNext	(	int *	next_node_index,
		bool *	cyclic,
		std::vector< int > *	output_cycle_nodes = nullptr )

Performs in O(average degree) in average. If a cycle is detected and "output_cycle_nodes" isn't NULL, it will require an additional O(number of edges + number of nodes in the graph) time.

Pop one orphan node.

Swap out the adjacency list, since we won't need it afterwards, to decrease memory usage.

Add new orphan nodes to nodes_with_zero_indegree_.

Definition at line 129 of file topologicalsorter.cc.

◆ operator=()

template<bool stable_sort = false>

DenseIntTopologicalSorterTpl & util::internal::DenseIntTopologicalSorterTpl< stable_sort >::operator= ( const DenseIntTopologicalSorterTpl< stable_sort > & )

delete

◆ RemoveDuplicates()

template<bool stable_sort>

int util::internal::DenseIntTopologicalSorterTpl< stable_sort >::RemoveDuplicates	(	std::vector< AdjacencyList > *	lists,
		int	skip_lists_smaller_than )

static

Given a vector<AdjacencyList> of size n such that elements of the AdjacencyList are in [0, n-1], remove the duplicates within each AdjacencyList of size greater or equal to skip_lists_smaller_than, in linear time. Returns the total number of duplicates removed. This method is exposed for unit testing purposes only.

We can always skip lists with less than 2 elements.

To optimize the duplicate removal loop, we split it in two: first, find the first duplicate, then copy the rest of the shifted adjacency list as we keep detecting duplicates.

Skip the shifted copy if there were no duplicates at all.

Definition at line 203 of file topologicalsorter.cc.

◆ StartTraversal()

template<bool stable_sort>

void util::internal::DenseIntTopologicalSorterTpl< stable_sort >::StartTraversal ( )

Iterate over all adjacency lists, and fill the indegree[] vector.

Note: we don't bother removing duplicates: there can't be too many, since we removed them progressively, and it is actually cheaper to keep them at this point.

Initialize the nodes_with_zero_indegree_ vector.

Definition at line 170 of file topologicalsorter.cc.

◆ TraversalStarted()

template<bool stable_sort = false>

bool util::internal::DenseIntTopologicalSorterTpl< stable_sort >::TraversalStarted ( ) const

inline

Definition at line 245 of file topologicalsorter.h.

The documentation for this class was generated from the following files:

ortools/graph/topologicalsorter.h
ortools/graph/topologicalsorter.cc

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Typedef Documentation

◆ AdjacencyList

Constructor & Destructor Documentation

◆ DenseIntTopologicalSorterTpl() [1/3]

◆ DenseIntTopologicalSorterTpl() [2/3]

◆ DenseIntTopologicalSorterTpl() [3/3]

Member Function Documentation

◆ AddEdge()

◆ AddEdges()

◆ AddNode()

◆ ExtractCycle()

◆ GetCurrentFringeSize()

◆ GetNext()

◆ operator=()

◆ RemoveDuplicates()

◆ StartTraversal()

◆ TraversalStarted()