用于Python的快速max-flow min-cut库

Question

是否有一个可靠且记录良好的Python库,可快速实现一种算法,可以在有向图中找到最大流量和最小切割量？

来自python-graph的pygraph.algorithms.minmax.maximum_flow解决了这个问题,但速度很慢:在一个有4000个节点和11000个边缘的有向图中查找最大流量和最小切割需要> 1分钟.我正在寻找至少快一个数量级的东西.

赏金:我在这个问题上提供了一笔赏金,看看自从提出这个问题以来情况是否发生了变化.如果您对自己推荐的图书馆有个人经验,可以获得奖励积分!

Answer 1

我使用图形工具来完成类似的任务.

Graph-tool是一个高效的python模块,用于图形(也称为网络)的操作和统计分析.他们甚至拥有关于max-flow算法的精湛文档.

目前图形工具支持给定的算法:

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

从文档中获取的示例:使用Boykov-Kolmogorov查找maxflow:

>>> 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包"
• 或Sage wiki中的其他选定图形工具.

Answer 2

我不知道它是否更快,你需要检查一下,但你尝试过networkx吗？看起来它提供了您正在寻找的功能,根据我的经验,它是一个非常易于使用的库来处理图形.

Answer 3

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

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

不同实现在性能方面的比较将始终取决于您感兴趣的最大流量图的结构，但作为一个简单的基准测试，我尝试通过 NetworkX、图形工具和 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 应该为您提供与图形工具相当的性能。