networkx/networkx — pull request #1095 by jtorrents (2014-04-05 14:19:23+00:00)
Title: Add a parameter in connectivity functions to select a max_flow function

Modify all node and edge connectivity functions to accept an additional parameter for defining the implementation in the computation of local maximum flow. With the recent addition of the `preflow_push` algorithm by @ysitu, we now have two maximum flow implementations.

I was going to set the new `preflow_push` as the default function, but it seems that in connectivity algorithms it is actually slower than @loicseguin implementation of `ford_fulkerson` algorithm. I've put together a small benchmark for maximum flow implementations for connectivity at:

https://gist.github.com/jtorrents/9992146

You need the changes in this PR to run the benchmark. In my machine (linux 64-bit) the results using python 2.7 are:

```
jtorrents@saturn:~/projects/benchmark$ python2.7 benchmark_flow.py
Name: fast_gnp_random_graph(600,0.02)
Type: Graph
Number of nodes: 600
Number of edges: 3633
Average degree: 12.1100
Mean and std of computing the maximum flow among 100 pairs of nodes
Kind of capacity: unit
preflow_push:	0.022 (0.0033) seconds
ford_fulkerson:	0.012 (0.0021) seconds
Kind of capacity: random ints
preflow_push:	0.024 (0.0039) seconds
ford_fulkerson:	0.013 (0.0024) seconds
Time computing node connectivity
preflow_push:	33.42 seconds
ford_fulkerson:	9.68 seconds
Time computing edge connectivity
preflow_push:	3.54 seconds
ford_fulkerson:	1.69 seconds

Name: fast_gnp_random_graph(200,0.2)
Type: Graph
Number of nodes: 200
Number of edges: 3962
Average degree: 39.6200
Mean and std of computing the maximum flow among 100 pairs of nodes
Kind of capacity: unit
preflow_push:	0.020 (0.0031) seconds
ford_fulkerson:	0.012 (0.0021) seconds
Kind of capacity: random ints
preflow_push:	0.021 (0.0033) seconds
ford_fulkerson:	0.013 (0.0022) seconds
Time computing node connectivity
preflow_push:	20.70 seconds
ford_fulkerson:	7.68 seconds
Time computing edge connectivity
preflow_push:	0.53 seconds
ford_fulkerson:	0.29 seconds

Name: Power law configuration model
Type: Graph
Number of nodes: 970
Number of edges: 2413
Average degree: 4.9753
Mean and std of computing the maximum flow among 100 pairs of nodes
Kind of capacity: unit
preflow_push:	0.021 (0.0054) seconds
ford_fulkerson:	0.008 (0.0024) seconds
Kind of capacity: random ints
preflow_push:	0.021 (0.0073) seconds
ford_fulkerson:	0.008 (0.0019) seconds
Time computing node connectivity
preflow_push:	49.52 seconds
ford_fulkerson:	12.74 seconds
Time computing edge connectivity
preflow_push:	13.25 seconds
ford_fulkerson:	5.05 seconds
```

As you can see, `preflow_push` is quite slower than `ford_fulkerson` for the kind of computations needed for connectivity algorithms (ie multiple max flow computations on arbitrary pairs of non-connected nodes). However, @ysitu in #1082 showed in a different kind of benchmark that `preflow_push` outperformed `ford_fulkerson`. Not sure why is that. Any ideas?

Note that the difference in time is bigger in `node_connectivity` computations. Maybe the structure of the auxiliary digraph used in connectivity algorithms has something to do with `ford_fulkerson` outperforming `preflow_push`?

I did not modify analogously the cut functions because the residual graph returned by `preflow_push` needs preprocessing (remove all edges that exhausted their capacity), thus increasing even more the time required for cuts using the `preflow_push` algorithm. However if someone thinks it would be useful, I can do the necessary changes.