如何使用NetworKit/SNAP获得最大匹配

Question

我想得到一个图的最大匹配。

现在，我使用Networkx:nx.algorithms.bipartite.matching.hopcroft_karp_matching(G)中的算法

然而，我在这里的SNACENTER链接描述中没有找到类似的算法。

对于NetworKit，我发现了这个页面：在这里输入链接描述。但我不知道如何使用它。

有什么想法吗？如何使用NetworKit/SNAP来获得图形的最大匹配度？

Answer 1

关于NetworKit：还没有提供计算精确最大匹配的算法，但您可以使用networkit.matching.PathGrowingMatcher，它实现了Drake和Hougardy[1]的最大匹配的线性时间1/2近似算法。您可以按如下方式使用它：

import networkit as nk
# g is your graph
# Create and run the matching algorithm
matcher = nk.matching.PathGrowingMatcher(g).run()
# Get the matching, this returns an object of type networkit.matching.Matching
matching = matcher.getMatching()
# You can parse the computed matching by using
# matching.isMatched and matching.mate, for example:
for u in g.iterNodes():
if matching.isMatched(u):
print(f"Node {u} is matched with node {matching.mate(u)}")

[1]https://dl.acm.org/doi/10.1016/S0020-0190%2802%2900393-9