用于 Python 的快速最大流最小切割库 [英] Fast max-flow min-cut library for Python

问题描述

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

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

悬赏:我在这个问题上悬赏，看看自从提出这个问题以来情况是否发生了变化.如果您对推荐的图书馆有个人经验，可以加分！

解决方案

我用过 graph-tool用于类似的任务.

Graph-tool 是一个高效的 Python 模块，用于操作和统计分析图(又名网络).他们甚至有关于最大流算法的出色文档.

目前graph-tool支持给定的算法:

• Edmonds-Karp - 使用 Edmonds-Karp 算法计算图形上的最大流量.
• 推送重新标记 - 使用推送重新标记算法计算图上的最大流量.
• Boykov Kolmogorov - 使用 Boykov-Kolmogorov 算法计算图上的最大流量.

从文档中获取的示例:使用 Boykov 查找 maxflow-科尔莫哥洛夫:

<预><代码>>>>g = gt.load_graph("flow-example.xml.gz") #生产示例在文档中>>>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 # 实际流量>>>max_flow = sum(res[e] for e in tgt.in_edges())>>>打印最大流量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 接口
• 链接主题 图论的 Python 包"
• 或Sage wiki中的其他选定图形工具.

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!

解决方案

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.

这篇关于用于 Python 的快速最大流最小切割库的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！