JAVA program

Homework 15 Stable Marriage Problem

Objectives:

Practice LinkedList.

You are going to write a program that solves a classic computer science problem known as the stable marriage problem. The input file is divided into men and women and the program tries to pair them up so as to generate as many marriages as possible that are all stable. A set of marriages is unstable if you can find a man and a woman who would rather be married to each other than to their spouses (in which case, the two would be inclined to divorce their spouses and marry each other).

The input file for the program will list all of the men, one per line, followed by a line with just the word END on it, followed by all of the women, one per line, followed by another line with just the word END on it. The men and women are numbered by their position in the input file. To make this easier, we assign numbers starting at 0 (the first man is #0, the second man is #1, and so on; the first woman is #0, the second woman is #1, and so on). Each input line (except the two lines with END) has a name followed by a colon followed by a list of integers. The integers are the preferences for this particular person. For example, the following input line in the men's section:

Joe: 9 7 34 8 19 21 32 5 28 6 31 15 17 24

indicates that the person is named Joe and that his first choice for marriage is woman #9, his second choice is woman #7, and so on. Any women not listed are considered unacceptable to Joe. The data file has been purged of any impossible pairings where one person is interested in the other, but the other considers that person unacceptable. Thus, if a woman appears on Joes list, then Joe is acceptable to that woman.

There are many ways to approach the stable marriage problem. You are to implement a specific algorithm described below. This is the basic outline:

set each person to be free;

while (some man m with a nonempty preference list is free) {

w = first woman on m's list;

if (some man p is engaged to w) {

set p to be free

}

set m and w to be engaged to each other

for (each successor q of m on w's list) {

delete w from q's preference list

delete q from w's preference list

}

}

Consider, for example, the following short input:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1

Man 1: 1 2 0 3 Woman 1: 0 2 1 3

Man 2: 1 3 2 0 Woman 2: 0 1 2 3

Man 3: 2 0 3 1 Woman 3: 3 0 2 1

It doesn't matter where we start, so suppose we start with man 0. We engage him to woman 3 (the first choice on his list). Men 2 and 1 appear after man 0 in woman 3's list. Thus, we delete those connections.

Man 0: 3 0 1 2 Woman 0: 3 0 2 1

Man 1: 1 2 0 Woman 1: 0 2 1 3

Man 2: 1 2 0 Woman 2: 0 1 2 3

Man 3: 2 0 3 1 Woman 3: 3 0

Notice that three things have changed: the list for man 1, the list for man 2 and the list for woman 3.

Suppose we next go to man 1. We engage him to woman 1. Man 3 appears after man 1 on woman 1's list, so we have to delete that connection, obtaining:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1

Man 1: 1 2 0 Woman 1: 0 2 1

Man 2: 1 2 0 Woman 2: 0 1 2 3

Man 3: 2 0 3 Woman 3: 3 0

Notice that two things have changed: the list for man 3 and the list for woman 1.

Suppose we next go to man 2. We engage him to woman 1, which requires breaking woman 1's engagement to man 1 (making man 1 again available). Man 1 appears after man 2 on woman 1's list, so we break that connection, obtaining:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1

Man 1: 2 0 Woman 1: 0 2

Man 2: 1 2 0 Woman 2: 0 1 2 3

Man 3: 2 0 3 Woman 3: 3 0

Suppose we next go to man 3. We engage him to woman 2. Nobody appears on woman 2's list after man 3, so we don't have to remove any connections:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1

Man 1: 2 0 Woman 1: 0 2

Man 2: 1 2 0 Woman 2: 0 1 2 3

Man 3: 2 0 3 Woman 3: 3 0

Now we go back to man 1 (because he's still free). We engage him to woman 2, which requires breaking woman 2's engagement to man 3 (making man 3 again available). Men 2 and 3 appear after man 1 on woman 2's list, so we break those connections, obtaining:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1

Man 1: 2 0 Woman 1: 0 2

Man 2: 1 0 Woman 2: 0 1

Man 3: 0 3 Woman 3: 3 0

Finally, the last free man is man 3. We engage him to woman 0. We could actually stop at this point, but according to the algorithm, we should notice that men 0, 2 and 1 all appear after man 3 on woman 0's list, so we break those connections:

Man 0: 3 1 2 Woman 0: 3

Man 1: 2 Woman 1: 0 2

Man 2: 1 Woman 2: 0 1

Man 3: 0 3 Woman 3: 3 0

This, then, is our stable marriage solution.

An interesting property of this simple stable marriage algorithm is that it favors one group over the other. The approach above favors the men at the expense of the women. In fact, the final result will give each man his best possible match for stable marriage situations, and will give each woman her worst possible match. But there is no reason that the algorithm can't be reversed with the women being favored over the men (just reversing the roles in the algorithm above).

You will also report in a column called Choice the relative position of the chosen partner in the original preference list and you will report the average of the choice column at the end of each sub-list. For the following report, you will find the results favor the men:

Matches for men

Name Choice Partner

--------------------------------------

Man 0 1 Woman 3

Man 1 2 Woman 2

Man 2 1 Woman 1

Man 3 2 Woman 0

Mean choice = 1.5

Matches for women

Name Choice Partner

--------------------------------------

Woman 0 1 Man 3

Woman 1 2 Man 2

Woman 2 2 Man 1

Woman 3 2 Man 0

Mean choice = 1.75

For example, man 0 is paired with woman 3, and woman 3 was first on man 0's original list. However, man 0 was the third on woman 3s original list.

The stable marriage algorithm always converges on an answer, but it is possible that some people will end up without being paired (this is inevitable in the large sample input file where there are 40 men and 35 women). Remember that the original algorithm terminates when there are no men left who are free and have a nonempty preference list. People are unpaired in the final result if they run out of choices on their

preference lists. Be careful not to report a choice value for these people and don't include them in the calculation of the overall choice value.

You are going to write a Java program to implement the algorithm in which you will utilize LinkedList data structures. In order to represent a woman or a man, you will also need to define a class named Person. Your Person class should at least have the following public methods:

public void erasePartner()

o It makes this person engage with nobody (i.e., no partner).

public boolean hasPartner()

o It returns true if this person currently engages with somebody.

public int getPartner()

o It returns this persons current partner. Notice that each woman and man has an implicitly ID which is based on the position this person appears in the input file. All persons IDs starts from 0. Men and women have separate ID numberings.

public void setPartner(int partner)

o It sets this persons current partner to be the one who has the passed-in ID.

public String getName()

o It returns this persons name shown in the input file.

public boolean hasChoices()

o It returns true if this persons preference list is currently non-empty.

public int getFirstChoice()

o It returns the ID of the first person in this persons preference list.

public void addChoice(int person)

o It adds the specified person to this persons preference list.

public LinkedList getChoices()

o It returns this persons preference list.

You are free to define other methods, public or private, which you deem necessary or helpful.

Besides, a Person object should at least have the following private fields:

private String name

o It is this persons name. Note that name can be same as or different from the persons implicit ID.

private int partner

o It is this persons current partner. It can be none.

private LinkedList preferences

o It is this persons preference list. Note that it is an integer list whose elements are person IDs.

After class design, continue to write a Java program to implement the above described stable marriage algorithm. The program should also accept the name of the input file via command argument. The output should be the display of two match tables, one for men and the other for women. At the bottom of each table, you have to report the mean choice for that group.

User interface specifications:

Input

o The program prompts users for the name of an input data file.

The input file should be on the same folder as the program.

You can assume data in the input file are clean.

A sample file is shown below:

Man 0: 3 0 1 2

Man 1: 1 2 0 3

Man 2: 1 3 2 0

Man 3: 2 0 3 1

END

Woman 0: 3 0 2 1

Woman 1: 0 2 1 3

Woman 2: 0 1 2 3

Woman 3: 3 0 2 1

END

Output

o Two match tables, one for men and the other for women. For the above input data file, the display should be:

Matches for men

Name Choice Partner

--------------------------------------

Man 0 1 Woman 3

Man 1 2 Woman 2

Man 2 1 Woman 1

Man 3 2 Woman 0

Mean choice = 1.5

Matches for women

Name Choice Partner

--------------------------------------

Woman 0 1 Man 3

Woman 1 2 Man 2

Woman 2 2 Man 1

Woman 3 2 Man 0

Mean choice = 1.75

Code specifications:

The header comment lines at the top of your java files contain a brief description of the program or the class. The description should be one or 2 lines long describing the purpose of the program or the class.

You also have to include comment lines in all of your public methods, static or not.

Use Javadocs comment formats for program and public methods documentation.

Use descriptive variable names and function names.

Define constants whenever appropriate