scipy.sparse.csgraph.maximum_bipartite_matching¶
- scipy.sparse.csgraph.maximum_bipartite_matching(graph, perm_type='row')¶
返回一个二部图的匹配，该二部图的基数与该图的任何给定匹配的基数一样小。
- 参数
- graph稀疏矩阵
CSR格式的输入稀疏，其行表示图形的一个分区，其列表示另一个分区。两个顶点之间的边由其稀疏表示中存在的矩阵中的相应条目来指示。
- perm_type字符串，{‘行’，‘列’}
根据以下条件返回匹配的分区：IF
'row'时，该函数将生成一个数组，其长度为输入中的列数，并且该数组 \(j\) ‘第个元素是与 \(j\) ‘第8列。相反，如果perm_type是'column'，则返回与每行匹配的列。
- 退货
- permndarray
两个分区之一中的顶点的匹配。不匹配的顶点由
-1在结果中。
注意事项
此函数实现Hopcroft-Karp算法 [1]. 它的时间复杂度是 \(O(\lvert E \rvert \sqrt{{\lvert V \rvert}})\) ，其空间复杂度与行数呈线性关系。在实践中，行和列之间的这种不对称性意味着，如果输入包含的列数多于行数，则转置输入会更有效。
根据Konig定理，匹配的基数也是图的最小顶点覆盖中出现的点数。
请注意，如果稀疏表示包含显式零，则仍将这些视为边。
在SciPy 1.4.0中对实现进行了更改，以允许一般二部图的匹配，而以前的版本假设存在完美匹配。因此，针对1.4.0编写的代码不一定能在旧版本上运行。
参考文献
- 1
约翰·E·霍普克罗夫特和理查德·M·卡普。“二部图中最大匹配的n^{5/2}算法”，见：暹罗计算杂志2.4(1973)，第225--231页。 DOI:10.1137/0202019
示例
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import maximum_bipartite_matching
举个简单的例子，考虑一个二部图，其中的分区分别包含2个和3个元素。假设一个分区包含标记为0和1的顶点，而另一个分区包含标记为A、B和C的顶点。假设存在连接0和C、1和A以及1和B的边，则此图将由以下稀疏矩阵表示：
>>> graph = csr_matrix([[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、Nothing和0匹配。
请注意，显式零仍会转换为边。这意味着表示上图的另一种方式是直接使用CSR结构，如下所示：
>>> data = [0, 0, 0] >>> indices = [2, 0, 1] >>> indptr = [0, 1, 3] >>> graph = csr_matrix((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_matrix((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_matrix(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]]