networkx/networkx — pull request #1126 by jtorrents (2014-04-29 11:53:35+00:00)
Title: Refactor connectivity package

Use the new algorithms and the new interfaces provided by the flow package. I think that the code is quite clearer by using the new interface, and the new algorithms and interface provide a significant speed up in running time. For some problems, this code is one order of magnitude faster (see #1102 for bechmarks). So far the code is still backwards compatible, but we should discuss some possible non backward compatible improvements. I have some doubts about the implementation and documentation that I'd like to discuss.

1. In this first version I've added the `flow_func` parameter to all connectivity functions. It is great for tests to be able to use several flow algorithms. Also, the two algorithms that make sense in this scenario (`edmonds_karp` and `shortest_augmenting_path`) perform better in different scenarios: the former is faster in very sparse power-law like degree distribution networks, and the latter for denser networks with the edges more evenly distributed among nodes. Thus it makes sense to allow users to pick an algorithm. The implementation takes care of using the optimal parameters (`cutoff` for both and `two_phase` for SAP) for this two algorithms. So far I've set the default flow function to `edmonds_karp` because is faster in a wide set of contexts. I'll prepare more detailed benchmarks between these two algorithms.

2. Much of the increment of speed comes from reusing the data structures that we use for the underlying maximum flow computations (residual network) and local node|edge connectivity (auxiliary digraph). I think we should explain this to users and show them how they can also do that in their code. I've tried to do that in the docstings of `local_node_connectivity` and `local_edge_connectivity`. Do you think that we should document how to reuse the data structures?

3. The connectivity algorithms rely on two data structures (`residual` and `auxiliary`) that are conceptually different, but could be merged in an unique (more complex) data structure. This does not simplify the code a lot (we get rid of a parameter in function calls and a line of code each time we initialize the data structures) and I think it makes more difficult to understand what the code is actually doing. So I'd prefer to keep them separated but I'm open to merging them.

4. This changes are, so far are backwards compatible, but I think that we can improve the interface: an user that is only interested in computing node|edge cuts|connectivity will have enough using `node_connectivity`, `edge_connectivity`, `minimum_node_cut` and `minimum_edge_cut`. These functions support computing that for the whole graph and also for two nodes. So I think that these are the functions that we should import to the base NetworkX namespace. The other functions (`local_*` and `minumum_st_*_cuts`) are more specialized and should be used by users interested in building connectivity algorithms themselves. These functions accept all parameters of the the flow interface, and some more on their own, in order to reuse of data structures and achieve a significant speed up. So I think that we could keep these functions only to the connectivity package and require users that want to use them to import them explicitly from the connectivity package.

5. I was tempted to remove some connectivity functions, such as `all_pairs_node_connectivity_matrix` because it seems easy to write the few lines of code required for computing it. However I'm a bit hesitant because if you implement them without reusing the data structures, they will be a lot slower than the version that we provide here. This could be solved maybe with better documentation.