JuliaAttic
Edmonds-Karp Max Flow/Min Cut
An implementation of Max Flow and Min st cut with test/example and documentation. Coincidently someone was requesting this just recently: https://github.com/JuliaLang/Graphs.jl/issues/202 (I beat you to it @pranavtbhat!)
Nice! Have you done any benchmarking with existing implementations? Would be nice to know that there are no obvious performance bottlenecks that users will run into
No, someone might want to look over it to see if it can be better written. The code is basically right out of the wikipedia pseudocode.
I did a small test versus Python's networkx package and I seem to get the same results:
Python got 0.0001840381 Julia got 0.00012774970229999962 (after 1 call to get the function compiled)
The example is the example from the networkx package
Python Code
import networkx as nx
import time
from networkx.algorithms.flow import edmonds_karp
G = nx.DiGraph()
G.add_edge('x','a', capacity=3.0)
G.add_edge('x','b', capacity=1.0)
G.add_edge('a','c', capacity=3.0)
G.add_edge('b','c', capacity=5.0)
G.add_edge('b','d', capacity=4.0)
G.add_edge('d','e', capacity=2.0)
G.add_edge('c','y', capacity=2.0)
G.add_edge('e','y', capacity=3.0)
tot_time = 0;
for t in range(0, 10000):
t0 = time.clock();
flow_value = nx.maximum_flow_value(G, 'x', 'y');
t1 = time.clock();
tot_time = tot_time + (t1 - t0)
print tot_time/10000
Julia Code
using Graphs
g = inclist(["a","b","c","d","e","x","y"], is_directed=true)
c = zeros(8)
add_edge!(g,"x", "a"); c[1] = 3.0
add_edge!(g,"a", "b"); c[2] = 1.0
add_edge!(g,"a", "c"); c[3] = 3.0
add_edge!(g,"b", "c"); c[4] = 5.0
add_edge!(g,"b", "d"); c[5] = 4.0
add_edge!(g,"d", "e"); c[6] = 2.0
add_edge!(g,"c", "y"); c[7] = 2.0
add_edge!(g,"e", "y"); c[8] = 3.0
f = max_flow(g,"x","y",c)
tot_time = 0
for j in 1:10000
tic()
f = max_flow(g,"x","y",c)
tot_time += toq()
end
println(tot_time/10000)
That's encouraging, though would be good to see the scalability to larger problems. @pranavtbhat, any comments on this implementation?
I agree a large scale example would be beneficial. I'm not an expert in this field and I am not sure where to find such a large example or how to generate one.
I think adding sister edge information (somewhere) would speed up the code (to get the reverse edge, right now you are doing a linear search in the targets neighborhood?), also if it is a multigraph your code might crash. You can compute the residual flow during the BFS (but not necessary). Other than that it looks good! Though maybe implementing preflow-push with labels might be a good idea for scalability.
Thanks for the comments @emreyamangil. I will probably get around to implementing these changes eventually, but it may be awhile (quite a busy season of life).
@bdeonovic, I don't think it's necessary to delay merging for these improvements. But I would add to the documentation that the max flow implementation uses a textbook implementation of Edmonds-Karp which is not competitive with state of the art approaches like preflow-push for large scale instances.
I've found that Bidirectional BFS works much faster with Edmond Karp's algorithm. (especially for large graphs).
