C crash, BFS possible routes on large graph

Question

I've writen a Bread-First Search algorithm in C that searches through a graph structure (in this case representing a grid of streets) and returns ALL possible routes from node A to node B.

What I've found is that the function works very quickly for small graphs (around 24 nodes), but will crash with anything larger than this. I thought it was a problem with too many mallocs, so I added free() into my function to remove space while running through the queue. This does not, unfortunately, fix the problem. Also note that I never get the error message "Out of memory," either, so I'm not sure what's happening...

void BFS_search(struct map *m, int start, int end){
int n = m->nb_vertice+1;
int i=0;
int num=0;

//BFS requires a queue (pile) to maintain a list of nodes to visit 
struct queue {
    int current_node;
    int visited[n]; //cannot be a pointer! Otherwise the pointer may influence other queue structures
    struct queue *suivant;
};

//Function to add a node at the end of the queue.
void addqueue (int value, struct queue *old, int * old_seen) {
    int i;
    if (old->suivant==NULL){
        struct queue *nouveau;
        nouveau = (struct queue *)malloc(sizeof(struct queue));
        if (nouveau == NULL){
            printf("\n\nSnap! Out of memory, exiting...\n");
            exit(1);
        }
        nouveau->current_node = value;
        for (i = 0; i <= n; ++i){ 
            if (old_seen[i]==1)
                nouveau->visited[i]=1;
            else nouveau->visited[i]=0;
        }
        nouveau->suivant = NULL;
        old->suivant=nouveau;
        return;
    }
    else addqueue(value,old->suivant,old_seen);
}

struct queue * dequeue (struct queue *old){
    struct queue *nouveau;
    nouveau = (struct queue *)malloc(sizeof(struct queue));
    if (nouveau == NULL){
        printf("\n\nSnap! Out of memory, exiting...\n");
        exit(1);
    }
    nouveau = old->suivant;
    free(old);
    return(nouveau);
}

//the actual Breadth First Search Algorithm
int BFS(struct map *m, struct queue *q, int num, int end){
    int k;
    q->visited[q->current_node]=1; //mark current node as visited

    while(q!=NULL){
        //if we reached the destination, add +1 to the counter
        if (q->current_node==end){
            num+=1;
        }
        //if not the destination, look at adjacent nodes
        else {
            for (k=1;k<n;++k)
                if (m->dist[q->current_node][k]!=0 && q->visited[k]!=1){
                    addqueue(k,q,q->visited);
                }
            }
        //if queue is empty, stop and return the number 
        if (q->suivant==NULL){
            return(num);
        }
        //if queue is not empty, then move to next in queue
        else
            return(BFS(m,dequeue(q),num,end));
    }
}

//create and initialize start structure
struct queue *debut;
debut = (struct queue *)malloc(sizeof(struct queue));
for (i = 0; i <= n; ++i)
    debut->visited[i]=0;            
debut->current_node=start;
debut->visited[start]=1;
debut->suivant = NULL;

num=BFS(m,debut,0,end);
printf("\nIl existe %d routes possibles! \n",num);
}

Note that I'm using a struct map, which stores all the edges and nodes for my graph, including nb_vertices (number of nodes), and a distance matrix dist[i][j], which is the distance from node i to j, or 0 if not connected.

Any help would be greatly appreciated! I assume it's an error with the amount of memory available. I'd at least like to have a way to output a specific error message if I can't avoid the memory problems...

In C, you should [never cast the return value of malloc.](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — , Jan 18 '13 at 11:00
Also, `return` is not a function. I know this style is common, but I still think it's worth pointing out just so you're doing it *knowingly* (for some benefit that I don't understand). — unwind, Jan 18 '13 at 11:11

score 2 · Accepted Answer · answered Jan 18 '13 at 11:00

2

Your dequeue operation is leaking memory. You malloc some memory and store the pointer in nouveau, but then you say nouveau = old->suivant, losing the malloc'd buffer. There's no need to malloc at all when popping from the front of a linked list:

struct queue *dequeue(struct queue *q)
{
    struct queue *next = q->suivant;
    free(q);
    return next;
}

As for why you don't get an "out of memory" error, I'm guessing you're on Linux and you're experiencing the sad effects of overcommit.

answered Jan 18 '13 at 11:00

Fred Foo

355,277
75
744
836

Thanks for the help! This allows my program to run a little longer, but it still crashes after about 30 seconds if I run it on a graph of 50 nodes. – Drew75 Jan 18 '13 at 12:25
Also, I am running it on my Windows partition. I can try on the linux side to see if that changes things... – Drew75 Jan 18 '13 at 12:26
@user1990100 Another issue is your use of `int visited[n]` in the definition of `struct queue`. You should need only a single visited set for the whole algorithm. – Fred Foo Jan 18 '13 at 12:31
Actually with a single visited set, the program will never find all possible paths, it will only find subsets. Each different path needs to keep track of the nodes it has traversed, while not knowing which nodes it's neighbors have seen already. – Drew75 Jan 18 '13 at 15:05
@user1990100: Ah. But then you'll want to keep the set of paths as a parent-pointer DAG in your queue nodes (tricky, but doable with reference counting). – Fred Foo Jan 18 '13 at 15:42
Well the visited[] matrix does the trick -- the program does work and produce correct answers for small graphs. I'm still not able to solve the crash issue, though. Are there any other "warning messages" I could insert that could help me find where the problem is? – Drew75 Jan 19 '13 at 08:16

C crash, BFS possible routes on large graph

1 Answers1