CODEWITHSUNDEEP
cpointersgraphinitializationstructure
rfgamaral
rfgamaral

Reputation: 16842

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

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.

Upvotes: 1

Views: 1506

Answers (3)

rfgamaral
rfgamaral

Reputation: 16842

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;
}

Upvotes: 0

user257111
user257111

Reputation:

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.

Upvotes: 0

James Bedford
James Bedford

Reputation: 28962

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. :)

Upvotes: 2

Related Questions