MIS.cpp

//set input is the adjacent graph
#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 
#include <cstdlib>
#include <sys/stat.h>
using namespace std;
bool removable(vector<int> neighbor, vector<int> cover); 
int max_removable(vector<vector<int> > neighbors, vector<int> cover); 
vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover); 
vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover, int k); 
int cover_size(vector<int> cover); 

bool FileExists(string filename) {
    struct stat fileInfo;
    return stat(filename.c_str(), &fileInfo) == 0;
}

int main(int argc, char * argv[])
{ 
  string inFileName; 
  string outFileName; 
  if (argc <= 2) {
      cout << "not enough arguments" << endl;
      cout <<" you need to provide the adjacent graph file name and then desired output file name"<<endl; 
      exit (EXIT_FAILURE); 
  }else{
    inFileName = argv[1];
    outFileName = argv[2]; 
  } 
  
  //checking whehter the file exist or no 
  if (!FileExists(inFileName)){
      cout << inFileName << "  does not exist"<< endl;
      exit (EXIT_FAILURE); 
  }

  //  if (!FileExists(outFileName)){
  //      cout << outFileName << "  does not exist"<< endl;
  //      exit (EXIT_FAILURE); 
  //  }

  ifstream infile (inFileName.c_str()); 
  ofstream outfile (outFileName.c_str()); 
  cout<<"Independent Set Algorithm."<<endl; 
 int n, i, j, k, K, p, q, r, s, min, edge, counter=0; 
 infile>>n; 
 vector< vector<int> > graph; 
 for(i=0; i<n; i++) 
 { 
  vector<int> row; 
  for(j=0; j<n; j++) 
  { 
   infile>>edge; 
   row.push_back(edge); 
  } 
  graph.push_back(row); 
 } 
 //Find Neighbors 
 vector<vector<int> > neighbors; 
 for(i=0; i<graph.size(); i++) 
 { 
  vector<int> neighbor; 
  for(j=0; j<graph[i].size(); j++) 
  if(graph[i][j]==1) neighbor.push_back(j); 
  neighbors.push_back(neighbor); 
 } 
 cout<<"Graph has n = "<<n<<" vertices."<<endl; 
 //Read maximum size of Independent Set wanted 
 //cout<<"Find an Independent Set of size at least k = "; 
 K = 0; 
 //cin>>K; k=n-K; 
 k = n - K; 
 //Find Independent Sets 
 bool found=false; 
 cout<<"Finding Independent Sets..."<<endl; 
 min=n+1; 
 vector<vector<int> > covers; 
 vector<int> allcover; 
 for(i=0; i<graph.size(); i++) 
 allcover.push_back(1); 
 for(i=0; i<allcover.size(); i++) 
 { 
  if(found) break; 
  counter++;// cout<<counter<<". ";  outfile<<counter<<". "; 
  vector<int> cover=allcover; 
  cover[i]=0; 
  cover=procedure_1(neighbors,cover); 
  s=cover_size(cover); 
  if(s<min) min=s; 
  if(s<=k) 
  { 
   outfile<<"("<<n-s<<"): "; 
   for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<j+1<<" "; 
   outfile<<endl; 
   //cout<<"Independent Set Size: "<<n-s<<endl; 
   covers.push_back(cover); 
   found=true; 
   break; 
  } 
  for(j=0; j<n-k; j++) 
  cover=procedure_2(neighbors,cover,j); 
  s=cover_size(cover); 
  if(s<min) min=s; 
  outfile<<"Independent Set ("<<n-s<<"): "; 
  for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<j+1<<" "; 
  outfile<<endl; 
  //cout<<"Independent Set Size: "<<n-s<<endl; 
  covers.push_back(cover); 
  if(s<=k){ found=true; break; } 
 } 
//Pairwise Intersections 
 for(p=0; p<covers.size(); p++) 
 { 
  if(found) break; 
  for(q=p+1; q<covers.size(); q++) 
  { 
   if(found) break; 
   counter++; cout<<counter<<". ";  outfile<<counter<<". "; 
   vector<int> cover=allcover; 
   for(r=0; r<cover.size(); r++) 
   if(covers[p][r]==0 && covers[q][r]==0) cover[r]=0; 
   cover=procedure_1(neighbors,cover); 
   s=cover_size(cover); 
   if(s<min) min=s; 
   if(s<=k) 
   { 
    outfile<<"Independent Set ("<<n-s<<"): "; 
    for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<j+1<<" "; 
    outfile<<endl; 
    //cout<<"Independent Set Size: "<<n-s<<endl; 
    found=true; 
    break; 
   } 
   for(j=0; j<k; j++) 
   cover=procedure_2(neighbors,cover,j); 
   s=cover_size(cover); 
   if(s<min) min=s; 
   outfile<<"Independent Set ("<<n-s<<"): "; 
   for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<j+1<<" "; 
   outfile<<endl; 
   //cout<<"Independent Set Size: "<<n-s<<endl; 
   if(s<=k){ found=true; break; } 
   } 
 } 
 //if(found) cout<<"Found Independent Set of size at least "<<K<<"."<<endl; 
 //else cout<<"Could not find Independent Set of size at least "<<K<<"."<<endl 
 cout<<"Maximum Independent Set size found is "<<n-min<<"."<<endl; 
 cout<<"See " << argv[2] << " for results."<<endl; 
 //system("PAUSE"); 
 return 0; 
}

bool removable(vector<int> neighbor, vector<int> cover) 
{ 
 bool check=true; 
 for(int i=0; i<neighbor.size(); i++) 
 if(cover[neighbor[i]]==0) 
 { 
  check=false; 
  break; 
 } 
 return check; 
}

int max_removable(vector<vector<int> > neighbors, vector<int> cover) 
{ 
 int r=-1, max=-1; 
 for(int i=0; i<cover.size(); i++) 
 { 
  if(cover[i]==1 && removable(neighbors[i],cover)==true) 
  { 
   vector<int> temp_cover=cover; 
   temp_cover[i]=0; 
   int sum=0; 
   for(int j=0; j<temp_cover.size(); j++) 
   if(temp_cover[j]==1 && removable(neighbors[j], temp_cover)==true) 
   sum++; 
   if(sum>max) 
   { 
    max=sum; 
    r=i; 
   } 
  } 
 } 
 return r; 
}

vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover) 
{ 
 vector<int> temp_cover=cover; 
 int r=0; 
 while(r!=-1) 
 { 
  r= max_removable(neighbors,temp_cover); 
  if(r!=-1) temp_cover[r]=0; 
 } 
 return temp_cover; 
}

vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover, int k) 
{ 
 int count=0; 
 vector<int> temp_cover=cover; 
 int i=0; 
 for(int i=0; i<temp_cover.size(); i++) 
 { 
  if(temp_cover[i]==1) 
  { 
   int sum=0, index; 
   for(int j=0; j<neighbors[i].size(); j++) 
   if(temp_cover[neighbors[i][j]]==0) {index=j; sum++;} 
   if(sum==1 && cover[neighbors[i][index]]==0) 
   { 
    temp_cover[neighbors[i][index]]=1; 
    temp_cover[i]=0; 
    temp_cover=procedure_1(neighbors,temp_cover); 
    count++; 
   } 
   if(count>k) break; 
  } 
 } 
 return temp_cover; 
}

int cover_size(vector<int> cover) 
{ 
 int count=0; 
 for(int i=0; i<cover.size(); i++) 
 if(cover[i]==1) count++; 
 return count; 
}