C++ Reference: class DenseIntTopologicalSorterTpl

This documentation is automatically generated.

Method
AddEdge

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.

AddNode

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.

DenseIntTopologicalSorterTpl

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

DenseIntTopologicalSorterTpl

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.

ExtractCycle

Return type: void

Arguments: std::vector<int>* cycle_nodes

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

GetCurrentFringeSize

Return type: int

GetNext

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.

RemoveDuplicates

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.

StartTraversal

Return type: void

TraversalStarted

Return type: bool