Find the maximum number of unique pairs from a matrix-CodePudding

So I am trying to solve a problem in python and I am able to generate a matrix of the form:

[
 [ 0, 0, 0, 1, 1, 1 ],
 [ 0, 0, 1, 0, 1, 1 ],
 [ 0, 1, 0, 0, 0, 1 ],
 [ 1, 0, 0, 0, 1, 1 ],
 [ 1, 1, 0, 1, 0, 0 ],
 [ 1, 1, 1, 1, 0, 0 ],
]

Which is just an array of arrays. The matrix is a square matrix whose diagonal is always going to be 0 because it essentially represents compatibility between two entities. For example, entity 0 is compatible with entity 3, 4, and 5, represented by 1's in the first column. The matrix is mirrored along the diagonal because if entity 1 is compatible with entity 3 then entity 3 will also be compatible with entry 1.

Now what I essentially want to do is find a way that maximum number of compatible entities get paired up, without repetition. For example, if entity 0 has been paired with entity 3, then it should not be paired up with entity 4. However if entity 3 has another compatible entity but entity 4 does not, then entity 0 should be paired with entity 4 and not entity 3.

The end goal is to find out the number of entities that would remain unpaired. I could probably brute force such a solution but since its more of a math problem than a programming one, I would like to know if there is an efficient way of going about it.

CodePudding user response：

It appears what you have is an adjacency matrix of a graph and you want the maximal matching. There's networkx API in Python that deals with graphs and if you're willing to use it, the problem becomes very simple.

You first build a graph object from the adjacency matrix; then call max_weight_matching to find the maximal matching. It implements Edmonds' blossom algorithm.

# pip install networkx
import networkx as nx
G = nx.from_numpy_matrix(data)
tmp = nx.max_weight_matching(G)

Output:

{(0, 5), (1, 2), (3, 4)}

From there, if you want to find the number of nodes that are unmatched, you can find the difference between the nodes and the matched nodes:

out = G.nodes - {x for pair in list(tmp) for x in pair}

Output (there is no unmatched node in this graph in a maximal matching):

set()