2

I am working on a Graph problem, so my program has an initialization which sets all connection using an adjacencyList. Currently encountering a really weird bug and was wondering if anyone could give some insights as to what may be happening.

So I have a function that sets a connection

void setConnection(Graph g, int sVertex, int eVertex){
    ListNode *newNode = (ListNode *) malloc(sizeof(ListNode*));
    newNode->vertex = eVertex;

    ListNode *temp = g.list[sVertex-1];

    if (temp == NULL){ // Corresponding list is empty
        newNode->next = NULL;
        g.list[sVertex-1] = newNode;
    }
    else{ // Insert new node to the front
        newNode->next = temp; // set newNode's next to current 'head'
        g.list[sVertex-1] = newNode; // Replace head as newNode
    }


    //printf("Connection set from %d to %d\n", sVertex, g.list[sVertex-1]->vertex);
    return;
}

After initialization, I usually attempt to print out the adjacencyList to check if the logic is correct. The function is as follow:

void printGraphList(Graph g){
    int i;
    ListNode* temp;

    for(i=0;i<g.V;i++)
    {
        printf("|");
        printf("%d:\t",i+1);
        temp = g.list[i];
        while(temp != NULL){
            printf("%d -> ",temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

So here's the weird part, the code works fine most of the time, but occasionally crashes randomly when printing the adjancencyList. I debugged it down to

printf("%d -> ", temp->vertex);

For some reason, there are cases where the first node inserted does not have its ->next set to NULL properly. hence in the list traversal, it does not exit properly, and as such the temp->vertex is unobtainable, therefore causing the crash.

I have also debugged setConnection to ensure the links are properly set, like the actual pointer values themselves T.T

Below is an example of a working run, and a problem run. I printed an & before printing the vertex and and @ after. As shown in the image, for vertex 7, it should be linked to only vertex 9 and 10, but in the problem run, it looks like the node for 9's next is not set to NULL properly, causing the program to crash in attempt to get node 9's->next->vertex as it does not exist...

As mentioned before, this happens once every 3 to 4 runs and i have no clue whats causing this inconsistency. Any help is appreciated! Thanks in advance.

Problem Example Working Example

KerubinGema Yuen
  • 31
  • 5
  • Are you sure that `g` is being initialized to NULL for all nodes at init? – Beshambher Chaukhwan Apr 09 '21 at 04:43
  • @BeshambherChaukhwan Yup, in my main, I have a for loop that sets each g.list[i] = NULL – KerubinGema Yuen Apr 09 '21 at 04:45
  • 2
    Please provide a [complete minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example). That is, the smallest amount of complete code that anyone can run exactly as shown to repro the problem. – kaylum Apr 09 '21 at 04:45
  • 2
    `malloc(sizeof(ListNode*))` -> `malloc(sizeof(ListNode))` – kaylum Apr 09 '21 at 04:47
  • @kaylum Understood, will try to edit it to replicate the problem. *Edit* Omg i think the malloc solution was the problem. Thanks! – KerubinGema Yuen Apr 09 '21 at 04:48
  • 4
    Tip: Using the wrong type in malloc is a common error. To avoid that use this form: `ListNode *newNode = malloc(sizeof(*newNode));`. That is, use the variable itself for the `sizeof` to guarantee that it matches the exact type of the pointer. – kaylum Apr 09 '21 at 04:50
  • @kaylum Thanks, will definitely be using that tip. Just curious, is it by luck that my program managed to run some of the times? Where the memory just happened to have empty space and there was no conflicts? – KerubinGema Yuen Apr 09 '21 at 04:52
  • 1
    That's called Undefined Behaviour in C. In practice it means the program may crash, or may get garbage values or may even appear to "work". But the behaviour may change at any time so the program is essentially unstable. Having it crash is actually the best result during development as hidden problems waiting to explode are the worst. See: [Undefined, unspecified and implementation-defined behavior](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior) – kaylum Apr 09 '21 at 05:10

0 Answers0