Why Gale Shapley matching algorithm third iteration is not executing?

100 views Asked by At

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

Code output

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()
0

There are 0 answers