networkx/networkx — pull request #1280 by ysitu (2014-11-02 04:32:03+00:00)
Title: Reimplement the network simplex method for min-cost flows

Addresses #401, #598, #630, #1106.

Performance comparison with `capacity_scaling`:

```
netgen-1 (n=400, e=1500)
network_simplex : 0.090
capacity_scaling : 0.080

netgen-2 (n=400, e=1416)
network_simplex : 0.100
capacity_scaling : 0.790

netgen-3 (n=400, e=2676)
network_simplex : 0.140
capacity_scaling : 1.200

netgen-4 (n=1000, e=2900)
network_simplex : 0.240
capacity_scaling : 1.030

netgen-5 (n=1500, e=4342)
network_simplex : 0.410
capacity_scaling : 2.660

netgen-6 (n=8000, e=15000)
network_simplex : 5.700
capacity_scaling : 77.440 (bugged out)

netgen-7 (n=3000, e=35000)
network_simplex : 4.700
capacity_scaling : 111.320

netgen-8 (n=3000, e=23000)
network_simplex : 3.210
capacity_scaling : 50.600
```

As noted in #1106, the existing implementation is much too slow for these cases.