//Create by GangYan,Wubo
//Revise on 09/01/06 03:32
#include "d:\scilab-4.0\routines\stack-c.h"
#include  <stdio.h>
#include  <stdlib.h>
#include  <math.h>
#include  <time.h>

void com __PARAMS((int *C,int m,int n,int *num,int *m0,int *inedge,int *outedge,double *pro,int *c,int *d));
void precom(int c,int num,int m0,double M,double P,double T);


struct  linknode {
    int             name;
    struct linknode *next; 
};

struct nodeinfo {
    int     degree;          //degree of the node
    int     com;             //the com-th community:{0,1,2,...,C-1}
    struct  linknode *next;
};

struct nodeinfo node[100000];

int edgenum;


int intcom(fname) 
char *fname;
{
    static int l1, m1, n1, l2, m2, n2, l3,m3,n3,l4,l5,l6,l7,l8;
    static int minlhs=0, maxlhs=2, minrhs=6, maxrhs=6;   //why the minlhs must equal zero??
    static int tmp1,tmp2,tmp3;
    static double tmp4,tmp5,tmp6;

    /* Check number of inputs (rhs=2) and outputs (lhs=1) */
    CheckRhs(minrhs,maxrhs) ;
    CheckLhs(minlhs,maxlhs) ;
    //m2=10;
    GetRhsVar(1, "i", &m1, &m1, &l1);   //the following sentence must be wrote together!!!! 
    GetRhsVar(2, "i", &m1, &m1, &l2);   
    GetRhsVar(3, "i", &m1, &m1, &l3);
    GetRhsVar(4, "i", &m1, &m1, &l4);
    GetRhsVar(5, "i", &m1, &m1, &l5);
    GetRhsVar(6, "d", &m1, &m1, &l6);

    tmp1=*istk(l1);  //number of communities  -> C
    tmp2=*istk(l2);  //the number of nodes in all communities -> N
    tmp3=*istk(l3);  //the number of nodes of intial nodes -> M0
    tmp4=(double)*istk(l4)+(*stk(l6)); //number of attaching edges each step -> M
    tmp5=(double)*istk(l5)+(1-*stk(l6)); //fraction of inter-attaching step -> P
//  sciprint("%e %e\n",tmp4,tmp5);
    tmp6=tmp2/tmp1-tmp3; //steps of evolution -> T
//  sciprint("tmp = %i %i %i %e %e %e\n",tmp1,tmp2,tmp3,tmp4,tmp5,tmp6);
    precom(tmp1,tmp2,tmp3,tmp4,tmp5,tmp6);
    m2=edgenum;
    CreateVar(7, "i", &m1, &m2, &l7);  
    CreateVar(8, "i", &m1, &m2, &l8);
    com(istk(l1), m1, m1, istk(l2),istk(l3),istk(l4),istk(l5),stk(l6),istk(l7),istk(l8));

    LhsVar(1) = 7;
    LhsVar(2)=  8;
    return 0;
}




