graph.cpp

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include "graph.h"


/********************
* rounding function *
* of a given graph  *
********************/
double round(double x) {
  if(x==0)
    return(0);
  if(x>0)
    return floor(x+0.5);
  if(x<0)
    return ceil(x-0.5);
}

/************************************
* print out the relevant quantities *
* of a given graph                  *
************************************/
void printgraph(graphs *graph, int what) {
  int i, node, socket, tonode, tosocket;
  FILE *fp;

  /* print general parameters */
  if ((what&1)!=0) {
    printf("\n");
    printf("Graph: rate:=%g\n", (*graph).rate);
    printf("vnodenum:=%6d  cnodenum:=%6d\n", (*graph).vnodenum, (*graph).cnodenum);
    printf("vdegreesnum:=%3d  cdegreesnum:=%3d\n", (*graph).vdegreesnum, (*graph).cdegreesnum);
    printf("vmaxdegree:= %3d  cmaxdegree:= %3d\n", (*graph).vmaxdegree, (*graph).cmaxdegree);
    printf("\n");
    printf("vdegreelist:\n");
    for (i=0; i<(*graph).vdegreesnum; i++)
      printf("degree:=%3d number of nodes:=%3d\n", (*(*graph).vdegreelist).degree[i], (*(*graph).vdegreelist).numofnodes[i]);
    printf("\n");
    printf("cdegreelist:\n");
    for (i=0; i<(*graph).cdegreesnum; i++)
      printf("degree:=%3d number of nodes:=%3d\n", (*(*graph).cdegreelist).degree[i], (*(*graph).cdegreelist).numofnodes[i]);
  }

  /* print connection list */
  if ((what&2)!=0) {
    /* connection list */
    printf("list of neighbors from vnode perspective:\n");
    for (node=0; node<(*graph).vnodenum; node++) {
      printf("%6d: ", node);
      for (socket=0; socket<vnodedegree; socket++)
        printf("%6d[%2d] ", vnodeedge.dest, vnodeedge.socket);
      printf("\n");
    }

    printf("list of neighbors from the cnode perspective:\n");
    for (node=0; node<(*graph).cnodenum; node++) {
      printf("%6d:", node);
      for (socket=0; socket<cnodedegree; socket++)
        printf("%6d[%2d] ", cnodeedge.dest, cnodeedge.socket);
      printf("\n");
    }
  }

  /* print messages */
  if ((what&4)!=0) {
    /* print variable messages */
    printf("variable messages:\n");
    for (node=0; node<(*graph).vnodenum; node++) {
      printf("%6d: [%6g] ", node, vnodevalue);
      for (socket=0; socket<vnodedegree; socket++) {
        tonode=vnodeedge.dest;
        tosocket=vnodeedge.socket;
        printf("%6g ", cnodetoedge.message);
      }
      printf("\n");
    }

    /* print check messages */
    printf("check messages:\n");
    for (node=0; node<(*graph).cnodenum; node++) {
      printf("%6d: ", node);
      for (socket=0; socket<cnodedegree; socket++) {
        tonode=cnodeedge.dest;
        tosocket=cnodeedge.socket;
        printf("%6g ", vnodetoedge.message);
      }
      printf("\n");
    }
  }
}

