#include <stdio.h>#include <stdlib.h>#include <iostream.h>#include <fstream.h>#include "BigGirth.h"#include "Random.h"NodesInGraph::NodesInGraph(void) {;}void NodesInGraph::setNumOfConnectionSymbolBit(int deg) {  if(deg<=0) {cout<<"Wrong NodesInGraph::setNumOfConnectionSymbolBit()"<<endl;exit(-1);}  numOfConnectionSymbolBit=deg;  connectionSymbolBit=new int[deg];}void NodesInGraph::initConnectionParityBit(void) {  maxDegParity=10000;  numOfConnectionParityBit=0;  connectionParityBit=new int[1];//dummy memory, actually not used}void NodesInGraph::initConnectionParityBit(int deg) {  maxDegParity=deg;  numOfConnectionParityBit=0;  connectionParityBit=new int[1];//dummy memory, actually not used}NodesInGraph::~NodesInGraph(void) {  if(connectionParityBit!=NULL)    delete [] connectionParityBit;  if(connectionSymbolBit!=NULL)    delete [] connectionSymbolBit;}BigGirth::BigGirth(void) {;}BigGirth::BigGirth(int M, int N, int *symbolDegSequence, char *filename, int sglConcent, int tgtGirth){  int i, j, k, m, index, localDepth=100;  int *mid;  EXPAND_DEPTH=(tgtGirth-4)/2;   if(EXPAND_DEPTH<0) EXPAND_DEPTH=0;  //      corresponds to depth l in the PEG paper;    //      the target girth = 2*EXPAND_DEPTH+4  //      if set large, then GREEDY algorithm  myrandom=new Random();  //(12345678l, 987654321lu);  (*this).M=M;  (*this).N=N;  (*this).filename=filename;  mid=new int[M];  localGirth=new int[N];  nodesInGraph=new NodesInGraph [N];  for(i=0;i<N;i++)    nodesInGraph[i].setNumOfConnectionSymbolBit(symbolDegSequence[i]);  j=0;  for(k=0;k<N;k++) j+=symbolDegSequence[k];  k=j/M;  for(i=0;i<M;i++) mid[i]=k;  for(i=0;i<j-k*M;i++) mid[i]++;  k=0; for(i=0;i<M;i++) k+=mid[i];  if(k!=j) {cout<<"Wrong in computing maxDegParity!"<<endl;exit(-1);}  for(i=0;i<M;i++) {    if(sglConcent==0) nodesInGraph[i].initConnectionParityBit(mid[i]);    else  nodesInGraph[i].initConnectionParityBit();   }         for(k=0;k<N;k++){    m=1000000;index=-1;    for(i=0;i<M;i++){      if(nodesInGraph[i].numOfConnectionParityBit<m && nodesInGraph[i].numOfConnectionParityBit<nodesInGraph[i].maxDegParity) {	m=nodesInGraph[i].numOfConnectionParityBit;	index=i;      }    }    nodesInGraph[k].connectionSymbolBit[0]=index;//least connections of parity bit    int iter=0;   ITER:    localGirth[k]=100;    for(m=1;m<nodesInGraph[k].numOfConnectionSymbolBit;m++){      nodesInGraph[k].connectionSymbolBit[m]=selectParityConnect(k, m, localDepth);      localGirth[k]=(localGirth[k]>localDepth)?localDepth:localGirth[k];            if(k>0 && localGirth[k]<localGirth[k-1] && iter<20) {iter++; goto ITER;}      if(localGirth[k]==0 && iter<30) {iter++; goto ITER;}    }    //if((k+1)%100==0) {      cout<<"k="<<k<<"  ";      for(m=0;m<nodesInGraph[k].numOfConnectionSymbolBit;m++)	cout<<nodesInGraph[k].connectionSymbolBit[m]<<" ";      cout<<"LocalGirth="<<2*localGirth[k]+4;      cout<<endl;      //}    updateConnection(k);  }  cout<<"Showing the row weight distribution..."<<endl;  for(i=0;i<M;i++)    cout<<nodesInGraph[i].numOfConnectionParityBit<<" ";  cout<<endl;  delete [] mid;  ofstream cycleFile;  cycleFile.open("leftHandGirth.log", ios::out);  localDepth=100;  for(k=0;k<N;k++) {    if(localGirth[k]<localDepth) localDepth=localGirth[k];    if(localDepth==100) cycleFile<<"inf ";    else cycleFile<<2*localDepth+4<<" ";  }  cycleFile<<endl;  cycleFile.close();  cout<<"*************************************************************"<<endl;  cout<<"       The global girth of the PEG Tanner graph :="<< 2*localDepth+4<<endl;  cout<<"*************************************************************"<<endl;  loadH();}BigGirth::~BigGirth(void) {  if(H!=NULL) {    for(int i=0;i<M;i++)      delete [] H[i];    delete [] H;    H=NULL;  }    delete [] localGirth;  delete [] nodesInGraph;  nodesInGraph=NULL;  delete myrandom;}int BigGirth::selectParityConnect(int kthSymbol, int mthConnection, int & cycle) {  int i, j, k, index, mincycles, numCur, numNext, cpNumCur;  int *tmp, *med;  int *current;//take note of the covering parity bits  mincycles=0;  tmp=new int[M]; med=new int[M];  numCur=mthConnection;  current=new int[mthConnection];  for(i=0;i<mthConnection;i++) current[i]=nodesInGraph[kthSymbol].connectionSymbolBit[i];LOOP:  mincycles++;  for(i=0;i<M;i++) tmp[i]=0;  //maintain   for(i=0;i<mthConnection;i++) tmp[nodesInGraph[kthSymbol].connectionSymbolBit[i]]=1;  for(i=0;i<numCur;i++){    for(j=0;j<nodesInGraph[current[i]].numOfConnectionParityBit;j++){      for(k=0;k<nodesInGraph[nodesInGraph[current[i]].connectionParityBit[j]].numOfConnectionSymbolBit;k++){        tmp[nodesInGraph[nodesInGraph[current[i]].connectionParityBit[j]].connectionSymbolBit[k]]=1;      }    }  }  index=0; cpNumCur=0;  for(i=0;i<M;i++) {    if(tmp[i]==1) cpNumCur++;    if(tmp[i]==1 || nodesInGraph[i].numOfConnectionParityBit>=nodesInGraph[i].maxDegParity)       index++;     }  if(cpNumCur==numCur) {//can not expand any more    //additional handlement to select one having least connections    j=10000000; //dummy number    for(i=0;i<M;i++){      if(tmp[i]==0 && nodesInGraph[i].numOfConnectionParityBit<j && nodesInGraph[i].numOfConnectionParityBit<nodesInGraph[i].maxDegParity)	j=nodesInGraph[i].numOfConnectionParityBit;    }    for(i=0;i<M;i++){      if(tmp[i]==0){	if(nodesInGraph[i].numOfConnectionParityBit!=j || nodesInGraph[i].numOfConnectionParityBit>=nodesInGraph[i].maxDegParity){	  tmp[i]=1;	}      }    }    index=0;    for(i=0;i<M;i++) if(tmp[i]==1) index++;    //----------------------------------------------------------------    j=(*myrandom).uniform(0, M-index)+1; //randomly selected    index=0;    for(i=0;i<M;i++){      if(tmp[i]==0) index++;      if(index==j) break;    }    delete [] tmp; tmp=NULL;    delete [] current; current=NULL;    return(i);  }  else if(index==M || mincycles>EXPAND_DEPTH){//covering all parity nodes or meet the upper bound on cycles        cycle=mincycles-1;    for(i=0;i<M;i++) tmp[i]=0;    for(i=0;i<numCur;i++) tmp[current[i]]=1;    index=0;    for(i=0;i<M;i++) if(tmp[i]==1) index++;    if(index!=numCur) {cout<<"Error in the case of (index==M)"<<endl;exit(-1);}    //additional handlement to select one having least connections    j=10000000;     for(i=0;i<M;i++){      if(tmp[i]==0 && nodesInGraph[i].numOfConnectionParityBit<j && nodesInGraph[i].numOfConnectionParityBit<nodesInGraph[i].maxDegParity)	j=nodesInGraph[i].numOfConnectionParityBit;    }    for(i=0;i<M;i++){      if(tmp[i]==0){	if(nodesInGraph[i].numOfConnectionParityBit!=j || nodesInGraph[i].numOfConnectionParityBit>=nodesInGraph[i].maxDegParity){	  tmp[i]=1;	}      }    }          index=0;    for(i=0;i<M;i++) if(tmp[i]==1) index++;       j=(*myrandom).uniform(0, M-index)+1;    index=0;    for(i=0;i<M;i++){      if(tmp[i]==0) index++;      if(index==j) break;    }    delete [] tmp; tmp=NULL;    delete [] current; current=NULL;    return(i);  }  else if(cpNumCur>numCur && index!=M){    delete [] current;    current=NULL;    numCur=cpNumCur;    current=new int[numCur];    index=0;    for(i=0;i<M;i++) {      if(tmp[i]==1) {current[index]=i; index++;}    }    goto LOOP;  }  else {    cout<<"Should not come to this point..."<<endl;    cout<<"Error in BigGirth::selectParityConnect()"<<endl;    return(-1);  }}void BigGirth::updateConnection(int kthSymbol){  int i, j, m;  int *tmp;  for(i=0;i<nodesInGraph[kthSymbol].numOfConnectionSymbolBit;i++){    m=nodesInGraph[kthSymbol].connectionSymbolBit[i];//m [0, M) parity node    tmp=new int[nodesInGraph[m].numOfConnectionParityBit+1];    for(j=0;j<nodesInGraph[m].numOfConnectionParityBit;j++)      tmp[j]=nodesInGraph[m].connectionParityBit[j];    tmp[nodesInGraph[m].numOfConnectionParityBit]=kthSymbol;    delete [] nodesInGraph[m].connectionParityBit;    nodesInGraph[m].connectionParityBit=NULL;    nodesInGraph[m].numOfConnectionParityBit++; //increase by 1    nodesInGraph[m].connectionParityBit=new int[nodesInGraph[m].numOfConnectionParityBit];    for(j=0;j<nodesInGraph[m].numOfConnectionParityBit;j++)      nodesInGraph[m].connectionParityBit[j]=tmp[j];    delete [] tmp;    tmp=NULL;  }}void BigGirth::loadH(void){  int i, j;  if(H==NULL) {    H=new int*[M];    for(i=0;i<M;i++) H[i]=new int[N];  }