networkx/networkx — pull request #1099 by ysitu (2014-04-08 16:43:32+00:00)
Title: Add shortest augmenting path maximum flow algorithm

This is Ahuja & Orlin's shortest augmenting path algorithm briefly touched on in #1095. See [1] for detailed description. The two-phase method tailored for unit-capacity networks in [1] is also provided through an optional parameter.

##### Timing tests
###### Cases from #1082
For general problems, SAP is no doubt an improvement over Edmonds–Karp, but highest-label preflow-push is a better idea.

| Case | `ford_fulkerson` | `shortest_augmenting_path` | `preflow_push` |
|:-----|-----------------:|---------------------------:|---------------:|
| GL1 | 1.36 s | 0.68 s | 0.12 s |
| GL2 | 4.05 s | 1.27 s | 0.20 s |
| GL3 | 17.50 s | 5.30 s | 0.80 s |
| GL4 | 65.67 s | 11.74 s | 1.25 s |
| GL5 | 308.97 s | 39.69 s | 2.88 s |
| GL6 | 1508.11 s | 170.58 s | 6.65 s |
| GW1 | 0.52 s | 0.49 s | 0.33 s |
| GW2 | 2.50 s | 1.68 s | 0.70 s |
| GW3 | 7.80 s | 4.22 s | 1.79 s |
| GW4 | 34.07 s | 12.46 s | 4.05 s |
| GW5 | 165.34 s | 40.50 s | 10.94 s |
| GW6 | 844.14 s | 117.70 s | 28.95 s |
| WLM1 | 0.09 s | 0.04 s | 0.02 s |
| WLM2 | 0.42 s | 0.10 s | 0.06 s |
| WLM3 | 1.38 s | 0.24 s | 0.12 s |
| WLM4 | 7.80 s | 0.83 s | 0.32 s |
| WLM5 | 42.75 s | 2.56 s | 1.06 s |
| WLM6 | 188.53 s | 6.06 s | 3.01 s |

###### 3000 vs 3000 random bipartite matching
Edmonds–Karp is good when the graph is very dense (*m*/*n*² > 0.1) or very sparse (*m*/*n*² < 0.00001). In the more sensible range, SAP is the king.

The two-phase method seems to make a difference only when the gap heuristic is disabled. When enabled, the heuristic always terminates the algorithm before the criterion for switching to phase 2 is met. So there is no reason to disable it.

| #edges | `ford_fulkerson` | `shortest_augmenting_path` | `preflow_push` |
|--------:|-----------------:|---------------------------:|---------------:|
| 9000000 | 52.570 s | 96.890 s | 189.640 s |
| 901033 | 8.100 s | 9.930 s | 11.290 s |
| 89714 | 3.290 s | 1.250 s | 1.610 s |
| 8832 | 3.750 s | 0.700 s | 0.750 s |
| 882 | 1.380 s | 0.150 s | 0.260 s |
| 90 | 0.250 s | 0.120 s | 0.210 s |
| 11 | 0.070 s | 0.110 s | 0.210 s |

* 6000 extra edges needed for reducing bipartite matching to maximum flow are not counted.

##### Reference
1. Ahuja, R. K.; Orlin, J. B. (1991). "[Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems](http://onlinelibrary.wiley.com/doi/10.1002/1520-6750%28199106%2938:3%3C413::AID-NAV3220380310%3E3.0.CO;2-J/abstract)". *Naval Research Logistics*, **38** (3): 413–430.