graphnetworkxmatchingsnappynetworkit

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


I want to get the maximum matching of a graph.

Now, I use the algorithm in Networkx: nx.algorithms.bipartite.matching.hopcroft_karp_matching(G)

However, I didn't find a similar algorithm in SNAPenter link description here.

And for NetworKit, I found this page:enter link description here. But I don't know how to use it.

Any ideas? How to use NetworKit/SNAP to get the maximum matching of a graph?


Solution

  • Concerning NetworKit: an algorithm to compute an exact maximum matching is not yet provided, but you can use networkit.matching.PathGrowingMatcher, which implements the linear time 1/2-approximation algorithm for maximum matching by Drake and Hougardy [1]. You can use it as follows:

    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