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。“二分图中最大匹配的 n^{5 / 2} 算法” 在:SIAM Journal of Computing 2.4 (1973),第 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]])
在这里,1 可以是任何东西,只要它们最终存储为稀疏数组中的元素。 现在我们可以按如下方式计算最大匹配项
>>> 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]]