Graphs and Pointers on adjacency list Array

This is a discussion on Graphs and Pointers on adjacency list Array within the C Programming forums, part of the General Programming Boards category; I have the following structure for Graphs: Code: #define MaxV 100 #define MaxE 50 typedef struct edge { int dest; ...

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    158

    Graphs and Pointers on adjacency list Array

    I have the following structure for Graphs:

    Code:
    #define MaxV 100
    #define MaxE 50
    
    typedef struct edge {
        int dest;
        int cost;
    
        struct edge *next;
    } Edge, *Graph[MaxV];
    This cannot be changed, it must remain exactly like it is above.

    After a few hours I came up with the following code:

    Code:
    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;
    }
    This seems to be working and Valgrind didn't report any reading/writing memory errors, I'm assuming I did everything alright but I need a second opinion.

    Also, I couldn't find a different way other than (*g)[index] to solve that specific graph typedef, which cannot be changed. Is this the only way? Isn't there a way to simplify this?
    Last edited by Nazgulled; 02-04-2011 at 11:36 PM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,265
    Quote Originally Posted by Nazgulled
    Also, I couldn't find a different way other than (*g)[index] to solve that specific graph typedef, which cannot be changed. Is this the only way? Isn't there a way to simplify this?
    Graph is a typedef for an array of MaxV pointers to struct edge objects. Since arrays are converted to pointers to their first elements when passed as an argument, you can avoid passing a pointer to the array, and just pass a pointer to the array's first element, e.g.,
    Code:
    void initGraph(Graph g) {
        for (int i = 0; i < MaxV; i++)
            g[i] = NULL;
    }
    
    int main(void) {
        Graph g1;
        initGraph(g1);
        /* ... */
    }
    If you do want to use malloc, then remember to use free.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Thank you, that's it.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21