FIND THE NUMBER OF COMPONENTS IN A GRAPH : ADJACENCY MATRIX REPRESENTATION - MERGING NODES

Write a program to check whether given graph is connected or not. Compute number of components for disconnected graph.

In graph theory, a connected component (or just component) of an undirected graph is a sub-graph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the super-graph.

For example the following graph has 3 components.

Clearly if a graph has a total of only one component, then the graph is called Connected, and on the other hand if the graph has more than one component then the graph is called Disconnected graph.

The following program finds the number of components in a graph. For representing a graph, I have used here the Adjacency Matrix representation of Graph.

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. If the adjacency matrix has an entry of 1 corresponding to the ith row and jth column, this means that there is an edge from the ith vertex to the jth vertex.

No, doubt we will need V x V bits in total to store the adjacency matrix of the graph, where V is the number of vertices. Note that many novice programmers will create an integer array of size V x V which will definitely lead to wastage of memory because every entry in the adjacency matrix is either 0 or 1, 0 representing no edge and 1 representing an edge. And because of this nature of the adjacency matrix we don't need to have an integer array when we can do the same task in a 2D bit array. This is what I have exactly done in the following program.

Now an obvious question will be that how to maintain a 2D bit array in a programming language like C. For this I have a 1D integer array, in which i will utilize each and every single bit to represent an edge between two vertices.

I will explain this using an example.

Suppose you have a graph of 5 vertices, the size of your adjacency list will be 25 bits. And we know that in a 32 bit C compiler (like gcc 4.8.2) these all 25 bits could be accommodated in a single integer, saving an enormous amount of memory.

But suppose you have 10 vertices, so then the size of your adjacency matrix will be 100 bits, which could be easily (and surely) accommodated in 4 integers, so the size of your adjacency matrix will be just 4 integers.

I think I have made myself clear, all the readers have got the concept and from now they will definitely appreciate concept of bit representation of the adjacency matrix.

The reader should note here that this representation is applicable only when the graph is un-weighted, that is there are no associated weights with the edges, otherwise this representation will not work.

Now I would like to explain the algorithm for finding the number of components in a graph given the adjacency matrix of the graph.

The basic idea of this algorithm is to merge adjacent vertices of the graph. We start with a vertex in the graph and merge all the adjacent vertices. Then we take the newly formed vertex after merging and again merge all the vertices that are adjacent to it. And we continue this step until no more merging is possible. After the exhaustive step when no more merging is possible, the number of remaining vertices will denote the number of components in the original graph.

Here I would like to add that, in adjacency matrix merging of ith vertex with the jth vertex can be accomplished by bit-wise OR operation, and I have followed the same in the source code presented below.

Here is the source code of all the things that I explained to you in above paragraphs:

one_D_bit_array.h

int get_one_D_bit_array(int ,int *);
void reset_one_D_bit_array(int ,int *);
void set_one_D_bit_array(int ,int *);

one_D_bit_array.c

#include"one_D_bit_array.h"
int get_one_D_bit_array(int i,int* arr)
{
 if((arr[i/32]&((unsigned int)1<<(31-i%32)))!=0)
  return 1;
 return 0;
}
void set_one_D_bit_array(int i,int *arr)
{
 arr[i/32]|=((unsigned int)1<<(31-i%32));  // to set its 31-(n%32) th bit.
}
void reset_one_D_bit_array(int i,int *arr)
{
 arr[i/32]&=(~((unsigned int)1<<(31-i%32))); // to reset its 31-(n%32) th bit.
}

two_D_bit_array.h

int get_two_D_bit_array(int ,int ,int *,int);
void set_two_D_bit_array(int ,int ,int *,int);
void reset_two_D_bit_array(int ,int ,int *,int);

two_D_bit_array.c

#include"two_D_bit_array.h"

/*  
  this function will return bit value in 
  ith row and 
  jth column
  from the array 'arr'
  which provides an abstraction of 2-D bit array of size n * n.
*/ 
int get_two_D_bit_array(int i,int j,int* arr,int n)
{
 int bitNumber=i*n+j;
 if((arr[bitNumber/32]&((unsigned int)1<<(31-bitNumber%32)))!=0)
  return 1;
 return 0;
}

