-- Program to solve arbitrary instances of the stable roommates problem -- Author: Rob Irving, University of Glasgow -- Date: August 2000 -- Input is as follows: -- Line 1: N, a positive integer, size of instance -- Lines 2..N+1: the preference lists, each has form X : A B C ... -- where X is the owner and A, B, C, ... are entries in order; -- person identifiers are arbitrary strings of upt to 20 chars -- Output consists of: -- the original preference lists; -- the so-called 'phase-1 table'; -- an indication of whether a stable matching exists; -- if so, the preference lists annotated with one such matching -- and a list of the matched pairs -- Assumptions -- each person's list is on a single line, with no trailing blanks; -- number of lists corresponds to input value of n -- lists need not be complete, nor need they be consistent with Ada.Text_Io; use Ada.Text_Io; with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; with Rm_Pref_Info; procedure Solve_Roommates is N : Natural; begin Get(N); -- the number of persons in the instance Skip_Line; declare -- block to allow instantiation of appropriate package package P is new Rm_Pref_Info(N); -- N is appropriate size for -- the preference structure use P; P_I : Pref_Info_Type; -- the preference structure Sm_Possible : Boolean := True; -- stable matching still possible while this true Sm_Found : Boolean := False; -- stable matching found when this true begin -- Get the preference lists Get_Pref_Info(P_I); -- Echo the given lists Put("Given preference lists:"); New_Line(2); Put_Complete_Pref_Lists(P_I); New_Line(3); -- Apply phase 1 of the roommates algorithm Apply_Phase_1(P_I, Sm_Possible); Put_Line("Phase 1 Lists:"); New_Line; Put_Current_Pref_Lists(P_I); New_Line(3); if not Sm_Possible then Put_Line("No stable matching exists"); else -- apply phase 2 of the roomates algorithm Apply_Phase_2(P_I, Sm_Found); if Sm_Found then Put("Stable matching displayed as follows:"); New_Line(2); Display_Stable_Matching(P_I); New_Line(3); Put("Stable matching listed as follows:"); New_Line(2); List_Stable_Matching(P_I); else Put_Line("No stable matching exists"); end if; end if; exception when Table_Overflow => Put_Line("Too many names; perhaps a name was mis-spelt."); Put_Line("Please check data."); when Pref_List_Error => Put_Line("Error in input."); Put_Line("Some person appears on his own preference list"); end; end Solve_Roommates;