scipy.sparse.csgraph.

min_weight_full_bipartite_matching#

scipy.sparse.csgraph.min_weight_full_bipartite_matching(biadjacency, maximize=False)#

返回二分圖的最小權重完整匹配。

在 1.6.0 版本中新增。

參數:

biadjacency稀疏陣列或矩陣: 二分圖的鄰接矩陣：CSR、CSC 或 COO 格式的稀疏陣列，其列代表圖的一個分割，而其欄代表另一個分割。兩個頂點之間的邊由矩陣中對應的條目表示，邊的權重由該條目的值給出。這不應與圖的完整鄰接矩陣混淆，因為我們只需要定義二分結構的子矩陣。
maximizebool (預設值：False): 如果為 true，則計算最大權重匹配。

返回:

row_ind, col_ind陣列: 行索引陣列和對應的欄索引陣列，給出最佳匹配。匹配的總權重可以計算為 graph[row_ind, col_ind].sum()。行索引將被排序；在方陣的情況下，它們將等於 numpy.arange(graph.shape[0])。

註解

令 \(G = ((U, V), E)\) 為具有非零權重 \(w : E \to \mathbb{R} \setminus \{0\}\) 的加權二分圖。此函數接著產生一個匹配 \(M \subseteq E\)，其基數為

\[\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),\]

這最小化了匹配中包含的邊的權重總和 \(\sum_{e \in M} w(e)\)，如果不存在這樣的匹配，則引發錯誤。

當 \(\lvert U \rvert = \lvert V \rvert\) 時，這通常被稱為完美匹配；在此，由於我們允許 \(\lvert U \rvert\) 和 \(\lvert V \rvert\) 不同，我們遵循 Karp [1] 並將匹配稱為完整匹配。

此函數實作 LAPJVsp 演算法 [2]，是 “Linear assignment problem, Jonker–Volgenant, sparse” 的縮寫。

它解決的問題等同於矩形線性指派問題。[3] 因此，此函數可用於解決與 scipy.optimize.linear_sum_assignment 相同的問題。當輸入密集時，或者對於某些特定類型的輸入（例如 \((i, j)\) 第 i, j 個條目是歐幾里德空間中兩點之間的距離），該函數的效能可能會更好。

如果不存在完整匹配，此函數會引發 ValueError。為了確定圖中最大匹配的大小，請參閱 maximum_bipartite_matching。

我們要求權重僅為非零，以避免在不同稀疏表示之間轉換時處理顯式零的問題。零權重可以通過向所有權重添加常數來處理，以便結果矩陣不包含零。

如果有多個有效解，則輸出可能因 SciPy 和 Python 版本而異。

參考文獻

[1]

Richard Manning Karp: An algorithm to Solve the m x n Assignment Problem in Expected Time O(mn log n). Networks, 10(2):143-152, 1980.

[2]

Roy Jonker and Anton Volgenant: A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38:325-340, 1987.

[3]

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

範例

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import min_weight_full_bipartite_matching

讓我們先考慮一個所有權重都相等的範例

>>> biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])

在這裡，我們得到的只是圖的完美匹配

>>> print(min_weight_full_bipartite_matching(biadjacency)[1])
[2 0 1]

也就是說，第一、第二和第三行分別與第三、第一和第二欄匹配。請注意，在本範例中，輸入矩陣中的 0 並不對應於權重為 0 的邊，而是對應於未被邊配對的頂點對。

另請注意，在這種情況下，輸出與應用 maximum_bipartite_matching 的結果相符

>>> from scipy.sparse.csgraph import maximum_bipartite_matching
>>> biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])
>>> print(maximum_bipartite_matching(biadjacency, perm_type='column'))
[2 0 1]

當有多個邊可用時，優先選擇權重最低的邊

>>> biadjacency = csr_array([[3, 3, 6], [4, 3, 5], [10, 1, 8]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(col_ind)
[0 2 1]

在這種情況下，總權重為 \(3 + 5 + 1 = 9\)

>>> print(biadjacency[row_ind, col_ind].sum())
9

當矩陣不是方陣時，即當兩個分割具有不同的基數時，匹配的大小與兩個分割中較小的一個相同

>>> biadjacency = csr_array([[0, 1, 1], [0, 2, 3]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[0 1] [2 1]
>>> biadjacency = csr_array([[0, 1], [3, 1], [1, 4]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[0 2] [1 0]

當一個或兩個分割都為空時，匹配也為空

>>> biadjacency = csr_array((2, 0))
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[] []

一般來說，我們總是會達到與使用 scipy.optimize.linear_sum_assignment 相同的權重總和，但請注意，對於後者，遺失的邊由 float('inf') 的陣列條目表示。讓我們產生一個具有介於 1 到 10 之間整數條目的隨機稀疏陣列

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from scipy.optimize import linear_sum_assignment
>>> sparse = random_array((10, 10), rng=42, density=.5, format='coo') * 10
>>> sparse.data = np.ceil(sparse.data)
>>> dense = sparse.toarray()
>>> dense = np.full(sparse.shape, np.inf)
>>> dense[sparse.row, sparse.col] = sparse.data
>>> sparse = sparse.tocsr()
>>> row_ind, col_ind = linear_sum_assignment(dense)
>>> print(dense[row_ind, col_ind].sum())
25.0
>>> row_ind, col_ind = min_weight_full_bipartite_matching(sparse)
>>> print(sparse[row_ind, col_ind].sum())
25.0