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
