scipy.sparse.csgraph.min_weight_full_bipartite_matching¶
- scipy.sparse.csgraph.min_weight_full_bipartite_matching(biadjacency_matrix, maximize=False)¶
返回二部图的最小权重完全匹配。
1.6.0 新版功能.
- 参数
- biadjacency_matrix稀疏矩阵
二部图的二邻接矩阵：CSR、CSC或COO格式的稀疏矩阵，行表示图的一个分区，列表示另一个分区。两个顶点之间的边由矩阵中的相应条目指示，边的权重由该条目的值指定。这不应该与图的完全邻接矩阵混淆，因为我们只需要定义二部结构的子矩阵。
- maximize布尔值(默认值：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\) 与之不同的是，我们跟随卡普 [1] 并将匹配称为 full 。
此函数实现LAPJVsp算法 [2], “线性分配问题，容克--体积，稀疏”的缩写。
它所解决的问题等价于矩形线性分配问题。 [3] 因此，此函数可用于解决与
scipy.optimize.linear_sum_assignment。当输入密集时，或者对于某些特定类型的输入，该函数可能执行得更好，例如 \((i, j)\) ‘第项是欧几里得空间中两点之间的距离。如果不存在完全匹配，此函数将引发
ValueError。有关确定图形中最大匹配的大小的信息，请参见maximum_bipartite_matching。我们要求权重为非零值，只是为了避免在不同稀疏表示之间转换时显式零的处理问题。可以通过将常数添加到所有权重来处理零权重，以便结果矩阵不包含零。
参考文献
- 1
Richard Manning Karp：一个在期望时间O(Mn Log N)内解决m×n分配问题的算法。网络，10(2)：143-152,1980。
- 2
Roy Jonker和Anton Volgenant：求解稠密和稀疏线性分配问题的最短增广路径算法。计算38：325-340,1987。
- 3
示例
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import min_weight_full_bipartite_matching
让我们首先考虑一个所有权重相等的示例：
>>> biadjacency_matrix = csr_matrix([[1, 1, 1], [1, 0, 0], [0, 1, 0]])
在这里，我们得到的只是图表的完美匹配：
>>> print(min_weight_full_bipartite_matching(biadjacency_matrix)[1]) [2 0 1]
也就是说，第一、第二和第三行分别与第三、第一和第二列匹配。请注意，在此示例中，输入矩阵中的0 not 对应于权重为0的边，而不是与边不成对的一对顶点。
另请注意，在这种情况下，输出与应用的结果相匹配
maximum_bipartite_matching：>>> from scipy.sparse.csgraph import maximum_bipartite_matching >>> biadjacency = csr_matrix([[1, 1, 1], [1, 0, 0], [0, 1, 0]]) >>> print(maximum_bipartite_matching(biadjacency, perm_type='column')) [2 0 1]
当有多条边可用时，首选权重最低的边：
>>> biadjacency = csr_matrix([[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_matrix([[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_matrix([[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_matrix((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 >>> from scipy.optimize import linear_sum_assignment >>> sparse = random(10, 10, random_state=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()) 28.0 >>> row_ind, col_ind = min_weight_full_bipartite_matching(sparse) >>> print(sparse[row_ind, col_ind].sum()) 28.0