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

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

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

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_flow6.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中其他选定的图形工具。