适用于Python的快速最大流最小剪切库

Question

是否存在一个可靠且文档齐全的Python库，该库可以 快速 实现一种算法，该算法可以在有向图中找到最大流量和最小切口？

pygraph.algorithms.minmax.maximum_flow从蟒-图形解决了问题，但它是非常缓慢：找到最大-流和最小切口在一个有向图的东西，如4000级的节点和11000个边缘取>
1分钟。我正在寻找至少快一个数量级的东西。

赏金 ：我提供这个问题的赏金，以查看自问这个问题以来情况是否发生了变化。如果您对推荐的图书馆有亲身体验，可获赠积分！

Answer 1

我已使用图形工具完成类似任务。

Graph-tool是一个高效的python模块，用于图形的操纵和统计分析（又名网络）。他们甚至拥有关于最大流算法的极好的文档。

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

• Edmonds-Karp-使用Edmonds-Karp算法在图形上计算最大流量。
• 推入重贴标签-使用推入重贴标签算法计算图形上的最大流量。
• Boykov Kolmogorov-使用Boykov-Kolmogorov算法在图形上计算最大流量。

来自文档的示例：使用Boykov-Kolmogorov查找maxflow：

>>> 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软件包”
• 或Sage Wiki中其他选定的图形工具。