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

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

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.

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.

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