graph.cpp

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

    if(degreesnum<vdegreesnum-1)
      degreesnum++;
    else
      degreesnum=0;
  }
}

/**************************/
/*  Second part of graph  */
/**************************/
void secondpartgraph(graphs *graph, int user,int *vnodenum, int vdegreesnum, int *cdegreesnum, int *cdegreelist, double* cpercentagelist, int verbose) {
  int i, degreesnum;
  int vedgecount, cedgecount, cnodenum;

  printf("\nFinal variable node numbers:\n");

  (*vnodenum)=0;
  for(degreesnum=0; degreesnum<vdegreesnum; degreesnum++)
    (*vnodenum) +=(*(*graph).vdegreelist).numofnodes[degreesnum];
  printf("vnodenum[%d]=%d\n", user, (*vnodenum));


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


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

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

  /* calculate cnodenum */

  if(verbose>0)
    printf("Initial number of check nodes\n");

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

  if(verbose>0)
    printf("\ncnodenum[%d]=%d\n\n", user, cnodenum);


  /* 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];

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



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

  /*   Match graph edges  */

  if(cedgecount<vedgecount) {
    if((*cdegreesnum)==1) {
      //		(*cdegreesnum)++;
      (*graph).cdegreesnum=(*cdegreesnum)+1;
      (*(*graph).cdegreelist).degree[1]=(*(cdegreelist))+1;
      (*(*graph).cdegreelist).numofnodes[1]=0;
    }
  }


  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 ++;
    }
  }

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

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


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

  cedgecount=0;
  for (degreesnum=0; degreesnum<(*graph).cdegreesnum; degreesnum++)
    cedgecount+=(*(*graph).cdegreelist).numofnodes[degreesnum]*(*(*graph).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);
  }

  /* verify that edges and variables match */
  assert(vedgecount==cedgecount);

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

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

  if(verbose)
    printf("\nuser=%d real rate of code =%g\n\n", user, (*graph).rate);

}


/*************************************/
/*  Last part of graph construction  */
/*************************************/
void lastpartgraph(graphs *graph, int user, char *graphfile, int verbose) {
  int degree, degreecounter, node, tonode;
  int vedgecountnew, cedgecountnew;

  int edgecounter, socket, tosocket;
  int *perm, *iperm;
  int *whichnode, *whichsocket;

  int *iphi;

  /* 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<(*graph).vdegreesnum-1)) {
      degree++;
      while((*(*graph).vdegreelist).numofnodes[degree]<=0)
        degree++;
      assert(degree<(*graph).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<(*graph).cdegreesnum-1)) {
      degree++;
      while((*(*graph).cdegreelist).numofnodes[degree]<=0)
        degree++;
      assert(degree<(*graph).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;
  printf("user=%d, vedgecountnew=%d\n", user, vedgecountnew);

  cedgecountnew=0;
  for (node=0; node<(*graph).cnodenum; node++)
    cedgecountnew+=cnodedegree;
  printf("user=%d, cedgecountnew=%d\n", user, cedgecountnew);


  /* 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)*vedgecountnew);
  iperm=(int *)allocate(sizeof(int)*vedgecountnew);
  randompermutation(perm, iperm, vedgecountnew);

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

  /* 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);

  savegraph(graph, -1, iphi, graphfile, verbose, 0);

  //   freegraph(graph);

}


/****************************************/
/** Free most of the memory of a graph **/
/****************************************/
void freegraph(graphs *graph) {
  int node;

  /* deallocate memory for edges */
  for (node=0; node<(*graph).vnodenum; node++) {
    //	   printf("node=%d\n", node);
    free(vnodeedgelist);
  }
  for (node=0; node<(*graph).cnodenum; node++)
    free(cnodeedgelist);

  /* deallocate memory for nodes */
  free((*graph).vnodelist);
  free((*graph).cnodelist);

  /* deallocate memory for degreelist */
  free((*graph).vdegreelist);
  free((*graph).cdegreelist);

  //   printf("Finished");

}

/*******************
* switch two edges *
*******************/
void switchedges(graphs *graph, int nodea, int socketa, int nodeb, int socketb) {
  int node, socket, tonodea, tosocketa, tonodeb, tosocketb;

  /* find right hand side of edge a */
  node=nodea;
  socket=socketa;
  tonodea=vnodeedge.dest;
  tosocketa=vnodeedge.socket;

  /* find right hand side of edge b */
  node=nodeb;
  socket=socketb;
  tonodeb=vnodeedge.dest;
  tosocketb=vnodeedge.socket;

  /* now switch */
  /* left hand side of edge a */
  node=nodea;
  socket=socketa;
  vnodeedge.dest=tonodeb;
  vnodeedge.socket=tosocketb;

  /* right hand side of edge a */
  node=tonodeb;
  socket=tosocketb;
  cnodeedge.dest=nodea;
  cnodeedge.socket=socketa;

  /* left hand side of edge b */
  node=nodeb;
  socket=socketb;
  vnodeedge.dest=tonodea;
  vnodeedge.socket=tosocketa;

  /* right hand side of edge b */
  node=tonodea;
  socket=tosocketa;
  cnodeedge.dest=nodeb;
  cnodeedge.socket=socketb;
}

/********************
* switch two vnodes *
********************/
void switchvnodes(graphs *graph, int nodea, int nodeb) {}


/************************************/
/* Skip all data of a file until    */
/* next C "end of comment" symbol   */
/* appears. verbose=1 will result   */
/* in all skipped data being        */
/* printed.                         */
/************************************/
void skip(FILE *fp, int verbose) {
  int cold, cnew;
  cold=' ';

  while((cnew = getc(fp)) != EOF) {
    if (verbose)
      printf("%c", cnew);
    if (cnew == '/' && cold == '*')
      break;
    cold = cnew;
  }
  if (cnew == EOF)
    return;
  if ((cnew = getc(fp)) != '\n')
    ungetc(cnew, fp);
}


/********************************
* Allocate a pointer to void of *
* size n bytes.                 *
********************************/
void *allocate(int n) {
  void *p;

  if ((p = malloc(n)) == NULL) {
    printf("/***********************************/");
    printf("/*    W   A   R   N   I   N   G    */");
    printf("/***********************************/");
    printf("/*      Not sufficient memory!     */");
    printf("/***********************************/");
    exit(1);
  }

  return p;
}

/**********************************
* generate random permutation of  *
* n elements and inverse function *
**********************************/
void randompermutation(int *perm, int *iperm, int n) {
  int i, j;

  for (i=0; i<n; i++)
    *(iperm+i)=i;

  for (i=n-1; i>=0; i--) {
    //      j=(int)floor((i+1)*erand48(simrand));

    /* compatible with fast program */
    *(perm+n-1-i)=*(iperm+j);

    /* original version */
    /* *(perm+i)=*(iperm+j); */

    *(iperm+j)=*(iperm+i);
  }

  for (i=0; i<n; i++)
    *(iperm+*(perm+i))=i;
}