Первый поисковый код в C, возможное переполнение стека

Question

Я написал код для поиска в ширину в C, используя сжатую структуру данных разреженных строк.Код, кажется, хорошо работает для одного графика, но возвращает ошибку для другого графического файла.Он хорошо работает для этого файла , но выдает ошибку для этого файла Будучи новичком в программировании на C, я не могу найти причину проблемы и буду признателен за любую помощь

Я попытался проверить условие для цикла while.Условие для цикла истинно, когда код зависает и возвращает ошибку.Я запускаю этот код на CodeBlocks 16.01 с компилятором mingw.

#include <stdio.h>
#include <stdlib.h>
// Declaring a struct type to hold

int main(){
int n, m, counter, current, x, src, dst;
n=0, m=0, counter = 0, current =0, src = 0, dst = 0;

FILE *fp; //create a pointer to the file directory
fp = fopen("filename.graph","r"); //set the directory pointer to the path of the text file containing graph data
if ((fp == NULL)){ perror("Error, no such file exists \n");  exit(1);} 
//If file not found, print error message and exit the program
else
    {
        fscanf(fp,"%d %d", &n,&m); //read first line of text file to get number of vertices and edges in graph

        struct CSRgraph //Create CSR data structure
            {
                int heads[m];    //Stores heads of edges
                int offsets[n+1]; //Stores information on the number of edges leaving each node
            };
        struct CSRgraph g;  //Create an instance of the CSR graph data structure
        g.offsets[0] = 0; //Set the initial offset value to 0
        g.offsets[n] = m; //Set the offset value of 'phantom' node to the number of edges in graph

        for(x=0;x<m;x++) //iterate over all lines containing edge information in text file
            //Read file and create CSR data structure from information in text file
            {
                fscanf(fp,"%d %d",&src,&dst); //read source and head information from file
                g.heads[x] = dst; //assign head information to the next available slot in data structure
                if (src < n+1) //Check that node is valid
                    {
                        if (src == current) //check that current edge originates from same source as previous edge
                            {
                                counter++; //increment counter for the number of edges that originate from current source
                            }
                        else //Current edge does not originate from previous source. New source node encountered
                            {
                                g.offsets[src] = counter + g.offsets[src -1]; //Update offset value for previous source
                                counter = 1; //restart edge origin counter
                                current = src ; //set current to current source
                            }
                    }

            }

fclose(fp); //Close file after use

int Discovered[n],Queue[n+1],Explored[n], *front_ptr,*end_ptr,*exp_ptr;
front_ptr = Queue;  //Initialize the front pointer to the Queue array
end_ptr = Queue;    //Initialize the end pointer to the Queue array
exp_ptr = Explored; //Initialize the explored pointer to the Explored array

for (x=0;x<n;x++)
{
    Discovered[x] = 0; //An array to track discovered nodes. Not necessarily explored, but nodes that have showed up previously
}
// Advance the pointers in the direction you want
*end_ptr = 0; //setting the first element in the queue as the node 0
end_ptr++; //advancing the end pointer to the next available array spot
Discovered[0] = 1;

while (front_ptr != end_ptr)
    { //Queue is empty if front pointer is the same as end pointer
        int p,curr;
        curr = *front_ptr; //grab the front of the queue and set it as current node
        front_ptr++; //equivalent to removing from element and pushing the next node in line to the front
        *exp_ptr = curr; //set current node to explored
        exp_ptr++; //advance the explored pointer one step

    for (p = g.offsets[curr]; p < g.offsets[curr+1]; p++)
        //iterate over all neighbors of current node
        {
        if (Discovered[g.heads[p]] == 0)
        //if node is not already discovered, set it to discovered, add it to queue and advanced the end pointer of queue one step
            {
                Discovered[g.heads[p]] = 1;
                *end_ptr = g.heads[p];
                end_ptr++;
            }
        }
    }

}
    return 0;
}

Answer 1

Использование int heads[m]; в качестве VLA для int с m = 108744 (наряду с другими 4 VLA, которые вы выделяете из 2950 целых чисел), вероятно, вызывает StackOverflow ... (это будет компилятор, ОС и память- зависит от модели).Чтобы устранить проблему, измените CSRgraph, чтобы члены heads и offsets были указателями, а затем динамически распределяли хранилище на основе чисел, считанных из первой строки файла, например,

typedef struct {    /* typdef for convenience */
    int *heads,
        *offsets;
} CSRgraph_t;

