Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class DenseIntTopologicalSorterTpl
Note: 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.
|
GetCurrentFringeSize | Return type: int |
GetNext | Return type: bool Arguments: int* next_node_index, bool* cyclic,
std::vector<int>* 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.
|
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 |
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[],["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"]]
