/*
Using Gale-Shapley algorithm find perfect matching between Students and Mentor. Input needs to be taken from two files, named Student.csv and Mentor.csv. Each student and mentor should provide their preferences via these two files. Output should produce the allocation between them.
*/
Sample Files
C Program Code
/*Implementation of Gale-Shapley algorithm find perfect matching between Students and Mentor.*/
#include<stdio.h>
#include<stdlib.h>
/*Macro to calculate the Array Size*/
#define ARRAYSIZE(x) (sizeof(x)/sizeof(*(x)))
#define TRUE 1
#define FALSE 0
/*Declaration of functions*/
void compute_stable_matching( int number, int **student_pref_list, int **mentor_pref_list );
int Is_student_Free_and_Notproposed(int number,int *student_free_list, int **student_proposed_list);
int find_Free_Student(int number, int *student_free_list);
int find_Free_Student_Not_Proposed_Mentor(int number, int free_Student, int **student_proposed_list, int **student_pref_list);
int find_To_Whom_Mentor_Engaged(int number, int mentor, int *engaged_list);
void print_2D_array(int rows, int cols, int **array);
void print_matched_array(int rows, int *array);
int main()
{
const char Student_filename[] = "Student.csv";
const char Mentor_filename[] = "Mentor.csv";
size_t i, j, k;
int s_count, m_count;
char buffer[BUFSIZ], *ptr;
/*File Pointers to read the Preference file.*/
FILE *file_student, *file_mentor;
/*Pointers to Preference list and other Arrays*/
int **student_pref_list;
int **mentor_pref_list;
/* Count number of lines in student CVS file.*/
file_student = fopen(Student_filename, "r");
if ( file_student )
{
for ( s_count = 0; fgets(buffer, sizeof buffer, file_student); ++s_count )
{ }
}
else /* fopen() returned NULL */
{
perror(Student_filename);
}
fclose(file_student);
/* Count number of lines in mentor CVS file.*/
file_mentor = fopen(Mentor_filename, "r");
if ( file_mentor )
{
for ( m_count = 0; fgets(buffer, sizeof buffer, file_mentor); ++m_count )
{ }
}
else /* fopen() returned NULL */
{
perror(Mentor_filename);
}
fclose(file_mentor);
/* Checking whether s_count and m_count is equal or not. If not, exit the peogram.*/
if (s_count!=m_count)
{
printf("The Number of students and Number of mentors are not equal. Unable to proceed..");
exit(0);
}
/*Allocating the student_pref_list Array Dynamically.. */
student_pref_list = (int **)malloc(s_count * sizeof(int *));
for(i=0; i<s_count; i++)
{
student_pref_list[i] = (int *)malloc(m_count * sizeof(int));
}
/*Allocating the mentor_pref_list Array Dynamically.. */
mentor_pref_list = (int **)malloc(m_count * sizeof(int *));
for(i=0; i<m_count; i++)
mentor_pref_list[i] = (int *)malloc(s_count* sizeof(int));
/* Reading Preferences from the student.CVS file and storing it in "student_pref_list".*/
file_student = fopen(Student_filename, "r");
if ( file_student )
{
/*Read each line from the array*/
for ( i = 0; fgets(buffer, sizeof buffer, file_student); ++i )
{
/* Parse the comma-separated values from each line into "student_pref_list". */
for ( j = 0, ptr = buffer; j < m_count; ++j, ++ptr )
{
student_pref_list[i][j] = (int)strtol(ptr, &ptr, 10);
}
}
}
else /* fopen() returned NULL */
{
perror(Student_filename);
}
fclose(file_student);
/* Reading Preferences from the mentor.CVS file and storing it in "mentor_pref_list".*/
file_mentor = fopen(Mentor_filename, "r");
if ( file_mentor )
{
/*Read each line from the array*/
for ( i = 0; fgets(buffer, sizeof buffer, file_mentor); ++i )
{
/* Parse the comma-separated values from each line into "student_pref_list". */
for ( j = 0, ptr = buffer; j < s_count; ++j, ++ptr )
{
mentor_pref_list[i][j] = (int)strtol(ptr, &ptr, 10);
}
}
}
else /* fopen() returned NULL */
{
perror(Mentor_filename);
}
fclose(file_mentor);
/*Printing the "student_pref_list" Array.*/
printf("\nStudent Preference List:\n");
print_2D_array(s_count, m_count, student_pref_list);
/*Printing the "mentor_pref_list" Array.*/
printf("\nMentor Preference List:\n");
print_2D_array(m_count, s_count, mentor_pref_list);
/*Calling compute_stable_matching(...) Function to compute the Matchings*/
compute_stable_matching( s_count, student_pref_list, mentor_pref_list );
return 0;
}
/*---------------------*/
/*End of Main Function*/
/*---------------------*/
/*Function Defination of compute_stable_matching(...). */
void compute_stable_matching( int number, int ** student_pref_list, int **mentor_pref_list )
{
int i,j, free_Student, engaged_student, not_Proposed_Mentor, not_Proposed_Mentor_loc;
/*Pointers to few necessary Arrays*/
int *student_free_list;
int *mentor_free_list;
int *engaged_list;
int **student_proposed_list;
/*Allocating the other required Array's Dynamically.. */
student_free_list = (int *)malloc(number * sizeof(int));
mentor_free_list = (int *)malloc(number * sizeof(int));
engaged_list = (int *)malloc(number * sizeof(int));
/*Initilizing all the Array's values as FALSE(0)... */
for (i=0; i<number; ++i)
{
student_free_list[i] = FALSE;
mentor_free_list[i] = FALSE;
engaged_list[i] = FALSE;
}
/*Allocating the student_proposed_list Array Dynamically.. */
student_proposed_list = (int **)malloc(number * sizeof(int *));
for(i=0; i<number; i++)
{
student_proposed_list[i] = (int *)malloc(number * sizeof(int));
}
/*Initilizing all the "student_proposed_list" Array values with FALSE(0)... */
for(i=0; i<number; ++i)
{
for(j=0; j<number; ++j)
{
student_proposed_list[i][j] = FALSE;
}
}
/*-------------------------------------------------*/
/*Gale-Shapely Algorithm for finding Stable Matchings*/
/*-------------------------------------------------*/
while( Is_student_Free_and_Notproposed(number,student_free_list, student_proposed_list ) )
{
free_Student = find_Free_Student(number, student_free_list);
not_Proposed_Mentor_loc = find_Free_Student_Not_Proposed_Mentor(number, free_Student, student_proposed_list, student_pref_list);
not_Proposed_Mentor = not_Proposed_Mentor_loc+1;
if( mentor_free_list[not_Proposed_Mentor_loc] == FALSE )
{
/* (Student, Mentor) become engaged*/
engaged_list[free_Student] = not_Proposed_Mentor;
/*Makind the Necessary Changes of the free values*/
student_proposed_list[free_Student][not_Proposed_Mentor_loc] = TRUE;
student_free_list[free_Student] = TRUE;
mentor_free_list[not_Proposed_Mentor_loc] = TRUE;
}
else
{
engaged_student = find_To_Whom_Mentor_Engaged(number, not_Proposed_Mentor, engaged_list);
/*If Mentor prefers "engaged_student" over "free_student". Keep "free_student" free and make necessary changes..*/
if (mentor_pref_list[not_Proposed_Mentor-1][engaged_student] < mentor_pref_list[not_Proposed_Mentor-1][free_Student])
{
student_proposed_list[free_Student][not_Proposed_Mentor_loc] = TRUE;
}
/*If Mentor prefers "free_student" over "engaged_student". Engage the Mentor with "free_student" and make "engaged_student" free..*/
else
{
engaged_list[free_Student] = not_Proposed_Mentor;
engaged_list[engaged_student] = FALSE;
student_proposed_list[free_Student][not_Proposed_Mentor_loc] = TRUE;
student_free_list[free_Student] = TRUE;
student_free_list[engaged_student] = FALSE;
}
}
}
/*Display the Stable Matchings from the Engaged_list*/
printf("\n\nThe Final Stable Matching is: \n");
print_matched_array(number, engaged_list);
}
/*END of Cpmpute Matching Function*/
/*Function Defination of print_2D_array(...). */
void print_2D_array(int rows, int cols, int **array)
{
int i,j;
for ( i = 0; i < rows; ++i )
{
for ( j = 0; j < cols; ++j )
{
printf("%3d ", array[i][j]);
}
printf("\n");
}
}
/*Function Defination of print_2D_array(...). */
void print_matched_array(int rows, int *array)
{
int i;
for ( i = 0; i < rows; ++i )
{
printf("( %d, %d) ", i+1, array[i]);
}
printf("\n\n");
}
int Is_student_Free_and_Notproposed(int number,int *student_free_list, int **student_proposed_list)
{
int i, j, r_value=FALSE;
for (i=0; i<number; i++)
{
if( student_free_list[i] == FALSE )
{
for(j=0; j<number; ++j)
{
if( student_proposed_list[i][j] == FALSE)
{
r_value=TRUE;
return r_value;
}
}
}
}
return r_value;
}
int find_Free_Student(int number, int *student_free_list)
{
int i, r_value;
for( i=0; i<number; i++)
{
if( student_free_list[i] == FALSE)
{
r_value=i;
return r_value;
}
}
}
int find_Free_Student_Not_Proposed_Mentor(int number, int free_Student, int **student_proposed_list, int **student_pref_list)
{
int i,j;
for (i=1; i<=number; ++i)
{
for (j=0; j<number; ++j)
{
if( (student_pref_list[free_Student][j]==i) && (student_proposed_list [free_Student][j] == FALSE) )
{
return j;
}
}
}
}
int find_To_Whom_Mentor_Engaged(int number, int mentor, int *engaged_list)
{
int i;
for (i=0; i<number; ++i)
{
if (engaged_list[i] == mentor)
{
return i;
}
}
}
/*End of the Program*/
Using Gale-Shapley algorithm find perfect matching between Students and Mentor. Input needs to be taken from two files, named Student.csv and Mentor.csv. Each student and mentor should provide their preferences via these two files. Output should produce the allocation between them.
*/
Sample Files
C Program Code
/*Implementation of Gale-Shapley algorithm find perfect matching between Students and Mentor.*/
#include<stdio.h>
#include<stdlib.h>
/*Macro to calculate the Array Size*/
#define ARRAYSIZE(x) (sizeof(x)/sizeof(*(x)))
#define TRUE 1
#define FALSE 0
/*Declaration of functions*/
void compute_stable_matching( int number, int **student_pref_list, int **mentor_pref_list );
int Is_student_Free_and_Notproposed(int number,int *student_free_list, int **student_proposed_list);
int find_Free_Student(int number, int *student_free_list);
int find_Free_Student_Not_Proposed_Mentor(int number, int free_Student, int **student_proposed_list, int **student_pref_list);
int find_To_Whom_Mentor_Engaged(int number, int mentor, int *engaged_list);
void print_2D_array(int rows, int cols, int **array);
void print_matched_array(int rows, int *array);
int main()
{
const char Student_filename[] = "Student.csv";
const char Mentor_filename[] = "Mentor.csv";
size_t i, j, k;
int s_count, m_count;
char buffer[BUFSIZ], *ptr;
/*File Pointers to read the Preference file.*/
FILE *file_student, *file_mentor;
/*Pointers to Preference list and other Arrays*/
int **student_pref_list;
int **mentor_pref_list;
/* Count number of lines in student CVS file.*/
file_student = fopen(Student_filename, "r");
if ( file_student )
{
for ( s_count = 0; fgets(buffer, sizeof buffer, file_student); ++s_count )
{ }
}
else /* fopen() returned NULL */
{
perror(Student_filename);
}
fclose(file_student);
/* Count number of lines in mentor CVS file.*/
file_mentor = fopen(Mentor_filename, "r");
if ( file_mentor )
{
for ( m_count = 0; fgets(buffer, sizeof buffer, file_mentor); ++m_count )
{ }
}
else /* fopen() returned NULL */
{
perror(Mentor_filename);
}
fclose(file_mentor);
/* Checking whether s_count and m_count is equal or not. If not, exit the peogram.*/
if (s_count!=m_count)
{
printf("The Number of students and Number of mentors are not equal. Unable to proceed..");
exit(0);
}
/*Allocating the student_pref_list Array Dynamically.. */
student_pref_list = (int **)malloc(s_count * sizeof(int *));
for(i=0; i<s_count; i++)
{
student_pref_list[i] = (int *)malloc(m_count * sizeof(int));
}
/*Allocating the mentor_pref_list Array Dynamically.. */
mentor_pref_list = (int **)malloc(m_count * sizeof(int *));
for(i=0; i<m_count; i++)
mentor_pref_list[i] = (int *)malloc(s_count* sizeof(int));
/* Reading Preferences from the student.CVS file and storing it in "student_pref_list".*/
file_student = fopen(Student_filename, "r");
if ( file_student )
{
/*Read each line from the array*/
for ( i = 0; fgets(buffer, sizeof buffer, file_student); ++i )
{
/* Parse the comma-separated values from each line into "student_pref_list". */
for ( j = 0, ptr = buffer; j < m_count; ++j, ++ptr )
{
student_pref_list[i][j] = (int)strtol(ptr, &ptr, 10);
}
}
}
else /* fopen() returned NULL */
{
perror(Student_filename);
}
fclose(file_student);
/* Reading Preferences from the mentor.CVS file and storing it in "mentor_pref_list".*/
file_mentor = fopen(Mentor_filename, "r");
if ( file_mentor )
{
/*Read each line from the array*/
for ( i = 0; fgets(buffer, sizeof buffer, file_mentor); ++i )
{
/* Parse the comma-separated values from each line into "student_pref_list". */
for ( j = 0, ptr = buffer; j < s_count; ++j, ++ptr )
{
mentor_pref_list[i][j] = (int)strtol(ptr, &ptr, 10);
}
}
}
else /* fopen() returned NULL */
{
perror(Mentor_filename);
}
fclose(file_mentor);
/*Printing the "student_pref_list" Array.*/
printf("\nStudent Preference List:\n");
print_2D_array(s_count, m_count, student_pref_list);
/*Printing the "mentor_pref_list" Array.*/
printf("\nMentor Preference List:\n");
print_2D_array(m_count, s_count, mentor_pref_list);
/*Calling compute_stable_matching(...) Function to compute the Matchings*/
compute_stable_matching( s_count, student_pref_list, mentor_pref_list );
return 0;
}
/*---------------------*/
/*End of Main Function*/
/*---------------------*/
/*Function Defination of compute_stable_matching(...). */
void compute_stable_matching( int number, int ** student_pref_list, int **mentor_pref_list )
{
int i,j, free_Student, engaged_student, not_Proposed_Mentor, not_Proposed_Mentor_loc;
/*Pointers to few necessary Arrays*/
int *student_free_list;
int *mentor_free_list;
int *engaged_list;
int **student_proposed_list;
/*Allocating the other required Array's Dynamically.. */
student_free_list = (int *)malloc(number * sizeof(int));
mentor_free_list = (int *)malloc(number * sizeof(int));
engaged_list = (int *)malloc(number * sizeof(int));
/*Initilizing all the Array's values as FALSE(0)... */
for (i=0; i<number; ++i)
{
student_free_list[i] = FALSE;
mentor_free_list[i] = FALSE;
engaged_list[i] = FALSE;
}
/*Allocating the student_proposed_list Array Dynamically.. */
student_proposed_list = (int **)malloc(number * sizeof(int *));
for(i=0; i<number; i++)
{
student_proposed_list[i] = (int *)malloc(number * sizeof(int));
}
/*Initilizing all the "student_proposed_list" Array values with FALSE(0)... */
for(i=0; i<number; ++i)
{
for(j=0; j<number; ++j)
{
student_proposed_list[i][j] = FALSE;
}
}
/*-------------------------------------------------*/
/*Gale-Shapely Algorithm for finding Stable Matchings*/
/*-------------------------------------------------*/
while( Is_student_Free_and_Notproposed(number,student_free_list, student_proposed_list ) )
{
free_Student = find_Free_Student(number, student_free_list);
not_Proposed_Mentor_loc = find_Free_Student_Not_Proposed_Mentor(number, free_Student, student_proposed_list, student_pref_list);
not_Proposed_Mentor = not_Proposed_Mentor_loc+1;
if( mentor_free_list[not_Proposed_Mentor_loc] == FALSE )
{
/* (Student, Mentor) become engaged*/
engaged_list[free_Student] = not_Proposed_Mentor;
/*Makind the Necessary Changes of the free values*/
student_proposed_list[free_Student][not_Proposed_Mentor_loc] = TRUE;
student_free_list[free_Student] = TRUE;
mentor_free_list[not_Proposed_Mentor_loc] = TRUE;
}
else
{
engaged_student = find_To_Whom_Mentor_Engaged(number, not_Proposed_Mentor, engaged_list);
/*If Mentor prefers "engaged_student" over "free_student". Keep "free_student" free and make necessary changes..*/
if (mentor_pref_list[not_Proposed_Mentor-1][engaged_student] < mentor_pref_list[not_Proposed_Mentor-1][free_Student])
{
student_proposed_list[free_Student][not_Proposed_Mentor_loc] = TRUE;
}
/*If Mentor prefers "free_student" over "engaged_student". Engage the Mentor with "free_student" and make "engaged_student" free..*/
else
{
engaged_list[free_Student] = not_Proposed_Mentor;
engaged_list[engaged_student] = FALSE;
student_proposed_list[free_Student][not_Proposed_Mentor_loc] = TRUE;
student_free_list[free_Student] = TRUE;
student_free_list[engaged_student] = FALSE;
}
}
}
/*Display the Stable Matchings from the Engaged_list*/
printf("\n\nThe Final Stable Matching is: \n");
print_matched_array(number, engaged_list);
}
/*END of Cpmpute Matching Function*/
/*Function Defination of print_2D_array(...). */
void print_2D_array(int rows, int cols, int **array)
{
int i,j;
for ( i = 0; i < rows; ++i )
{
for ( j = 0; j < cols; ++j )
{
printf("%3d ", array[i][j]);
}
printf("\n");
}
}
/*Function Defination of print_2D_array(...). */
void print_matched_array(int rows, int *array)
{
int i;
for ( i = 0; i < rows; ++i )
{
printf("( %d, %d) ", i+1, array[i]);
}
printf("\n\n");
}
int Is_student_Free_and_Notproposed(int number,int *student_free_list, int **student_proposed_list)
{
int i, j, r_value=FALSE;
for (i=0; i<number; i++)
{
if( student_free_list[i] == FALSE )
{
for(j=0; j<number; ++j)
{
if( student_proposed_list[i][j] == FALSE)
{
r_value=TRUE;
return r_value;
}
}
}
}
return r_value;
}
int find_Free_Student(int number, int *student_free_list)
{
int i, r_value;
for( i=0; i<number; i++)
{
if( student_free_list[i] == FALSE)
{
r_value=i;
return r_value;
}
}
}
int find_Free_Student_Not_Proposed_Mentor(int number, int free_Student, int **student_proposed_list, int **student_pref_list)
{
int i,j;
for (i=1; i<=number; ++i)
{
for (j=0; j<number; ++j)
{
if( (student_pref_list[free_Student][j]==i) && (student_proposed_list [free_Student][j] == FALSE) )
{
return j;
}
}
}
}
int find_To_Whom_Mentor_Engaged(int number, int mentor, int *engaged_list)
{
int i;
for (i=0; i<number; ++i)
{
if (engaged_list[i] == mentor)
{
return i;
}
}
}
/*End of the Program*/
No comments:
Post a Comment