/*  
  this function will set the bit value in 
  ith row and 
  jth column
  in the array 'arr'
  which provides an abstraction of 2-D bit array of size n * n
  to 1.
*/ 
void set_two_D_bit_array(int i,int j,int *arr,int n)
{ 
 int bitNumber=i*n+j;
 arr[bitNumber/32]|=((unsigned int)1<<(31-bitNumber%32));  // to set its 31-(bitNumber%32) th bit.
}

/*  
  this function will set the bit value in 
  ith row and 
  jth column
  in the array 'arr'
  which provides an abstraction of 2-D bit array of size n * n
  to 0.
*/ 
void reset_two_D_bit_array(int i,int j,int *arr,int n)
{
 int bitNumber=i*n+j;
 arr[bitNumber/32]&=(~((unsigned int)1<<(31-bitNumber%32))); // to reset its 31-(bitNumber%32) th bit.
}

graph.h

struct Graph
{
 int numberOfVertices,numberOfEdges;
 unsigned int*adjacencyMatrix;
};
struct Graph*makeNewGraph();
void initializeAdjacencyMatrix(struct Graph*);
void createEdge(struct Graph*,int,int);
void removeEdge(struct Graph*,int,int);
void showAdjacencyMatrix(struct Graph*);
int findNumberOfComponents(struct Graph*);

graph.c

#include<stdio.h>
#include<stdlib.h>
#include"Graph_AdjacencyMatrix.h"
#include"two_D_bit_array.h"
#include"one_D_bit_array.h"

