graph.cpp

This a framework to test new ideas in transmission technology. Actual development is a LDPC-coder in

  /*   Match graph edges  */
  while(cedgecount<vedgecount) {
    if((*(*graph).cdegreelist).numofnodes[0]!=0) {
      (*(*graph).cdegreelist).numofnodes[0]--;
      (*(*graph).cdegreelist).numofnodes[1]++;
      cedgecount ++;
    } else {
      (*(*graph).cdegreelist).numofnodes[1]--;
      (*(*graph).cdegreelist).numofnodes[2]++;
      cedgecount ++;
    }
  }

  while(cedgecount>vedgecount) {
    if((*(*graph).cdegreelist).numofnodes[1]!=0) {
      (*(*graph).cdegreelist).numofnodes[1]--;
      (*(*graph).cdegreelist).numofnodes[0]++;
      cedgecount --;
    }
  }

  /*  Match graph1 edges */

  while(cedgecount1<vedgecount1) {
    if((*(*graph1).cdegreelist).numofnodes[0]!=0) {
      (*(*graph1).cdegreelist).numofnodes[0]--;
      (*(*graph1).cdegreelist).numofnodes[1]++;
      cedgecount1 ++;
    } else {
      (*(*graph1).cdegreelist).numofnodes[1]--;
      (*(*graph1).cdegreelist).numofnodes[2]++;
      cedgecount1 ++;
    }
  }

  while(cedgecount1>vedgecount1) {
    if((*(*graph1).cdegreelist).numofnodes[1]!=0) {
      (*(*graph1).cdegreelist).numofnodes[1]--;
      (*(*graph1).cdegreelist).numofnodes[0]++;
      cedgecount1 --;
    }
  }



  vedgecount=0;
  for (degreesnum=0; degreesnum<vdegreesnum; degreesnum++)
    vedgecount+=(*(*graph).vdegreelist).numofnodes[degreesnum]*(*(*graph).vdegreelist).degree[degreesnum];

  cedgecount=0;
  for (degreesnum=0; degreesnum<cdegreesnum; degreesnum++)
    cedgecount+=(*(*graph).cdegreelist).numofnodes[degreesnum]*(*(*graph).cdegreelist).degree[degreesnum];


  vedgecount1=0;
  for (degreesnum=0; degreesnum<vdegreesnum1; degreesnum++)
    vedgecount1+=(*(*graph1).vdegreelist).numofnodes[degreesnum]*(*(*graph1).vdegreelist).degree[degreesnum];

  cedgecount1=0;
  for (degreesnum=0; degreesnum<cdegreesnum1; degreesnum++)
    cedgecount1+=(*(*graph1).cdegreelist).numofnodes[degreesnum]*(*(*graph1).cdegreelist).degree[degreesnum];


  if (verbose>0) {
    printf("\n\n   Final counts:\n");
    printf("  vnodenum=%d cnodenum=%d vedgecount:=%d cedgecount:=%d\n", vnodenum, cnodenum, vedgecount, cedgecount);
    printf("  vnodenum1=%d cnodenum1=%d vedgecount1:=%d cedgecount1:=%d\n", vnodenum1, cnodenum1, vedgecount1, cedgecount1);
  }



  /* verify that edges and variables match */
  assert(vnodenum==vnodenum1);
  assert(vedgecount==cedgecount);
  assert(vedgecount1==cedgecount1);


  /* enter them into graph structure */
  (*graph).vnodenum=vnodenum;
  (*graph).cnodenum=cnodenum;

  (*graph1).vnodenum=vnodenum1;
  (*graph1).cnodenum=cnodenum1;


  /******************************************************/
  /***********  Operations for first graph   ************/
  /******************************************************/

  /* now the true rate is determined for graph*/
  (*graph).rate=1.0-((double)(*graph).cnodenum)/((double)(*graph).vnodenum);

  /* allocate memory for nodes of graph */
  (*graph).vnodelist=(vnode *)allocate(sizeof(vnode)*(*graph).vnodenum);
  (*graph).cnodelist=(cnode *)allocate(sizeof(cnode)*(*graph).cnodenum);

  /* set the degree of each node */
  degree=0;
  while ((*(*graph).vdegreelist).numofnodes[degree]<=0)
    degree++;
  degreecounter=(*(*graph).vdegreelist).numofnodes[degree];
  assert(degreecounter>0);

  for (node=0; node<(*graph).vnodenum; node++) {
    vnodedegree=(*(*graph).vdegreelist).degree[degree];
    degreecounter--;
    assert(degreecounter>=0);

    if ((degreecounter==0) && (degree<vdegreesnum-1)) {
      degree++;
      while((*(*graph).vdegreelist).numofnodes[degree]<=0)
        degree++;
      /* assert(degree<vdegreesnum); */

      degreecounter=(*(*graph).vdegreelist).numofnodes[degree];
      assert(degreecounter>0);
    }
  }
  degree=0;
  while ((*(*graph).cdegreelist).numofnodes[degree]<=0)
    degree++;
  degreecounter=(*(*graph).cdegreelist).numofnodes[degree];
  assert(degreecounter>0);

  for (node=0; node<(*graph).cnodenum; node++) {
    cnodedegree=(*(*graph).cdegreelist).degree[degree];
    degreecounter--;
    assert(degreecounter>=0);

    if ((degreecounter==0) && (degree<cdegreesnum-1)) {
      degree++;
      while((*(*graph).cdegreelist).numofnodes[degree]<=0)
        degree++;
      assert(degree<cdegreesnum);

      degreecounter=(*(*graph).cdegreelist).numofnodes[degree];
      assert(degreecounter>0);
    }
  }

  /* count the edges again to make sure no mistakes were made */
  vedgecountnew=0;
  for (node=0; node<(*graph).vnodenum; node++)
    vedgecountnew+=vnodedegree;
  assert(vedgecountnew==vedgecount);

  cedgecountnew=0;
  for (node=0; node<(*graph).cnodenum; node++)
    cedgecountnew+=cnodedegree;
  assert(cedgecountnew==cedgecount);

  /* now allocate memory for edges */
  for (node=0; node<(*graph).vnodenum; node++)
    vnodeedgelist=(edge *)allocate(sizeof(edge)*vnodedegree);
  for (node=0; node<(*graph).cnodenum; node++)
    cnodeedgelist=(edge *)allocate(sizeof(edge)*cnodedegree);

  /* generate random permutation which determines graph */
  perm=(int *)allocate(sizeof(int)*vedgecount);
  iperm=(int *)allocate(sizeof(int)*vedgecount);
  randompermutation(perm, iperm, vedgecount);

  /* allocate temporary memory */
  whichnode=(int *)allocate(sizeof(int)*vedgecount);
  whichsocket=(int *)allocate(sizeof(int)*vedgecount);

  /* fill in whichnode and whichsocket */
  edgecounter=0;
  for (node=0; node<(*graph).cnodenum; node++) {
    for (socket=0; socket<cnodedegree; socket++) {
      *(whichnode+edgecounter)=node;
      *(whichsocket+edgecounter)=socket;
      edgecounter++;
    }
  }
  edgecounter=0;
  for (node=0; node<(*graph).vnodenum; node++) {
    for (socket=0; socket<vnodedegree; socket++) {
      tonode=*(whichnode+*(perm+edgecounter));
      tosocket=*(whichsocket+*(perm+edgecounter));

      vnodeedge.dest=tonode;
      vnodeedge.socket=tosocket;
      cnodetoedge.dest=node;
      cnodetoedge.socket=socket;

      edgecounter++;
    }
  }

  /* free temporary memory */
  free(perm);
  free(iperm);
  free(whichnode);
  free(whichsocket);

  /******************************************************/
  /***********  Operations for second graph   ***********/
  /******************************************************/

  /* now the true rate is determined */
  (*graph1).rate=1.0-((double)(*graph1).cnodenum)/((double)(*graph1).vnodenum);

  /* allocate memory for nodes */
  (*graph1).vnodelist=(vnode *)allocate(sizeof(vnode)*(*graph1).vnodenum);
  (*graph1).cnodelist=(cnode *)allocate(sizeof(cnode)*(*graph1).cnodenum);

  /* set the degree of each node */
  degree=0;
  while ((*(*graph1).vdegreelist).numofnodes[degree]<=0)
    degree++;
  degreecounter=(*(*graph1).vdegreelist).numofnodes[degree];
  assert(degreecounter>0);

  for (node=0; node<(*graph1).vnodenum; node++) {
    vnodedegree1=(*(*graph1).vdegreelist).degree[degree];


    degreecounter--;
    assert(degreecounter>=0);

    if ((degreecounter==0) && (degree<vdegreesnum1-1)) {
      degree++;
      while((*(*graph1).vdegreelist).numofnodes[degree]<=0)
        degree++;
      /* assert(degree<vdegreesnum1); */

      degreecounter=(*(*graph1).vdegreelist).numofnodes[degree];
      assert(degreecounter>0);
    }
  }

  degree=0;
  while ((*(*graph1).cdegreelist).numofnodes[degree]<=0)
    degree++;
  degreecounter=(*(*graph1).cdegreelist).numofnodes[degree];
  assert(degreecounter>0);

  for (node=0; node<(*graph1).cnodenum; node++) {
    cnodedegree1=(*(*graph1).cdegreelist).degree[degree];
    degreecounter--;
    assert(degreecounter>=0);

    if ((degreecounter==0) && (degree<cdegreesnum1-1)) {
      degree++;
      while((*(*graph1).cdegreelist).numofnodes[degree]<=0)
        degree++;
      assert(degree<cdegreesnum1);

      degreecounter=(*(*graph1).cdegreelist).numofnodes[degree];
      assert(degreecounter>0);
    }
  }

  /* count the edges again to make sure no mistakes were made */
  vedgecountnew1=0;
  for (node=0; node<(*graph1).vnodenum; node++)
    vedgecountnew1+=vnodedegree1;
  assert(vedgecountnew1==vedgecount1);

  cedgecountnew1=0;
  for (node=0; node<(*graph1).cnodenum; node++)
    cedgecountnew1+=cnodedegree1;
  assert(cedgecountnew1==cedgecount1);

  /* now allocate memory for edges */
  for (node=0; node<(*graph1).vnodenum; node++)
    vnodeedgelist1=(edge *)allocate(sizeof(edge)*vnodedegree1);
  for (node=0; node<(*graph1).cnodenum; node++)
    cnodeedgelist1=(edge *)allocate(sizeof(edge)*cnodedegree1);

  /* generate random permutation which determines graph */
  perm=(int *)allocate(sizeof(int)*vedgecount1);
  iperm=(int *)allocate(sizeof(int)*vedgecount1);
  randompermutation(perm, iperm, vedgecount1);

  /* allocate temporary memory */
  whichnode=(int *)allocate(sizeof(int)*vedgecount1);
  whichsocket=(int *)allocate(sizeof(int)*vedgecount1);

  /* fill in whichnode and whichsocket */
  edgecounter=0;
  for (node=0; node<(*graph1).cnodenum; node++) {
    for (socket=0; socket<cnodedegree1; socket++) {
      *(whichnode+edgecounter)=node;
      *(whichsocket+edgecounter)=socket;
      edgecounter++;
    }
  }
  edgecounter=0;
  for (node=0; node<(*graph1).vnodenum; node++) {
    for (socket=0; socket<vnodedegree1; socket++) {
      tonode=*(whichnode+*(perm+edgecounter));
      tosocket=*(whichsocket+*(perm+edgecounter));

      vnodeedge1.dest=tonode;
      vnodeedge1.socket=tosocket;
      cnodetoedge1.dest=node;
      cnodetoedge1.socket=socket;

      edgecounter++;
    }
  }

  /* free temporary memory */
  free(perm);
  free(iperm);
  free(whichnode);
  free(whichsocket);

}


/*********************************/
/* Begin construction of graphs  */
/*********************************/
void beginconstructgraph(int user, graphs *graph, int *vnodenum, int *vdegreelist, double *vpercentagelist, int vdegreesnum, int *cdegreelist, double *cpercentagelist, int cdegreesnum, int verbose) {
  int node, socket, tosocket, tonode, i, j, flag;
  int *perm, *iperm, *temp;

  int cnodenum, degreesnum, conodenum, degree, degreecounter;
  int vedgecount, cedgecount, vedgecountnew, cedgecountnew, edgecounter;
  int *whichnode, *whichsocket;
  double sumv, sumc, target;



  /* set number of degrees and max degrees */
  if (verbose>0) {
    printf("\nuser %d\n", user);
    printf("Construction of (irregular) graphs:\n");
    printf("1. Set number of degrees and max degrees.\n");
  }


  assert(vdegreesnum>0 && cdegreesnum>0);				       /* for first graph  */
  (*graph).vdegreesnum=vdegreesnum;

  (*graph).cdegreesnum=cdegreesnum;
  (*graph).vmaxdegree=*(vdegreelist+vdegreesnum-1);
  (*graph).cmaxdegree=*(cdegreelist+cdegreesnum-1);


  /* take the percentage lists and convert them */
  /* into node perspective                      */
  if (verbose>0)
    printf("2. Convert node percentages into node perspective.\n");

  sumv=0;
  /* for first graph */
  for (degreesnum=0; degreesnum<vdegreesnum; degreesnum++)
    sumv+=*(vpercentagelist+degreesnum)/((double)*(vdegreelist+degreesnum));
  (*graph).sumv=sumv;

  sumc=0;
  for (degreesnum=0; degreesnum<cdegreesnum; degreesnum++)
    sumc+=*(cpercentagelist+degreesnum)/((double)*(cdegreelist+degreesnum));
  (*graph).sumc=sumc;

  /* allocate memory */
  (*graph).vdegreelist=(degreelist *)allocate(sizeof(degreelist));
  (*graph).cdegreelist=(degreelist *)allocate(sizeof(degreelist));

  if (verbose>0)
    printf("3. Number of vnodes: [before adjustments]\n");

  for (degreesnum=vdegreesnum-1; degreesnum>=0; degreesnum--) {
    (*(*graph).vdegreelist).degree[degreesnum]=*(vdegreelist+degreesnum);
    (*(*graph).vdegreelist).numofnodes[degreesnum]=(int)round((*vnodenum)**(vpercentagelist+degreesnum)/(sumv**(vdegreelist+degreesnum)));
    if (verbose>0) {
      printf("degreesnum:=%d\n", degreesnum);
      printf("   vdegree:=%d vdegreenum:=%d\n\n", (*(*graph).vdegreelist).degree[degreesnum], (*(*graph).vdegreelist).numofnodes[degreesnum]);
    }
  }

  if(verbose>0)
    printf("\n\n");




  /* first calculation of vnodenum */
  (*vnodenum)=0;
  for(degreesnum=0; degreesnum<vdegreesnum; degreesnum++)
    (*vnodenum) +=(*(*graph).vdegreelist).numofnodes[degreesnum];

  if(verbose>0) {
    printf("vnodenum[%d]=%d\n", user, (*vnodenum));
  }
}

/*****************************************************/
/*  Verify if all graphs have same number of vnodes  */
/*****************************************************/
int verifyvnodenum(int *vnodenum, int numus) {
  int i, flag, flag1=-1;

  flag=vnodenum[0];

  for(i=1; i<numus; i++) {
    if(vnodenum[i]<flag)
      flag1=1;

    if(vnodenum[i]>flag) {
      flag=vnodenum[i];
      flag1=1;
    }
  }


  if(flag1==1)
    return(flag);
  else
    return(-1);
}

/*****************************/
/*  Arrange number of vnode  */
/*****************************/
void arrangevnode(graphs *graph, int vdegreesnum, int vnodenum, int vnodemax) {

  int degreesnum=0;

  while(vnodenum<vnodemax) {
    (*(*graph).vdegreelist).numofnodes[degreesnum]++;
    vnodenum++;