Ctrl+K
scipy.sparse.csgraph.

maximum_flow#

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

最大化圖形中兩個頂點之間的流量。

在 1.4.0 版本中新增。

參數:
csgraphcsr_array

表示有向圖的方陣，其 (i, j) 項為整數，表示頂點 i 和 j 之間邊的容量。

sourceint

流量從中流出的來源頂點。

sinkint

流量流向的目標頂點。

method: {‘edmonds_karp’, ‘dinic’}, optional

用於計算最大流量的方法/演算法。支援以下方法：

  • ‘edmonds_karp’：Edmonds Karp 演算法，出自 [1]。

  • ‘dinic’：Dinic 演算法，出自 [4]。

預設為 ‘dinic’。

在 1.8.0 版本中新增。

返回:
resMaximumFlowResult

以 MaximumFlowResult 表示的最大流量，其中包含 flow_value 中的流量值，以及 flow 中的流量圖。

引發:
TypeError

如果輸入圖形不是 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 年。《Journal of the ACM》。19 (2)：第 248-264 頁

[2]

Cormen, T. H. 和 Leiserson, C. E. 和 Rivest, R. L. 和 Stein C.。《演算法導論》。第二版。2001 年。MIT Press。

[4] (1,2)

Dinic, Efim A. 網路中最大流量問題的解決演算法及功率估計。出自《Soviet Math. Doklady》，第 11 卷，第 1277-1280 頁。1970 年。

範例

也許最簡單的流量問題是只有兩個頂點的圖形，邊緣從來源 (0) 到目標 (1)

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

在這裡，最大流量只是邊緣的容量

>>> import numpy as np
>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import maximum_flow
>>> graph = csr_array([[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_array([[0, 5, 0], [0, 0, 3], [0, 0, 0]])
>>> maximum_flow(graph, 0, 2).flow_value
3

更不平凡的範例在 [2] 第 26.1 章中給出

>>> graph = csr_array([[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_array([[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_array((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）通常會表現得更好。

這種方法也可用於解決最大二分匹配問題的各種常見推廣。例如，如果某些頂點可以與多個其他頂點匹配，則可以透過適當修改新圖形的容量來處理這種情況。

在本頁面上