Understanding Structure Definition and Implementation

In this typedef declaration:

typedef struct graph *Graph;

there is introduces the incomplete structure type struct graph and for the pointer to objects of the structure type struct graph * there is introduced the alias (typedef) name Graph.

That is you may declare a variable of the pointer type like:

struct graph *p;

or:

Graph p;

So this function declaration:

Graph GRAPHinit(int);

is equivalent to:

struct graph * GRAPHinit(int);

Pay attention to that the type struct graph is incomplete type. So you may not define an object of the structure type until you will provide the structure definition. On the other hand, pointers themselves are always complete types. So you may define an object of the pointer type struct graph * or that is the same Graph.

Where is such a typedef declaration is used?

For example imagine that you have a header file where there is the function declaration:

Graph GRAPHinit(int);

To make the declaration valid you need to sat the compiler what the name Graph means.

So before the function declaration in the header you will write:

typedef struct graph *Graph;
Graph GRAPHinit(int);

It is enough to make this header syntactically and semantically correct.

The complete structure declaration can be a very big as for example:

struct graph
{
   T1 data_member_1;
   //...
   Tn data_member_n;
};

typedef struct graph *Graph;

But to declare the function in the header above this complete structure declaration is not required. So in the header there is used only this typedef:

typedef struct graph *Graph;

that introduces all required types to make the function declaration

Graph GRAPHinit(int);

correct.

To make this typedef declaration:

typedef struct graph *Graph;

more clear consider this typedef declaration

typedef int *Ptr;

It introduces the pointer typedef name Ptr as an alias for the pointer type int *. But the type specifier int is a fundamental type. It is known for the compiler. As for the type specifier struct graph then it is a user-defined type specifier. So this typedef declaration:

typedef struct graph *Graph;

introduces the new (incomplete) type specifier struct graph and also an alias for the pointer type struct graph * named like Graph.

This code

  typedef struct graph *Graph;

is to be read as

  typedef struct graph* Graph;

which means, Graph is a pointer of type struct graph. The second statement then can be interpreted as

 struct graph * GRAPHinit(int);

which looks very much like a forward declaration of a function, accepting an int and returning a pointer to struct graph.

Note: While this usage is perfectly legal, it's confusing at best. never hide pointers behind a typedef, rather keep the type simple. Use it like

typedef struct graph myGraph;
myGraph* GRAPHinit(int);