struct Graph*makeNewGraph()
{
	struct Graph*g;
	g=(struct Graph*)malloc(sizeof(struct Graph));
	return g;
}
void initializeAdjacencyMatrix(struct Graph*g)
{
	/*
		The adjacencyMatrix corresponding to vertex u and v will contain 1 if there is an edge from u to v
		otherwise it will contain 0

		Description of data structure used for making adjacencyMatrix:
			* We will need n*n bits to represent the existence of an edge between two vertices
			* These n*n bits should be assumed to be arranged in the linear fashion
			* For implementing this linear fashion we will use an array of integers.
			* For a standard 32 bit compiler (like gcc 4.8.2) size of an integer is 32 bits (4 bytes).
			* By this linear arrangement of AdjacencyMatrix we will optimally exploit every single bit.
	*/
	int sizeOfIntegerColumns,i,j;
	sizeOfIntegerColumns=((g->numberOfVertices)*(g->numberOfVertices))/32+1;
	(g->adjacencyMatrix)=(unsigned int*)malloc(sizeof(unsigned int)*sizeOfIntegerColumns);
	for(i=0;i<sizeOfIntegerColumns;i++)
		(g->adjacencyMatrix)[i]=0;
}
void createEdge(struct Graph*g,int a,int b)
{
	set_two_D_bit_array(a,b,g->adjacencyMatrix,g->numberOfVertices);
}
void removeEdge(struct Graph*g,int a,int b)
{
	reset_two_D_bit_array(a,b,g->adjacencyMatrix,g->numberOfVertices);
}
void showAdjacencyMatrix(struct Graph*g)
{
	int i,j,bitNumber;
	printf("The adjacency Matrix of the Graph is as follows : \n");
	for(i=0;i<(g->numberOfVertices);i++)
	{
		for(j=0;j<(g->numberOfVertices);j++)
			printf("%d",get_two_D_bit_array(i,j,g->adjacencyMatrix,g->numberOfVertices));
		printf("\n");
	}
}
int findNumberOfComponents(struct Graph*g)
{
	/*
		first of all we need to create a copy of the AdjacencyMatrix.
	*/
	unsigned int *adjacencyMatrix_copy,*flag,sizeOfIntegerColumns,i,j,k,components;
	sizeOfIntegerColumns=((g->numberOfVertices)*(g->numberOfVertices))/32+1;
	adjacencyMatrix_copy=(unsigned int*)malloc(sizeof(unsigned int)*sizeOfIntegerColumns);
	for(i=0;i<sizeOfIntegerColumns;i++)
		adjacencyMatrix_copy[i]=(g->adjacencyMatrix)[i];
	/* copy of adjacencyMatrix created */

	/* 	now we need to keep the track of vertices being merged
		for this we need to introduce a one-D bit array that will keep track of this information.
		let this one-D bit array be flag.
	*/
	flag=(unsigned int *)malloc(sizeof(unsigned int)*(g->numberOfVertices)/32+1);
	for(i=0;i<(g->numberOfVertices)/32+1;i++)
		flag[i]=0;
	/*
		if the nth bit of flag array is 0 this means that the vertex with vertexNumber 'n' is still
		alive and is not merged with any other vertex.

		if the nth bit of flag array is 1 this means that the vertex with vertexNumber 'n' is dead
		and is merged with some other vertex and has no existence now.
	*/
	/* now we are ready for merging vertices in our dummy (copied) adjacencyMatrix.  */
	for(i=0;i<(g->numberOfVertices);i++)
	{
		if(get_one_D_bit_array(i,flag)==0) // means ith vertex is alive
		{
			for(j=0;j<(g->numberOfVertices);j++)
			{
				if(j!=i && get_one_D_bit_array(j,flag)==0) // means the jth vertex is alive
				{
					if(get_two_D_bit_array(i,j,adjacencyMatrix_copy,g->numberOfVertices)==1)
					{
						/*
							now we need to merge the ith node with the jth node
							for this we need to merge
								ith row with jth row, and
								ith col with jth col
						*/
						for(k=0;k<(g->numberOfVertices);k++) // merging the ith and jth rows
						{
							if(get_two_D_bit_array(i,k,adjacencyMatrix_copy,g->numberOfVertices) | get_two_D_bit_array(j,k,adjacencyMatrix_copy,g->numberOfVertices))
								set_two_D_bit_array(i,k,adjacencyMatrix_copy,g->numberOfVertices);
						}
						for(k=0;k<(g->numberOfVertices);k++) // merging the ith and jth cols
						{
							if(get_two_D_bit_array(k,i,adjacencyMatrix_copy,g->numberOfVertices) | get_two_D_bit_array(k,j,adjacencyMatrix_copy,g->numberOfVertices))
								set_two_D_bit_array(k,i,adjacencyMatrix_copy,g->numberOfVertices);
						}
						/* now the jth vertex is merged with ith vertex so the ith vertex should have no existence */
						/* so we need to set the jth bit of flag array to 1 */
						set_one_D_bit_array(j,flag); // declaring that the jth vertex is now dead.
					}
				}
			}
		}
	}
	/* 
		now the total number of components in the graph will be the number of vertices that still have zero 
		correponding to their vertex number in flag array.
	*/
	components=0;
	for(i=0;i<(g->numberOfVertices);i++)
		if(get_one_D_bit_array(i,flag)==0)
			components++;
	return components;
}

main.c

#include<stdio.h>
#include"graph.h"

int main()
{
 int i,n,a,b;
 struct Graph*g;
 g=makeNewGraph();
 printf("Enter the number of Vertices in the Graph : ");
 scanf("%d",&(g->numberOfVertices));
 printf("Enter the number of Edges in the Graph : ");
 scanf("%d",&(g->numberOfEdges));
 initializeAdjacencyMatrix(g);
 printf("NOTE : The ordering of the vertices is zero indexed.\n");
 for(i=0;i<(g->numberOfEdges);i++)
 {
  printf("Enter the edge Number %d : ",i+1);
  scanf("%d%d",&a,&b);
  createEdge(g,a,b);
 }
 showAdjacencyMatrix(g);
 printf("Number of components in the Graph = %d\n",findNumberOfComponents(g));
 printf("\nProgram execution successful...\n");
 return 0;
}

Makefile

all: hello
hello: one_D_bit_array.o two_D_bit_array.o graph.o main.o
 gcc one_D_bit_array.o two_D_bit_array.o graph.o main.o -o hello
one_D_bit_array.o: one_D_bit_array.c
 gcc -c one_D_bit_array.c
two_D_bit_array.o: two_D_bit_array.c
 gcc -c two_D_bit_array.c
main.o: main.c
 gcc -c main.c
graph.o: graph.c
 gcc -c graph.c

To find the source code on GitHub click here