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,["# DenseIntTopologicalSorterTpl\n\nC++ Reference: class DenseIntTopologicalSorterTpl\n=================================================\n\n\nNote: This documentation is automatically generated.\n\n| Method ||\n|-----------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`AddEdge`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L174) | 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. |\n| [`AddNode`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L170) | 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. |\n| [`DenseIntTopologicalSorterTpl`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L151) | For efficiency, it is best to specify how many nodes are required by using the next constructor. |\n| [`DenseIntTopologicalSorterTpl`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L159) | 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. |\n| [`ExtractCycle`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L200) | Return type: `void ` Arguments: `std::vector\u003cint\u003e* cycle_nodes` To extract a cycle. When there is no cycle, cycle_nodes will be empty. |\n| [`GetCurrentFringeSize`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L182) | Return type: `int ` \u003cbr /\u003e |\n| [`GetNext`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L179) | Return type: `bool ` Arguments: `int* next_node_index, bool* cyclic, std::vector\u003cint\u003e* output_cycle_nodes = nullptr` 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. |\n| [`RemoveDuplicates`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L196) | Return type: `static int ` Arguments: `std::vector\u003cAdjacencyList\u003e* 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. |\n| [`StartTraversal`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L187) | Return type: `void ` \u003cbr /\u003e |\n| [`TraversalStarted`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/topologicalsorter.h#L189) | Return type: `bool ` \u003cbr /\u003e |"]]
