Problems initializing a Graph based on Array with adjacency lists in C

Question

I've played with Graphs before and I managed it alright with some help from StackOverflow but I never used a structure like the one below. I can't seem to understand what I'm doing wrong here...

#include "stdio.h"
#include "stdlib.h"

#define MaxV 100
#define MaxE 50

typedef struct edge {
    int dest;
    int cost;

    struct edge *next;
} Edge, *Graph[MaxV];

Graph *initGraph() {    
    Graph *g = (Graph*)malloc(sizeof(Edge) * MaxV);

    for(int i = 0; i < MaxV; i++)
        (*g[i])->next = NULL;

    return g;
}

int main(void) {
    Graph *g = initGraph();

    for(int i = 0; i < MaxV; i++) {
        if((*g[i])->next == NULL) printf("[%02d] NULL\n", i);
    }

    return 0;
}

I get a segmentation fault on the first iteration of (*g[i])->next = NULL; and I can't understand why. I've tried countless things but I can't seem to manage the Graph initialization with such structure. Also, is the way I'm declaring and returning a pointer to a Graph done the right way for this structure?

Am I complicating things with lots of pointers in the init function or what?

P.S: Please do not suggest different structure definitions, I cannot changing anything in the one above. That's the real issue. I know how to work with Graphs rolling my own structure, but I need to use the one above.

Have you tried using a debugger? I'm not sure how `g` is being allocated as. — Argote, Feb 04 '11 at 23:58
Yes, that's how I realized it was breaking on the first iteration cause I though it was breaking later, maybe because I hadn't allocated enough memory. But I find GDB confusing and I don't know how to use it properly. — rfgamaral, Feb 05 '11 at 00:09

score 2 · Answer 1 · answered Feb 05 '11 at 00:08

I don't really understand your second typedef of *Graph[MaxV].

What I would do is declare another struct as follows:

typedef struct graph {
    Edge *edges;
} Graph;

Then you can initialize the graph as follows:

Graph *initGraph() {  
    Graph *g = (Graph*)malloc(sizeof(Graph));

    g->edges = (Edge*)malloc(sizeof(Edge) * MaxV);
    for(int i = 0; i < MaxV; i++)
        g->edges[i].next = NULL;

    return g;
}

And printing out the graph is as follows:

for(int i = 0; i < MaxV; i++) {
    if(g->edges[i].next == NULL) printf("[%02d] NULL\n", i);
}

I think you'll find that having an extra struct for the graph will prove to be more sustainable over time too. :)

I cannot change the structure definitions. That's the real issue, I know how to do it without such a structure, but I need this one specifically. — rfgamaral, Feb 05 '11 at 00:11

score 0 · Answer 2 · edited May 23 '17 at 11:43

0

Complete revision of answer given the OP's requirement not to change the typedef in any way.

I would advise changing to this:

void initGraph(Graph g) {
    g[0] = malloc(sizeof(Edge) * MaxV);

    for(int i = 0; i < MaxV; i++)
        g[0][i].next = NULL;
    return;
}

int main(void) {
    Graph g;
    initGraph(g);

    for(int i = 0; i < MaxV; i++) {
        if(g[0][i].next == NULL) printf("[%02d] NULL\n", i);
    }

    free(g[0]);
    return 0;
}

The problem here is the "array of pointers" syndrome. Namely Graph** g is equivalent to Graph *g[10] with the obvious proviso that the outer array size is fixed. That creates problems because you can't return a fixed size array, but you can return a **.

I'm still not sure what the use case for an array of graphs is, but heck, this passes valgrind.

edited May 23 '17 at 11:43

Community

1
1

answered Feb 05 '11 at 00:19

I cannot change it, I need to use it like that. – rfgamaral Feb 05 '11 at 00:20
Ok, I've fixed it. Took me a while to get my head around it, it's late here. – Feb 05 '11 at 01:01
Thank you for the solution but there must be another way, without that `g[0]`, it seems odd. And if it's really `Graph** g` as you said, why can't we just return the pointer to the first element? – rfgamaral Feb 05 '11 at 02:49

rfgamaral · Accepted Answer · 2011-02-05T05:36:46.540

I think I found the solution I was looking for. I used Valgrind as best as I could to test for read/write permissions and there were no errors. Yes there were memory leaks, but that's not the point of this question (I'm aware of those, don't worry).

Here's the whole code to create a simple graph. Would love to hear any problems this implementation might have...

#include "stdio.h"
#include "stdlib.h"

#define MaxV 10
#define MaxE 5

typedef struct edge {
    int dest;
    int cost;

    struct edge *next;
} Edge, *Graph[MaxV];

Graph *initGraph() {
    Graph *g = (Graph*)malloc(sizeof(Graph));

    for(int i = 0; i < MaxV; i++)
        (*g)[i] = NULL;

    return g;
}

int insertEdge(Graph *g, int o, int d, int c) {
    if(!g) return -1;

    Edge *edge = (Edge*)malloc(sizeof(Edge));

    edge->dest = d;
    edge->cost = c;

    edge->next = (*g)[o];
    (*g)[o] = edge;

    return 0;
}

int main(void) {
    Graph *g1 = initGraph();
    Edge *aux = NULL;

    insertEdge(g1, 0, 1, 2);
    insertEdge(g1, 0, 2, 3);
    insertEdge(g1, 1, 4, 5);
    insertEdge(g1, 2, 4, 1);
    insertEdge(g1, 4, 8, 6);

    for(int i = 0; i < MaxV; i++) {
        printf("[%02d]\n", i);

        for(aux = (*g1)[i]; aux != NULL; aux = aux->next)
            printf(" [%d] » [%d] (%d)\n", i, aux->dest, aux->cost);
    }

    return 0;
}

Problems initializing a Graph based on Array with adjacency lists in C

3 Answers3