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

Question

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

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

但是我在SNAP中没有找到类似的算法enter link description here。

对于 NetworKit，我找到了这个页面：enter link description here。但是不知道怎么用

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

Answer 1

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

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

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

How to use NetworKit/SNAP to get the maximum matching?

graph

matching

networkx

snappy

networkit