//GRAPH COLORING PROBLEM
import java.io.*;
import java.util.*;
class Gr_Color
{
public int G[][],n,m,edges;
int color_tab[];
public Gr_Color(int MAX)
{
System.out.println("\n\n\t Graph Coloring ");
G=new int[MAX][MAX];
color_tab=new int[MAX];
for(int i=0;i<MAX;i++)
{
for(int j=0;j<MAX;j++)
{
G[i][j]=0;
color_tab[i]=0;
}
}
}
public void Gen_Col_Value(int k)
{
int j;
int a,b;
while(true)
{
a=color_tab[k]+1;
b=m+1;
color_tab[k] = a%b; // next highest color
if(color_tab[k]==0) return; // all colors have been used
for(j=1;j<=n;j++)
{
// check if this color is distinct from adjacent colors
if(G[k][j]!=0 && color_tab[k]==color_tab[j])
break;
}
if(j==n+1) return; // next new color found
}
}
public void Gr_coloring(int k)
{
Gen_Col_Value(k);
if(color_tab[k]==0) return; // No new color available
if(k==n) return; // at most m colors have been
else Gr_coloring(k+1); // used to color the n vertices
}
public void display()
{
System.out.print("\n The Vertices To be Coloured As...\n");
for(int i=1;i<=n;i++)
System.out.print("\n V"+i+":= "+color_tab[i]);
}
}
class Gr_ColorDemo
{
public static void main (String[] args )throws IOException,NullPointerException
{ Gr_Color obj=new Gr_Color(10);
int v1,v2;
System.out.println("\n Enter the number of nodes ");
obj.n=getInt();
System.out.println("\n Enter the number of edges ");
obj.edges=getInt();
obj.m=obj.n-1;
System.out.println("\n Create a graph");
for (int i=1;i<=obj.edges; i++)
{
System.out.println("\n Enter the edges of the graph");
System.out.println(" Enter value of V1 ");
v1=getInt();
System.out.println(" Enter value of V2 ");
v2=getInt();
obj.G[v1][v2] =obj. G[v2][v1] = 1;//if an edge is present then set it
}
obj.Gr_coloring(1);
obj.display();
}
public static String getString() throws IOException
{
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader b = new BufferedReader(input);
String str = b.readLine();//reading the string from console
return str;
}
public static char getChar() throws IOException
{
String str = getString();
return str.charAt(0);//reading first char of console string
}
public static int getInt() throws IOException
{
String str = getString();
return Integer.parseInt(str);//converting console string to numeric value
}
}
SAMPLE OUTPUT:
Graph Coloring
Enter the number of nodes 5
Enter the number of edges 8
Create a graph
Enter the edges of the graph
Enter value of V1 1
Enter value of V2 2
Enter the edges of the graph
Enter value of V1 1
Enter value of V2 3
Enter the edges of the graph
Enter value of V1 1
Enter value of V2 4
Enter the edges of the graph
Enter value of V1 2
Enter value of V2 3
Enter the edges of the graph
Enter value of V1 2
Enter value of V2 4
Enter the edges of the graph
Enter value of V1 2
Enter value of V2 5
Enter the edges of the graph
Enter value of V1 3
Enter value of V2 4
Enter the edges of the graph
Enter value of V1 4
Enter value of V2 5
The Vertices To be Coloured As...
V1:= 1
V2:= 2
V3:= 3
V4:= 4
V5:= 1