用于Python的Fast max flow min cut库

Question

有没有一个可靠的、文档丰富的Python库，它有一个在有向图中找到最大流和最小割集的算法的快速实现？

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

悬赏：我就这个问题悬赏，看问题提出后情况是否有所改变。如果你有你推荐的图书馆的个人经验，可以加分！

Answer 1

我用graph-tool来完成类似的任务。

Graph tool是一个高效的python模块，用于图形的操作和统计分析（也称为网络）。他们甚至有关于max-flow algorithms的优秀文档。

当前图形工具支持给定的算法：

• Edmonds Karp-使用Edmonds Karp算法计算图上的最大流量。
• Push relabel-使用Push relabel算法计算图形上的最大流。
• 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")

我用随机有向图（nodes=4000，vertices=23964）执行了这个例子，所有的过程只花了11秒。

替代库：

• igraph-主要用C实现，但有Python和R接口
• 链接主题"Python packages for graph theory"
• 或Sage wiki中选定的其他图形工具。

Answer 2

从1.4.0开始，SciPy在scipy.sparse.csgraph.maximum_flow中也有一个实现，它可能更易于作为构建链的一部分使用（因为包可以通过pip/conda获得）。

它通过操作表示图的邻接矩阵的稀疏矩阵（因此scipy.sparse）来工作，因此，底层数据结构接近金属，并且随着算法本身在Cython中的实现，性能应该与图工具一样。

不同的实现与性能的比较将始终取决于您感兴趣的最大流的图的结构，但作为一个简单的基准，我尝试通过NetworkX、graph tool和SciPy运行具有不同稀疏性的随机图。所有这些方法都能很好地处理NumPy数组，因此为了确保公平竞争，让我们创建一些方法，以便每个方法都将具有形状（密度*1000*1000，3）的NumPy数组作为输入，其行是边，其列是与给定边相关联的两个顶点，以及边的容量。

import numpy as np
from scipy.sparse import rand


def make_data(density):
    m = (rand(1000, 1000, density=density, format='coo', random_state=42)*100).astype(np.int32)
    return np.vstack([m.row, m.col, m.data]).T

data01 = make_data(0.1)
data03 = make_data(0.3)
data05 = make_data(0.5)

这样，各种框架可以计算最大流的值，如下所示：

import graph_tool.all as gt
from scipy.sparse import coo_matrix, csr_matrix
from scipy.sparse.csgraph import maximum_flow
import networkx as nx


def networkx_max_flow(data, primitive):
    m = coo_matrix((data[:, 2], (data[:, 0], data[:, 1])))
    G = nx.from_numpy_array(m.toarray(), create_using=nx.DiGraph())
    return nx.maximum_flow_value(G, 0, 999, capacity='weight', flow_func=primitive)


def graph_tool_max_flow(data, primitive):
    g = gt.Graph()
    cap = g.new_edge_property('int')
    eprops = [cap]
    g.add_edge_list(data, eprops=eprops)
    src, tgt = g.vertex(0), g.vertex(999)
    res = primitive(g, src, tgt, cap)
    res.a = cap.a - res.a
    return sum(res[e] for e in tgt.in_edges())


def scipy_max_flow(data):
    m = csr_matrix((data[:, 2], (data[:, 0], data[:, 1])))
    return maximum_flow(m, 0, 999).flow_value

有了这个，IPython基准的例子就变成了

%timeit networkx_max_flow(data01, nx.algorithms.flow.shortest_augmenting_path)
%timeit graph_tool_max_flow(data03, gt.push_relabel_max_flow)
%timeit scipy_max_flow(data05)

然后我看到以下结果：

+----------------------------------------------+----------------+----------------+---------------+
|                  Algorithm                   |  Density: 0.1  |  Density: 0.3  |  Density: 0.5 |
+----------------------------------------------+----------------+----------------+---------------+
| nx.algorithms.flow.edmonds_karp              |  1.07s         |  3.2s          |  6.39s        |
| nx.algorithms.flow.preflow_push              |  1.07s         |  3.27s         |  6.18s        |
| nx.algorithms.flow.shortest_augmenting_path  |  1.08s         |  3.25s         |  6.23s        |
| gt.edmonds_karp_max_flow                     |  274ms         |  2.84s         |  10s          |
| gt.push_relabel_max_flow                     |  71ms          |  466ms         |  1.42s        |
| gt.boykov_kolmogorov_max_flow                |  79ms          |  463ms         |  895ms        |
| scipy.sparse.csgraph.maximum_flow            |  64ms          |  234ms         |  580ms        |
+----------------------------------------------+----------------+----------------+---------------+

同样，结果将取决于图形结构，但这至少表明SciPy应该提供与graph工具相同的性能。

Answer 3

我不知道是否更快，你需要检查一下，但是你试过networkx吗？ 似乎它提供了您正在寻找的functionality，根据我的经验，它是一个非常容易使用的处理图形的库。