Skip to main content
`Ctrl`+`K`

# topological_sort

topological_sort(G)

  Returns a generator of nodes in topologically sorted order.

  A topological sort is a nonunique permutation of the nodes of a directed graph such that an edge from u to v implies that u appears before v in the topological sort order. This ordering is valid only if the graph has no directed cycles.

  Parameters:
    G NetworkX digraph

      A directed acyclic graph (DAG)

  Yields:
    nodes

      Yields the nodes in topological sorted order.

  Raises:
    NetworkXError

      Topological sort is 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 sort exists 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

  `is_directed_acyclic_graph`, `lexicographical_topological_sort`

  Notes

  This algorithm is based on a description and proof in “Introduction to Algorithms: A Creative Approach” [1] .

  References

  [1]

  Manber, U. (1989). Introduction to Algorithms - A Creative Approach. Addison-Wesley.

  Examples

  To get the reverse order of the topological sort:

      >>> DG = nx.DiGraph([(1, 2), (2, 3)])
      >>> list(reversed(list(nx.topological_sort(DG))))
      [3, 2, 1]

  If your DiGraph naturally has the edges representing tasks/inputs and nodes representing people/processes that initiate tasks, then topological_sort is not quite what you need. You will have to change the tasks to nodes with dependence reflected by edges. The result is a kind of topological sort of the edges. This can be done with `networkx.line_graph()` as follows:

      >>> list(nx.topological_sort(nx.line_graph(DG)))
      [(1, 2), (2, 3)]