python - 用于 Python 的快速最大流最小切库

Question

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

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

赏金:我在这个问题上提供赏金，看看自提出这个问题以来情况是否发生了变化。如果您对推荐的图书馆有个人经验，则可获得奖励积分!

Answer 1

我用过graph-tool类似的任务。

Graph-tool 是一个高效的 Python 模块，用于对图形(也称为网络)进行操作和统计分析。他们甚至有关于 max-flow algorithms 的极好的文档。 .

目前图形工具支持给定算法:

• Edmonds-Karp - 使用 Edmonds-Karp 算法计算图上的最大流量。
• 推送重新标记 - 使用推送重新标记算法计算图上的最大流量。
• 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")

我使用随机有向图(节点 = 4000，顶点 = 23964)执行了这个示例，所有过程只用了 11 秒。

替代库:

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