Adds a directed edge with the given endpoints to the graph. There
is no requirement (nor is it an error) to call AddNode() for the
endpoints. Dies with a fatal error if called after a traversal
has been started (see TraversalStarted()).
Adds a node to the graph, if it has not already been added via
previous calls to AddNode()/AddEdge(). If no edges are later
added connecting this node, then it remains an isolated node in
the graph. AddNode() only exists to support isolated nodes. There
is no requirement (nor is it an error) to call AddNode() for the
endpoints used in a call to AddEdge(). Dies with a fatal error if
called after a traversal has been started (see TraversalStarted()),
or if more than INT_MAX nodes are being added.
Visits the least node in topological order over the current set of
nodes and edges, and marks that node as visited, so that repeated
calls to GetNext() will visit all nodes in order. Writes the newly
visited node in *node and returns true with *cyclic set to false
(assuming the graph has not yet been discovered to be cyclic).
Returns false if all nodes have been visited, or if the graph is
discovered to be cyclic, in which case *cyclic is also set to true.
If you set the optional argument "output_cycle_nodes" to non-NULL and
a cycle is detected, it will dump an arbitrary cycle of the graph
(whose length will be between 1 and #number_of_nodes, inclusive),
in the natural order: for example if "output_cycle_nodes" is filled
with ["A", "C", "B"], it means that A->C->B->A is a directed cycle
of the graph.
This starts a traversal (if not started already). Note that the
graph can only be traversed once.
Start a traversal. See TraversalStarted(). This initializes the
various data structures of the sorter. Since this takes O(num_nodes
+ num_edges) time, users may want to call this at their convenience,
instead of making it happen with the first GetNext().
[[["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\u003eThe \u003ccode\u003eTopologicalSorter\u003c/code\u003e class in C++ facilitates topological sorting of directed graphs.\u003c/p\u003e\n"],["\u003cp\u003eYou can add nodes and edges to the graph using \u003ccode\u003eAddNode\u003c/code\u003e and \u003ccode\u003eAddEdge\u003c/code\u003e methods, respectively, before initiating traversal.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eGetNext\u003c/code\u003e method allows you to iteratively visit nodes in topological order, detecting cycles if present.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eGetCurrentFringeSize\u003c/code\u003e provides the count of nodes with zero indegree at any point during traversal.\u003c/p\u003e\n"],["\u003cp\u003eTraversal can be explicitly started with \u003ccode\u003eStartTraversal\u003c/code\u003e for performance optimization in large graphs.\u003c/p\u003e\n"]]],["The `TopologicalSorter` class manages a directed graph, enabling topological sorting. Key actions include: `AddEdge` to connect nodes, `AddNode` to introduce isolated nodes, and `StartTraversal` to prepare for node traversal. `GetNext` visits nodes in topological order, detecting cycles and indicating if all nodes are visited. `GetCurrentFringeSize` returns the number of nodes with no incoming edges. `TraversalStarted` checks if traversal has begun, which disables further `AddNode` or `AddEdge` calls.\n"],null,[]]
