Why does this code break for m=3?

This is a discussion on Why does this code break for m=3? within the C Programming forums, part of the General Programming Boards category; This is a program that seeks to represent a network following the Barabasi-Albert algorithm. We start with a randomly generated ...

  1. #1
    Not bad at Crack Attack!
    Join Date
    Aug 2003
    Posts
    45

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

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I started to read through this, but a couple of things jumped out:

    You're either compiling as C++, or you're using a C99 compiler. I doubt it's the latter, because I don't think MS has a C99 compiler. And if it's MSCV++ 6.x, I know it's not C99.

    That being the case, you can't declare new variables in mid scope.
    Code:
    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++){
    Furthermore, you should actually narrow down what function the problem is in, rather than just posting a half a dozen functions and hoping we'll debug them all for you. Some people will, but I tend not to.

    Finally, while this isn't your problem, it's highly inefficient for you to keep opening and closing your file every single time you need to write to it. Simply open it once and pass the file pointer around to whatever function you need.

    You'll also want to fflush your output stream every time you display some output, just to make sure you see it when you should. It will make debugging much easier, since you'll actually know how far you're getting.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Not bad at Crack Attack!
    Join Date
    Aug 2003
    Posts
    45

    Where I think the problem is...

    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help it won't compile!!!!!
    By esbo in forum C Programming
    Replies: 58
    Last Post: 01-04-2009, 02:22 PM
  2. A Full Program to analyze.
    By sergioms in forum C Programming
    Replies: 2
    Last Post: 12-30-2008, 08:42 AM
  3. C problem with legacy code
    By andy_baptiste in forum C Programming
    Replies: 4
    Last Post: 05-19-2008, 06:14 AM
  4. Keypress reading
    By geek@02 in forum Windows Programming
    Replies: 1
    Last Post: 06-16-2004, 12:16 PM
  5. cant get code to work
    By duffy in forum C Programming
    Replies: 13
    Last Post: 10-20-2002, 05:23 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21