COMP1927 - Adjacency List

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;
  List *adjList;  
};
 
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--;
 
         newGraph->adjList = malloc(numVertices * sizeof(List));
         assert (newGraph->adjList != NULL);
 
         int i;
         for (i = 0; i < numVertices; i++) {
             newGraph->adjList[i] = createHead(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++) {      
         current = g->adjList[i]->next;         
         while (current != NULL) {
              next = current->next;
              free(current);
              current = current->next;
         }
      }
 
      // Free the initially allocated column
      free(g->adjList);
 
      // 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))) {   
 
         Node temp = g->adjList[e->from]->next;
         g->adjList[e->from]->next = createList(e->to);   
         g->adjList[e->from]->next->next = temp;
         g->adjList[e->from]->numEdges++;
         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
     Node current = g->adjList[e->from]->next;
     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)
        Node current = g->adjList[e->from]->next;
 
        // 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);
          }
           g->adjList[e->from]->numEdges--;
      }
 
   }
 
}

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++) {
        current = g->adjList[x]->next;
         for (y = 0; y < g->adjList[x]->numEdges; y++)  {
            printf ("%d-%d ", x, current->to);
            current = current->next;  
         }
         printf ("\n");
      }
 
   }
 
}