是否有可靠且文档齐全的 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.