SegFault with malloc

[Sourabh Verma]

I wrote a program to detect if a graph is tree or not. Initially it was using static memory. Later I changed it to use memory dynamically using malloc().
M problem is that, my program it works great for case when graph is not tree but fails if it is.

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


int main()
{
    bool **graph, isTree = true;
    // bool graph[100][100], isTree = true;
    int u, v, i, j, queueTop = 0, queueBottom = 0;
    int nodes, edges, *node_status, *queue;
    // int nodes, edges, node_status[100], queue[100];
    // node_status 0 -> unvisited, 1 -> ready, 2 -> visited


    scanf("%d %d", &nodes, &edges);


    // dynamic memory allocation


    graph = (bool**) malloc(sizeof(bool*) * (nodes+1));
    for (i=0; i<edges; i++)
        graph[i] = (bool*) malloc(sizeof(bool) * nodes);
    queue = (int*) malloc(sizeof(int) * nodes * 2);
    node_status = (int*) malloc(sizeof(int) * nodes);


    // initialize
    for (i=0; i<nodes; i++) {
        for (j=0; j<nodes; j++) {
            if (i == j)
                graph[i][i] = true;
            else
                graph[i][j] = false;
            printf("graph[%d][%d] allocated\n", i, j);
        }
    }


    queue[0] = 0;


    for (i=0; i<nodes; i++)
        node_status[i] = 0;
    node_status[0] = 1;




    // input the values
    for (i=0; i<edges; i++) {
        scanf("%d %d", &u, &v);
        graph[--u][--v] = true;
        graph[v][u] = true;
    }




    while (queueBottom >= queueTop) {
        u = queue[queueTop++];
        node_status[u] = 2; // set u to visited
        // find all connected nodes
        for (i=0; i<nodes; i++) {
            if (i != u && graph[u][i] == true) {
                // check if cycle exists
                if (node_status[i] == 2 || node_status[i] == 1) {
                    isTree = false;
                    break;
                }


                // enqueue node
                queue[++queueBottom] = i;
                node_status[i] = 1;


                // remove connection to avoid back-tracing
                graph[u][i] = false;
                graph[i][u] = false;
            }
        }
        if (!isTree)
            break;
    }


    if (isTree)
        printf("YES\n");
    else
        printf("NO\n");


    return (0);
}

As you can see below, my program fails to allocate last row of **graph in case when answer is supposed to be YES

Test case : 5 5 1 2 1 4 1 5 4 3 5 3 (Ans: NO)
Output:

graph[0][0] allocated
graph[0][1] allocated
graph[0][2] allocated
graph[0][3] allocated
graph[0][4] allocated
graph[1][0] allocated
graph[1][1] allocated
graph[1][2] allocated
graph[1][3] allocated
graph[1][4] allocated
graph[2][0] allocated
graph[2][1] allocated
graph[2][2] allocated
graph[2][3] allocated
graph[2][4] allocated
graph[3][0] allocated
graph[3][1] allocated
graph[3][2] allocated
graph[3][3] allocated
graph[3][4] allocated
graph[4][0] allocated
graph[4][1] allocated
graph[4][2] allocated
graph[4][3] allocated
graph[4][4] allocated
NO

Test case : 5 4 1 2 1 4 1 5 4 3 (Ans: YES)
Output:

graph[0][0] allocated
graph[0][1] allocated
graph[0][2] allocated
graph[0][3] allocated
graph[0][4] allocated
graph[1][0] allocated
graph[1][1] allocated
graph[1][2] allocated
graph[1][3] allocated
graph[1][4] allocated
graph[2][0] allocated
graph[2][1] allocated
graph[2][2] allocated
graph[2][3] allocated
graph[2][4] allocated
graph[3][0] allocated
graph[3][1] allocated
graph[3][2] allocated
graph[3][3] allocated
graph[3][4] allocated
[1]    25801 segmentation fault (core dumped)  ./a.out

I also tried with 7 6 2 3 2 7 3 4 3 6 7 1 1 5 but it gives a similar problem

[c99tutorial]

It looks like you're accessing some indices that you haven't alllocated, however it's difficult by eyeballing it where exactly the problem is. One way is to add some quick assertion checks before your array accesses. For example, you're assuming when you do graph[i][j] that i is in 0...edges-1 and j is in 0...nodes-1. So one way to catch an error in addressing this would be to place a check before you actually touch graph[i][j] by writing something like this beforehand:

assert(i >= 0 && i <= edges-1);
assert(j >= 0 && j <= nodes-1);
// do something with graph[i][j]

Also notice you never are freeing your mallocs. Basically if you don't free, it probably means you have a design problem in your allocation. For every malloc you should have a corresponding free somewhere.

[Sourabh Verma]

Thanks for your help c99tutorial. This was a typo:

    for (i=0; i<edges; i++)
        graph[i] = (bool*) malloc(sizeof(bool) * nodes);

It was supposed to be:

    for (i=0; i<nodes; i++)
        graph[i] = (bool*) malloc(sizeof(bool) * nodes);

In the NO case, nodes == edges but I misinterpreted this. I thought that only YES case was giving the segfault.

Thanks for your help again