Java Program to Implement Gale Shapley Algorithm

This is a Java Program to Implement Gale Shapley Algorithm. Gale Shapley Algorithm is used to solve the stable marriage problem (SMP). SMP is the problem of finding a stable matching between two sets of elements given a set of preferences for each element.

Algorithm is as follows :

function stableMatching {
Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to {
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}
}

Here is the source code of the Java Program to Implement Gale Shapley Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. /**
2.  *    Java Program to Implement Gale Shapley Algorithm
3.  **/
4.
5. /** Class GaleShapley **/
6. public class GaleShapley
7. {
8.     private int N, engagedCount;
9.     private String[][] menPref;
10.     private String[][] womenPref;
11.     private String[] men;
12.     private String[] women;
13.     private String[] womenPartner;
14.     private boolean[] menEngaged;
15.
16.     /** Constructor **/
17.     public GaleShapley(String[] m, String[] w, String[][] mp, String[][] wp)
18.     {
19.         N = mp.length;
20.         engagedCount = 0;
21.         men = m;
22.         women = w;
23.         menPref = mp;
24.         womenPref = wp;
25.         menEngaged = new boolean[N];
26.         womenPartner = new String[N];
27.         calcMatches();
28.     }
29.     /** function to calculate all matches **/
30.     private void calcMatches()
31.     {
32.         while (engagedCount < N)
33.         {
34.             int free;
35.             for (free = 0; free < N; free++)
36.                 if (!menEngaged[free])
37.                     break;
38.
39.             for (int i = 0; i < N && !menEngaged[free]; i++)
40.             {
41.                 int index = womenIndexOf(menPref[free][i]);
42.                 if (womenPartner[index] == null)
43.                 {
44.                     womenPartner[index] = men[free];
45.                     menEngaged[free] = true;
46.                     engagedCount++;
47.                 }
48.                 else
49.                 {
50.                     String currentPartner = womenPartner[index];
51.                     if (morePreference(currentPartner, men[free], index))
52.                     {
53.                         womenPartner[index] = men[free];
54.                         menEngaged[free] = true;
55.                         menEngaged[menIndexOf(currentPartner)] = false;
56.                     }
57.                 }
58.             }
59.         }
60.         printCouples();
61.     }
62.     /** function to check if women prefers new partner over old assigned partner **/
63.     private boolean morePreference(String curPartner, String newPartner, int index)
64.     {
65.         for (int i = 0; i < N; i++)
66.         {
67.             if (womenPref[index][i].equals(newPartner))
68.                 return true;
69.             if (womenPref[index][i].equals(curPartner))
70.                 return false;
71.         }
72.         return false;
73.     }
74.     /** get men index **/
75.     private int menIndexOf(String str)
76.     {
77.         for (int i = 0; i < N; i++)
78.             if (men[i].equals(str))
79.                 return i;
80.         return -1;
81.     }
82.     /** get women index **/
83.     private int womenIndexOf(String str)
84.     {
85.         for (int i = 0; i < N; i++)
86.             if (women[i].equals(str))
87.                 return i;
88.         return -1;
89.     }
90.     /** print couples **/
91.     public void printCouples()
92.     {
93.         System.out.println("Couples are : ");
94.         for (int i = 0; i < N; i++)
95.         {
96.             System.out.println(womenPartner[i] +" "+ women[i]);
97.         }
98.     }
99.     /** main function **/
100.     public static void main(String[] args)
101.     {
102.         System.out.println("Gale Shapley Marriage Algorithm\n");
103.         /** list of men **/
104.         String[] m = {"M1", "M2", "M3", "M4", "M5"};
105.         /** list of women **/
106.         String[] w = {"W1", "W2", "W3", "W4", "W5"};
107.
108.         /** men preference **/
109.         String[][] mp = {{"W5", "W2", "W3", "W4", "W1"},
110.                          {"W2", "W5", "W1", "W3", "W4"},
111.                          {"W4", "W3", "W2", "W1", "W5"},
112.                          {"W1", "W2", "W3", "W4", "W5"},
113.                          {"W5", "W2", "W3", "W4", "W1"}};
114.         /** women preference **/
115.         String[][] wp = {{"M5", "M3", "M4", "M1", "M2"},
116.                          {"M1", "M2", "M3", "M5", "M4"},
117.                          {"M4", "M5", "M3", "M2", "M1"},
118.                          {"M5", "M2", "M1", "M4", "M3"},
119.                          {"M2", "M1", "M4", "M3", "M5"}};
120.
121.         GaleShapley gs = new GaleShapley(m, w, mp, wp);
122.     }
123. }

Gale Shapley Marriage Algorithm

Couples are :
M4 W1
M2 W2
M5 W3
M3 W4
M1 W5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]