add node function changes index during function call in c

Question

I am trying to create an adjacency list for an undirected, weighted graph so I can run Dijkstra's and Kruskal's algorithms on and I'm running into an interesting problem. Whenever I try to add a second edge to a list index, it seems like it changes the list index to the new edge during the function call, erasing the previous edge list index was pointing to. (I think this person was having a similar problem but there isn't an answer for it: How to create an adjacency list of a directed graph in C?). Here is the code:

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

// Edge node
struct edge{
    int v1;                 // vertex it's coming from
    int v2;                 // vertex it's going to
    int weight;             // weight of edge
    struct edge *next;
}

const int MAX = 9;

void createAdjList(struct edge **list);
struct createEdge(int v1, int v2, int weight);
void addEdge(struct edge **list, struct edge newEdge);

int main(){
    struct edge *list = malloc(MAX * sizeof(struct edge));
    createAdjList(&list);
    ...
    return 0;
}
// creates the adjacency list
void createAdjList(struct edge **list){
    for(int i = 0; i < MAX; ++i)
        list[i] = 0;

    // first edge from vertex 0 to 1
    addEdge(list, createEdge(0, 1, 22));
    addEdge(list, createEdge(1, 0, 22));

// this is where the problem happens, when i call addEdge(list, createEdge(0, 2, 9)); 
// as soon as it enters addEdge, list[0] goes from pointing to the 0-1 edge to already
// pointing to this second edge, 0 to 2

    // second edge from vertex 0 to 2
    addEdge(list, createEdge(0, 2, 9));
    addEdge(list, createEdge(2, 0, 9));

    ...
}
// creates and returns an edge node
struct createEdge(int v1, int v2, int weight){
    struct edge newEdge;
    newEdge.v1 = v1;
    newEdge.v2 = v2;
    newEdge.weight = weight;
    newEdge.next = 0;
    return newEdge;
}
// adds the edge to the adjacency list
void addEdge(struct edge **list, struct edge newEdge){
// at this point, after the addEdge(list, createEdge(0, 2, 9)); call, list[0] is now 
// pointing to this new edge and Edge(0, 1, 22) is gone
    for(int i = 0; i < MAX; ++i){
        // if edge vertex equals index i
        if(newEdge.v1 == i){
            // if list index is empty, place it at head and return
            if(list[i] == 0){
                list[i] = &newEdge;
                return;
            // else traverse to the end, place it and return
            }else{
                struct edge* curr = list[i];
                while(curr->next != 0)
                    curr = curr->next;
                curr->next = &newEdge;
                return;
            }
        }
    }
}

thanks

Please post the Minimal, Complete, and Verifiable example that shows the problem. How can code in main call functions that have not been declared? And no library headers are included. Otherwise, reverse the sequence of the functions in the source code, so each has already been defined when it is called. Enable compiler warnings. Otherwise we have to ask stupid questions like "did you #include the library header?", and so on. — Weather Vane
– Weather Vane, Commented Feb 14, 2018 at 21:23
The createEdge function returns an instance of the structure. That structure is passed by value to addEdge. The newEdge parameter is a local copy of the structure. That local copy ceases to exist as soon as addEdge returns. So list[i] = &newEdge is not valid, it makes list[i] point to something that doesn't exist after addEdge returns. — user3386109
– user3386109, Commented Feb 14, 2018 at 21:26

Stack Exchange Broke The Law · Accepted Answer · 2018-02-14 22:17:44Z

0

list[i] = &newEdge;

Here newEdge is a function parameter, which is the same as a local variable in that it is destroyed when the function addEdge returns.

So after addEdge returns, the list has a pointer that points to where newEdge used to be. Chances are the values of the edge are still there, and chances are that memory will be reused for something else the next time you call a function. In your case it happened to be reused to hold the next edge.

The solution would be to malloc some space to hold the edge in the list. Memory allocated with malloc can't be reused until you free it.

answered Feb 14, 2018 at 22:17

Stack Exchange Broke The Law

59.2k7 gold badges57 silver badges103 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

add node function changes index during function call in c

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related