[FIXED] Why does function crush when reading values and implementing graph?

Issue

It reads from file as it should, it adds fine all the vertices in the graph but after first call of AddEge() the program prints the first two printfs and crushes with -1 process returning code. It won't get into the while loop.

I did some pointer sketching on file using pen but hey, nothing wrong seems to me so far. Anybody ideas?

struct adjvertexlist
{
    int index_vertex;
    struct adjvertexlist *next;
};

struct vertexlist
{
    int index_vertex;
    struct vertexlist *next;
    struct adjvertexlist *list;
};


struct graphrep
{
    int nv;
    int ne;
    struct vertexlist *head;
};

typedef struct graphrep graph;

graph* AddVertex(graph *g, int v)
{
    struct vertexlist *new_vcell;
    new_vcell = (struct vertexlist*)malloc(sizeof(struct vertexlist));
    new_vcell->next = g->head;
    g->head = new_vcell;
    new_vcell->index_vertex = v;
    new_vcell->list = NULL;
    printf("Added %i vertex on graph\n", v);
    return g;
}

graph* AddEdge(graph *g, int v1, int v2)
{
    printf("\nAddEdge() started\n");
    printf("Edge to add from %i to %i and from %i to %i\n", v1, v2, v2, v1);
    printf("awesome characters");
    struct adjvertexlist *new_adjvcell;
    struct vertexlist *iterat_vlist;
    iterat_vlist = g->head;
    printf("text");
    while(iterat_vlist)
    {
        if(iterat_vlist->index_vertex == v1)
        {
            new_adjvcell = (struct adjvertexlist *)malloc(sizeof(struct adjvertexlist));
            new_adjvcell->index_vertex = v2;
            new_adjvcell->next = iterat_vlist->list;
            iterat_vlist->list = new_adjvcell;
            printf("Added edge from %i to %i\n", iterat_vlist->index_vertex, v2);
        }
        if(iterat_vlist->index_vertex == v2)
        {
            new_adjvcell->index_vertex = v1;
            new_adjvcell->next = iterat_vlist->list;
            iterat_vlist->list = new_adjvcell;
            printf("Added edge from %i to %i\n", iterat_vlist->index_vertex, v1);
        }
        iterat_vlist = iterat_vlist->next;
    }
    printf("AddEdge() finished\n\n");
    return g;
}
graph* ReadGraph(graph *g, FILE *f)
{
    int i, x, y;
    fscanf(f, "%i %i", &g->nv, &g->ne);
    printf("Number of vertices read: %i\n", g->nv);
    printf("Number of edges read: %i\n", g->ne);
    for(i=1; i<=g->nv; i++)
    {
        fscanf(f, "%i", &x);
        g = AddVertex(g, x);
    }
    for(i=1; i<=g->ne; i++)
    {
        fscanf(f, "%i %i", &x, &y);
        printf("Edge read: %i, %i\n", x, y);
        g = AddEdge(g, x, y);
    }
    fclose(f);
    return g;
}

The main function

int main()
{
    graph *g1;
    FILE *f1;
    g1 = (graph *)malloc(sizeof(graph));
    g1->head = NULL;
    f1 = fopen("graph1.txt", "r");
    g1 = ReadGraph(g1, f1);
    return 0;
}

The content of graph1. txt file

4 3
9 17 103 5002
9 17
17 103
103 5002

Solution

On the AddEdge function, you have two if statements

    if(iterat_vlist->index_vertex == v1)
    {
        new_adjvcell = (struct adjvertexlist *)malloc(sizeof(struct adjvertexlist));
        new_adjvcell->index_vertex = v2;
        new_adjvcell->next = iterat_vlist->list;
        iterat_vlist->list = new_adjvcell;
        printf("Added edge from %i to %i\n", iterat_vlist->index_vertex, v2);
    }
    if(iterat_vlist->index_vertex == v2)
    {
        new_adjvcell->index_vertex = v1;
        new_adjvcell->next = iterat_vlist->list;
        iterat_vlist->list = new_adjvcell;
        printf("Added edge from %i to %i\n", iterat_vlist->index_vertex, v1);
    }

In this context new_adjvcell has garbage data, because it's never initialised. If iterat_vlist->index_vertex == v1 then everything works correctly because you called malloc on it, however if index_vertex == v2 you use new_adjvcell it without calling malloc on it first, like the previous if. I found it using a debugger, which promptly showed me the crashing line.

I didn't check if the algorithm is correct though.

Answered By - Henrique Jung

Answer Checked By - Gilberto Lyons (PHPFixing Admin)