hi, i need some help with progamming..i have a program which has to implement gale shapley's algorithm. i have 2 preference lists one is for companies and the other is for persons. i have to match the companies with the persons according to the gale shapley algorithm.
/----------------------------------------------------------------------------------------/
please help me as i m not getting the correct output.
Code:
/----match.h--------------------------------------------------------------/
#include <iostream>
#include<vector>
using namespace std;
/*------Declarations------*/
extern int n; // No. of companies.
extern int m; // No. of persons.
void read(); // Reads the input values from the user.
void gsa(); // implementing gale shapley algorithm.
// class Data Structure for Company.
class company
{
public:
int openPos; // "oi" No. of open positions in a company.
int perAccept; // "ai" No. of persons acceptable by company.
int cId; // Id's of companies.
vector <int> currentmatch; // vector to keep track of the current matches.
};
// Class Data Structure for Person.
class person
{
public:
int comAccept; // "ai" No. of companies acceptable by person.
int pId; // Vector containing Id's of persons.
vector <int> currentmatch; // vector to keep track of the current matches.
};
/------------acme.cpp-------------------------------------------------------------/
# include"match.h"
using namespace std;
int main()
{
cout<<"xxxxx\n";
read();// reads the input values from the user.
gsa(); // implements gale shapley algorithm.
return 0;
}
/------------match.cpp-----------------------------------------------------------/
# include"match.h"
using namespace std;
int n; // No. of companies.
int m; // No. of persons.
int temp,temp1,temp2; // temporary variables to store data.
company cpy; // an object of type company.
vector <company> cmp; // a Vector of type company.
vector <vector <int> > cPref; // Vector having the preference list for companies.
vector <vector <int> > pPref; // Vector having the preference list for persons.
person per; // an object of type person.
vector <person> psn; // a Vector of type person.
//vector <int>::iterator iter;
// Reads the input values from the user.
void read()
{
cout<<"Enter the number of companies : ";
cin>>n;
cout<<"Enter the number of persons : ";
cin>>m;
cPref.resize(n); // resize the vector.
pPref.resize(m); // resize the vector.
for(int i=0;i<n;i++)
{
cout<<"The company id :"<<i<<endl;
cpy.cId=i;
cout<<"Enter the number of open positions for company : ";
cin>>cpy.openPos;
cout<<"Enter the number of applicants acceptable : ";
cin>>cpy.perAccept;
cpy.currentmatch.resize(cpy.openPos);
cmp.push_back(cpy);
cPref[i].resize(cpy.perAccept);
for(int j=0;j<cpy.perAccept;j++)
{
cout<<"Enter the preference ";
cin>>temp; // this value goes in cPref.
cPref[i][j]=temp;
}
}
for(int i=0;i<cmp.size();i++)
{
cout<<cmp[i].cId<<" ";
cout<<cmp[i].openPos<<" ";
cout<<cmp[i].perAccept<<endl;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<cPref[i].size();j++)
{
cout<<cPref[i][j]<<" ";
}
cout<<endl;
}
for(int i=0;i<m;i++)
{
cout<<"Enter the person id :"<<i;
per.pId=i;
cout<<endl;
cout<<"Enter the number of companies acceptable for person : ";
cin>>per.comAccept;
psn.push_back(per);
pPref[i].resize(per.comAccept);
for(int j=0;j<per.comAccept;j++)
{
cout<<"Enter the preference ";
cin>>temp1; // this value goes in cPref.
pPref[i][j]=temp1;
}
}
for(int i=0;i<psn.size();i++)
{
cout<<psn[i].pId<<" ";
cout<<psn[i].comAccept<<endl;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<pPref[i].size();j++)
{
cout<<pPref[i][j]<<" ";
}
cout<<endl;
}
}
// Implements the Gale-Shapley algorithm.
void gsa()
{
// take the first company and check the no. of positions available
// if no positions are available then do nothing
// if positions are available then check the no. of acceptable.
// if acceptable is zero then do nothing
// otherwise check the preference for company to person
// if the person is free then the company hire that
// otherwise it should check its next preference and go on.
// once a company hires a person store the value of that person
// in company's currentmatch and company value in persons currentmatch.
for(int i=0;i<n;i++)
{
if(cmp[i].openPos!=0)
{
if(cmp[i].perAccept!=0)
{
if(cpy.currentmatch.size()!=0)
{
for(int j=cmp[i].perAccept;j>0;j--)
{
temp2=cPref[i][j];
//for(int k=0;k<m;k++)
//{
if(pPref[i][j]==temp2)
{
cpy.currentmatch.push_back(pPref[i][j]);
per.currentmatch.push_back(cPref[i][j]); }
//}
}
}
}
}
}
for(int i=0;i<cpy.currentmatch.size();i++)
{
cout<<cpy.currentmatch[i]<<endl;
}
cout<<"akash";
for(int i=0;i<per.currentmatch.size();i++)
{
cout<<per.currentmatch[i]<<endl;
}
}
please help me as i m not getting the correct output.
Comment