I am executing the following code of Gale Shapley matching algorithm in python, first two iteration are working fine but third iteration system stuck in loop. Kindly help to identify and resolve the issue
Libraries
import networkx as nx
import matplotlib.pyplot as plt
Example preference lists for 3 men and 3 women
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']
}
Create the bipartite graph
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)
Run the Gale-Shapley algorithm
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
Draw the graph with the new matching
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()
