Issue with realloc function on dynamic array of linked-lists based graph

Question

currently working on some computer science exercises, when I ran into a weird issue. The idea of the exercise is to create and work on a graph using first dynamic matrices (no issues there) and later an array of linked lists. The exercise asks to create functions and data structures, and specifically the following ones:

• graph data structure and dynamic array of linked lists structure
• create the graph
• add a new node
• add a new edge
• delete the graph
• delete an edge
• print the graph

I've created all the previous functions without any issues, however when I try to

1. create the graph
2. add a few edges
3. add a new node
4. print

the graph seems to lose the memory addresses for the linked lists, which is weird because instead when I do

1. create the graph
2. add a new node
3. add a few edges
4. add another node
5. print

the test works perfectly.

I'm new to the realloc function (first time I work with dynamic arrays and matrices) therefore if I'm missing something I'm sure the fault is mine. That said here you are the functions i'm using (I'll just post the meaningful ones):

typedef struct edg
{
    int key;
    struct edg *next;
} edge;

typedef struct grap
{
    int nv;
    edge **adj;
} graph;

graph *makegraph()
{
    return (graph*)malloc(sizeof(graph));
}

edge *makeedge()
{
    return (edge*)malloc(sizeof(edge));
}

graph *newgraph(int n)
{
    graph *g;
    int i;
    g = makegraph();
    if(g == NULL)
        printf("Error: mem allocation failure");
    else
        {
            g->adj = (edge**)malloc(sizeof(edge*));
                if(g->adj == NULL)
                    {
                        printf("Error: memory allocation failure");
                        free(g);
                        g = NULL;
                    }
                else
                    {
                        g->nv = n;
                            for(i = 0; i < n; i++)
                                g->adj[i] = NULL;
                    }
        }
    return g;
}

graph* addnode(graph *g)
{
    edge **e;
    if(g == NULL)
        return NULL;
    e = (edge **)realloc(g->adj, (g->nv+1)*sizeof(edge*));
    if(e == NULL)
        {
            printf("Errore: failed to relocate memory");
        }
    else
        {
            g->adj = e;
            g->adj[g->nv] = NULL;
            g->nv++;
        }
    return g;
}

void printgraph(graph *g)
{
    if( g == NULL || g->adj == NULL)
        {
            printf("Error: graph not found or NULL");
            return;
        }
    edge *scroll;
    int i;
    for(i = 0; i < g->nv; i++)
        { 
            printf("\nEdges node n %d:   ",i+1);
            if(g->adj[i] != NULL)
                {
                    printf(" %d  ",(g->adj[i])->key);
                    scroll = g->adj[i]->next;
                        while(scroll != NULL)
                            {
                                printf(" %d  ",scroll->key);
                                scroll = scroll->next;
                            }
                }   
        }
}

edge *addedge(graph *g,int vert1,int vert2)
{
    if( g == NULL || g->adj == NULL)
        {
            printf("Error: graph not found or NULL");
            return;
        }
    if(vert1 > g->nv || vert2 > g->nv || vert1 <= 0 || vert2 <= 0)
        {
            printf("Node not found");
            return;
        }
    vert1--;
    edge *tmp,*search;
    tmp = makeedge();
    tmp->next = NULL;
    tmp->key = vert2;
    if (g->adj[vert1] == NULL)
        g->adj[vert1] = tmp;
    else
        {
            search = g->adj[vert1];
            while(search->next != NULL)
                search = search->next;
            search->next = tmp;
        }
}

It all ends up working if I call for something like

newgraph -> addnode -> addegdge (as many as you like) -> addnode -> print

but breaks if instead I do not add a new node before adding the edges.

The main goal of the exercise is to create to libraries which will work with the same main(). I so far, it did manage to achieve the goal with both the matrix based structure and this one, however while the former doesn't seem to display this problem the latter does.

Any help in shedding some light on this inconvenience is rather appreciated!

Answer 1

Without knowing how your graph is build from the client code, it's a bit hard to understand your data structure. On one hand you have a contiguous vector of edges, on the other hand you have something akin to a linked list where edges are connected by next pointers.

You can, of course, maintain a vector of edges and point into it, but a reallocation of this vector with realloc might change the location of the vector, which will render all pointers into the old memory illegal. (Your code is very careful to reallocate to a temporary variable, so that the original is not overwritten, so it seems that you are aware of this behaviour.)

You allow to create the graph with n null edges, but you allocate space for on edge only. This:

g->adj = (edge**)malloc(sizeof(edge*));

should probably be:

g->adj = malloc(n * sizeof(edge*));

When you create the graph, your error allocation is wrong and not consistent with the number of edges in your graph. When you reallocate in addnode, this is fixed, because you have now space for nv edges.

One last thing: Please consider renaming your variables and symbols. You onlyx have edges in your graph, according to your structure, but their number is nv, which is for vertices, I reckon. The addnode function doesn't add a node, it adds a null pointer. I haven't bothered to check what addedge does exactly, but it should probably be a void finction. It's all very confusing.