Java

Linear Data Structures

Stable Marriage Problem

Project 3 100 points Due Thursday October 12

Note: You must do your own work. Solutions for this problem exist on the Internet. Code copied from the Internet will get a grade of 0. Code from the Internet often uses the Map, HashMap, and ArrayList data strutures. These are not allowed. You must use the data structures defined in the text.

For this assignment, you may work in pairs. There is no extra credit for working alone.

The assignment is to write a console-based program to solve the Stable Matching Problem using the Gale-Shapley algorithm. You must use a linked list for the preference list of each man and woman. See the posting Stable Matching.ppt in the Algorithms folder. There are also numerous references to the Gale-Shapley algorithm on the Internet.

The input to the program will be a text file listing, in order,

1. the number n of men and women,

2. the names of the n men,

3. the names of the n women,

4. the list of preferences for each of the n men, and

5. the list of preferences for each of the n women.

For example, consider the following example of the contents of a file

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

5

Brian George John Robert Stephen

Anne Joyce Nancy Patricia Susan

// Preferences Men:

John: Susan Joyce Nancy Patricia Anne

Robert: Nancy Anne Joyce Susan Patricia

Brian: Patricia Susan Joyce Anne Nancy

Stephen: Joyce Anne Susan Nancy Patricia

George: Nancy Joyce Patricia Susan Anne

// Preferences Women:

Nancy: John Brian Stephen Robert George

Joyce: George John Stephen Robert Brian

Patricia: George Brian Robert Stephen John

Anne: George Stephen John Brian Robert

Susan: Brian George Stephen John Robert

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

The output will be the list of arranged marriages.

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

Marriages:

(Anne,Stephen)

(Joyce,George)

(Susan,John)

(Patricia,Brian)

(Nancy,Robert)

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

The program will operate as follows:

1. Ask the user for the name of the input file

2. Display the number of men and women, and the lists of men and women

3. Display the list of mens preferences and the list of womens preferences

4. Ask the user to select one of the following:

Men Propose

Women Propose

5. Ask the user for the go-ahead to apply the Gale-Shapley algorithm

6. Display the list of marriages.

The submission should include a printout of using the data given above.

Extra Credit: (30 points) Construct a GUI using JavaFX. The GUI must be defined in a separate class and follow the posted coding guidelines. You must declare all variables at the top of the class or method, and must not initialize variables in the declaration. (10 points for correctness of the GUI, 10 for the efficacy and attractiveness of the GUI, and 10 for following the coding guidelines nicely.)