Today I am going to post a program that will be able to produce all the mColorings of a given graph G.

--------------------------------------------------------------------------------------------------------------------------

__: 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 m-colors in all possible ways. This is called m-coloring of a graph G. Suppose for a graph G and 3 colors , we have to show all its 3-colorings.__**What is mColoring**__: 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 m-colorings can be represented as a tree.__**How to solve the problem**Graph G to be colored |

Tree for 3-coloring 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**

**Related Posts**
To color a graph with least number of colors visit

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]?