This is a program that seeks to represent a network following the Barabasi-Albert algorithm. We start with a randomly generated cluster for an initial n nodes (user input) and then to each of the remaining N-n nodes in turn we "preferentially attach" m nodes. This is according to the principle that a node is more likely to be chosen if it is already well linked to. (the mechanics of this are in the subfunction "findmeanode")

All seems to be fine for the case m=1 and m=2, but things go wrong for m=3 onwards. I have googled for the error messages that I have been getting and the results of that search seem to suggest one or both of the following things may be occuring:

1) I have used an array index out of range of an array.

2) a pointer has been dereferenced that doesn't point to allocated memory.

My suspicion is the former and I have tried hard to find it without sucess. I get the feeling the problem is rather subtle or my flu is just getting the better of me!

(Notes before code: Salem wrote the extend and show functions and laserlight suggested the tags array for tracking deletions that helped me get the code to this stage ... thanks to you both!)

Matt

Here is the code: (I'm using MS visual studio C++)

Code:#include "stdafx.h" #include<stdio.h> #include<stdlib.h> #include<math.h> #include<time.h> #include<gsl/gsl_rng.h> /*Need Gnu Scientific Library*/ /*GLOBAL VARIABLES*/ gsl_rng * seed = gsl_rng_alloc(gsl_rng_ranlux389); /*Above line will need to be changed for different compiler*/ #define N 100 /*Number of nodes*/ #define FILENAME "C:\\matt\\output\\output.dot" /*FUNCTION PROTOTYPES*/ void extend(int**, int[], int, int); void show(int**, int[], int); int findmeanode(int**, int[], int[], int); void deletefrom(int[], int, int); void opendot(char[]); void writedot(char[],int,int); void closedot(char[]); int main(int argc, char* argv[]) { int m,n,c; int i,j,k; int step; int *nodes, *targets, *tags, *temp; char getm[20], getn[20], getc[3]; opendot(FILENAME); printf("There are %d nodes.\n", N); printf("To change this, please change N and recompile.\n"); printf("Please enter m, the number of links added at each preferential attachment step:\n"); fgets(getm, 20, stdin); m=atoi(getm); printf("The value for m is %d.\n",m); printf("Please enter n, the size of the initial cluster:\n"); printf("(We suggest approximately m+2)\n"); fgets(getn, 20, stdin); n=atoi(getn); printf("The initial cluster will now be built.\n"); printf("This is a random graph with n=%d nodes which are connected with probability 0.6",N); int *nbrs[N]={NULL}; /*No neighbours for any node to begin with*/ int degrees[N]={0}; /*Each node initially has degree zero*/ for(i=0;i<=n-2;i++){ for(j=1;j<=n-1;j++){ if(i<j) if(gsl_rng_uniform(seed)<0.6){ extend(nbrs, degrees, i, j); writedot(FILENAME,i,j); extend(nbrs, degrees, j, i); } } } printf("Enter 1 to see the initial cluster.\n"); fgets(getc, 3, stdin); c=atoi(getc); if (c==1) show(nbrs,degrees,n); printf("The program will now follow the Barabasi-Albert algorithm to generate the remainder of the network.\n"); printf("NB: for large N, this may take some time!\n"); for(step=n; step<N; step++){ targets=(int*)calloc(m,sizeof(int)); for(i=0;i<m;i++){ //choose m nodes to be pref. attached if(i==0){ nodes=(int*)calloc(step,sizeof(int)); tags=(int*)calloc(step,sizeof(int)); for(j=0;j<step;j++){ nodes[j]=j; tags[j]=0; //just to be sure! }//j targets[i]=findmeanode(nbrs,degrees,nodes,step); tags[targets[i]]=1; //update tags }//i==0 else{ temp=(int*)calloc(step-i,sizeof(int)); k=0; for(j=0;j<step;j++){ if(tags[i]==1) continue; else{ temp[j]=nodes[k]; k++; } } free(nodes); nodes=(int*)calloc(step-i,sizeof(int)); for(j=0;j<step-i;j++) nodes[j]=temp[j]; free(temp); targets[i]=findmeanode(nbrs,degrees,nodes,step-i); tags[targets[i]]=1; }//else }//i for(i=0;i<m;i++){ //add the m new nodes to current node etc extend(nbrs,degrees,targets[i],step); writedot(FILENAME,targets[i],step); extend(nbrs,degrees,step,targets[i]); } free(targets); free(tags); } show(nbrs,degrees,N); closedot(FILENAME); return 0; } /*FUNCTIONS*/ void extend(int *arrays[], int lengths[], int array_num, int value) { int len = lengths[array_num]; int *temp; /* extend the array by 1 space, preserving existing contents */ temp = (int*)realloc(arrays[array_num],sizeof(int)*(len+1)); /* if successful, add the new value at the end of the new array */ if (temp!=NULL){ arrays[array_num] = temp; /* update the array pointer */ arrays[array_num][len] = value; /* append the value */ lengths[array_num]++; /* increment the count of values */ } else { printf("Failure in realloc.\n"); return; } return; } /* print each array up to its current length */ void show(int *arrays[], int lengths[], int limit) { int i, j; if (limit>N) limit=N; for(i=0; i<limit; i++){ printf("array[%d]=",i); for(j=0; j<lengths[i]; j++){ printf("%d ",arrays[i][j]); } printf("\n"); } return; } int findmeanode(int *nbrs[], int degrees[], int nodes[], int step) { int i,totaldegree,target; int *cumulative; double random; double *probtable; cumulative=(int*)calloc(step,sizeof(int)); probtable=(double*)calloc(step,sizeof(double)); for(i=0; i<step; i++){ if(i==0) cumulative[i]=degrees[nodes[i]]; else cumulative[i]=cumulative[i-1]+degrees[nodes[i]]; } totaldegree=cumulative[step-1]; for(i=0;i<step;i++) probtable[i]=(double)cumulative[i]/(double)totaldegree; random=gsl_rng_uniform(seed); for(i=0;i<step;i++){ if(random<probtable[i]){ target=nodes[i]; break; } else target=nodes[step-1]; } return target; } void opendot(char filename[]) { /*OPENS A DOT FILE TO WRITE GRAPH STRUCTURE*/ FILE *fptr; fptr=fopen(filename, "w"); if(fptr==NULL){ fprintf(stderr, "Unable to open \"%s\" to write.\n", filename); return; } fprintf(fptr, "strict graph matt {\n"); fclose(fptr); return; } void writedot(char filename[], int a, int b) { FILE *fptr; fptr=fopen(filename, "a"); if(fptr==NULL){ fprintf(stderr, "Unable to open \"%s\" to write.\n", filename); return; } fprintf(fptr, "%d -- %d;\n", a, b); fclose(fptr); return; } void closedot(char filename[]) { /*CLOSES DOT FILE*/ FILE *fptr; fptr=fopen(filename, "a"); if(fptr==NULL){ fprintf(stderr, "Unable to open \"%s\" to write.\n", filename); return; } fprintf(fptr, "}\n"); fclose(fptr); return; }