pagerank.cpp

pagerank pagerank pagerank pagerank pagerank

//Simplified RankPage Algorithm
//input data in file
#include<iostream>
#include<algorithm>
#include<fstream>
#include<vector>
#include<math.h> 
#include <time.h>

using namespace std;
using std::vector;

const int scale=1000;

double sqr(double t)
{
  return t*t;       
}

bool Yes(double PRValue[][scale+1],int cc)
{
  double vary=0;
  cc=cc%2;
  int dd=(cc+1)%2;
  for (int i=1;i<=scale;i++)
    vary+=sqr((PRValue[cc][i]-PRValue[dd][i]));
  vary=sqrt(vary);
      
  return vary<=0.0000001?true:false;
}

int main()
{
  vector<int> PRGraph[scale+1];
  double PRValue[2][scale+1];        //recursive PageRank Value array
  int PRCount[scale+1];              //Voting count
  int seq[scale+1];                  //Page Number Array (for output)
  double PRparCount[scale+1];        //par PageRank Value in every iteration 
  char DataAddr[100];                //Data Address
  int i,j,k;                         //recursive variable
  int temp,pp;
  int tt=10001;
  int cc=0;
  //double start = time(NULL);
  
/* initialization */
  for (i=0;i<=scale;i++)
    {
      PRGraph[i].push_back(0);
      PRCount[i]=0;
      PRValue[0][i]=1;
      PRValue[1][i]=0;
    }  
/* Read from file */  
  for (i=0;i<scale;i++)
  {
     DataAddr[0]='\0';
     sprintf(DataAddr,"D:\\Documents\\My Studies\\Code\\PageRank\\data\\Demo%d\\%d",scale,i+1);
     fstream Demo(DataAddr);
     Demo>>tt;
     pp=0;
     temp=0;
     if (tt==10001)
       for (j=1;j<=scale;j++)
         {
           PRCount[i+1]=scale;
           PRGraph[j][0]+=1;
           PRGraph[j].push_back(i+1);
         }
     else
     { 
       {
         temp=tt;
         if (temp==pp)
           break; 
         PRGraph[tt][0]+=1;  
         PRGraph[tt].push_back(i+1); 
         tt=10001;
         pp=temp;
       } 
     while (!Demo.eof())
     {
       PRCount[i+1]+=1;
       Demo>>temp;
       if (temp==pp) 
         break; 
       PRGraph[temp][0]+=1;  
       PRGraph[temp].push_back(i+1);
       pp=temp;   
     }
     }
     Demo.close();  
  }
  
  /*
  double end = time(NULL);
  printf("%f seconds.\n",difftime(end,start));
  start = time(NULL); 
  for (i=1;i<=scale;i++)
    {
      k=PRGraph[i][0];
      for (j=1;j<=k;j++)
        cout<<PRGraph[i][j]<<" ";
      cout<<endl;                    
    }
  */

/* Iteration */  
  while (!Yes(PRValue,cc))
  {
    temp=cc%2;
    for (i=1;i<=scale;i++)
      PRparCount[i]=PRValue[temp][i]/PRCount[i];
    temp=(temp+1)%2;
    for (i=1;i<=scale;i++)
      {
        PRValue[temp][i]=0;
        k=PRGraph[i][0];
        for (j=1;j<=k;j++)
          PRValue[temp][i]+=PRparCount[PRGraph[i][j]];                    
      }  
    cc+=1;      
  }
  
  pp=cc;
  cc=cc%2;
  
/* idiotic sort */  
  for (i=1;i<=scale;i++)
    seq[i]=i;
  
  for (i=1;i<=scale;i++) 
    for (j=1;j<scale;j++)
      {
         if (PRValue[cc][i]<PRValue[cc][j])
         {
           double tmp=PRValue[cc][i];
           PRValue[cc][i]=PRValue[cc][j];
           PRValue[cc][j]=tmp;
           temp=seq[i];
           seq[i]=seq[j];
           seq[j]=temp;                                  
         }           
                          
      }
/* output to screen (why not to file?~?~??~) */
  for (i=1;i<=scale;i++)
    {
      printf("Pg%.5d: ",seq[i]);
      printf("%.7f ",PRValue[cc][i]);
      //cout<<"Page"<<seq[i]<<": "<<PRValue[cc][i]<<"  ";
      if (i%4==0)
        cout<<endl;                    
    }
  cout<<endl<<endl;
  cout<<"iteration times:"<<pp<<endl; 
  /*
  end = time(NULL);
  printf("%f seconds.\n",difftime(end,start));
  */
  
  system("pause"); 
}