用於Python的快速最大流最小切分庫

Question

是否有一個可靠且記錄完備的Python庫，其中有快速實現了一種算法，可在有向圖中找到最大流量和最小切分？

pygraph.algorithms.minmax.maximum_flow from python-graph解決了這個問題，但它很痛苦緩慢：在有向圖中找到類似4000節點和11000條邊的最大流和最小切分量需要> 1分鐘。我在尋找的東西至少要快一個數量級。

賞金：我對這個問題提供了一個賞金，看看這個問題出現以後情況是否發生了變化。如果您有推薦的圖書館個人經驗，可以獲得獎勵積分！

Answer 1

我已經使用graph-tool進行類似的任務。

圖形工具是一個高效的python模塊，用於圖形的操作和統計分析（也稱爲網絡）。他們甚至有關於max-flow algorithms的高超文件。

目前圖的工具支持給定的算法：

• 埃德蒙斯-卡普 - 計算與所述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接口
• 鏈接主題"Python packages for graph theory"
• 或其它選定的圖形工具在Sage wiki。

Answer 2

我不知道它是否更快，你需要檢查，但你有沒有試過networkx？ 似乎它提供了您正在尋找的functionality，並且從我的經驗來看，它是一個非常易於使用的庫，用於處理圖形。

Answer 3

對於非常好的性能，您可以嘗試將整個線性程序重新組合爲一個整體線性程序，任何標準的ILP工具都應該給您足夠的性能。

維基百科包含商業和開源tools的很好列表，其中很多似乎都有python綁定。其中最着名的是CPLEX和lp_solve。

我個人使用lp_solve相當嚴重，在過去的幾年裏，發現它足以只寫輸入lp_solve爲plain text files並調用lp_solve使用shell。回想起來，我可能應該花費更多的精力來讓官方的python綁定到lp_solve工作。