scipy.sparse.csgraph.

maximum_bipartite_matching#

scipy.sparse.csgraph.maximum_bipartite_matching(graph, perm_type='row')#

返回二分图的匹配，其基数至少与该图的任何给定匹配的基数相同。

参数:

graph稀疏数组或矩阵: 输入 CSR 格式的稀疏矩阵，其行表示图的一个分区，其列表示另一个分区。两个顶点之间的边通过矩阵中相应的条目以稀疏表示形式存在来指示。
perm_typestr, {‘row’, ‘column’}: 返回匹配的分区：如果 'row'，则该函数生成一个数组，其长度是输入的列数，并且其第 \(j\) 个元素是与第 \(j\) 列匹配的行。相反，如果 perm_type 是 'column'，则返回与每行匹配的列。

返回:

permndarray: 两个分区之一中顶点的匹配。未匹配的顶点在结果中用 -1 表示。

说明

此函数实现 Hopcroft–Karp 算法 [1]。其时间复杂度为 \(O(\lvert E \rvert \sqrt{\lvert V \rvert})\)，其空间复杂度与行数呈线性关系。实际上，行和列之间的这种不对称性意味着如果输入包含的列多于行，则转置输入可能更有效。

根据柯尼希定理，匹配的基数也是图中最小顶点覆盖中出现的顶点数。

请注意，如果稀疏表示形式包含显式零，则这些零仍被视为边。

SciPy 1.4.0 中更改了实现，以允许匹配一般的二分图，而之前的版本会假设存在完美匹配。因此，针对 1.4.0 编写的代码不一定在旧版本上有效。

如果存在多个有效解，则输出可能因 SciPy 和 Python 版本而异。

参考文献

[1]

John E. Hopcroft 和 Richard M. Karp。“An n^{5 / 2} Algorithm for Maximum Matchings in Bipartite Graphs” In: SIAM Journal of Computing 2.4 (1973), pp. 225–231. DOI:10.1137/0202019

示例

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

作为一个简单的例子，考虑一个二分图，其中分区分别包含 2 个和 3 个元素。假设一个分区包含标记为 0 和 1 的顶点，而另一个分区包含标记为 A、B 和 C 的顶点。假设存在连接 0 和 C、1 和 A 以及 1 和 B 的边。那么该图将由以下稀疏数组表示

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

这里，1s 可以是任何值，只要它们最终以稀疏数组中的元素存储即可。我们现在可以计算最大匹配，如下所示

>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

第一个输出告诉我们 1 和 2 分别与 C 和 A 匹配，第二个输出告诉我们 A、B 和 C 分别与 1、无和 0 匹配。

请注意，显式零仍然会转换为边。这意味着表示上述图的另一种方法是直接使用 CSR 结构，如下所示

>>> data = [0, 0, 0]
>>> indices = [2, 0, 1]
>>> indptr = [0, 1, 3]
>>> graph = csr_array((data, indices, indptr))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

当一个或两个分区为空时，匹配也为空

>>> graph = csr_array((2, 0))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[-1 -1]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[]

当输入数组为正方形，并且已知该图允许完美匹配（即，图中每个顶点都属于匹配中的某个边），那么可以将输出视为行（或列）的排列，从而使输入数组的对角线元素均为非空

>>> a = [[0, 1, 2, 0], [1, 0, 0, 1], [2, 0, 0, 3], [0, 1, 3, 0]]
>>> graph = csr_array(a)
>>> perm = maximum_bipartite_matching(graph, perm_type='row')
>>> print(graph[perm].toarray())
[[1 0 0 1]
 [0 1 2 0]
 [0 1 3 0]
 [2 0 0 3]]