Issue with insertion in an adjacency list

Question

I'm trying to insert nodes in a non-directed graph, at the very first insertion the code does very well, but at the second time the code doesn't work anymore and I don't understand why. Can someone help me with this issue?

I already tried to compile in Dev-c++ and sometimes the code run and others not, but in CodeBlocks and CMD(Windows) just doesn't work.

Here is my code:

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

typedef struct tedge {
    int vdest; //destiny vertex
    double weight;
    struct tedge* next;
}TypeEdge;

typedef TypeEdge* TypePointer;

typedef struct {
    TypePointer* listAdj;
    int numVertex;
    int numEdges;
}TypeGraph;

//initialize the graph
bool initializeGraph(int nv, TypeGraph* graph) {
    if(nv <= 0) return false;

    int i;

    if(graph->listAdj = (TypePointer*)malloc(nv*sizeof(TypePointer))) {

        graph->numEdges = 0;
        graph->numVertex = nv;

        for(i = 0; i < nv; i++)
            graph->listAdj[i] = NULL;

        return true;
    }

    return false;
}


//insertion
bool insertEdge(int v1, int v2, double weight, TypeGraph *graph) {
    if(!graph) return false;
    if((v1 < 0) || (v1 >= graph->numVertex)) return false;
    if((v2 < 0) || (v2 >= graph->numVertex)) return false;

    TypePointer new = (TypePointer)malloc(sizeof(TypePointer));
    new->vdest = v2;
    new->weight = weight;
    new->next = graph->listAdj[v1];
    graph->listAdj[v1] = new;

    TypePointer simetry = (TypePointer)malloc(sizeof(TypePointer));
    simetry->vdest = v1;
    simetry->weight = weight;
    simetry->next = graph->listAdj[v2];
    graph->listAdj[v2] = simetry;

    graph->numEdges++;

    return true;
}

void printGraph(TypeGraph* graph) {
    int i;

    for(i = 0; i < graph->numVertex; i++) {
        TypePointer actual = graph->listAdj[i];
        printf("v %i: ", i);

        while(actual != NULL) {
            printf("(adj %i, weight %g); ", actual->vdest, actual->weight);
            actual = actual->next;
        }

        printf("\n");
    }
}

int main() {
    TypeGraph graph;


    initializeGraph(9, &graph);

    insertEdge(0, 1, 8, &graph);
    insertEdge(0, 3, 4, &graph);
    insertEdge(0, 6, 11, &graph);
    insertEdge(1, 2, 7, &graph);
    insertEdge(1, 4, 2, &graph);
    insertEdge(1, 8, 4, &graph);
    insertEdge(2, 5, 9, &graph);
    insertEdge(2, 8, 14, &graph);
    insertEdge(3, 6, 8, &graph);
    insertEdge(4, 6, 7, &graph);
    insertEdge(5, 8, 10, &graph);
    insertEdge(6, 7, 1, &graph);
    insertEdge(7, 8, 2, &graph);

    printGraph(&graph);

    return 0;
}

If someone can help me with this, I accept any sugestion. Thanks.

Do not hide pointer nature behind a typedef, as your TypePointer does. Doing so causes more problems than it solves. — John Bollinger
– John Bollinger, Commented Mar 29, 2019 at 18:36
Also do not cast the return value of malloc() in C. (But also do not suppose you're writing in C if you compile with a C++ compiler.) — John Bollinger
– John Bollinger, Commented Mar 29, 2019 at 18:39

Weather Vane · Accepted Answer · 2019-03-29 18:45:51Z

See the danger in the typedef of pointers with

TypePointer new = (TypePointer)malloc(sizeof(TypePointer));
new->vdest = v2;
new->weight = weight;
new->next = graph->listAdj[v1];

which only allocates enough memory for the pointer. I would suggest

TypePointer new = malloc(sizeof(*new));

Also here

TypePointer simetry = (TypePointer)malloc(sizeof(TypePointer));

which should be

TypePointer simetry = malloc(sizeof(*simetry));

Having made those corrections, the program reports:

v 0: (adj 6, weight 11); (adj 3, weight 4); (adj 1, weight 8);
v 1: (adj 8, weight 4); (adj 4, weight 2); (adj 2, weight 7); (adj 0, weight 8);
v 2: (adj 8, weight 14); (adj 5, weight 9); (adj 1, weight 7);
v 3: (adj 6, weight 8); (adj 0, weight 4);
v 4: (adj 6, weight 7); (adj 1, weight 2);
v 5: (adj 8, weight 10); (adj 2, weight 9);
v 6: (adj 7, weight 1); (adj 4, weight 7); (adj 3, weight 8); (adj 0, weight 11);
v 7: (adj 8, weight 2); (adj 6, weight 1);
v 8: (adj 7, weight 2); (adj 5, weight 10); (adj 2, weight 14); (adj 1, weight 4);

I notice too that the functions return a status, which is ignored, though that did not contribute to the crash here.

Collectives™ on Stack Overflow

Issue with insertion in an adjacency list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related