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.