[PYTHON] Junior high school committee (NetworkX version)

problem

Based on the student's wishes, solve the "problem of assigning class members" as a matching problem.

reference

--Original article "Story of optimizing junior high school committeeing with minimum cost flow": [Minimum cost flow problem](https://qiita. Solved as com / SaitoTsutomu / items / 41d625df63f1946c7216) --The above "Junior high school committeeing": Solved as a mixed integer optimization

policy

This time, we will solve it as a matching problem. To do this, when the required number of members is n, it is necessary to increase the number of nodes for that member to n. Also, since it is set to Maximum weight maximum matching problem, the weight w is converted to "40 --w".

Let's solve

import networkx as nx

lst = [['Taprice', 'Disciplinary committee', 10], ['Aoba', 'Class representative', 10], ['Kaguya', 'Disciplinary committee', 10],
       ['Chino', 'Class representative', 10], ['mirror', 'Disciplinary committee', 10],
       ['Taprice', 'Class representative', 30], ['Aoba', 'library Commission', 30], ['Kaguya', 'library Commission', 30],
       ['Chino', 'Disciplinary committee', 30], ['mirror', 'Class representative', 30]]
need = {"Class representative": 1, "library Commission": 2, "Disciplinary committee": 2}
g = nx.Graph()
lst2 = [(s, f'{c}{i}', 40 - w) for s, c, w in lst for i in range(need[c])]
g.add_weighted_edges_from(lst2)
print(nx.max_weight_matching(g, maxcardinality=True))

output

{('Kaguya', 'Library committee 1'),
 ('Chino', 'Class representative 0'),
 ('Library committee 0', 'Aoba'),
 ('Disciplinary Committee 0', 'mirror'),
 ('Disciplinary Committee 1', 'Taprice')}

I got the same solution as the original article and the above.

Supplement

Matching is used in many parts of society. For example, it is introduced on the site of the teacher who is studying matching below (Stable matching) (https::) instead of Weight matching used this time. //qiita.com/SaitoTsutomu/items/2ec5f7626054f4b4de63)).

Reference: https://www.nii.ac.jp/faculty/informatics/yokoi_yu/

This time, I solved it with networkx.max_weight_matching (Edmonds method), but when solving a real problem, the mathematical optimization model can create the model more flexibly and [calculate faster](https: / /qiita.com/SaitoTsutomu/items/7fd199a95d78a6f3b741).