topological_generations¶

topological_generations(G)[source]¶

Stratifies a DAG into generations.

A topological generation is node collection in which ancestors of a node in each generation are guaranteed to be in a previous generation, and any descendants of a node are guaranteed to be in a following generation. Nodes are guaranteed to be in the earliest possible generation that they can belong to.

Parameters

GNetworkX digraph: A directed acyclic graph (DAG)

Yields

sets of nodes: Yields sets of nodes representing each generation.

Raises

NetworkXError: Generations are defined for directed graphs only. If the graph G is undirected, a NetworkXError is raised.
NetworkXUnfeasible: If G is not a directed acyclic graph (DAG) no topological generations exist and a NetworkXUnfeasible exception is raised. This can also be raised if G is changed while the returned iterator is being processed
RuntimeError: If G is changed while the returned iterator is being processed.

See also

topological_sort

Notes

The generation in which a node resides can also be determined by taking the max-path-distance from the node to the farthest leaf node. That value can be obtained with this function using enumerate(topological_generations(G)).

Examples

>>> DG = nx.DiGraph([(2, 1), (3, 1)])
>>> [sorted(generation) for generation in nx.topological_generations(DG)]
[[2, 3], [1]]