在C或Python中快速求解最大二分图匹配问题

Question

有没有C或Python中快速的最大基数二分图匹配的现成实现？我尝试了networkx，但它非常慢。我的两层图每层有约1000个节点，密度不同。在这种情况下，我可以期望多长时间？我看到了这篇文章Fast max-flow min-cut library for Python ，但有没有更快的方法？

- ivan

Answer 1

SciPy自1.4.0版本起，包含了Hopcroft-Karp的实现，位于scipy.sparse.csgraph.maximum_bipartite_matching，在性能方面比NetworkX表现更优。该函数在之前版本中也存在，但假定为完美匹配；这一假设在1.4.0版本中被取消。

它的表现将取决于二分图的结构，但仅通过随机图（并忽略NetworkX初始化底层数据结构所需的时间），我得到了大约200倍的性能提升：

import networkx as nx
from scipy.sparse import rand
from scipy.sparse.csgraph import maximum_bipartite_matching


n = 5000
graph = rand(n, n, density=.1, format='csr', random_state=42)
G = nx.algorithms.bipartite.from_biadjacency_matrix(graph)

>>> %timeit maximum_bipartite_matching(graph, perm_type='column')
8.95 ms ± 183 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
>>> %timeit nx.algorithms.bipartite.maximum_matching(G, top_nodes=range(n))
2.01 s ± 118 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

- fuglede

Answer 2

如果您打算使用网络流方法，所有可用的算法似乎在时间复杂度上都至少有一个因子为O（|V||E|），甚至在大多数情况下更多（例如O（|V|^2|E|））。如果您有一个具有2000个节点的图形，即使边的数量|E|与顶点数成线性关系，时间复杂度为O（|V|^2|E|）的算法也会在普通电脑上执行几分钟。如果图是密集的，并且|E|与|V|^2成线性关系，则可能需要几天才能执行。

一种解决二分图最大匹配问题的替代算法可能是霍普克洛夫特-卡普算法。它从一个空的双向匹配集合M开始，并尝试通过在给定图中查找增广路径来扩展M。该算法具有O(|E|√|V|)的复杂度，比像Push Relabel或Edmonds-Karp这样的网络流算法更好。

此外，已经有一个Python库实现了Hopcroft-Karp算法，我相信这也是您正在寻找的内容之一。

- ilim

---

NetworkX还实现了Hopcroft-Karp算法，位于networkx.algorithms.bipartite.matching.hopcroft_karp_matching中（自2015年以来一直存在）。 - fuglede