Basic Graph Data Structure to demonstrate Friendships

Graphs have numerous applications out of which Social Networks is quite popular.

In this Article I have tried to present a simple use case to demonstrate how to represent it using Adjacency Lists.  Idea is to help you get started with Graphs.

Since we are discussing friendships the Graph used is an undirected one.

Consider a simple case, we have a really small town with only 6 people. The figure below shows how they are connected to each other. So for example Ankur is friend with Dikshit and Reena.

So how can we capture this data?

A Graph is a set of Vertices and Edges. In our case the people are the vertices and the relationship between them are the Edges.

There are two popular ways to represent a Graph. One is the Adjacency Matrix approach and another one is the Adjacency List approach. The second one is more popular because of it’s efficiency. If you need more details on these two representations kindly visit the following links Adjacency Matrix  &  Adjacency List

Please drop a comment if you want me to explain these approaches as well. For now I want to keep things short and simple.

In the List approach we maintain an Array of Vertices and each Vertex in the Array has a Linked List which points to it’s Edges. See the figure below. I have shown one of the Linked List that shows Ankur’s connections.

Now let’s see how to implement this using C. If you are not quite familiar with Arrays and Linked List I will recommend you to visit Wiki for the same. I have written sample programs for Array and Linked List here and I am planning to explain them soon.

This code is also available in Github

#include<stdio.h>
#include<stdlib.h>

/*
	Author: @ankur
	Date: March 22, 2018
	Version: 0.1
	This Program illustrates the Graph Data Structure.  
*/

#define MAXV 6 /* maximum number of vertices */

/*Structure for Vertex*/
struct node{
	int label; /*data*/
	char *name; /*data*/
	struct node *next; /*Pointer to next node*/
};

struct node vertices[MAXV];
char *names[MAXV];

void addToList(struct node *x, int data);
void traverseGraph();
void initNames();
void displayNames();

int main(){
	/*Initialize Names*/
	initNames();
	displayNames();
	
	/*Initialize the Array*/
	for(int i=0;i<MAXV;i++){
		vertices[i].label = i;
		vertices[i].name = names[i];
		vertices[i].next = NULL;
	}
	/*
		Say we have the following Edges {(0,1), (0,2), (1,2)}
		Let's build the Adjacency List.
	*/
	
	addToList(&vertices[0], 1);
	addToList(&vertices[0], 3);
	addToList(&vertices[1], 2);
	addToList(&vertices[1], 0);
	addToList(&vertices[1], 4);
	addToList(&vertices[2], 1);
	addToList(&vertices[3], 0);
	addToList(&vertices[3], 5);
	addToList(&vertices[4], 1);
	
	/*Traverse the Adjacency List*/
	traverseGraph();
	
	return 0;
}

/*Here we are trying to add an edge x->y*/
void addToList(struct node *x, int data){
	printf("Going to Add %d to the Vertex %d \n", data, x->label);
	struct node *y = (struct node *)(malloc(sizeof(struct node)));
	if(y!=NULL){
		y->label = data;
		y->name = names[data];
		if(x->next != NULL)
			y->next = x->next;
		else
			y->next = NULL;
		
		x->next = y;
	}
}

void traverseGraph(){
	//printf("Ready to traverse the graph \n");
	int array_size = sizeof(vertices) / sizeof(vertices[0]);
	//printf("No of elements in Array = %d \n", array_size);
	printf("\n");
	printf("Let's see who all are Friends \n");
	printf("\n");
	for(int i=0;i<MAXV;i++){
		struct node *temp = &vertices[i];
		printf("%s is friend to --> ", temp->name);
		if(temp->next != NULL){
			temp = temp->next;
			while(temp != NULL){
				printf("%s", temp->name);
				if(temp->next != NULL)
					printf(", ");
				temp = temp->next;
			}			
		}
		printf("\n\n---------------------------------------------\n\n");
	}
}

void initNames(){
	names[0] = "Ankur";
	names[1] = "Dikshit";
	names[2] = "Mohan";
	names[3] = "Nidhi";
	names[4] = "Reena";
	names[5] = "Suresh";
}

void displayNames(){
	printf("\nWe have the following folks staying in a small town \n\n");
	for(int i=0;i<MAXV;i++){
		printf("%s ", names[i]);
	}
	printf("\n\n---------------------------------------------\n\n");
}

When you will run this Program you will get the following output.

If you find any mistakes in the approach / codebase please feel free to drop a comment.

Author: Ankur

I am Enthusiastic about Learning new things and sharing my Knowledge. I like programming and have a pretty good background in Computer Science. View all posts by Ankur