scipy.sparse.csgraph.maximum_flow¶

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

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

1.4.0 新版功能.

参数

csgraphcsr_matrix

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

source集成

流从其流出的源顶点。

sink集成

流流向的水槽顶点。

method: {{'edmonds_karp', 'dinic'}}, optional

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

‘Edmonds_Karp’：中的Edmonds Karp算法 [1].

“Dinic”：Dinic的算法 [4].

默认值为‘dinic’。

1.8.0 新版功能.

退货

resMaximumFlowResult: 属性表示的最大流 MaximumFlowResult 中的流的值 flow_value ，和中的残差图 residual 。

加薪

类型错误：: 如果输入图形不是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: 科曼，T.H.和莱瑟森，C.E.和Rivest，R.L.和Stein C.算法导论。第二版。2001年。麻省理工学院出版社。
3: https://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision
4(1,2): 用功率估计解决网络中最大流问题的算法。在苏联数学课上。DokLady，Vol.11，第1277-1280页。1970年

示例

也许最简单的流问题是只有两个顶点的图，其边从source(0)到ink(1)：

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

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

>>> 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], 第261章：

>>> 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个条目为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]]

此时，我们可以找到添加的汇和添加的源之间的最大流量，通过将残差图限制到原始图对应的挡路即可得到期望的匹配：

>>> flow = maximum_flow(graph_flow, 0, i+j+1, method='dinic')
>>> matching = flow.residual[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 ，通常会表现得更好。

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

scipy.sparse.csgraph.reverse_cuthill_mckee

scipy.sparse.csgraph.maximum_bipartite_matching