//March 2016, Etemadi and Lu
//E_g method
#include<iostream>
#include<fstream>
#include<string.h>
#include<iomanip>
#include<omp.h>
#include<cstdlib>
#include<time.h>
#include <cmath>
#include <iomanip>
using namespace std;             
char Dataset_name[20][30]={"Ego-facebook","Enron-email","Brightkite","Dblp-Coau"
                           ,"Amazon","Web-NotreDame","Citeseer","Dogster","Web-Google","Youtube","Dblp","As-skitter","FLicker","Orkut","Livejournal"
                           ,"Orkut2","Web-Arabic","MicrosoftAG","Twitter","Friendster"};
// 0 "ego-Facebook"  ,1   "Enron-email",2   "Brightkite" ,3   "DBLP-coauthor",4   "amazon"      
// 5  "web-NotreDame", 6  "citeseer"     , 7 "Petster"     ,8 "web-Google" ,9  "Youtube"    ,10  "dblp"       ,11  "as-skitter"   ,12  "FLicker"
// 13 "Orkut"        , 14 "Livejournal"  ,15 "Orkut2"     ,16  "Web-Arabic",17  "MicrosoftAG",18  "twitter"      ,19  "friendster"                          
   
double min_RSE[20]={0.34, 0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 ,0.34 };
double step[20]={0.03, 0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 ,0.03 };
double max_RSE[20]={0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04};
long repeat[20]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};

class node
{
  public:
     long nid;
     node * link;
};

long count_closed_wedge(node **,long);
void run_dataset(long);
void load_graph(long,node **,long **,long,long);
void print_edges(node **,long);
void create_sample_graph_g(long **,node **,double,long &,long,long);
void delete_nodes(node **,long);
double find_p(double p1,double (*f)(double,double,double,double),double T,double K,double RSE );
double RSE_Eg(double T,double K,double p,double RSE);
int main()
{  srand (time(NULL));
   // #pragma omp  parallel for schedule(dynamic,1)   /*uncomment for parallel run*/
   for(long i=0;i<=7;i++)  
     run_dataset(i);     
   return 0; 
}

