Thursday, April 14, 2011

Graph Coloring Problem -- GCP


import java.util.*;
import java.io.*;
class demo
{
int m,n;
int x[],graph[][];
void mcolor(int k)
{

int i;
while(1)
{
callnextvalue(k);
if(x[k]==o)break;
if(k==n)
{
for (i=1;i<=n;i++)
System.out.println(" "+x[i]);
System.out.println();
}
else
mcolor(k+1);
}
}
int callnextvalue(int k)
{
int j;
while(1)
{
x[k]=(x[k]+1)%(m+1);
if(x[k]==0) return 0;
for(j=1;j<=n;j++)
if(graph[k][j]&&x[k]==x[j])
break;
if(j==n+1) return 0;
}
}

public static void main(String arg[])
{
int i,e,a,b;
Scanner in=new Scanner(System.in);
System.out.println("Enter the verticesS");
System.out.println(n);
System.out.println("Enter no. of edges:");
e=in.nextInt();
for(i=1;i<e;i++)
{
System.out.println("Enter edge:");
a=in.nextInt();
b=in.nextInt();
graph[a][b]=1;
graph[b][a]=1;
}
for(i=1;i<=n;i++)
x[i]=0;
System.out.println("Enter no. of colors: )";
cin>>m;
System.out.println("Following are no. of ways in which nodes can be colored");
mcolor(1);
}
}
----------------------------------------------------------------------

         OUTPUT

Enter the vertices
5
Enter no of edges:
7
Enter edge:
1 2
Enter edge:
2 3
Enter edge:
3 4
Enter edge:
4 5
Enter edge:
5 1
Enter edge:
1 3
Enter edge:
2 5
Enter no. of colors:
3
Following are no. of ways in which nodes can be colored
1 2 3 1 3
1 2 3 2 3
1 3 2 1 2
1 3 2 3 2
2 1 3 1 3
2 1 3 2 3
2 3 1 2 1
2 3 1 3 1
3 1 2 1 2
3 1 2 3 2
3 2 1 2 1
3 2 1 3 1