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

问题描述

是否有一个可靠且记录完备的Python库，其中有一个 fast 实现的算法，可以在有向图中找到最大流量和最小削减量？

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

赏金：我为这个问题提供赏金如果自问这个问题出现以后情况发生了变化。奖励积分，如果你有你的推荐图书馆的个人经验！

解决方案

我已经使用图形工具用于类似的任务。

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

目前图形工具支持以下算法：

• Edmonds -Karp - 使用Edmonds-Karp算法计算图上的最大流量。
  
• 推送重新标记 - 使用push-relabel算法计算图上的最大流量。
  
• Boykov Kolmogorov - 用Boykov-Kolmogorov算法计算图表上的最大流量。
  从文档中提取的示例：使用Boykov-Kolmogorov 查找maxflow ：

   >>> g = gt.load_graph（flow-example.xml.gz）＃生成示例在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＃实际流程
  >>> max_flow = sum（res [e] for t 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 。
    
  
  

  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屋！