//create the network and  inntial
void Create_Net(int N,int C,int M0,double M,double P,double T)       
{
    int     i,j,k;
    struct  linknode *p,*q;
    int      temp1;
    int      s;
    int      m;
    int      flag;
    double   ssk[100000];
    double   frand;
    double   kk;
    struct   linknode *r,*t;
    struct   linknode *p2;
    int      intM;
    double   doubleM;
    int      intrand;
    int      temp2;
    int      intP;
    double   doubleP;
    int temp;

//sciprint("%i %i %i %e %e %e\n",N,C,M0,M,P,T);	

    //initialization the network
    for (i=0;i<C;i++) {
        for (j=i*N/C;j<(i+1)*N/C;j++) {
            node[j].com=i;
            node[j].degree=0;
            node[j].next=NULL;
        }
    }

    for (i=0;i<C;i++) {
        for (j=i*N/C;j<(M0+i*N/C);j++) {
            for (k=i*N/C;k<(M0+i*N/C);k++) {
                if (k!=j) {
                    p=(struct linknode*)malloc(sizeof(struct linknode));
                    p->name=k;
                    p->next=NULL;
                    q=node[j].next;
                    if (q!=NULL) {
                        while (q->next!=NULL) {
                            q=q->next;
                        }
                        q->next=p;
                    } else {
                        node[j].next=p;
                    }
                    node[j].degree++;
                }
            }
        }
    }

//evolution 





    for (j=1;j<=T;j++) {
        for (i=0;i<C;i++) {

//linking in each community(NO inter-connected)
            temp1=i*N/C+M0-1;
            kk=0;
            for (s=i*N/C;s<(temp1+j);s++) {
                ssk[s-i*N/C]=kk;
                kk+=node[s].degree;
            }
            for (s=0;s<(M0-1+j);s++) {
                ssk[s]=(double)(ssk[s]/kk);
            }
            ssk[M0+j]=1.0;
            m=0;

            intM=(int)M;
            doubleM=M-intM;
//	 sciprint("%e %d %e\n",M,intM,doubleM);
            frand=(double)rand()/RAND_MAX;
//	 sciprint("%e\n",frand);
            if (frand<doubleM)
                intM++;
            while (m<intM) {
                int temp;
                frand=(double)rand()/RAND_MAX;
                for (s=0;s<(M0-1+j);s++) {
                    if (frand>=ssk[s] && frand<ssk[s+1]) {
                        temp=s+i*N/C;
                        break;
                    } else {
                        if (frand==1.0) {
                            temp=M0+j-2+i*N/C;
                            break;
                        }
                    }
                }
                flag=1;
                p2=node[temp].next;
                while (p2!=NULL) {
                    if (p2->name==temp1+j) {
                        flag=0;
                        break;
                    }
                    p2=p2->next;
                }
                if (flag) {
                    m++;
                    r=(struct linknode *)malloc(sizeof(struct linknode));
                    r->name=temp1+j;
                    r->next=NULL;
                    node[temp].degree++;
//			 sciprint("%i\n",node[temp].degree);
                    t=node[temp].next;
                    if (t!=NULL) {
                        while (t->next!=NULL)
                            t=t->next;
                        t->next=r;
                    } else {
                        node[temp].next=r;
                    }
                    q=(struct linknode *)malloc(sizeof(struct linknode));
                    q->name=temp;
                    q->next=NULL;
                    node[temp1+j].degree++;
                    p=node[temp1+j].next;
                    if (p!=NULL) {
                        while (p->next!=NULL)
                            p=p->next;
                        p->next=q;
                    } else {
                        node[temp1+j].next=q;
                    }
                }
            }

//inter-linking with probility P

            intP=(int)P;
            doubleP=P-intP;
//	sciprint("%e %d %e\n",P,intP,doubleP);
            frand=(double)rand()/RAND_MAX;
            if (frand<=doubleP) {
                intP++;
            }
            m=0;
            while (m<intP) {
                intrand=rand()%(C-1);
                if (intrand>=i)
                    intrand++;
                temp2=intrand*N/C+M0-1;
                kk=0;
                for (s=intrand*N/C;s<(temp2+j);s++) {
                    ssk[s-intrand*N/C]=kk;
                    kk+=node[s].degree;
                }
                for (s=0;s<(M0-1+j);s++) {
                    ssk[s]=(double)(ssk[s]/kk);
                }
                ssk[M0+j]=1.0;

                frand=(double)rand()/RAND_MAX;
                for (s=0;s<(M0-1+j);s++) {
                    if (frand>=ssk[s] && frand<ssk[s+1]) {
                        temp=s+intrand*N/C;
                        break;
                    } else {
                        if (frand==1.0) {
                            temp=temp2+j-1;
                            break;
                        }
                    }
                }
                flag=1;
                p2=node[temp].next;
                while (p2!=NULL) {
                    if (p2->name==temp1+j) {
                        flag=0;
                        break;
                    }
                    p2=p2->next;
                }
                if (flag) {
                    m++;
                    r=(struct linknode *)malloc(sizeof(struct linknode));
                    r->name=temp1+j;
                    r->next=NULL;
                    node[temp].degree++;
                    t=node[temp].next;
                    if (t!=NULL) {
                        while (t->next!=NULL)
                            t=t->next;
                        t->next=r;
                    } else {
                        node[temp].next=r;
                    }
                    q=(struct linknode *)malloc(sizeof(struct linknode));
                    q->name=temp;
                    q->next=NULL;
                    node[temp1+j].degree++;
                    p=node[temp1+j].next;
                    if (p!=NULL) {
                        while (p->next!=NULL)
                            p=p->next;
                        p->next=q;
                    } else {
                        node[temp1+j].next=q;
                    }
                }
            }
        }
    }

    edgenum=0;

    for (i=0;i<N;i++) {
        edgenum+=node[i].degree;
//    sciprint("%i\n",node[i].degree);
    }

    edgenum=edgenum/2;
//sciprint("%i\n",edgenum);
}


void precom(int c,int num,int m0,double M,double P,double T)
{
    srand((unsigned)time(NULL));
//	sciprint("%i %i %i %e %e %e\n",c,num,m0,M,P,T);
    Create_Net(num,c,m0,M,P,T);
}

//void com __PARAMS((int *c,int m,int n,int *num,int *m0,int *inedge,int *outedge,double *pro,int *c,int *d));

void com(C,m,n,num,m0,inedge,outedge,pro,c,d)
int C[],num[],inedge[],outedge[],c[],d[];
double pro[];
int m,n;
int m0[];
{
    int i,index,N;
    struct linknode *p;
    N=*(num);
    index=0;
    for (i=0;i<N;i++) {
        p=node[i].next;
        while (p!=NULL) {
            if (p->name>i) {
                c[index]=i+1;
                d[index]=p->name+1;
                index++;        
            }
            p=p->next;
        }
    }


}