networkx/networkx — pull request #763 by larose (2012-09-09 03:01:01+00:00)
Title: Improved performance of topological_sort and topological_sort_recursive.

The current implementations of topological_sort and topological_sort_recursive are slow because they do not take into consideration how list is implemented in CPython (it is implemented as an array).

Instead of inserting at the beginning of a list, it is preferable to insert at the end (append) and then reverse the list once at the end of the algorithm.

Moreover, "in" on a list takes O(N) as opposed to O(1) on a set.

On a randomly generated dag with 199496 vertices and 600000 arcs, topological_sort took ~15 seconds and topological_sort_recursive took > 15 minutes. Now they take less than a second. See https://github.com/larose/nx-topological-sort-benchmark