scipy/scipy — pull request #4166 by atiasnir (2014-11-18 19:18:16+00:00)
Title: A faster DFS implementation: (i) linear (ii) releases gil. Some assumpti...

I've re-implemented `depth_first_order`.

The new implementation offers the following advantages:
1. linear in the the size of the input graph
2. releases gil (does not use the interpreter at all)

As a result the new implementation is much faster.

In addition, this new implementation offers a deviation from the original functionality by representing the root of the tree using a self loop (which, to the best of my knowledge, is more standard). The original implementation uses "-9999" which introduces indices outside the domain of the nodes. Currently this behavior is only available through a deisgnated keyword.