how to find the minimum-weight perfect matching if the graph is not bipartite in python

0
votes

the concept of perfect matching in wiki:

A perfect matching is a matching that matches all vertices of the graph. That is, a matching is perfect if every vertex of the graph is incident to an edge of the matching.

So the minimum-weight perfect matching is one of combinations which has smallest weight. At first, my idea is following greedy algorithm(Notice: my graph is complete, each vertex have edges to rest of vertices):

Picking one vertex from the graph and find its closest neighbor vertex in each step, then drop them and do the loop until there is no vertex in the graph. However, it is not optimal unless calcualting n! times:

while odd_vert:
    v = vertices.pop()
    length = float("inf")
    closest = 0
    for u in odd_vert:
        if graph[v][u]["weight"] < length:
            length = graph[v][u]["weight"]
            closest = u
    graph_minimum_match.add_edge(v, closest, weight = length)

I find some function in networkx but it ask the graph is bipartite:

nx.algorithms.bipartite.matching.minimum_weight_full_matching(G, top_nodes=None, weight='weight')

Besides, find the maximum weight matching:

nx.algorithms.matching.max_weight_matching(G, maxcardinality=True)

Then, I search an article shows blossom belief propagation, but I am not sure if it can be achieved, so any idea of it?

1
python-3.xalgorithmgraphnetworkxgraph-algorithm
Is your graph complete? That is, is every vertex linked to every other? - ADdV
@ADdV sorry, I forget to add, it is complete - 4daJKong

1 Answers

6
votes

You can reduce minimum weight matching to maximum weight matching

You can invert all edge weights in your graph, either by multiplying by -1 or by subtracting them from the maximum weight. Then, if you can find a maximum perfect matching in this transformed graph, that matching is minimal in your original graph.

nx.algorithms.matching.max_weight_matching has the parameter maxcardinality which, if set to True, means that it will only allow for complete matchings if such a matching exists. Thus, you can call the networkx function on your transformed graph and check if indeed the matching is complete. If it is, this matching is your desired result. If it is not, then no perfect matching is possible.

In a complete graph with an even number of vertices a complete matching is of course always possible. In addition, if the transformed graph has only positive weights (for example by using the subtraction-based transformation), the maximum weight graph will always have maximum cardinality.