COMP1927 - Adjacency Matrix

An adjacency matrix is a method of representing the edges in a graph through an n*n array. If an edge exists between [i][j] then array[i][j] will be a 1, else 0.

## Data Structures

```typedef int bool;
typedef int vertex;
typedef struct edge *Edge;
typedef struct graph *Graph;

struct edge {
vertex to;
vertex from;
};

struct graph {
int numVertices;
int numEdges;
};
```

## Create a 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 = 0;

assert (newGraph->adjMatrix != NULL);

int i;
for (i = 0; i < numVertices; i++) {
assert (newGraph->adjMatrix[i] != NULL);
}
}
}

return newGraph;

}
```

## Delete a Graph

```void deleteGraph (Graph toDelete) {

// If the graph is null we do nothing
if (toDelete != NULL) {
int i;
// Free each row of the matrix
for (i = 0; i < toDelete->numVertices; i++) {
}
// Free the intially allocated column
// Free the graph itself
free(toDelete);
}

}
```

## Create an Edge

```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 an Edge

```void deleteEdge (Edge e) {

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

}
```

## Edge Functions

### Insert an Edge

```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++;
}
}

}
```

### Is Edge

```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
edgeExists = TRUE;
}
}

return edgeExists;
}
```

### Check if an Edge is Valid

```// Checks 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 with 7 nodes
// We can only have an edge from 0-6
} 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

```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))) {
g->numEdges--;
}
}

}
```

## Show a 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
for (x = 0; x < g->numVertices; x++) {
for (y = g->numVertices-1; y >= 0; y--) {