scipy.sparse.csgraph.

最大流

scipy.sparse.csgraph.maximum_flow(csgraph, source, sink)

最大化图表中两个顶点之间的流量。

Added in version 1.4.0.

参数:

csgraphcsr_matrix

表示有向图的方阵，其 (i, j) 项是一个整数，表示顶点 i 和 j 之间边的容量。

源代码整数

流从其流出的源顶点。

下沉整数

流流向的汇顶点。

方法: {‘edmonds_karp’, ‘dinic’}, 可选

用于计算最大流的方法/算法。支持以下方法，

• ‘edmonds_karp’: [1] 中的 Edmonds Karp 算法

• ‘dinic’: [4] 中的 Dinic 算法。

默认是 ‘dinic’。

Added in version 1.8.0.

返回:

resMaximumFlowResult

一个由 MaximumFlowResult 表示的最大流，其中包括流值 flow_value 和流图 flow。

Raises:

类型错误：

如果输入的图不是CSR格式。

ValueError:

如果容量值不是整数，或者源或汇超出边界。

注释

这解决了给定有向加权图上的最大流问题：流将一个值（也称为流）关联到每条边，该值小于边的容量，使得对于每个顶点（除了源顶点和汇顶点），总流入流等于总流出流。流的值是离开源顶点的所有边的流的总和，最大流问题包括找到一个值最大的流。

根据最大流最小割定理，流的极大值也是最小割中边的总权重。

为了解决问题，我们提供了Edmonds–Karp算法 [1] 和Dinic算法 [4]。这两种算法的实现都力求利用稀疏性。前者的复杂度为 \(O(|V|\,|E|^2)\)，空间复杂度为 \(O(|E|)\)。后者通过构建层次图并在其中寻找阻塞流来实现其性能。其时间复杂度为 \(O(|V|^2\,|E|)\)，空间复杂度为 \(O(|E|)\)。

最大流问题通常定义为实值容量，但我们要求所有容量均为整数以确保收敛。当处理有理数容量，或属于 \(x\mathbb{Q}\) 的容量（其中 \(x \in \mathbb{R}\) 是某个固定值）时，可以通过相应地缩放所有容量将问题简化为整数情况。

解决最大流问题可以用于例如计算机视觉中的图割优化 [3]。

参考文献

[1] (1,2)

Edmonds, J. 和 Karp, R. M. 网络流问题中算法效率的理论改进。1972年。ACM期刊。19 (2): 第248-264页

[2]

Cormen, T. H. 和 Leiserson, C. E. 和 Rivest, R. L. 和 Stein C. 算法导论。第二版。2001年。麻省理工学院出版社。

[3]

https://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision

[4] (1,2)

Dinic, Efim A. 算法用于解决网络中最大流问题的解决方案，具有功率估计。发表于《苏联数学纪要》，第11卷，第1277-1280页。1970年。

示例

Try it in your browser!

也许最简单的流问题是只有两个顶点的图，其中一个顶点是源点 (0)，另一个顶点是汇点 (1)，它们之间有一条边:

(0) --5--> (1)

这里，最大流量就是边的容量：

>>> import numpy as np
>>> from scipy.sparse import csr_matrix
>>> from scipy.sparse.csgraph import maximum_flow
>>> graph = csr_matrix([[0, 5], [0, 0]])
>>> maximum_flow(graph, 0, 1).flow_value
5
>>> maximum_flow(graph, 0, 1, method='edmonds_karp').flow_value
5

另一方面，如果源和汇之间存在瓶颈，这可能会减少最大流量:

(0) --5--> (1) --3--> (2)

>>> graph = csr_matrix([[0, 5, 0], [0, 0, 3], [0, 0, 0]])
>>> maximum_flow(graph, 0, 2).flow_value
3

一个不太简单的例子在 [2] ，第26.1章中给出。

>>> graph = csr_matrix([[0, 16, 13,  0,  0,  0],
...                     [0,  0, 10, 12,  0,  0],
...                     [0,  4,  0,  0, 14,  0],
...                     [0,  0,  9,  0,  0, 20],
...                     [0,  0,  0,  7,  0,  4],
...                     [0,  0,  0,  0,  0,  0]])
>>> maximum_flow(graph, 0, 5).flow_value
23

可以将二分图中的最大匹配问题简化为最大流问题：设 \(G = ((U, V), E)\) 是一个二分图。然后，向图中添加一个源顶点，该顶点与 \(U\) 中的每个顶点都有边相连，并添加一个汇顶点，该顶点与 \(V\) 中的每个顶点都有边相连。最后，给结果图中每条边赋予容量 1。然后，新图中的最大流给出了原始图中由 \(E\) 中流量为正的边组成的最大匹配。

假设边由一个 \(\lvert U \rvert \times \lvert V \rvert\) 的CSR格式矩阵表示，其中 \((i, j)\) 项为1表示存在从 \(i \in U\) 到 \(j \in V\) 的边，否则为0；即输入格式符合 maximum_bipartite_matching 的要求。那么上述构建的图的CSR表示包含该矩阵作为一个块。以下是一个示例：

>>> graph = csr_matrix([[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 1, 0]])
>>> print(graph.toarray())
[[0 1 0 1]
 [1 0 1 0]
 [0 1 1 0]]
>>> i, j = graph.shape
>>> n = graph.nnz
>>> indptr = np.concatenate([[0],
...                          graph.indptr + i,
...                          np.arange(n + i + 1, n + i + j + 1),
...                          [n + i + j]])
>>> indices = np.concatenate([np.arange(1, i + 1),
...                           graph.indices + i + 1,
...                           np.repeat(i + j + 1, j)])
>>> data = np.ones(n + i + j, dtype=int)
>>>
>>> graph_flow = csr_matrix((data, indices, indptr))
>>> print(graph_flow.toarray())
[[0 1 1 1 0 0 0 0 0]
 [0 0 0 0 0 1 0 1 0]
 [0 0 0 0 1 0 1 0 0]
 [0 0 0 0 0 1 1 0 0]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0]]

在这一点上，我们可以在添加的汇和源之间找到最大流，并且通过将流函数限制在对应于原始图的块上来获得所需的匹配：

>>> result = maximum_flow(graph_flow, 0, i+j+1, method='dinic')
>>> matching = result.flow[1:i+1, i+1:i+j+1]
>>> print(matching.toarray())
[[0 1 0 0]
 [1 0 0 0]
 [0 0 1 0]]

这告诉我们，在 \(U\) 中的第一个、第二个和第三个顶点分别与 \(V\) 中的第二个、第一个和第三个顶点匹配。

虽然这通常解决了最大二分匹配问题，但请注意，专门针对该问题的算法，如 maximum_bipartite_matching，通常会表现得更好。

这种方法也可以用来解决最大二分匹配问题的各种常见推广。例如，如果某些顶点可以与多个其他顶点匹配，这可以通过适当修改新图的容量来处理。

Go BackOpen In Tab