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;
   int **adjMatrix;
};

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;
 
         newGraph->adjMatrix = calloc(numVertices,sizeof(int*));
         assert (newGraph->adjMatrix != NULL);
 
         int i;
         for (i = 0; i < numVertices; i++) {
            newGraph->adjMatrix[i] = calloc(numVertices,sizeof(int));
            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(toDelete->adjMatrix[i]);
      }
      // Free the intially allocated column
      free(toDelete->adjMatrix);
      // 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->adjMatrix[e->to][e->from] += 1;
         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
      if (g->adjMatrix[e->to][e->from]) {
         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->adjMatrix[e->to][e->from] = 0;
         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--) {
            if (g->adjMatrix[x][y]) {
               printf ("%d-%d ", x, y);
            }
         }
         printf ("\n");
      }
   }
 
}