Adjacency List Representation of Graph

LinkedList_Generic.h

struct LinkedList_Generic
{
 struct ListNode_Generic*start;
 int elementSize;
 /*
  elementSize, will store the size of each element. 
  The element size is important, because generics in C are limited to void pointers, 
  in order to let the compiler know the amount of memory needed by malloc/memcpy. 
  This information should always be supplied dynamically. The caller should use sizeof(int) rather than 4.
 */
};
struct ListNode_Generic
{
 void *data;
 struct ListNode_Generic*next;
};
struct LinkedList_Generic *makeAndInitialiseLinkedList();
struct ListNode_Generic *makeAndInitialiseListNode(struct LinkedList_Generic *list,void*element);
void addElement(struct LinkedList_Generic*list,struct ListNode_Generic*element);
void removeElement(struct LinkedList_Generic*list,struct ListNode_Generic*node);
struct ListNode_Generic*getNodeReferenceWithGivenData(struct LinkedList_Generic*list,void*data);

LinkedList_Generic.c

#include<stdlib.h>
#include<string.h>
#include"LinkedList_Generic.h"

struct LinkedList_Generic *makeAndInitialiseLinkedList(int elementSize)
{
 struct LinkedList_Generic *list;
 list=(struct LinkedList_Generic*)malloc(sizeof(struct LinkedList_Generic));
 list->start=NULL;
 list->elementSize=elementSize;
 return list;
}
struct ListNode_Generic *makeAndInitialiseListNode(struct LinkedList_Generic *list,void*element)
{
 struct ListNode_Generic*listNode;
 listNode=(struct ListNode_Generic*)malloc(sizeof(struct ListNode_Generic));
 listNode->data=element;
 //listNode->data=malloc(sizeof(list->elementSize));
 //memcpy(listNode->data,element,list->elementSize);
 listNode->next=NULL;
 return listNode;
}
void addElement(struct LinkedList_Generic*list,struct ListNode_Generic*element)
{
 struct ListNode_Generic*ptr,*prev;
 if((list->start)==NULL)
  (list->start)=element;
 else
 {
  for(ptr=(list->start);ptr;prev=ptr,ptr=ptr->next);
  (prev->next)=element;
 }
}
void removeElement(struct LinkedList_Generic*list,struct ListNode_Generic*node)
{
 struct ListNode_Generic*ptr,*prev;
 for(ptr=(list->start),prev=NULL;ptr && (ptr)!=node;prev=ptr,ptr=ptr->next);
 if(ptr)
 {
  if(prev!=NULL)
  {
   prev->next=ptr->next;
   if(ptr)
   {
    free(ptr);
   }
  }
  else if(prev==NULL && ptr!=NULL) // means the element that we need to delete is the start of the list.
  {
   prev=list->start;
   (list->start)=((list->start)->next);
   if(prev)
   {
    free(prev);
   }
  }
 }
}
struct ListNode_Generic*getNodeReferenceWithGivenData(struct LinkedList_Generic*list,void*data)
{
 struct ListNode_Generic*node;
 for(node=list->start;node;node=node->next)
 {
  if((node->data)==data)
   return node;
 }
}

Graph_AdjacencyList.h

#include"LinkedList_Generic.h"
struct Graph_AdjacencyList
{
 struct LinkedList_Generic *vertexList;
 int numberOfVertices;
};
struct Vertex_AdjacencyList
{
 int id;
 struct LinkedList_Generic *adjacencyList;
};
struct Graph_AdjacencyList*makeAndInitialiseGraph();
void addVertex(struct Graph_AdjacencyList*graph,struct Vertex_AdjacencyList*vertex);
int getVertexId(struct ListNode_Generic*node);
void removeVertex(struct Graph_AdjacencyList*graph,int vertexNumber);
void addEdge(struct Graph_AdjacencyList*graph,int sourceVertexNumber,int destinationVertexNumber);
void removeEdge(struct Graph_AdjacencyList *graph,int sourceVertexNumber,int destinationVertexNumber);
struct Vertex_AdjacencyList *makeVertex();
void printGraph_AdjacencyList(struct Graph_AdjacencyList*graph);

Graph_AdjacencyList.c

/*
 This representation of graph is the Adjacency List representation.
 Corresponding to each vertex of the graph we maintain a list of vertices that are connected to that vertex.
 for maintaining the vertex list (adjacency List) corresponding to each vertex, we maintain a Generic List.
 this generic list is defined in LinkedList_Generic.c
 
 this adjacencyList corresponding to each vertex will just store the references of vertex (reference of c, don't get confused with the reference variables of c++)
 
 this storing of reference will have the following advantage :
  Suppose you need to modify any of the data for a specific vertex, then you just need to modify the data correnponding to that vertex in the vertex list.
  you dont need to modify each and every node where this vertex may apper in the adjacencyList of any vertex.
*/