/******************************************
* save a graph in a file                  *
******************************************/
void savegraph(graphs *graph, int gap, int *iphi, char *graphfile, int verbose, int val) {
  int i, node, vnodenum, cnodenum, vdegreesnum, cdegreesnum;
  int row, col;
  int vmaxdegree, cmaxdegree, degree, socket, tonode, tosocket;
  double rate;

  FILE *fp;

  /* open the file */
  if ((fp=fopen(graphfile, "w"))==NULL) {
    fprintf(stderr, "I can't open the indicated graph file.\n");
    return exit(1);
  }

  /* read in main parameters */
  fprintf(fp, "/*****************************\n");
  fprintf(fp, "* Description File of a Code *\n");
  fprintf(fp, "*****************************/\n");

  fprintf(fp, "\n");
  fprintf(fp, "/* vnodenum and cnodenum */\n");
  fprintf(fp, "%7d %7d\n", (*graph).vnodenum, (*graph).cnodenum);

  fprintf(fp, "\n");
  fprintf(fp, "/* vdegreesnum and cdegreesnum */\n");
  fprintf(fp, "%7d %7d\n", (*graph).vdegreesnum, (*graph).cdegreesnum);

  fprintf(fp, "\n");
  fprintf(fp, "/* vmaxdegree and cmaxdegree */\n");
  fprintf(fp, "%7d %7d\n", (*graph).vmaxdegree, (*graph).cmaxdegree);

  fprintf(fp, "\n");
  fprintf(fp, "/* list of vnode degrees     */\n");
  for (i=0; i<(*graph).vdegreesnum; i++)
    fprintf(fp, "%3d %3d\n", (*(*graph).vdegreelist).degree[i],
            (*(*graph).vdegreelist).numofnodes[i]);

  fprintf(fp, "\n");
  fprintf(fp, "/* list of cnode degrees     */\n");
  for (i=0; i<(*graph).cdegreesnum; i++)
    fprintf(fp, "%3d %3d\n", (*(*graph).cdegreelist).degree[i],
            (*(*graph).cdegreelist).numofnodes[i]);

  fprintf(fp, "\n");
  fprintf(fp, "/* description of vnodes    *\n");
  fprintf(fp, "*  in the following format  *\n");
  fprintf(fp, "*  vnodedegree              *\n");
  fprintf(fp, "*  tonode tosocket ....    */\n");
  for (node=0; node<(*graph).vnodenum; node++) {
    fprintf(fp, "%3d  ", vnodedegree);
    for (socket=0; socket<vnodedegree; socket++) {
      if (socket%3==0 && socket>0)
        fprintf(fp, "\n     ");

      fprintf(fp, "%7d ", vnodeedge.dest);
      fprintf(fp, "%7d   ", vnodeedge.socket);
    }

    fprintf(fp, "\n");
  }

  fprintf(fp, "\n");
  fprintf(fp, "/* description of cnodes    *\n");
  fprintf(fp, "*  in the following format  *\n");
  fprintf(fp, "*  cnodedegree              *\n");
  fprintf(fp, "*  tonode tosocket ....    */\n");
  for (node=0; node<(*graph).cnodenum; node++) {
    fprintf(fp, "%3d  ", cnodedegree);

    for (socket=0; socket<cnodedegree; socket++) {
      if (socket%3==0 && socket>0)
        fprintf(fp, "\n     ");

      fprintf(fp, "%7d ", cnodeedge.dest);
      fprintf(fp, "%7d   ", cnodeedge.socket);
    }

    fprintf(fp, "\n");
  }

  fprintf(fp, "\n\n -1\n\n");

  /* if decoder is known write   */
  /* gap and inverse of phi onto */
  /* file as well                */
  fprintf(fp, "/* information for encoder    *\n");
  fprintf(fp, "*  gap [-1 indicates no info] *\n");
  fprintf(fp, "*  inverse of phi row by row */\n");
  if (gap>=0) {
    fprintf(fp, "%d\n", gap);

    for (row=0; row<gap; row++) {
      for (col=0; col<gap; col++)
        fprintf(fp, "%1d ", *(iphi+row*gap+col));
      fprintf(fp, "\n");
    }
    fprintf(fp, "\n");
  }
  fprintf(fp, "-1\n\n");

  /* if val==1 write values of messages */
  /* from check nodes to variable       */
  fprintf(fp, "/* values of messages to variable nodes     *\n");
  fprintf(fp, "*  val==1 indicate messages to be written   *\n");
  fprintf(fp, "*  messages are written one after the other */\n");
  if (val==1) {
    fprintf(fp, "%d\n", val);
    for (node=0; node<(*graph).vnodenum; node++) {
      for (socket=0; socket<vnodedegree; socket++) {
        if (socket%10==0 && socket>0)
          fprintf(fp, "\n     ");
        fprintf(fp, "%lf ", vnodeedge.message);
      }
    }
    fprintf(fp, "\n");
  }
  fprintf(fp, "-1\n");

  /* close file */
  fclose(fp);
}

