NetworkX

Previous topic

networkx.algorithms.dag.is_directed_acyclic_graph

Next topic

networkx.algorithms.dag.topological_sort_recursive

networkx.algorithms.dag.topological_sort

networkx.algorithms.dag.topological_sort(G, nbunch=None)

Return a list of nodes in topological sort order.

A topological sort is a nonunique permutation of the nodes such that an edge from u to v implies that u appears before v in the topological sort order.

Parameters :

G : NetworkX digraph

A directed graph

nbunch : container of nodes (optional)

Explore graph in specified order given in nbunch

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.

Notes

This algorithm is based on a description and proof in The Algorithm Design Manual [R79] .

References

[R79](1, 2) Skiena, S. S. The Algorithm Design Manual (Springer-Verlag, 1998). http://www.amazon.com/exec/obidos/ASIN/0387948600/ref=ase_thealgorithmrepo/