Monday, December 3, 2012
Today I am going to post a program that will be able to produce all the mColorings of a given graph G.
What is mColoring : The problem statement says that for a given graph G(V,E) and m colors, we have to color all the vertices the graph G with mcolors in all possible ways. This is called mcoloring of a graph G. Suppose for a graph G and 3 colors , we have to show all its 3colorings.
How to solve the problem : Here we first define a function mColoring(int k) that will use the concept of backtracking. Here in this function we call another function next_color(int k) that will try to color the kth vertex. Now if we are successful then check whether all vertex have been colored. If it is true then we print the solution and then try another solution vector otherwise color the remaining vertex. If we were unsuccessful then we go back (backtrack)) to the last successful situation and try a different path. Our final solution i.e. all the possible mcolorings can be represented as a tree.

What is mColoring : The problem statement says that for a given graph G(V,E) and m colors, we have to color all the vertices the graph G with mcolors in all possible ways. This is called mcoloring of a graph G. Suppose for a graph G and 3 colors , we have to show all its 3colorings.
How to solve the problem : Here we first define a function mColoring(int k) that will use the concept of backtracking. Here in this function we call another function next_color(int k) that will try to color the kth vertex. Now if we are successful then check whether all vertex have been colored. If it is true then we print the solution and then try another solution vector otherwise color the remaining vertex. If we were unsuccessful then we go back (backtrack)) to the last successful situation and try a different path. Our final solution i.e. all the possible mcolorings can be represented as a tree.
Graph G to be colored 
Tree for 3coloring of graph G 

Java Source Code

public class MWayGrColor{ /*G is graph's adjacency matrix and x is solution vector */ private int G[][],x[],n,m,soln; public void mColoring(int k){ //backtracking function for(int i=1;i<=n;i++){ next_color(k); //coloring kth vertex if(x[k]==0) return; //if unsuccessful then backtrack if(k==n) //if all colored then show write(); else mColoring(k+1); /* successful but still left to color */ } } private void next_color(int k){ do{ int i=1; x[k]=(x[k]+1)%(m+1); if(x[k]==0) return; for(i=1;i<=n;i++) if(G[i][k]!=0 && x[k]==x[i]) /* checking adjacency and not same color */ break; if(i==n+1) return; //new color found }while(true); } private void write(){ System.out.print("\nColoring(V C) # "+(++soln)+">"); for(int i=1;i<=n;i++) System.out.print("\t("+i+" "+x[i]+")"); //solution vector } public void input(){ java.util.Scanner sc=new java.util.Scanner(System.in); System.out.print("Enter no. of vertices : "); n=sc.nextInt(); G=new int[n+1][n+1]; x=new int[n+1]; System.out.print("Enter no. of colors : "); m=sc.nextInt(); System.out.println("Enter adjacency matrix>"); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) G[i][j]=sc.nextInt(); } public static void main (String[] args) { MWayGrColor obj=new MWayGrColor(); obj.input(); obj.mColoring(1); if(obj.soln==0) System.out.println("\nNeed more than "+obj.m+" colors"); else System.out.print("\nTOTAL SOLN : "+obj.soln); } }

Output

Enter no. of vertices : 4
Enter no. of colors : 3
Enter adjacency matrix>
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
Coloring(V C) # 1> (1 1) (2 2) (3 3) (4 2)
Coloring(V C) # 2> (1 1) (2 3) (3 2) (4 3)
Coloring(V C) # 3> (1 2) (2 1) (3 3) (4 1)
Coloring(V C) # 4> (1 2) (2 3) (3 1) (4 3)
Coloring(V C) # 5> (1 3) (2 1) (3 2) (4 1)
Coloring(V C) # 6> (1 3) (2 2) (3 1) (4 2)
TOTAL SOLN : 6

Enter no. of colors : 3
Enter adjacency matrix>
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
Coloring(V C) # 1> (1 1) (2 2) (3 3) (4 2)
Coloring(V C) # 2> (1 1) (2 3) (3 2) (4 3)
Coloring(V C) # 3> (1 2) (2 1) (3 3) (4 1)
Coloring(V C) # 4> (1 2) (2 3) (3 1) (4 3)
Coloring(V C) # 5> (1 3) (2 1) (3 2) (4 1)
Coloring(V C) # 6> (1 3) (2 2) (3 1) (4 2)
TOTAL SOLN : 6

Download Links

DOWNLOAD the source from Mediafire
DOWNLOAD the source from Dropbox
DOWNLOAD the source from 4shared
DOWNLOAD the source from Dropbox
DOWNLOAD the source from 4shared

Related Posts

To color a graph with least number of colors visit
Labels:Algorithms
Subscribe to:
Post Comments
(Atom)
Labels
 Algorithms (7)
 Annotation (3)
 Files (6)
 Generics (3)
 Graphics2D (5)
 Graphics2DImages (7)
 Inheritance (2)
 J2EE (9)
 Java 8 (4)
 Java FAQs (19)
 JDBC (3)
 Networking (2)
 Packages (1)
 Reflection (4)
 Security (7)
 Sorting (2)
 Swing (3)
 Threads (3)
 Utils (3)
Popular Posts

 UPDATE  I have updated the code on request of some followers so that they can directly...

Today I will show you how you can implement Bankers algorithm in Java. The Banker's algorithm is a resource allocation and deadlock a...

UPDATE I have updated my post so that now it can detect IE 11. This modification was necessary as t...

Today I am going to post a program that will be able to produce all the mColorings of a given graph G. What is mColoring : The problem st...

Today I am going to show you how you can generate and validate captcha. A CAPTCHA (an acronym for "Completely Automated Public Turin...

Today in this article I will tell you how to convert an infix expression to postfix expression using stack. This is an important applicat...

Radix Sort is a type of bucket sort. This type of sort is based on radix i.e. 10 for decimal numbers and 26 for alphabets. This technique ...

The heapsort algorithm starts by using BUILDMAXHEAP to build a maxheap on the input array A[1 : : n ],where n=A:length. Since the maximu...
Links
About Me

Nirupam Das
 I am a student of BTech Computer Science Engineering from RCCIIT,Kolkata. I am a crazy lover of Java and wants to settle as a Java developer. I have a seven years Java experience with an application developer experience for 2 years. Recently from March 2012 I am a registered S40 app developer for Nokia and has corrected an app of them. I am currently writing blogs to encourage and grow interest in all those who don't know or learning Java.
Where does it get the value for x[k] in next_color() method?
ReplyDeleteIt becomes x[1] from main's obj.mcoloring(1), right?
but what's the value for x[1]?
Thanks bro.
ReplyDelete