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.

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.

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

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.

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

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.

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.

If you look at the very confusing typedefs which I hate so much:

Code:

typedef struct node *link;

link is already a struct node*.

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.

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.

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