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_generations

topological_generations(dag, /)

Return the topological generations of a directed graph.

A topological generation is a collection of nodes where all ancestors of a node are guaranteed to be in a previous generation, and all descendants of a node are guaranteed to be in a subsequent generation. Nodes are placed in the earliest possible generation they can belong to.

>>> G = rx.PyDiGraph()
>>> G.add_nodes_from([0, 1, 2, 3, 4])
>>> G.add_edges_from_no_data([(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])
>>> rx.topological_generations(G)
[NodeIndices[0], NodeIndices[1, 2], NodeIndices[3], NodeIndices[4]]

For a topologically sorted node list without generations, see topological_sort().

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

Parameters:

dag (PyDiGraph) – The directed graph to get the topological generations from.

Returns:

A list of topological generations, where each generation is represented as a list of node indices.

Return type:

list[NodeIndices]

Raises:

DAGHasCycle – if a cycle is encountered while processing the graph.o