22

是否有可靠且有据可查的 Python 库，该库可以快速实现算法，在有向图中找到最大流和最小割？

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

赏金：我在这个问题上提供赏金，看看自提出这个问题以来情况是否发生了变化。如果您对推荐的图书馆有个人经验，则可以加分！

4

5 回答 5

25

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

Graph-tool 是一个高效的 p​​ython 模块，用于对图形（又名网络）进行操作和统计分析。他们甚至有关于最大流算法的优秀文档。

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

  • 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")

我使用随机有向图（节点 = 4000，顶点 = 23964）执行了这个示例，所有过程只用了11 秒。

替代库：

于 2011-08-29T06:37:31.687 回答
6

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

于 2011-08-23T14:12:32.777 回答
5

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

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

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

于 2019-11-12T09:14:07.230 回答
1

为了获得真正好的性能，您可以尝试将问题重新表述为整数线性程序，任何标准 ILP 工具都应该为您提供足够的性能。

Wikipedia 包含此类商业和开源工具的良好列表，其中许多似乎具有 python 绑定。其中最著名的是CPLEX和lp_solve。

在过去的几年里，我个人大量使用了 lp_solve，发现只需将输入作为纯文本文件写入 lp_solve并使用 shell 调用 lp_solve 就足够了。回想起来，我可能应该投入更多的精力来让官方 python 绑定到 lp_solve 工作。

于 2011-08-29T11:18:24.960 回答
1

检查PyMaxflow和igraph。

PyMaxflow 是一个用于图构建和最大流计算（通常称为图割）的 Python 库。这个库的核心是 Vladimir Kolmogorov 的 C++ 实现，可以从他的主页下载。

除了 C++ 库的包装器之外，PyMaxflow 还提供 NumPy 集成、计算机视觉和图形中常见图形布局的快速构建方法，以及使用 maxflow 方法（αβ-swap 和 α-expansion）的快速能量最小化算法的实现。

igraph 是一个用于创建、操作和分析图形的 C 库。它旨在尽可能强大（即快速）以支持处理大图。igraph 也可用于：R、Python 和 Mathematica。

在我的测试用例中，igraph比PyMaxflow快 2-5 倍，比 快 6-10 倍，比 快Scipy100-115 倍Networkx。

于 2021-09-01T13:37:47.137 回答