Fast max-flow min-cut library for Python

问题:

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!

回答1:

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:

• Edmonds-Karp - Calculate maximum flow on the graph with the Edmonds-Karp algorithm.
• Push relabel - Calculate maximum flow on the graph with the push-relabel algorithm.
• Boykov Kolmogorov - Calculate maximum flow on the graph with the Boykov-Kolmogorov algorithm.

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:

• igraph - mainly implemented in C, but has Python and R interface
• Linked topic "Python packages for graph theory"
• or other selected graph tools in Sage wiki.

回答2:

I don't know if it is faster, you'll need to check that, but have you tried networkx ? Seems like it offers the functionality you're looking for and from my experience it is a very easy to use library for handling graphs.

回答3:

For really good performance, you can try reformulating your problem as an Integer Linear Program, any of the standard ILP tools should give you more than adequate performance.

Wikipedia contains a good list of such both commercial and open source tools, many of which seem to have python bindings. Amongst the most well known are CPLEX and lp_solve.

I've personally used lp_solve reasonably heavily over the last few years and found it sufficient to just write input to lp_solve as plain text files and invoke lp_solve using the shell. Thinking back, I probably should have invested a bit more effort to get the official python bindings to lp_solve working.