适用于Python的快速最大流最小割库

Question

有没有一个可靠且文档齐全的Python库，能快速实现一个算法，用来找出有向图中的最大流和最小割？

pygraph.algorithms.minmax.maximum_flow来自python-graph，可以解决这个问题，但速度非常慢：在一个有大约4000个节点和11000条边的有向图中寻找最大流和最小割需要超过1分钟。我希望能找到一个快上不少的解决方案。

悬赏：我在这个问题上提供悬赏，想看看自从这个问题被提出来后，情况有没有变化。如果你推荐的库有个人使用经验，那就更好了！

Answer 1

我不知道这样做是否更快，你需要自己去验证一下。不过你有没有试过networkx这个库？看起来它提供了你需要的功能，而且根据我的经验，这个库在处理图形方面非常简单易用。

Answer 2

SciPy 从1.4.0版本开始，提供了一个在 scipy.sparse.csgraph.maximum_flow 中的实现，这个实现可能更容易在你的项目中使用，因为这个包可以通过pip或conda安装。

它的工作原理是处理稀疏矩阵（所以叫 scipy.sparse），这些矩阵代表了图的邻接矩阵。这样，底层的数据结构比较接近底层硬件，而且算法是用Cython实现的，所以性能应该和其他工具，比如graph-tool差不多。

不同实现的性能比较总是取决于你关注的最大流图的结构。不过，作为一个简单的基准，我尝试用NetworkX、graph-tool和SciPy来运行不同稀疏度的随机图。它们都能很好地与NumPy数组配合使用，所以为了公平比较，我们创建一些方法，让它们的输入都是形状为(density*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-tool相当。

Answer 3

我之前用过 graph-tool 来做类似的事情。

graph-tool 是一个高效的 Python 模块，用于处理和分析图（也就是网络）。他们还有很棒的文档，专门讲解 最大流算法。

目前 graph-tool 支持以下算法：

• Edmonds-Karp - 使用 Edmonds-Karp 算法计算图中的最大流。
• Push relabel - 使用 push-relabel 算法计算图中的最大流。
• Boykov Kolmogorov - 使用 Boykov-Kolmogorov 算法计算图中的最大流。

文档中的一个例子： 使用 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 中的图论包”
• 或者在 Sage wiki 中找到其他一些精选的图工具。