The Hospitals/Residents Program
-------------------------------

Rob Irving, University of Glasgow
---------------------------------


General
-------

This is a program designed to solve arbitrary instances of the hospitals / residents
problem [1, 2]. It incorporates the extended version of the Gale-Shapley algorithm first published in [1],
and described in detail in [2].

For a given instance of the problem, the program will find both the resident-optimal
and the hospital-optimal stable matching.

The preference lists need not be complete - in other words, participants may class
certain others as unacceptable. Nor need they be consistent  -  X may appear on Y's
preference list even although Y does not appear on that of X (but in such a case X and
Y cannot, of course, be paired in a stable matching).

The participants may be represented by arbitrary identifiers of up to 20 characters in length.


Input / output
--------------

The program is entirely text-based, reading from standard input and writing to standard output.

The required input is as follows: 
   -- line 1: N M  -  positive integers, numbers of residents and
      hospitals respectively, space-separated
   -- lines 2..N+1: the resident preference lists, each has form X : A B C ...
   -- where X is the owner and A, B, C, ... are entries in order;
   -- lines N+2..M+N+1: the hospital preference lists, each has form X : P : A B C ...
   -- where X is the owner, P is the number of posts, and A, B, C, ... are entries in order;
   -- identifiers are arbitrary strings of up to 20 characters, space-separated in the lists


The output consists of:
   -- the original preference lists
   -- the so-called 'GS lists'
   -- the preference lists annotated with the resident-optimal matching,
      and for each hospital, the number of posts filled
   -- a list of the matched pairs for the resident-optimal matching
   -- the preference lists annotated with the hospital-optimal matching,
      and for each hospital, the number of posts filled
   -- a list of the matched pairs for the hospital-optimal matching
   
   
-- Assumptions
   -- each preference list is on a single line, with no trailing blanks;
   -- the number of lists corresponds exactly to the input values of N and M
   -- lists need not be complete, nor need they be consistent, but no list contains
      an identifier that does not have its own list, and no list contains a repeated entry
   -- each line is terminated by an EOL (end of line) character



Source code
-----------

The src folder contains the source code, written in Ada 95.  It consists of the following:

	-- a main program, solve_hr
	-- a generic package to represent preference information, hr_pref_info
	-- a generic package to represent a table of names, name_table
	-- a package to represent names, names
	-- a generic package to represent a stack, stack

It is portable, and may be compiled with any Ada 95 compiler.


Executable
----------

The bin folder contains executable versions for Windows and Unix (PC x86
and Sparc Solaris)

	-- solve_hr.exe   for Windows
	-- solve_hr.x86  for Unix on PC architecture
	-- solve_hr.sparc  for Unix on Sparc architecture

together with sample input files.


DISCLAIMER: this program is not supported, and although it has been subjected
to extensive testing, the authors cannot take responsibility for any loss etc.
resulting from errors or unexpected behaviour.

Copies of the program may be made freely for private study or educational use,
provided that the program headers acknowledging the authors are retained.


References
----------

1. D.Gale & L.S.Shapley, College admissions and the stability of marriage, American
Mathematical Monthly, 69 (1962), 9 - 15.

2. D.Gusfield & R.W.Irving, The Stable Marriage Problem: Structure and Algorithms,
MIT Press, 1989.