Add Boykov Kolmogorov algorithm for maximum flow problems.

This algorithm has worse case complexity `O(n^2m|C|)` where |C| is the
cost of the minimum cut [1], but it is faster than other algorithms with
theoretically better worse case complexities for some problems, such as
vision and image processing, and maybe others.

For the case of connectivity problems in networks with higly skewed
degree distributions (eg social networks) this algorithm doesn't run
faster than Edmonds-Karp but after reading about it I thought that it
was really cool and decided to implement it.

This is still WIP as the marking heuristic described in [2] is
not yet implemented. According to the authors it speeds up the running
time considerably.

[1] Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of
min-cut/max-flow algorithms for energy minimization in vision.
http://www.csd.uwo.ca/~yuri/Papers/pami04.pdf
[2] Vladimir Kolmogorov. Graph-based Algorithms for Multi-camera
Reconstruction Problem. PhD thesis, Cornell University, CS Department,
2003. pp. 109-114.
https://pub.ist.ac.at/~vnk/papers/thesis.pdf

2 files changed, 4 insertions, 2 deletions

diff --git a/networkx/algorithms/flow/tests/test_maxflow.py b/networkx/algorithms/flow/tests/test_maxflow.py
index 30c0603a..fc1bbbcd 100644
--- a/networkx/algorithms/flow/tests/test_maxflow.py
+++ b/networkx/algorithms/flow/tests/test_maxflow.py
@@ -5,12 +5,13 @@ from nose.tools import *
 
 import networkx as nx
 from networkx.algorithms.flow import build_flow_dict, build_residual_network
+from networkx.algorithms.flow import boykov_kolmogorov
 from networkx.algorithms.flow import edmonds_karp
 from networkx.algorithms.flow import preflow_push
 from networkx.algorithms.flow import shortest_augmenting_path
 from networkx.algorithms.flow import dinitz
 
-flow_funcs = [dinitz, edmonds_karp, preflow_push, shortest_augmenting_path]
+flow_funcs = [boykov_kolmogorov, dinitz, edmonds_karp, preflow_push, shortest_augmenting_path]
 max_min_funcs = [nx.maximum_flow, nx.minimum_cut]
 flow_value_funcs = [nx.maximum_flow_value, nx.minimum_cut_value]
 interface_funcs = sum([max_min_funcs, flow_value_funcs], [])
diff --git a/networkx/algorithms/flow/tests/test_maxflow_large_graph.py b/networkx/algorithms/flow/tests/test_maxflow_large_graph.py
index 89e4f595..f9db6778 100644
--- a/networkx/algorithms/flow/tests/test_maxflow_large_graph.py
+++ b/networkx/algorithms/flow/tests/test_maxflow_large_graph.py
@@ -11,6 +11,7 @@ from nose.tools import *
 
 import networkx as nx
 from networkx.algorithms.flow import build_flow_dict, build_residual_network
+from networkx.algorithms.flow import boykov_kolmogorov
 from networkx.algorithms.flow import edmonds_karp
 from networkx.algorithms.flow import preflow_push
 from networkx.algorithms.flow import shortest_augmenting_path
@@ -18,7 +19,7 @@ from networkx.algorithms.flow import dinitz
 
 # Dinitz algorithm is too slow in big and dense networks to test it here.
 # It is alredy tested in test_maxflow.py
-flow_funcs = [edmonds_karp, preflow_push, shortest_augmenting_path]
+flow_funcs = [boykov_kolmogorov, edmonds_karp, preflow_push, shortest_augmenting_path]
 
 msg = "Assertion failed in function: {0}"