void run_dataset(long i)
{   unsigned long N=0,M=0,CW=0,T=0,K=0,W=0;double CC=0,degree_ratio=0; string dataname;long M_g=0,W_g=0;
    char path[300]="../";
    strcat(path,Dataset_name[i]);
    strcat(path,"/properties.txt");
    ifstream fp;
    fp.open(path);
    fp>>dataname; fp>>N; fp>>M; fp>>CW; fp>>CC;fp>>W;fp>>T;fp>>K;fp>>degree_ratio;
    fp.close();
    //cout<<"\ndata"<<dataname<<"N="<<N<<"M="<<M<<"Cw="<<CW<<"W="<<W<<"T="<<T<<"K="<<K<<"deg="<<degree_ratio;
    node **nodes_G=new node*[N];    
    for(long t=0;t<N;t++){
	   nodes_G[t]=new node();
     nodes_G[t]->nid=0;
	   nodes_G[t]->link=NULL;
    }
    long **edges_G=new long*[M+1];
    for(long u = 0; u <=M; u++)
         edges_G[u] = new long[2];
    load_graph(i,nodes_G,edges_G,M,N); 
   // print_edges(nodes_G,N); 
    long CW_REg=0;   
    char path_results_REg[100]="intermidiate_data_RE_g/";
    char REg_file_name[400]="";strcat(REg_file_name,path_results_REg);strcat(REg_file_name,Dataset_name[i]);strcat(REg_file_name,"-raw-data-RE_g.txt"); 
    ofstream fp_raw_REg;fp_raw_REg.open(REg_file_name);  
    char REg_file_name1[400]="";strcat(REg_file_name1,path_results_REg);strcat(REg_file_name1,Dataset_name[i]);
    strcat(REg_file_name1,"-raw-data-plot-RE_g.txt"); 
    ofstream fp_raw_plot_REg;fp_raw_plot_REg.open(REg_file_name1);
     
    fp_raw_REg<<"****% Etemadi and Lu   Date: " <<__TIMESTAMP__;fp_raw_plot_REg<<"****% Etemadi and Lu   Date: " <<__TIMESTAMP__;
    fp_raw_REg<<"\nGraph name= "<<Dataset_name[i]<< " C= "<<CC<<" N= "<<N<<" M= "<<M<<" Triangles= "<<T
              <<" Pairs of dependent tiangles(K)= "<< K<<"  CW= "<<CW<<"  W= "<<W<<" degree ratio="<<degree_ratio<<"\n\n # iteration= "<< repeat[i]<<"\n\n";
    fp_raw_plot_REg<<"\nGraph name= "<<Dataset_name[i]<< " C= "<<CC<<" N= "<<N<<" M= "<<M<<" Triangles= "<<T<<" Pairs of dependent tiangles(K)= "
                   << K<<"  CW= "<<CW<<"  W= "<<W<<" degree ratio="<<degree_ratio<<"\n\n # iteration= "<< repeat[i]<<"\n\n";
    fp_raw_REg<<CC<<","<<N<<","<<M<<","<<T<<","<< K<<","<<CW<<","<<W<<","<<degree_ratio<<"\n"<< repeat[i]<<"\n";  
    fp_raw_plot_REg<<CC<<","<<N<<","<<M<<","<<T<<","<< K<<","<<CW<<","<<W<<","<<degree_ratio<<"\n"<< repeat[i]<<"\n";
    fp_raw_plot_REg<<"#run                   # sampled edges        CW             \n";                                  
    fp_raw_plot_REg<<"---------------------  ---------------------  -------------  \n";
      
    
    double Ecc=0;
    node **nodes_g=new node*[N];
    for(long t=0;t<N;t++){
	          nodes_g[t]=new node();
            nodes_g[t]->nid=0;
	          nodes_g[t]->link=NULL;
         }
    node **nodes_g1=new node*[N];
    for(long t=0;t<N;t++){
	          nodes_g1[t]=new node();
            nodes_g1[t]->nid=0;
	          nodes_g1[t]->link=NULL;
         }     
    double prob=0.0; double step1=step[i];
    double Delta_g;
    for(double sz=min_RSE[i];sz>=max_RSE[i];sz=sz-step1){
       // select Delta_g=sz;
       Delta_g=(3.0/(sz*sz));
       prob = pow((4.0 * Delta_g*M) / (N * N * degree_ratio * CC),(1.0/3.0));
       prob = (prob * N) / (2.0 * M); 
       prob=find_p(prob,RSE_Eg,T,K,sz);
       fp_raw_plot_REg<<prob<<",0,0,0,0,0\n";       
       fp_raw_REg<<"\n\np="<<setprecision(15)<<prob<<"\n       #run                   # sampled edges        CW\n";                    
       fp_raw_REg<<"---------------------  ---------------------  -------------  \n";
       W_g=0;
       for(long r=0;r<repeat[i];r++){
         
         create_sample_graph_g(edges_G,nodes_g,prob,M_g,N,M);
         CW_REg=count_closed_wedge(nodes_g,N);
         fp_raw_plot_REg<<r<<","<<M_g<<","<<CW_REg<<"\n";
         fp_raw_REg<<setw(21)<<r<<setw(21)<<M_g<<setw(13)<<CW_REg<<"\n";
         delete_nodes(nodes_g,N);
         delete_nodes(nodes_g1,N);
       }//for(long r=0;
       
    }//for(double sz=min_cw 
    delete_nodes(nodes_G,N);
    delete [] nodes_G;
    delete [] nodes_g;
    fp_raw_REg.close();
    fp_raw_plot_REg.close();
    
}
//*************************

