C++ Reference: class DenseIntTopologicalSorterTpl

This documentation is automatically generated.


Return type: void

Arguments: 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.


Return type: void

Arguments: 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.


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


Return type: explicit

Arguments: int num_nodes

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.


Return type: void

Arguments: std::vector<int>* cycle_nodes

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


Return type: int


Return type: bool

Arguments: int* next_node_index, bool* cyclic, std::vector<int>* output_cycle_nodes = NULL

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.


Return type: static int

Arguments: std::vector<AdjacencyList>* lists, int skip_lists_smaller_than

Given a vector 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.


Return type: void


Return type: bool