Segmentation fault in function implementing Ford-Fulkerson

Question

I'm working on a class assignment and I've run into an issue I haven't been able to figure out. I'm implementing the Ford-Fulkerson algorithm using BFS to find max flow. But while trying to set my Residual Capacity matrix to the given capacity, I hit a segmentation fault. In the test code we received, I can see that the original capacity matrix was passed by value by its address, but I have a feeling that in my code I'm not interacting with it the way I think I am? Which leads me to believe that I may have the same issue recurring elsewhere. I worked with gdb and saw that I hit a segmentation fault on this line here in my nested for loop :

    resCap[i][j] = *(capacity + i*n + j);

However, nothing I have tried has worked for me though so I am pretty stumped.

void maximum_flow(int n, int s, int t, int *capacity, int *flow)
{
    int i, j, resCap[n][n], path[n];    // residual capacity and BFS augmenting path
    int min_path = INT_MAX;    // min of the augmenting path

    // Assign residual capacity equal to the given capacity
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {  
            resCap[i][j] = *(capacity + i*n + j);
            *(flow + i*n + j) = 0;  // no initial flow
        }

    // Augment path with BFS from source to sink
    while (bfs(n, s, t, &(resCap[0][0]), path))
    {
        // find min of the augmenting path
        for (j = t; j != s; j = path[j])
        {
            i = path[j];
            min_path = min(min_path, resCap[i][j]);
        }

        // update residual capacities and flows on both directions
        for (j = t; j != s; j = path[j])
        {
            i = path[j];
            if(*(capacity + i*n + j) > 0)
             *(flow + i*n + j) += min_flow_path;
            else
             *(flow + j*n + i) -= min_flow_path;

            resCap[i][j] -= min_flow_path;
            resCap[j][i] += min_flow_path;
        }
    }
}

And here is the test code provided to us in case it is needed:

int main(void)
{  int cap[1000][1000], flow[1000][1000];
   int i,j, flowsum;
   for(i=0; i< 1000; i++)
     for( j =0; j< 1000; j++ )
       cap[i][j] = 0;

   for(i=0; i<499; i++)
     for( j=i+1; j<500; j++) 
       cap[i][j] = 2;
   for(i=1; i<500; i++)
     cap[i][500 + (i/2)] =4;
   for(i=500; i < 750; i++ )
   { cap[i][i-250]=3;
     cap[i][750] = 1;
     cap[i][751] = 1;
     cap[i][752] = 5;
   }
   cap[751][753] = 5;
   cap[752][753] = 5;
   cap[753][750] = 20;
   for( i=754; i< 999; i++)
   {  cap[753][i]=1;
      cap[i][500]=3;
      cap[i][498]=5;
      cap[i][1] = 100;
   }
   cap[900][999] = 1;
   cap[910][999] = 1;
   cap[920][999] = 1;
   cap[930][999] = 1;
   cap[940][999] = 1;
   cap[950][999] = 1;
   cap[960][999] = 1;
   cap[970][999] = 1;
   cap[980][999] = 1;
   cap[990][999] = 1;
   printf("prepared capacity matrix, now executing maxflow code\n");
   maximum_flow(1000,0,999,&(cap[0][0]),&(flow[0][0]));
   for(i=0; i<=999; i++)
     for(j=0; j<=999; j++)
     {  if( flow[i][j] > cap[i][j] )
        {  printf("Capacity violated\n"); exit(0);}
     }    
   flowsum = 0;
   for(i=0; i<=999; i++)
     flowsum += flow[0][i];
   printf("Outflow of  0 is %d, should be 10\n", flowsum);
   flowsum = 0;
   for(i=0; i<=999; i++)
     flowsum += flow[i][999];
   printf("Inflow of 999 is %d, should be 10\n", flowsum);

   printf("End Test\n");
}

Using a debugger, or printing intermediate steps, check at what line you receive the segmentation fault. This process is called debugging. If you don't know to debug your code, your other programming skills are not useful. — user31264, May 16 '16 at 18:19
I'm sorry! I forgot to mention in my post that I did use gdb to find where my segmentation fault is, I hit it at the line "resCap[i][j] = *(capacity + i*n + j);" I believe my issue is how I am copying the original capacity matrix into my residual capacity matrix, however nothing I try seems to get it right. — dream_koala21, May 16 '16 at 20:46
print `i` at every iteration of the loop. You will know at what `i` you get the segmentation fault. then, for this `i`, print `j` at every iteration of the innermost loop. — user31264, May 16 '16 at 21:07

score 0 · Answer 1 · answered May 17 '16 at 01:51

This line is likely going to segfault, it does using Clang.

int i, j, resCap[n][n], path[n];

You're declaring a very large array on the stack. Just how big can be seen when you try and allocated it using calloc. Try this instead and don't forget to free it using the same sort of loop.

int **resCap2 = calloc(1, n * sizeof(int *));
assert(resCap2);
for (i = 0; i < n; i++) {
  resCap2[i] = calloc(1, n * sizeof(int));
  assert(resCap2[i]);
}

This is a lot of space ie

(1000 * sizeof(int*) * (1000 * n * sizeof(int)))

It results in a segfault, it may have been caused by a stackoverflow. http://stackoverflow.com/questions/2685413/what-is-the-difference-between-a-segmentation-fault-and-a-stack-overflow — Harry, May 17 '16 at 01:59

Segmentation fault in function implementing Ford-Fulkerson

1 Answers1