Thread: Why does this code break for m=3?

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

I think the problem lies within the for loop that I've attached the comment "\\pref attach m nodes" to. I get the feeling that because the 0th case is dealt with seperately, the 2nd case (corresponding to m=3) is the first time the loop actually gets repeated - so I think something karmically bad is happening there.

I did read the link at the bottom of Salem's post about asking questions properly and tried to fit things along those lines. The last thing I wanted was to make people dredge through the whole of the code!