Problem:
The problem is, given m colors, find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color.the given graphs:
java program
package graphcolor;
import java.util.ArrayList;
public class Graph {
class Node {
public int vertex;
public int vcolor;
public ArrayList<Node> pointer =new ArrayList<Node>();
public Node( int v){
this.vertex=v;
}
}
Node[] n=new Node[7];
public Graph(){
for(int i=0;i<n.length;i++){
n[i]=new Node(i+1);
}
this.addEdge(n[0],n[1]);
this.addEdge(n[0],n[2]);
this.addEdge(n[1],n[3]);
this.addEdge(n[2],n[3]);
this.addEdge(n[2],n[4]);
this.addEdge(n[2],n[5]);
this.addEdge(n[3],n[4]);
this.addEdge(n[4],n[5]);
this.addEdge(n[6],n[6]);
}
public void addEdge(Node A, Node B){
A.pointer.add(B);
B.pointer.add(A);
}
public void colorGraph(){
for (int i=0;i<n.length;i++){
//method to finding the unused color
n[i].vcolor=this.findunusedcolor(n[i]);
}
}
public int findunusedcolor(Node n){
int unusedcolor = 0;
int usedcolor[]=new int[10];
for(int j=0;j<n.pointer.size();j++){
int c=n.pointer.get(j).vcolor;
usedcolor[j]=c;
}
int [] color=new int[3];
for(int i=0;i<color.length;i++){
color[i]=i;
}
boolean check;
for(int i=0;i<color.length;i++){
check=true;
for(int j=0;j<usedcolor.length;j++){
if(color[i]==usedcolor[j]){
check=false;
}
}
if(check){
unusedcolor=color[i];
}
}
return unusedcolor;
}
public void showGraph(){
for (int i=0;i<n.length;i++){
System.out.println("node"+ n[i].vertex+" color"+n[i].vcolor );
}
}
}
***********************************************
package graphcolor;
public class GraphTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Graph g=new Graph();
g.colorGraph();
System.out.println("The Problem's solution is:");
g.showGraph();
}
}
Output:
****************************
The Problem's solution is:
node1 color2
node2 color1
node3 color1
node4 color2
node5 color0
node6 color2
node7 color2
