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.
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.
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.
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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["`DenseIntTopologicalSorterTpl` is a class in C++ used for topological sorting of directed graphs with integer node indices."],["It provides methods for adding nodes and edges to the graph, initiating and performing the topological sort traversal, and detecting cycles."],["For efficiency, it is recommended to specify the number of nodes during construction, avoiding the need for `AddNode`."],["The `GetNext` method iteratively retrieves the next node in the topological order, while `ExtractCycle` can be used to identify a cycle if one exists."],["`RemoveDuplicates` is a utility function within the class."]]],["The `DenseIntTopologicalSorterTpl` class provides methods for topological sorting. Key actions include: adding nodes via `AddNode` or specifying the number of nodes during construction for efficiency; adding edges with `AddEdge`; traversing nodes using `GetNext`, which detects cycles; extracting cycles with `ExtractCycle`; initiating traversal via `StartTraversal`; determining if the traversal has been started using `TraversalStarted`; and retrieving the current fringe size using `GetCurrentFringeSize`. The `RemoveDuplicates` method helps in duplicate removal in a vector of lists.\n"]]