int main (int argc, char **argv) {

    CSRgraph_t g;                   /* declare instance of struct */
    ...
    /* allocate/validate g.heads & g.offsets */
    if (!(g.heads = malloc (m * sizeof *g.heads))) {
        perror ("malloc-g.heads");
        return 1;
    }
    /* calloc used to zero g.offsets */
    if (!(g.offsets = calloc ((n + 1), sizeof *g.offsets))) {
        perror ("malloc-g.offsets");
        return 1;
    }
    g.offsets[0] = 0;
    g.offsets[n] = m;
    ...

( примечание: calloc используется для offsets, чтобы инициализировать его всеми нулями при последующем сравнении p < g.offsets[curr+1])

Если сложить все вместе, вы можете сделать:

#include <stdio.h>
#include <stdlib.h>

typedef struct {    /* typdef for convenience */
    int *heads,
        *offsets;
} CSRgraph_t;

int main (int argc, char **argv) {

    CSRgraph_t g;                   /* declare instance of struct */
    int n, m, counter, current;
    n = m = counter = current = 0;
    /* use filename provided as 1st argument (stdin by default) */
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;

    if (!fp) {  /* validate file open for reading */
        perror ("file open failed");
        return 1;
    }
    if (fscanf (fp, "%d %d", &n, &m) != 2) {    /* validate EVERY read */
        fputs ("error: invalid format n, m.\n", stderr);
        return 1;
    }

    /* allocate/validate g.heads & g.offsets */
    if (!(g.heads = malloc (m * sizeof *g.heads))) {
        perror ("malloc-g.heads");
        return 1;
    }
    /* calloc used to zero g.offsets */
    if (!(g.offsets = calloc ((n + 1), sizeof *g.offsets))) {
        perror ("malloc-g.offsets");
        return 1;
    }
    g.offsets[0] = 0;
    g.offsets[n] = m;

    for (int x = 0; x < m; x++) {
        int src;    /* src is only needed within scope of loop */
        if (fscanf (fp, "%d %d", &src, &g.heads[x]) != 2) {
            fprintf (stderr, "error: invalid format - line %d.\n", x);
        }
        if (src < n+1) {
            if (src == current)
                counter++;
        }
        else {
            g.offsets[src] = counter + g.offsets[src -1];
            counter = 1;    /* restart edge origin counter */
            current = src;  /* set current to current source */
        }
    }

    if (fp != stdin) fclose (fp);   /* close file if not stdin */

    int Discovered[n], Queue[n+1], Explored[n], 
        *front_ptr, *end_ptr, *exp_ptr;

    front_ptr = Queue;  /* front pointer to the Queue array */
    end_ptr = Queue;    /* end pointer to the Queue array */
    exp_ptr = Explored; /* explored pointer to the Explored array */

    for (int x = 0; x < n; x++)
        Discovered[x] = 0;

    /* Advance the pointers in the direction you want */
    *end_ptr = 0;
    end_ptr++;
    Discovered[0] = 1;

    while (front_ptr != end_ptr) {
        int curr = *front_ptr;
        front_ptr++;
        *exp_ptr = curr;
        exp_ptr++;

        for (int p = g.offsets[curr]; p < g.offsets[curr+1]; p++) {
            if (Discovered[g.heads[p]] == 0) {
                Discovered[g.heads[p]] = 1;
                *end_ptr = g.heads[p];
                end_ptr++;
            }
        }
    }

    free (g.heads);
    free (g.offsets);

    return 0;
}

( примечание: избегайте жесткого кодирования имен файлов, например, fopen("filename.graph","r"), main() принимает аргументы, используйте их для передачи имени файла в качестве первого аргумента вашей программе [и вы можете читать из stdinпо умолчанию, если аргумент не указан])

Использование памяти / проверка ошибок

$ valgrind ./bin/readgraphsfile ~/tmp/graphfile/large.graph
==17345== Memcheck, a memory error detector
==17345== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==17345== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==17345== Command: ./bin/readgraphsfile ~/tmp/graphfile/large.graph
==17345==
==17345==
==17345== HEAP SUMMARY:
==17345==     in use at exit: 0 bytes in 0 blocks
==17345==   total heap usage: 3 allocs, 3 frees, 447,332 bytes allocated
==17345==
==17345== All heap blocks were freed -- no leaks are possible
==17345==
==17345== For counts of detected and suppressed errors, rerun with: -v
==17345== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Он отлично работает с вашим large.graph файлом.