#include"Graph_AdjacencyList.h"
#include<stdlib.h>
#include<stdio.h>
struct Graph_AdjacencyList*makeAndInitialiseGraph()
{
 struct Graph_AdjacencyList*graph;
 graph=(struct Graph_AdjacencyList*)malloc(sizeof(struct Graph_AdjacencyList));
 graph->numberOfVertices=0;
 graph->vertexList=makeAndInitialiseLinkedList(sizeof(struct Vertex_AdjacencyList));
 return graph;
}
struct Vertex_AdjacencyList *makeVertex()
{
 static int vertexNumber=0;
 struct Vertex_AdjacencyList*vertex;
 vertex=(struct Vertex_AdjacencyList*)malloc(sizeof(struct Vertex_AdjacencyList));
 (vertex->id)=vertexNumber++;
 vertex->adjacencyList=makeAndInitialiseLinkedList(sizeof(struct Vertex_AdjacencyList*));
 return vertex;
}
struct Vertex_AdjacencyList*getVertexReference(struct Graph_AdjacencyList*graph,int n)
{
 struct Vertex_AdjacencyList*vertex;
 struct ListNode_Generic*node;
 for(node=graph->vertexList->start;node;node=node->next)
 {
  vertex=(struct Vertex_AdjacencyList*)(node->data);
  if(vertex->id==n)
   return vertex;
 }
}
void addVertex(struct Graph_AdjacencyList*graph,struct Vertex_AdjacencyList*vertex)
{
 (graph->numberOfVertices)++;
 addElement(graph->vertexList,makeAndInitialiseListNode(graph->vertexList,vertex));
}

void removeVertex(struct Graph_AdjacencyList*graph,int vertexNumber)
{
 int i;
 struct ListNode_Generic*node;
 struct Vertex_AdjacencyList*vertex;
 for(node=graph->vertexList->start;node;node=node->next)
 {
  vertex=(struct Vertex_AdjacencyList*)(node->data);
  removeEdge(graph,vertex->id,vertexNumber);
 }
 removeElement(graph->vertexList,getNodeReferenceWithGivenData(graph->vertexList,getVertexReference(graph,vertexNumber)));
}

void addEdge(struct Graph_AdjacencyList*graph,int sourceVertexNumber,int destinationVertexNumber)
{
 addElement
 (
  getVertexReference(graph,sourceVertexNumber)->adjacencyList,
  makeAndInitialiseListNode
  (
   getVertexReference(graph,sourceVertexNumber)->adjacencyList,
   getVertexReference(graph,destinationVertexNumber)
  )
 );
}
void removeEdge(struct Graph_AdjacencyList *graph,int sourceVertexNumber,int destinationVertexNumber)
{
 removeElement
 (
  getVertexReference(graph,sourceVertexNumber)->adjacencyList,
  getNodeReferenceWithGivenData
  (
   getVertexReference(graph,sourceVertexNumber)->adjacencyList,
   getVertexReference(graph,destinationVertexNumber)
  )
 );
}
void printGraph_AdjacencyList(struct Graph_AdjacencyList*graph)
{
 struct Vertex_AdjacencyList*vertexPtr,*jointVertex;
 struct ListNode_Generic*pointer,*ptr;
 int i;
 printf("\nTotal Number Of Vertices in the Graph : %d\n",graph->numberOfVertices);
 printf("\nPrinting the Adjacency List of each vertex. \n");
 for(ptr=(struct ListNode_Generic*)((graph->vertexList)->start);ptr;ptr=ptr->next)
 {
  vertexPtr=(struct Vertex_AdjacencyList*)(ptr->data);
  printf("Vertex No. : %d: ",vertexPtr->id); // Printing the id of current vertex number.
  for(pointer=(struct ListNode_Generic*)((vertexPtr->adjacencyList)->start);pointer;pointer=pointer->next)
  {
   jointVertex=(struct Vertex_AdjacencyList*)(pointer->data);
   printf("%d ",jointVertex->id);
  }
  printf("\n\n");
 }
}

main.c

#include<stdio.h>
#include"Graph_AdjacencyList.h"
int main()
{
 struct Graph_AdjacencyList*graph;
 int a,b,weight,isDirected,i,numberOfVertices,numberOfEdges,sourceVertexNumber,destinationVertexNumber,vertexNumber;

 printf("Enter the number of Vertices in the Graph : ");
 scanf("%d",&(numberOfVertices));
 printf("Enter the number of Edges in the Graph : ");
 scanf("%d",&(numberOfEdges));

 graph=makeAndInitialiseGraph();

 for(i=0;i<numberOfVertices;i++)
  addVertex(graph,makeVertex());

 printf("NOTE 1 : The ordering of the Vertices and Edges is zero indexed.\n");
 printf("NOTE 2 : For each edge enter the following in Sequence : \n");
 printf("\t1. Source Vertex Number.\n");
 printf("\t2. Destination Vertex Number.\n");
 
 for(i=0;i<numberOfEdges;i++)
 {
  printf("Enter the edge Number %d : ",i+1);
  scanf("%d%d",&a,&b);
  addEdge(graph,a,b);
 }
 printGraph_AdjacencyList(graph);
 
 /* Deleting an Edge */
 printf("To Remove an Edge Enter the source and destination vertex number : ");
 scanf("%d%d",&sourceVertexNumber,&destinationVertexNumber);
 removeEdge(graph,sourceVertexNumber,destinationVertexNumber);
 printGraph_AdjacencyList(graph);
 
 /* Deleting a Vertex */
 printf("To delete a vertex enter the vertex number :");
 scanf("%d",&vertexNumber);
 removeVertex(graph,vertexNumber);
 printGraph_AdjacencyList(graph);
 printf("Program Execution Successful...\n");
 return 0;
}

Makefile

all: LinkedList_Generic.o Graph_AdjacencyList.o main.o
 gcc LinkedList_Generic.o Graph_AdjacencyList.o main.o -o hello
LinkedList_Generic.o: LinkedList_Generic.c
 gcc -c LinkedList_Generic.c
Graph_AdjacencyList.o: Graph_AdjacencyList.c
 gcc -c Graph_AdjacencyList.c
main.o: main.c
 gcc -c main.c
clean :
 rm -rf *~ *.o hello

SampleTest.txt

4
8
0 2
2 0
3 0
0 3
2 3
3 2
3 1
1 3

2 0

3