用于Python的Fast max flow min cut库

Question

有没有一个可靠的、文档丰富的Python库，它有一个在有向图中找到最大流和最小割集的算法的快速实现？

来自python-graph的pygraph.algorithms.minmax.maximum_flow解决了这个问题，但它的速度非常慢：在一个有向图中找到最大流和最小割（大约4000个节点和11000个边）需要1分钟。我要找的东西至少要快一个数量级。

悬赏：我就这个问题悬赏，看问题提出后情况是否有所改变。如果你有你推荐的图书馆的个人经验，可以加分！

Answer 1

我用graph-tool来完成类似的任务。

Graph tool是一个高效的python模块，用于图形的操作和统计分析（也称为网络）。他们甚至有关于max-flow algorithms的优秀文档。

当前图形工具支持给定的算法：

• Edmonds Karp-使用Edmonds Karp算法计算图上的最大流量。
• Push relabel-使用Push relabel算法计算图形上的最大流。
• Boykov Kolmogorov-使用Boykov Kolmogorov算法计算图上的最大流。

示例取自文档：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")

我用随机有向图（nodes=4000，vertices=23964）执行了这个例子，所有的过程只花了11秒。

替代库：

• igraph-主要用C实现，但有Python和R接口
• 链接主题"Python packages for graph theory"
• 或Sage wiki中选定的其他图形工具。