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 10:36 PM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    23,820
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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