Segmentierungsfehler in der Funktion, die Ford-Fulkerson implementiert

Question

Ich arbeite an einer Klassenaufgabe und ich bin auf ein Problem gestoßen, das ich nicht herausfinden konnte. Ich implementiere den Ford-Fulkerson-Algorithmus unter Verwendung von BFS, um den maximalen Fluss zu finden. Aber während ich versuchte, meine Restkapazitätsmatrix auf die gegebene Kapazität zu setzen, traf ich einen Segmentierungsfehler. In dem Testcode, den wir erhalten haben, kann ich sehen, dass die originale Kapazitätsmatrix wertmäßig an ihre Adresse weitergegeben wurde, aber ich habe das Gefühl, dass ich in meinem Code nicht so mit mir zusammenarbeite, wie ich denke. Was mich zu der Annahme verleitet, dass das gleiche Problem an anderer Stelle auftreten könnte. Ich arbeitete mit GDB und sah, dass ich einen Segmentation Fault auf dieser Linie hier in meinem verschachtelten for-Schleife getroffen:

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

jedoch nichts, was ich versucht habe, hat für mich gearbeitet, obwohl so ich ziemlich ratlos bin.

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

Und hier ist der Testcode zu uns, falls vorausgesetzt, es benötigt wird:

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

Answer 1

Diese Linie wahrscheinlich segfault wird, es Clang nicht verwenden.

Sie deklarieren ein sehr großes Array auf dem Stapel. Wie groß kann gesehen werden, wenn Sie versuchen, es mit Calloc zuzuordnen. Versuchen Sie dies stattdessen und vergessen Sie nicht free es mit der gleichen Art von Schleife.

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

Dies ist eine Menge Platz also

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