Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

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.