DATA STRUCTURE ME LAB PROGRAMS-->10. GRAPHCOLOURING

GRAPHCOLOURING

 Program Coding:

 

import java.io.*;

public class GraphColoring

{

       static int [][] G;

       static int [] x;

       static int n, m;

       static boolean found = false;

       public static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

       public static void main(String[] args) throws IOException

       {

             System.out.println("\t\t\t\tGRAPH COLORING");

            System.out.print("\nEnter the number of the vertices: ");

            n = Integer.parseInt(br.readLine());

            G = new int[n+1][n+1];

            x = new int[n+1];

            System.out.print("\nIf edge between the following vertices enter 1 else 0:\n");

            for(int i=1;i<=n;i++)

            {

                         for(int j=1;j<=n;j++)

                  {

                          if((i!=j)&&(i<j))

                          {

                            System.out.print(i+" and "+j+": ");

                            G[j][i]=G[i][j] = Integer.parseInt(br.readLine());

                           }

                           if(i==j)

                        G[i][j]=0;

                    }

            }       

            System.out.print("\nEnter the number of colors available: ");

            m = Integer.parseInt(br.readLine());

            System.out.println("\nSolution:");

            mColoring(1);

            if (found == false)

            System.out.println("No Solution possible!");

          }

        static void mColoring(int k)

        {

        while(true)

            {

                     NextValue(k);

                     if(x[k] == 0)

                     return;

                     if(k == n)

                     {

                        for(int i=1; i<=k;i++)

                        System.out.print(x[i]+" ");

                        System.out.println();

                        found = true;

                        return;

                       }

                       else

                           mColoring(k+1);

              }

            }

            static void NextValue(int k)

            {

            int j;

            while(true)

            {

                    x[k] = (x[k]+1)%(m+1);

                    if(x[k]==0)

                    return;

                    for(j=1; j<=n; j++)

                    if( (G[k][j] != 0) && (x[k] == x[j]) )

                    break;

                    if(j == n+1)

                    return;

            }

            }

 }

 

Output:

GRAPH COLORING

Enter the number of the vertices: 3

If edge between the following vertices enter 1 else 0:

1 and 2: 2

1 and 3: 0

2 and 3: 1

Enter the number of colors available: 3

Solution:

1 2 1

1 3 2

2 1 3

3 2 1