An adjacency list is a way of representing the edges in a graph by having an array of numVertices length, each of which contains a linked list of all the vertices it is connected to.

## Data Structures

```typedef int bool;
typedef int vertex;

typedef struct edge *Edge;
typedef struct graph *Graph;
typedef struct node *Node;
typedef struct list *List;

struct edge {
vertex to;
vertex from;
};

struct graph {
int numVertices;
int numEdges;
};

struct node {
vertex to;
Node next;
};

struct list {
Node next;
int numEdges;
vertex vertexNumber;
};
```

## Create Graph

```Graph createGraph (int numVertices) {

Graph newGraph = NULL;

// If there are negative vertices we cannot create the graph
// So we return the null graph

if (numVertices < 0) {
printf ("createGraph: Invalid number of vertices\n");
} else {

// Malloc space for the graph
// Checking that it returned correctly
newGraph = malloc(sizeof(struct graph));

// If there isn't enough memory
// We progress no further and return NULL

if (newGraph == NULL) {
printf ("createGraph: Out of memory\n");
} else {
newGraph->numVertices = numVertices;
newGraph->numEdges--;

int i;
for (i = 0; i < numVertices; i++) {
}
}

}

return newGraph;

}
```

## Delete a Graph

```void deleteGraph (Graph g) {

// If the graph is null we do nothing
if (g != NULL) {

int i;

// Free each row of the node
Node current;

Node next = NULL;
for (i = 0; i < g->numVertices; i++) {
while (current != NULL) {
next = current->next;
free(current);
current = current->next;
}
}

// Free the initially allocated column

// Free the graph itself
free(g);
}

}
```

## Create the Other Data Structures

```List createList (int vertexNumber) {

List newList = malloc(sizeof(struct list));
newList->next = NULL;
newList->numEdges = 0;
newList->vertexNumber = vertexNumber;

return newList;

}

Node createNode (int vertex) {

Node newNode = malloc(sizeof(struct node));
newNode->next = NULL;
newNode->to = vertex;

return newNode;

}

Edge createEdge() {

Edge newEdge = malloc(sizeof(struct edge))
assert (e != NULL);

newEdge->from = 0;
newEdge->to = 0;

return newEdge;

}

void newEdge (Edge e, int vertex1, int vertex2) {

e->to = vertex1;
e->from = vertex2;

}
```

## Delete Other Data Structures

```void deleteEdge (Edge e) {

if (e != NULL) {
free(e);
}

}
```

## Edge Functions

### Insert an Edge into the Graph

```void insertEdge (Graph g, Edge e) {

if (g == NULL) {
printf ("insertEdge: Graph is null\n");
} else {

// Increment the number of edges between the two vertices
// (assuming they're valid)
if ((isValidEdge(g, e)) && (!isEdge(g,e))) {

g->numEdges++;

}
}

}
```

### Check If an Edge Exists

```bool isEdge (Graph g, Edge e) {

bool edgeExists = FALSE;

if (g == NULL) {
printf ("isEdge: Graph is null\n");
edgeExists = ERROR;
} else {

// If the edge exists
// Have to start at next
// As the first item contains no data as it is list
while ((!edgeExists) && (current != NULL)) {
if (current->to == e->to) {
edgeExists = TRUE;
} else {
current = current->next;
}
}

}

return edgeExists;

}
```

### IsValid Edge

```// Checkes if an edge contains two valid vertices

bool isValidEdge (Graph g, Edge e) {

bool isValid = TRUE;

if (g == NULL) {
printf ("isValidEdge: Graph is null\n");
isValid = ERROR;
} else {
if (e->to < 0) {
isValid = FALSE;
// This is '>=' because we can only have 0-(n-1) edges
} else if (e->to >= g->numVertices) {
isValid = FALSE;
} else if (e->from < 0) {
isValid = FALSE;
} else if (e->from >= g->numVertices) {
isValid = FALSE;
}

if (!isValid) {
printf ("isValidEdge: Edge is invalid\n");
}

}

return isValid;

}
```

### Remove an Edge From the Graph

```void removeEdge (Graph g, Edge e) {

if (g == NULL) {
printf ("deleteEdge: Graph is null\n");
} else {

// If it has two valid edges and does exist we can delete it
if ((isValidEdge(g,e)) && (isEdge(g,e))) {
// Have to start at next
// (as the first item contains no data)

// prev must be stored so that we can relink when deleting
Node prev = NULL;

while ((current->to != e->to) && (current != NULL)) {
prev = current;
current = current->next;
}

// If we did find the edge
// (which we should, because we checked the edge exists)
if (current->to == e->to) {
prev->next = current->next;
free(current);
}
}

}

}
```

## Show the Graph

```void showGraph (Graph g) {

if (g == NULL) {
printf ("showGraph: Graph is null\n");
} else {

printf ("V=%d, E=%d\n", g->numVertices, g->numEdges/2);

int x;
int y;

// Go through each edge in increasing order
// And then print them out backwards
// Hence starting with y at the end

Node current = NULL;
for (x = 0; x < g->numVertices; x++) {