rustworkx.topological_sort

topological_sort(graph, /)

Return the topological sort of node indices from the provided directed graph.

Computes a topological ordering of the nodes in the given directed graph, ensuring that for every directed edge from node \(u\) to node \(v\), node \(u\) appears before node \(v\) in the resulting sequence. This is particularly useful in scenarios such as task scheduling and dependency resolution, where certain tasks must be completed before others.

>>> G = rx.PyDiGraph()
>>> G.add_nodes_from(["A", "B", "C", "D", "E", "F", "G"])
>>> G.add_edges_from_no_data([(0, 1),(1, 2), (2, 3), (3, 4), (5, 2), (6, 3)])
>>> rx.topological_sort(G)
NodeIndices[6, 5, 0, 1, 2, 3, 4]

For more advanced control over the nodes iteration, see TopologicalSorter.

For custom sorting algorithm, see lexicographical_topological_sort().

Parameters:

graph (PyDiGraph) – The directed graph to get the topological sort on.

Returns:

A list of node indices topologically sorted.

Return type:

NodeIndices

Raises:

DAGHasCycle – if a cycle is encountered while sorting the graph.