Ошибка сегментации в реализации функции Форда-Фулкерсона

Я работаю над классным заданием и столкнулся с проблемой, которую не смог понять. Я реализую алгоритм Форда-Фалкерсона, используя BFS, чтобы найти максимальный поток. Но при попытке установить матрицу остаточной емкости на заданную емкость я столкнулся с ошибкой сегментации. В тестовом коде, который мы получили, я вижу, что исходная матрица емкости была передана по значению по ее адресу, но у меня такое ощущение, что в моем коде я не взаимодействую с ней так, как я думаю? Это заставляет меня поверить, что у меня может быть такая же проблема, повторяющаяся в другом месте. Я работал с gdb и увидел, что здесь, в моем вложенном цикле for, я столкнулся с ошибкой сегментации в этой строке:

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

Тем не менее, ничто из того, что я пробовал, не сработало для меня, поэтому я довольно озадачен.

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

И вот тестовый код, предоставленный нам на случай, если он понадобится:

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

person dream_koala21    schedule 16.05.2016    source источник
comment
Используя отладчик или распечатав промежуточные шаги, проверьте, в какой строке вы получаете ошибку сегментации. Этот процесс называется отладкой. Если вы не умеете отлаживать свой код, другие ваши навыки программирования бесполезны.   -  person user31264    schedule 16.05.2016
comment
Мне жаль! Я забыл упомянуть в своем посте, что я использовал gdb, чтобы найти, где моя ошибка сегментации, я наткнулся на строку resCap[i][j] = (capacity + in + j); Я считаю, что моя проблема заключается в том, как я копирую исходную матрицу емкости в свою матрицу остаточной емкости, однако ничего из того, что я пытаюсь сделать, кажется правильным.   -  person dream_koala21    schedule 16.05.2016
comment
печатать i на каждой итерации цикла. Вы будете знать, при каком i вы получите ошибку сегментации. затем для этого i выводить j на каждой итерации самого внутреннего цикла.   -  person user31264    schedule 17.05.2016


Ответы (1)


Эта строка, скорее всего, будет segfault, она использует Clang.

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

Вы объявляете очень большой массив в стеке. Насколько большой можно увидеть, когда вы пытаетесь выделить его с помощью calloc. Вместо этого попробуйте это и не забудьте free использовать такой же цикл.

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

Это много места, т.е.

(1000 * sizeof(int*) * (1000 * n * sizeof(int)))
person Harry    schedule 17.05.2016
comment
Это приводит к segfault, возможно, это было вызвано переполнением стека. stackoverflow.com/questions/2685413/ - person Harry; 17.05.2016