Is there a way to return the edges used in a minimum weight matching on a bipartite graph?

user_19873506 0
Viewed 32

I've been using networkx to find the minimum weight full matching for my bipartite graph but I have been unable to find the result edges used in this minimum matching (or at least the weight of the result graph). If anyone knows how to do this any help would be appreciated, thank you

bipartite networkx python
1 Answers

This is the graph I am going to use for an example:

G = nx.Graph()
edges = [
    (0, 4, {'weight': 1}), (0, 6, {'weight': 4}),
    (1, 5, {'weight': 1}), (1, 6, {'weight': 1}),
    (2, 4, {'weight': 3}), (3, 4, {'weight': 2}),
]
G.add_edges_from(edges)

Here is how to get the edges that are part of the minimum matching (if your graph is undirected you'll end up having both (u, v) and (v, u)):

min_matching = list(nx.bipartite.minimum_weight_full_matching(G).items())

Here is the output:

>>> min_matching
[(0, 6), (1, 5), (3, 4), (6, 0), (5, 1), (4, 3)]

Here is how to get the total weight (remember that you have both (u, v) and (v, u) in the undirected case, that's why you need to divide by two):

weight = sum(
    G.edges[u, v]['weight']
    for u, v in nx.bipartite.minimum_weight_full_matching(G).items()
) // 2

Here is the output:

>>> weight
7
user_52961060
Related