C++ Reference: class TopologicalSorter

This documentation is automatically generated.

Method
AddEdge

Return type: void

Arguments: const T& from, const T& to

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()).

AddNode

Return type: void

Arguments: const T& node

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.

GetCurrentFringeSize

Return type: int

Returns the number of nodes that currently have zero indegree. This starts a traversal (if not started already).

GetNext

Return type: bool

Arguments: T* node, bool* cyclic_ptr, std::vector<T>* output_cycle_nodes = NULL

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.

StartTraversal

Return type: void

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().

TopologicalSorter

~TopologicalSorter

TraversalStarted

Return type: bool

Whether a traversal has started. If true, AddNode() and AddEdge() can no longer be called.