Generic Representation of Graph - Generic List of Vertices and Edges

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_Generic.h

struct Graph_Generic
{
 struct LinkedList_Generic *vertexList,*edgeList;
 int numberOfVertices, numberOfEdges;
};
struct Vertex
{
 int id;
 int inDegree,outDegree;
};
struct Edge
{
 int id,sourceVertex,destinationVertex,isDirected,weight;
};
struct Graph_Generic*makeAndInitialiseGraph();
void addVertex(struct Graph_Generic*graph,struct Vertex*vertex);
void removeVertex(struct Graph_Generic*graph,int vertexNumber);
void addEdge(struct Graph_Generic*graph,struct Edge*edge);
void removeEdge(struct Graph_Generic *graph,int ,int ,int);
struct Edge *makeEdge(int sourceVertex,int destinationVertex,int weight,int isDirected);
struct Vertex *makeVertex();
void printGraph_Generic(struct Graph_Generic*grpah);

Graph_Generic.c

#include"Graph_Generic.h"
#include"LinkedList_Generic.h"
#include<stdlib.h>
#include<stdio.h>
struct Graph_Generic*makeAndInitialiseGraph()
{
 struct Graph_Generic*graph;
 graph=(struct Graph_Generic*)malloc(sizeof(struct Graph_Generic));
 graph->numberOfVertices=0;
 graph->numberOfEdges=0;
 graph->vertexList=makeAndInitialiseLinkedList(sizeof(struct Vertex));
 graph->edgeList=makeAndInitialiseLinkedList(sizeof(struct Edge));
 return graph;
}
struct Edge *makeEdge(int sourceVertex,int destinationVertex,int weight,int isDirected)
{
 static int edgeNumber=0;
 struct Edge*edge;
 edge=(struct Edge*)malloc(sizeof(struct Edge));
 edge->sourceVertex=sourceVertex;
 edge->destinationVertex=destinationVertex; 
 edge->weight=weight;
 edge->isDirected=isDirected;
 edge->id=edgeNumber++;
 return edge;
}
struct Vertex *makeVertex()
{
 static int vertexNumber=0;
 struct Vertex*vertex;
 vertex=(struct Vertex*)malloc(sizeof(struct Vertex));
 (vertex->id)=vertexNumber++;
 return vertex;
}

void addVertex(struct Graph_Generic*graph,struct Vertex*vertex)
{
 (graph->numberOfVertices)++;
 addElement(graph->vertexList,makeAndInitialiseListNode(graph->vertexList,vertex));
}
void removeVertex(struct Graph_Generic*graph,int vertexNumber)
{
 struct Edge*e;
 struct ListNode_Generic*ptr,*ptr1;
 (graph->numberOfVertices)--;
 for(ptr=graph->vertexList->start;ptr;ptr=ptr->next)
 {
  if(((struct Vertex*)(ptr->data))->id==vertexNumber)
   break;
 }
 if(ptr)
 {
  /*
   when you will be deleting an vertex then all the edges from and to that vertex should be deleted.
  */
  for(ptr1=graph->edgeList->start;ptr1;ptr1=ptr1->next)
  {
   e=(struct Edge*)(ptr1->data);
   if(e->sourceVertex==vertexNumber || e->destinationVertex==vertexNumber)
    removeEdge(graph,e->sourceVertex,e->destinationVertex,e->weight);
  }
  removeElement(graph->vertexList,ptr);
 }
}
void addEdge(struct Graph_Generic*graph,struct Edge*edge)
{
 (graph->numberOfEdges)++;
 addElement(graph->edgeList,makeAndInitialiseListNode(graph->edgeList,edge));
}
void removeEdge(struct Graph_Generic *graph,int sourceVertex,int destinationVertex,int weight)
{
 struct ListNode_Generic*ptr;
 (graph->numberOfEdges)--;
 for(ptr=(graph->edgeList->start);ptr;ptr=ptr->next)
 {
  if(
   ((struct Edge*)(ptr->data))->sourceVertex==sourceVertex &&
   ((struct Edge*)(ptr->data))->destinationVertex==destinationVertex &&
   ((struct Edge*)(ptr->data))->weight==weight
  ) break;
 }
 if(ptr)
  removeElement(graph->edgeList,ptr);
}
void printGraph_Generic(struct Graph_Generic*graph)
{
 int i;
 struct ListNode_Generic*ptr;
 printf("\nPrinting the vertex List : \n");
 printf("\nTotal Number Of Vertices in the Graph : %d\n",graph->numberOfVertices);
 for(ptr=(struct ListNode_Generic*)((graph->vertexList)->start);ptr;ptr=ptr->next)
  printf("%d ",((struct Vertex*)(ptr->data))->id);
 printf("\nTotal Number Of Edges in the Graph : %d\n",graph->numberOfEdges);
 for(ptr=(struct ListNode_Generic*)((graph->edgeList)->start);ptr;ptr=ptr->next)
  printf("Edge No. : %d, from %d to %d with weight=%d and isDirected?=%d\n",((struct Edge*)(ptr->data))->id,((struct Edge*)(ptr->data))->sourceVertex,((struct Edge*)(ptr->data))->destinationVertex,((struct Edge*)(ptr->data))->weight,((struct Edge*)(ptr->data))->isDirected);
}

main.c

#include<stdio.h>
#include"Graph_Generic.h"
int main()
{
 struct Graph_Generic*graph;
 int a,b,weight,isDirected,i,numberOfVertices,numberOfEdges,sourceVertex,destinationVertex,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");
 printf("\t3. Weight associated with Edge.\n");
 printf("\t4. 1 if the Edge is Directed, and 0 otherwise.\n");
 
 for(i=0;i<numberOfEdges;i++)
 {
  printf("Enter the edge Number %d : ",i+1);
  scanf("%d%d%d%d",&a,&b,&weight,&isDirected);
  addEdge(graph,makeEdge(a,b,weight,isDirected));
 }
 printGraph_Generic(graph);
 
 printf("\nDeleting an Edge : \n");
 printf("Enter the sourceVertex, destinationVertex and weight of the graph : ");
 scanf("%d%d%d",&sourceVertex,&destinationVertex,&weight);
 removeEdge(graph,sourceVertex,destinationVertex,weight);
 
 printf("Deleting a Vertex : \n");
 printf("Enter the Vertex number to be deleted : ");
 scanf("%d",&vertexNumber);
 removeVertex(graph,vertexNumber);
 
 printGraph_Generic(graph);
 
 printf("Program Execution Successful...\n");
 return 0;
}

Makefile

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

SampleInputData.txt

6
9
1 0 1 1
1 3 1 1
1 2 1 1 
0 5 1 1
0 4 1 1
2 3 1 1
2 4 1 1
2 5 1 1
4 3 1 1
2 5 1
0