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."],[[["\u003cp\u003e\u003ccode\u003eDenseIntTopologicalSorterTpl\u003c/code\u003e is a class in C++ used for topological sorting of directed graphs with integer node indices.\u003c/p\u003e\n"],["\u003cp\u003eIt provides methods for adding nodes and edges to the graph, initiating and performing the topological sort traversal, and detecting cycles.\u003c/p\u003e\n"],["\u003cp\u003eFor efficiency, it is recommended to specify the number of nodes during construction, avoiding the need for \u003ccode\u003eAddNode\u003c/code\u003e.\u003c/p\u003e\n"],["\u003cp\u003eThe \u003ccode\u003eGetNext\u003c/code\u003e method iteratively retrieves the next node in the topological order, while \u003ccode\u003eExtractCycle\u003c/code\u003e can be used to identify a cycle if one exists.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eRemoveDuplicates\u003c/code\u003e is a utility function within the class.\u003c/p\u003e\n"]]],["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"],null,[]]
