Is there a reliable and well-documented Python library with a fast implementation of an algorithm that finds maximum flows and minimum cuts in directed graphs?
pygraph.algorithms.minmax.maximum_flow from python-graph solves the problem but it is painfully slow: finding max-flows and min-cuts in a directed graph with something like 4000 nodes and 11000 edges takes > 1 minute. I am looking for something that is at least an order of magnitude faster.
Bounty: I'm offering a bounty on this question to see if the situation has changed since when this question was asked. Bonus points if you have personal experience with the library you recommend!
I have used graph-tool for similar tasks.
Graph-tool is an efficient python module for manipulation and statistical analysis of graphs (a.k.a. networks). They even have superb documentation about max-flow algorithms.
Currently graph-tool supports given algorithms:
Example taken from docs: find maxflow using Boykov-Kolmogorov:
>>> g = gt.load_graph("flow-example.xml.gz") #producing example is in doc
>>> cap = g.edge_properties["cap"]
>>> src, tgt = g.vertex(0), g.vertex(1)
>>> res = gt.boykov_kolmogorov_max_flow(g, src, tgt, cap)
>>> res.a = cap.a - res.a # the actual flow
>>> max_flow = sum(res[e] for e in tgt.in_edges())
>>> print max_flow
6.92759897841
>>> pos = g.vertex_properties["pos"]
>>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-kolmogorov.png")
I executed this example with random directed graph(nodes=4000, vertices = 23964), all process took just 11seconds.
alternative libraries: