graph.cpp

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

  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];
  if (verbose>0) {
    printf("   Preliminary counts:\n");
    printf("   vedgecount:=%d cedgecount:=%d\n", vedgecount, cedgecount);
  }

  /* make sure that cedgecount >= vedgecount */
  if (cedgecount<vedgecount && verbose>0)
    printf("   Need to reduce cedgecount.\n");
  while (cedgecount<vedgecount) {
    /* remove one cnode of smallest degree */
    degree=0;
    while ((*(*graph).cdegreelist).numofnodes[degree]<=0)
      degree++;

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

  /* make adjustments if necessary         */
  if (vedgecount!=cedgecount) {
    if (verbose>0)
      printf("   Adjustments of edgecounts.\n");

    if ((vedgecount-cedgecount)%2!=0) {
      /* we need degree 3 nodes for the adjustment */
      assert((*(*graph).vdegreelist).degree[1]==3);

      if (cedgecount-vedgecount==1) {
        (*(*graph).vdegreelist).numofnodes[1]--;
        assert( (*(*graph).vdegreelist).numofnodes[1]>=0);

        vedgecount-=3;
      } else {
        (*(*graph).vdegreelist).numofnodes[1]++;
        vedgecount+=3;
      }
    }

    /* make up the rest with degree 2 nodes */
    assert((*(*graph).vdegreelist).degree[0]==2);
    (*(*graph).vdegreelist).numofnodes[0]+=(cedgecount-vedgecount)/2;
    vedgecount=cedgecount;
  }

  /* count them again to be sure */
  if (verbose>0)
    printf("   Check if edgecounts match after correction.\n");
  vedgecountnew=0;
  for (degreesnum=0; degreesnum<vdegreesnum; degreesnum++)
    vedgecountnew+=(*(*graph).vdegreelist).numofnodes[degreesnum]*(*(*graph).vdegreelist).degree[degreesnum];
  assert(vedgecountnew==vedgecount);

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

  /* determine the true vnodenum and cnodenum */
  vnodenum=0;
  for (degreesnum=0; degreesnum<vdegreesnum; degreesnum++)
    vnodenum+=(*(*graph).vdegreelist).numofnodes[degreesnum];
  cnodenum=0;
  for (degreesnum=0; degreesnum<cdegreesnum; degreesnum++)
    cnodenum+=(*(*graph).cdegreelist).numofnodes[degreesnum];

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

  if (verbose>0) {
    printf("6. True node numbers:\n");
    printf("   vnodenum:=%d cnodenum:=%d\n", vnodenum, cnodenum);
  }
  /* now the true rate is determined */
  (*graph).rate=1.0-((double)(*graph).cnodenum)/((double)(*graph).vnodenum);

  /* allocate memory for nodes */
  (*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);
}


/***************************************/
/* Constructs two irregular graphs for */
/* multi-access channels (same length) */
/***************************************/
void constructtwoirregulargraph(graphs *graph, graphs *graph1, int vnodenum, int vnodenum1, int *vdegreelist, int *vdegreelist1, double *vpercentagelist, double *vpercentagelist1, int vdegreesnum, int vdegreesnum1, int *cdegreelist, int *cdegreelist1, double *cpercentagelist, double *cpercentagelist1, int cdegreesnum, int cdegreesnum1, int verbose) {
  int node, socket, tosocket, tonode;
  int *perm, *iperm, *temp;
  int cnodenum, cnodenum1, degreesnum, conodenum, degree, degreecounter;
  int vedgecount, vedgecount1, cedgecount, cedgecount1, vedgecountnew, vedgecountnew1, cedgecountnew, cedgecountnew1, edgecounter;
  int *whichnode, *whichsocket;
  double sumv, sumv1, sumc, sumc1, target;

  /* set number of degrees and max degrees */
  if (verbose>0) {
    printf("\n");
    printf("Construction of (irregular) graph:\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);

  assert(vdegreesnum1>0 && cdegreesnum1>0);									/* for second graph */
  (*graph1).vdegreesnum=vdegreesnum1;
  (*graph1).cdegreesnum=cdegreesnum1;
  (*graph1).vmaxdegree=*(vdegreelist1+vdegreesnum1-1);
  (*graph1).cmaxdegree=*(cdegreelist1+cdegreesnum1-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));

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

  /**********************************************************************************/

  sumv1=0;																		/* for second graph */
  for (degreesnum=0; degreesnum<vdegreesnum1; degreesnum++)
    sumv1+=*(vpercentagelist1+degreesnum)/((double)*(vdegreelist1+degreesnum));

  sumc1=0;
  for (degreesnum=0; degreesnum<cdegreesnum1; degreesnum++)
    sumc1+=*(cpercentagelist1+degreesnum)/((double)*(cdegreelist1+degreesnum));


  /********************************************************************************************************/


  /* enter the degreelist */														/* for first graph */
  (*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");

  /* enter the degreelist */														/* for second graph */
  (*graph1).vdegreelist=(degreelist *)allocate(sizeof(degreelist));
  (*graph1).cdegreelist=(degreelist *)allocate(sizeof(degreelist));

  for (degreesnum=vdegreesnum1-1; degreesnum>=0; degreesnum--) {
    (*(*graph1).vdegreelist).degree[degreesnum]=*(vdegreelist1+degreesnum);
    (*(*graph1).vdegreelist).numofnodes[degreesnum]=(int)round(vnodenum1**(vpercentagelist1+degreesnum)/(sumv1**(vdegreelist1+degreesnum)));
    if (verbose>0) {
      printf("degreesnum1:=%d\n", degreesnum);
      printf("   vdegree:=%d vdegreenum:=%d\n\n", (*(*graph1).vdegreelist).degree[degreesnum],
             (*(*graph1).vdegreelist).numofnodes[degreesnum]);
    }
  }


  /* first calculation of vnodenum and vnodenum1 */

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

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

  /* make sure that vnodenum==vnodenum1 */
  if(verbose>0)
    printf("\nFirst vnodenum=%d and vnodenum1=%d\n\n", vnodenum, vnodenum1);

  if (vnodenum!=vnodenum1 && verbose>0)
    printf("   Need to match codeword lengths\n");


  degreesnum=0;
  while(vnodenum>vnodenum1) {
    if((*(*graph).vdegreelist).numofnodes[degreesnum]!=0) {
      (*(*graph).vdegreelist).numofnodes[degreesnum]--;
      vnodenum --;
    }
    printf("\n vnodenum=%d vnodenum1=%d degreesnum=%d \n", vnodenum, vnodenum1, degreesnum);
    if(degreesnum<vdegreesnum-1)
      degreesnum++;
    else
      degreesnum=0;
  }


  degreesnum=0;
  while(vnodenum1>vnodenum) {
    if((*(*graph1).vdegreelist).numofnodes[degreesnum]!=0) {
      (*(*graph1).vdegreelist).numofnodes[degreesnum]--;
      vnodenum1 --;
    }
    if(degreesnum<vdegreesnum1-1)
      degreesnum++;
    else
      degreesnum=0;
  }


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

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


  printf("\nFinal vnodenum=%d and vnodenum1=%d\n\n", vnodenum, vnodenum1);




  /* approximate number of cnodes */
  cnodenum=(int)round(vnodenum*sumc/sumv);
  if (verbose)
    printf("approx cnodenum:=%d\n", cnodenum);


  /* approximate number of cnodes */
  cnodenum1=(int)round(vnodenum1*sumc1/sumv1);
  if (verbose)
    printf("approx cnodenum1:=%d\n", cnodenum1);


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

  for (degreesnum=cdegreesnum-1; degreesnum>=0; degreesnum--)										/*  for first graph  */
  {
    (*(*graph).cdegreelist).degree[degreesnum]=*(cdegreelist+degreesnum);
    (*(*graph).cdegreelist).numofnodes[degreesnum]=(int)round(cnodenum**(cpercentagelist+degreesnum)/(sumc**(cdegreelist+degreesnum)));
    if (verbose>0)
      printf("   cdegree:=%d cdegreenum:=%d\n\n", (*(*graph).cdegreelist).degree[degreesnum],
             (*(*graph).cdegreelist).numofnodes[degreesnum]);
  }

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

  for (degreesnum=cdegreesnum1-1; degreesnum>=0; degreesnum--)										/*  for second graph  */
  {
    (*(*graph1).cdegreelist).degree[degreesnum]=*(cdegreelist1+degreesnum);
    (*(*graph1).cdegreelist).numofnodes[degreesnum]=(int)round(cnodenum1**(cpercentagelist1+degreesnum)/(sumc1**(cdegreelist1+degreesnum)));
    if (verbose>0)
      printf("   cdegree1:=%d cdegreenum1:=%d\n\n", (*(*graph1).cdegreelist).degree[degreesnum],
             (*(*graph1).cdegreelist).numofnodes[degreesnum]);
  }


  /* calculate cnodenum and cnodenum1 */

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

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

  if(verbose>0)
    printf("\nFirst cnodenum=%d and cnodenum1=%d\n", cnodenum, cnodenum1);


  /* make sure that the edgecounts match up */
  if (verbose>0)
    printf("5. See if edgecounts match up.\n");

  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("   Preliminary counts:\n");
    printf("  vnodenum=%d vedgecount:=%d cedgecount:=%d\n", vnodenum, vedgecount, cedgecount);
    printf("  vnodenum1=%d vedgecount1:=%d cedgecount1:=%d\n", vnodenum, vedgecount1, cedgecount1);
  }



  /***********************************************************/
  /***********   Check the below later      ******************/
  /***********************************************************/

  if(  (((vedgecount-cedgecount)!=0) || ((vedgecount1-cedgecount1)!=0)) && verbose>0  )
    printf("  Edges numbers didn't match\n");