#include <topologicalsorter.h>

Inheritance diagram for util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >:

Public Member Functions
	TopologicalSorter ()

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

TopologicalSorter &	operator= (const TopologicalSorter &)=delete

	~TopologicalSorter ()

void	AddNode (const T &node)

void	AddEdges (const std::vector< std::pair< T, T > > &edges)
	Shortcut to AddEdge() in bulk. Not optimized.

void	AddEdge (const T &from, const T &to)

bool	GetNext (T node, bool cyclic_ptr, std::vector< T > *output_cycle_nodes=nullptr)

int	GetCurrentFringeSize ()

void	StartTraversal ()

bool	TraversalStarted () const

Detailed Description

template<typename T, bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>
class util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >

A copy of each Node is stored internally. Duplicated edges are allowed, and discarded lazily so that AddEdge() keeps an amortized constant time, yet the total memory usage remains O(number of different edges + number of nodes).

DenseIntTopologicalSorter implements the core topological sort algorithm. For greater efficiency it can be used directly (TopologicalSorter<int> is about 1.5-3x slower).

TopologicalSorter requires that all nodes and edges be added before traversing the nodes, otherwise it will die with a fatal error.

TopologicalSorter is -compatible

Note(user): since all the real work is done by DenseIntTopologicalSorterTpl, and this class is a template, we inline every function here in the .h.

If stable_sort is true then the topological sort will preserve the original order of the nodes as much as possible. Note, the order which is preserved is the order in which the nodes are added (if you use AddEdge it will add the first argument and then the second).

Definition at line 325 of file topologicalsorter.h.

Constructor & Destructor Documentation

◆ TopologicalSorter() [1/2]

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::TopologicalSorter ( )

inline

Definition at line 327 of file topologicalsorter.h.

◆ TopologicalSorter() [2/2]

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::TopologicalSorter ( const TopologicalSorter< T, stable_sort, Hash, KeyEqual > & )

delete

This type is neither copyable nor movable.

◆ ~TopologicalSorter()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::~TopologicalSorter ( )

inline

Definition at line 332 of file topologicalsorter.h.

Member Function Documentation

◆ AddEdge()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

void util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::AddEdge	(	const T &	from,
		const T &	to )

inline

Adds a directed edge with the given endpoints to the graph. There is no requirement (nor is it an error) to call AddNode() for the endpoints. Dies with a fatal error if called after a traversal has been started (see TraversalStarted()).

The lookups are not inlined into AddEdge because we need to ensure that "from" is inserted before "to".

Definition at line 353 of file topologicalsorter.h.

◆ AddEdges()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

void util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::AddEdges ( const std::vector< std::pair< T, T > > & edges )

inline

Shortcut to AddEdge() in bulk. Not optimized.

Definition at line 345 of file topologicalsorter.h.

◆ AddNode()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

void util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::AddNode ( const T & node )

inline

Adds a node to the graph, if it has not already been added via previous calls to AddNode()/AddEdge(). If no edges are later added connecting this node, then it remains an isolated node in the graph. AddNode() only exists to support isolated nodes. There is no requirement (nor is it an error) to call AddNode() for the endpoints used in a call to AddEdge(). Dies with a fatal error if called after a traversal has been started (see TraversalStarted()), or if more than INT_MAX nodes are being added.

Definition at line 342 of file topologicalsorter.h.

◆ GetCurrentFringeSize()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

int util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::GetCurrentFringeSize ( )

inline

Returns the number of nodes that currently have zero indegree. This starts a traversal (if not started already).

Definition at line 399 of file topologicalsorter.h.

◆ GetNext()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

bool util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::GetNext	(	T *	node,
		bool *	cyclic_ptr,
		std::vector< T > *	output_cycle_nodes = nullptr )

inline

Visits the least node in topological order over the current set of nodes and edges, and marks that node as visited, so that repeated calls to GetNext() will visit all nodes in order. Writes the newly visited node in *node and returns true with *cyclic set to false (assuming the graph has not yet been discovered to be cyclic). Returns false if all nodes have been visited, or if the graph is discovered to be cyclic, in which case *cyclic is also set to true.

If you set the optional argument "output_cycle_nodes" to non-NULL and a cycle is detected, it will dump an arbitrary cycle of the graph (whose length will be between 1 and #number_of_nodes, inclusive), in the natural order: for example if "output_cycle_nodes" is filled with ["A", "C", "B"], it means that A->C->B->A is a directed cycle of the graph.

This starts a traversal (if not started already). Note that the graph can only be traversed once.

Definition at line 378 of file topologicalsorter.h.

◆ operator=()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

TopologicalSorter & util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::operator= ( const TopologicalSorter< T, stable_sort, Hash, KeyEqual > & )

delete

◆ StartTraversal()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

void util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::StartTraversal ( )

inline

Start a traversal. See TraversalStarted(). This initializes the various data structures of the sorter. Since this takes O(num_nodes

num_edges) time, users may want to call this at their convenience, instead of making it happen with the first GetNext().

We move elements from the absl::flat_hash_map to this vector, without extra copy (if they are movable).

Definition at line 408 of file topologicalsorter.h.

◆ TraversalStarted()

template<typename T , bool stable_sort = false, typename Hash = typename absl::flat_hash_map<T, int>::hasher, typename KeyEqual = typename absl::flat_hash_map<T, int, Hash>::key_equal>

bool util::TopologicalSorter< T, stable_sort, Hash, KeyEqual >::TraversalStarted ( ) const

inline

Whether a traversal has started. If true, AddNode() and AddEdge() can no longer be called.

Definition at line 422 of file topologicalsorter.h.

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

ortools/graph/topologicalsorter.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ TopologicalSorter() [1/2]

◆ TopologicalSorter() [2/2]

◆ ~TopologicalSorter()

Member Function Documentation

◆ AddEdge()

◆ AddEdges()

◆ AddNode()

◆ GetCurrentFringeSize()

◆ GetNext()

◆ operator=()

◆ StartTraversal()

◆ TraversalStarted()