/******************************************
* read in a graph from a file             *
******************************************/
void readgraph(graphs *graph, int *gap, int **iphi, char *graphfile, int verbose) {
  int i, num, node, vnodenum, cnodenum, vdegreesnum, cdegreesnum, val=0;
  int vmaxdegree, cmaxdegree, degree, socket, tonode, tosocket;
  int row, col, temp;
  double rate, tempdouble;

  FILE *fp;

  /* open the file containing the graph */
  if ((fp=fopen(graphfile, "r"))==NULL) {
    fprintf(stderr, "I can't open the indicated graph file.\n");
    return exit(1);
  }

  /* read in main parameters */
  skip(fp, 0);
  skip(fp, 0);
  fscanf(fp, "%d", &vnodenum);
  (*graph).vnodenum=vnodenum;
  fscanf(fp, "%d", &cnodenum);
  (*graph).cnodenum=cnodenum;
  (*graph).rate=1.0-((double)(*graph).cnodenum)/((double)(*graph).vnodenum);
  skip(fp, 0);
  fscanf(fp, "%d", &vdegreesnum);
  (*graph).vdegreesnum=vdegreesnum;
  fscanf(fp, "%d", &cdegreesnum);
  (*graph).cdegreesnum=cdegreesnum;
  skip(fp, 0);
  fscanf(fp, "%d", &vmaxdegree);
  (*graph).vmaxdegree=vmaxdegree;
  fscanf(fp, "%d", &cmaxdegree);
  (*graph).cmaxdegree=cmaxdegree;

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

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

  /* read in vnodelist */
  skip(fp, 0);
  for (i=0; i<(*graph).vdegreesnum; i++) {
    fscanf(fp, "%d", &degree);
    fscanf(fp, "%d", &num);
    (*(*graph).vdegreelist).degree[i]=degree;
    (*(*graph).vdegreelist).numofnodes[i]=num;
  }

  /* read in cnodelist */
  skip(fp, 0);
  for (i=0; i<(*graph).cdegreesnum; i++) {
    fscanf(fp, "%d", &degree);
    fscanf(fp, "%d", &num);
    (*(*graph).cdegreelist).degree[i]=degree;
    (*(*graph).cdegreelist).numofnodes[i]=num;
  }

  /* start by reading in vnodes */
  skip(fp, 0);
  for (node=0; node<(*graph).vnodenum; node++) {
    /* degree of the node */
    fscanf(fp, "%d", &degree);
    vnodedegree=degree;

    /* printf("node:=%d vnodedegree:=%d\n", node, vnodedegree); */

    /* allocate memory for edges */
    vnodeedgelist=(edge *)allocate(sizeof(edge)*degree);

    for (socket=0; socket<vnodedegree; socket++) {
      fscanf(fp, "%d", &tonode);
      fscanf(fp, "%d", &tosocket);

      vnodeedge.dest=tonode;
      vnodeedge.socket=tosocket;
    }
  }

  /* next read in cnodes */
  skip(fp, 0);
  for (node=0; node<(*graph).cnodenum; node++) {
    /* degree of the node */
    fscanf(fp, "%d", &degree);
    cnodedegree=degree;

    /* allocate memory for edges */
    cnodeedgelist=(edge *)allocate(sizeof(edge)*degree);

    for (socket=0; socket<cnodedegree; socket++) {
      fscanf(fp, "%d", &tonode);
      fscanf(fp, "%d", &tosocket);

      cnodeedge.dest=tonode;
      cnodeedge.socket=tosocket;
    }
  }

  /* now read in encoder information if available */
  skip(fp, 0);
  fscanf(fp, "%d", gap);
  if ((*gap)>=0) {
    /* allocate memory */
    *iphi=(int *)allocate((*gap)*(*gap)*sizeof(int));

    for (row=0; row<*gap; row++)
      for (col=0; col<*gap; col++) {
        fscanf(fp, "%d", &temp);
        *(*iphi+row*(*gap)+col)=temp;
      }
  }


  /* now read messages if available */
  skip(fp, 0);
  fscanf(fp, "%d", &val);
  if (val==1) {
    for (node=0; node<(*graph).vnodenum; node++) {
      for (socket=0; socket<vnodedegree; socket++) {
        fscanf(fp, "%lf", &tempdouble);

        vnodeedge.message=tempdouble;
      }
    }
  }

}


/*********************************************
* simplest constructor of an irregular graph *
* no check for double edges etc is done      *
*********************************************/
void constructirregulargraph(graphs *graph, int vnodenum,
                             int *vdegreelist, double *vpercentagelist, int vdegreesnum,
                             int *cdegreelist, double *cpercentagelist, int cdegreesnum,
                             int verbose) {
  int node, socket, tosocket, tonode;
  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("\n");
    printf("Construction of (irregular) graph:\n");
    printf("1. Set number of degrees and max degrees.\n");
  }
  assert(vdegreesnum>0 && cdegreesnum>0);
  (*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 (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));

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

  /* enter the degreelist */
  (*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", (*(*graph).vdegreelist).degree[degreesnum],
             (*(*graph).vdegreelist).numofnodes[degreesnum]);
    }
  }

  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)/(sumc**(cdegreelist+degreesnum)));
    if (verbose>0)
      printf("   cdegree:=%d cdegreenum:=%d\n", (*(*graph).cdegreelist).degree[degreesnum],
             (*(*graph).cdegreelist).numofnodes[degreesnum]);
  }

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