Bipartite matching in Python

Question

Does anybody know any module in Python that computes the best bipartite matching? I have tried the following two:

1. munkres
2. hungarian

However, in my case, I have to deal with non-complete graph (i.e., there might not be an edge between two nodes), and therefore, there might not be a match if the node has no edge. The above two packages seem not to be able to deal with this.

Any advice?

Answer 1

Set cost to infinity or a large value for an edge that does not exist. You can then tell by the result whether an invalid edge was used.