Graph Coloring in C Programming

Let G be a graph and m be a given positive integer. We want to whether the nodes of G can be colored in such a way that no two adjacent nodes have the same color yet only m colors are used.

Example:
Let graph G has 5 nodes (a, b, c, d, e) and adjacent matrix is as follows-
* a b c d e
a 0 1 1 0 1
b 1 0 1 0 1
c 1 1 0 1 0
d 0 0 1 0 1
e 1 1 0 1 0

Answer:
Vertex a is color 1
Vertex b is color 2
Vertex c is color 3
Vertex d is color 1
Vertex e is color 3

I have solve this problem in c programming and it run properly in Cygwin.

Source code:
[sourcecode language="C"]
/**********************************************************/
/* Coded By Md. Mahedi Azad and Presented By Insafeta.com */
/**********************************************************/

#include<stdio.h>
const int MAX = 100;
// a[i][j] = 0 if i-th and j-th vertices are not adjacent
int a[100][100];
// color[i] = 1 if we have colored
int color[100];
// array degree[n] stores the degrees of the vertices
int degree[100];
// array NN[] stores all the vertices that is not adjacent to current vertex
int NN[100];
//n is the number of vertex
int n;
// NNCount is the number of that set
int NNCount;
// unprocessed is the number of vertices with which we 've not worked
int unprocessed;

//input function
void GetInput(){
int i, j;
printf("Enter the number of row or colum: ");
scanf("%d", &n);
for (i=0; i<n; i++)
for (j=0; j<n; j++)
scanf("%d", &a[i][j]);
}

// initializing function
void Init(){
int i, j;
for (i=0; i<n; i++){
color[i] = 0;
degree[i] = 0;
for (j = 0; j<n; j++)
if (a[i][j] == 1)
degree[i] ++;
}
NNCount = 0;
unprocessed = n;
}

// this function finds the unprocessed vertex of which degree is maximum
int MaxDegreeVertex(){
int max = -1;
int max_i, i;
for (i =0; i<n; i++)
if (color[i] == 0)
if (degree[i]>max)
{
max = degree[i];
max_i = i;
}
return max_i;
}

// it reset the value of scanned array
void scannedInit(int scanned[MAX]){
int i;
for (i=0; i<n; i++)
scanned[i] = 0;
}

// this function updates NN array
void UpdateNN(int ColorNumber){
int i, j;
NNCount = 0;
for (i=0; i<n; i++)
if (color[i] == 0){
NN[NNCount] = i;
NNCount ++;
}
for (i=0; i<n; i++)
if (color[i] == ColorNumber)
for ( j=0; j<NNCount; j++)
while (a[i][NN[j]] == 1){
NN[j] = NN[NNCount - 1];
NNCount --;
}
}

// this function will find suitable y from NN
int FindSuitableY(int ColorNumber, int VerticesInCommon){
int temp,tmp_y,i,k,x,y;
int scanned[MAX];
VerticesInCommon = 0;
for (i=0; i<NNCount; i++){
tmp_y = NN[i];
temp = 0;
scannedInit(scanned);
for (x=0; x<n; x++)
if (color[x] == ColorNumber)
for ( k=0; k<n; k++)
if (color[k] == 0 && scanned[k] == 0)
if (a[x][k] == 1 && a[tmp_y][k] == 1){
temp ++;
scanned[k] = 1;
}
if (temp > VerticesInCommon){
VerticesInCommon = temp;
y = tmp_y;
}
}
return y;
}

// find the vertex in NN of which degree is maximum
int MaxDegreeInNN(){
int tmp_y, i, j;
int temp, max = 0;
for (i=0; i<NNCount; i++){
temp = 0;
for ( j=0; j<n; j++)
if (color[NN[j]] == 0 && a[i][NN[j]] == 1)
temp ++;
if (temp>max){
max = temp;
tmp_y = NN[i];
}
}
return tmp_y;
}

// processing function
void Coloring(){
int x,y;
int ColorNumber = 0;
int VerticesInCommon = 0;
while (unprocessed>0){
x = MaxDegreeVertex();
ColorNumber ++;
color[x] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
while (NNCount>0){
y = FindSuitableY(ColorNumber, VerticesInCommon);
if (VerticesInCommon == 0)
y = MaxDegreeInNN();
color[y] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
}
}
}

// print out the output
void PrintOutput(){
int i;
for ( i=0; i<n; i++)
printf("Vertex %d is colored %d \n", i+1, color[i] );
}

// main function
int main(){
GetInput();
Init();
Coloring();
PrintOutput();
}

[/sourcecode]