double find_p(double p1,double (*f)(double,double,double,double),double T,double K,double RSE ){
  double p0=0.8,p_new=0;
  do
  {  
     p_new=(p0+p1)/2.0;
     if(abs(f(T,K,p_new,RSE))<=0.000000001)
        return p_new;
     else if (f(T,K,p_new,RSE)*f(T,K,p1,RSE)<0){
        p0=p_new;
     }
     else{
     p1=p_new;
     }
  }while(1);   
}
double RSE_Eg(double T,double K,double p,double RSE){
   double a=RSE-pow((1.0/(T*p*p*p))*((1-p*p*p)+(2.0*K/T)*(p*p-p*p*p)),(1.0/2.0));
   return a; 
}


//******load graph*********
void load_graph(long ii,node *nodes[],long **edges_G, long M,long N)
{   ifstream fp;long s,e,k=1;node *p=NULL; node *ne=NULL,*le=NULL;
    char path1[300]="../";
    strcat(path1,Dataset_name[ii]);
    strcat(path1,"/edges.txt");
    fp.open(path1);   
    for(long j=0;j<M;j++){
       fp>>s;fp>>e;     
       if(s<e){//aa e
         edges_G[j+1][0]=s; edges_G[j+1][1]=e;
         p=new node();p->nid=e;
         nodes[s]->nid++;
         p->link=nodes[s]->link;
         nodes[s]->link=p;     
         }
      else if(s>e) {   // add s
         edges_G[j+1][0]=e; edges_G[j+1][1]=s;
         p=new node();
         p->nid=s;
         nodes[e]->nid++;
         p->link=nodes[e]->link;
         nodes[e]->link=p;
       }  
     }      
    fp.close();
}
void print_edges(node *nodes[],long N)
{    node *p;
     for(long i=0;i<N;i++)
     {  p=nodes[i]->link;
        while(p!=NULL){
          cout<<"\nedge="<<i<<" "<<p->nid;
          p=p->link;
        }
     }
} 
void create_sample_graph_g(long **edges_G,node *nodes_g[],double p,long &num_sampled_edges,long N,long M){   
    double ran_num,a1=0,a2=0,a3=0;long s,e; node *pn,*fnew; num_sampled_edges=0;  
    long ki=0,rand1; 
    while (ki<M){  
       rand1=rand()%RAND_MAX;
       ran_num=(double) rand1 / (double) (RAND_MAX);
       a1= log((1-ran_num)/(1-p));
       a2=log(1-p);
       a3=ceil(((a1/a2)+1));
       ki=ki+a3;
       if(ki>0 && ki<=M){
         s=edges_G[ki][0];
         e=edges_G[ki][1];
         num_sampled_edges++;
         //if(s<=e){//aa e
         fnew=new node();fnew->nid=e;nodes_g[s]->nid++;fnew->link=NULL;
         fnew->link=nodes_g[s]->link;
         nodes_g[s]->link=fnew;     
        // }
        // else {   // add s
        fnew=new node();fnew->nid=s;nodes_g[e]->nid++;fnew->link=NULL;
        fnew->link=nodes_g[e]->link;
        nodes_g[e]->link=fnew;
       
       } // end if(ki<M)   
    }// end while  
}
long count_closed_wedge(node * nodes_g[],long N)
{   long s,e,com=0,CW=0;node *pn,*pn1,*fs;
    for(long i=0;i<N;i++){
     pn= nodes_g[i]->link;
     while(pn!=NULL){
       s=pn->nid;pn1= pn->link;
       while(pn1!=NULL){
         e=pn1->nid;
         fs=nodes_g[s]->link; 
         com=0;
         while(fs!=NULL && com==0){
           if(fs->nid==e){  
              com++; break;
            }
           else{
              fs=fs->link;
           }           
         }  
         if(com!=0)     
            CW=CW+1;  
        pn1=pn1->link;         
       }       
       pn=pn->link;
     }// end while(pn!=NULL)
    }// end for i
    return CW;
}

void delete_nodes(node *nodes[],long N)
{  node *pn,*pn1;
   for(long i=0;i<N;i++){
      pn= nodes[i]->link;
      nodes[i]->link=NULL;
      nodes[i]->nid=0;
      while(pn!=NULL){
         pn1=pn;         
         pn=pn->link;
         delete pn1;
      }      
   }
}