networkx/networkx — pull request #1107 by ysitu (2014-04-17 17:24:09+00:00)
Title: Capacity scaling

This is the capacity scaling algorithm implementation mentioned in #1106. It contains and supersedes #1103.

Compared to `network_simplex`, `capacity_scaling` has the following features/differences:

* (Weakly) polynomial *O*(*m* log *U* (*n* + *m*) log (*n* + *m*)) running time. (Assuming use of `BinaryHeap`. `PairingHeap` also supported.)
* Supports `MultiDiGraph` and disconnected networks.
* Integral data only.
* Does not immediately integrate with other mincost flow functions.
* More or less expositional. Not the best algorithm in practice. Follows textbook description to the letter.

The underlying residual network is represented as a `MultiDiGraph` even when the input is a `DiGraph`. There is no intention to expose the residual network or define a format interchangeable with other algorithms because its structure varies widely by the algorithm. The dual solution (node potentials/prices) is also computed but not currently returned.