如何修改基于二分图的男性至多四配偶Gale Shapley匹配算法并添加节点权重

我希望根据年龄、身高、学历等特定标准为二分图的每个节点添加权重，在所有节点分配权重后执行算法，以根据男女双方的优先级推荐最优的稳定匹配。

规则条件 #

• 一名男性可娶1名、2名、3名女性，但同一时间不得超过4名
• 若配偶离婚或离世，男性可再娶一名女性
• 若男性离世，其所有配偶需等待3个月后方可再婚
• 一名女性同一时间只能嫁给一名男性
• 女性离婚后需等待3个月后方可再婚

导入Python库 #

import networkx as nx
import matplotlib.pyplot as plt

3名男性和3名女性的偏好列表示例 #

men_prefs = {
    'm1': ['w2', 'w1', 'w3'],
    'm2': ['w1', 'w2', 'w3'],
    'm3': ['w1', 'w3', 'w2']
}
women_prefs = {
    'w1': ['m3', 'm1', 'm2'],
    'w2': ['m2', 'm1', 'm3'],
    'w3': ['m1', 'm3', 'm2']
}

创建二分图 #

B = nx.Graph()
B.add_nodes_from(men_prefs.keys(), bipartite=0)
B.add_nodes_from(women_prefs.keys(), bipartite=1)
for man, prefs in men_prefs.items():
    for woman in prefs:
        B.add_edge(man, woman)

运行Gale-Shapley算法 #

free_men = set(men_prefs.keys())
engaged = {}
while free_men:
    man = free_men.pop()
    woman = men_prefs[man][0]
    if woman in engaged:
        current_man = engaged[woman]
        if women_prefs[woman].index(man) < women_prefs[woman].index(current_man):
            engaged[woman] = man
            free_men.add(current_man)
        else:
            free_men.add(man)
    else:
        engaged[woman] = man

绘制匹配后的图 #

pos = nx.bipartite_layout(B, men_prefs.keys())
plt.figure(figsize=(6, 4))
nx.draw_networkx_nodes(B, pos, node_color=['lightblue'])
nx.draw_networkx_edges(B, pos, edgelist=engaged.items(), edge_color='red', width=2)
nx.draw_networkx_labels(B, pos, font_size=12, font_family='sans-serif')
plt.axis('off')
plt.show()

内容的提问来源于stack exchange，提问作者comsian