Graph implementation

This is a discussion on Graph implementation within the C Programming forums, part of the General Programming Boards category; I'm trying to create a directed random graph and using the code in Robert Sedgewick's Algorithms book. Whilst the code ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    6

    Graph implementation

    I'm trying to create a directed random graph and using the code in Robert Sedgewick's Algorithms book. Whilst the code is working I am having trouble understanding how to use adjacency lists in particular the GraphinsertE function below. I have an idea in my head as to how it is working but when I try to follow the code I get confused with the pointer to pointers. I am trying to understand what happens with just 3 nodes A,B and C and what happens when I insert an edge between A and B, and then A and C. If anyone could talk me through this it would really help. Here is the code. I'm new to the board so hope I have done this right.

    Code:
    typedef struct { int v; int w; } Edge;
    typedef struct graph *Graph;
    typedef struct node *link;
    
    struct node { int v; link next; };
    struct graph { int V; int E; link *adj; };
    
    link NEW(int v, link next)
    {
      link x = malloc(sizeof *x);
      assert(x != NULL); 
      x->v = v; x->next = next;
      return x;
    }
    
    Graph GRAPHinit(int V)
    {
      int v;
      Graph G = malloc(sizeof *G);
      G->V = V; G->E = 0;
      G->adj = malloc(V*sizeof(link));
      for (v = 0; v < V; v++) G->adj[v] = NULL;
      return G;
    }
    
    void GRAPHinsertE(Graph G, Edge e)
    {
      int v = e.v, w = e.w;
      G->adj[v] = NEW(w, G->adj[v]);
      G->E++;
    }
    
    Edge EDGE(int a1, int a2)
    {
      Edge r;
      r.v = a1;
      r.w = a2;
      return r;
    }
    The bit I then need to understand is how
    Code:
    GRAPHinsertE(G,EDGE(i,j));
    would be working.

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Well, not sure what you mean exactly. I think that the reason you are confused is all the stupid typedefs making function arguments unreadable. (IMO)

    The function itself just takes a graph pointer and an edge between i and j. The graph seems to have some adjacency array in which each element is some other array (or list?.. not sure what NEW does) that holds all the nodes that share an edge with the respective node number.

    For example adj[i] is a list(or array) of all nodes you can go to from i.
    The function simply adds j to this list and increases the edge count.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    6
    Hi claudiuu, thankyou for your reply. I know the typedefs make it confusing but I was trying to stick with the code of Sedgewick.
    I understand what the code is doing, but it is how it is doing it that confuses me. I guess I will just need to read more about linked lists, until it becomes obvious.

    cheers

  4. #4
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    I completely missed the NEW function when reading the code the first time.

    What the insert_edge function seems to be doing is inserting a new node at the beginning of the list.

    Basically your data looks like this:

    v[0] ->.... ->.....->
    v[1] ->.....->....->
    .....
    v[i] -> .... -> ...->

    You have an array vertically and each array member is the head of the list. NEW seems to insert a new node in that list before a given node LINK. In the insert_edge function LINK seems to be the actual head of the list G->adj[i] (which is weird, because NEW seems to be working incorrectly).

    I think you can re-write new to make more sense.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Also, note that this is a pretty poor implementation complexity wise. I think a better way would be to have some sort of hash table so you can access all members of the data structure in constant time rather than iterate a whole list, which will take O(n).
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Posts
    6
    Thankyou, I think the bit you say is weird is the bit that is confusing me. I will look again as I may have made a mistake.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Posts
    6
    Ok I've been looking at this for a while and have now confused myself on something else:
    Graph G is a pointer to a structure graph. The graph structure contains a member adj where adj is a pointer to link, with link being a pointer to node. Now the function NEW returns a link. If this is all correct, how does the following code make sense
    Code:
      G->adj[v] = NEW(w, G->adj[v]);
    Is this not assigning adj[v] a link when it is expecting a pointer to link?
    Sorry if I'm speaking rubbish but if you can tell me where my interpretation is going wrong it would be appreciated.

  8. #8
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    If you look at the very confusing typedefs which I hate so much:

    Code:
    typedef struct node *link;
    link is already a struct node*.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Posts
    6
    I may be having a very basic misunderstanding but I still do not get how if adj[v] is a pointer to link and the function NEW returns a link, why is
    Code:
    G->adj[v] = New(w, G ->adj[v]);
    ok. I am new to C so am guessing I am probably not understanding something simple with regards to pointers.

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    adj[v] is not a pointer to a link. It is a link which is a pointer to a node.
    NEW returns a link, which again, is a pointer to a node.

    All this confusion stems from the fact that you are using a ton of typedefs and making your code unreadable to the point where you don't know what types are what. Get rid of those and just type struct <struct_name>* wherever you have a pointer to a struct.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Posts
    6
    Thankyou for your time claudiu. I now realise what you mean and understand why I should alter the code. I was trying to follow the code from Sedgewick but was completely misinterpreting how typedef was working. cheers

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ graph ploting
    By ivpavic in forum C++ Programming
    Replies: 1
    Last Post: 05-26-2010, 01:06 PM
  2. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 08:55 PM
  3. Help w/ graph as adjacency matrix
    By ac251404 in forum C++ Programming
    Replies: 4
    Last Post: 05-09-2006, 11:25 PM
  4. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 04:48 AM

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