Sunday 14 October 2012

Graph coloring problem with Backtracking in C

Today I am going to post a program in C that is used for solving the Graph Coloring problem.
What is Graph-Coloring : In this problem, for any given graph G we will have to color each of the vertices in G in such a way that no two adjacent vertices get the same color and the least number of colors are used.
How to solve the problem : First take input number of vertices and edges in graph G. Then input all the indexes of adjacency matrix of G whose value is 1. Now we will try to color each of the vertex. A next_color(k) function takes in index of the kth vertex which is to be colored. First we assign color1 to the kth vertex.Then we check whether it is connected to any of previous (k-1) vertices using backtracking. If connected then assign a color x[i]+1 where x[i] is the color of ith vertex that is connected with kth vertex.
--------------------------------------------------------------------------------------------------------------------------
SOURCE CODE
--------------------------------------------------------------------------------------------------------------------------
#include<stdio.h>
int G[50][50],x[50]; 
//G:adjacency matrix,x:colors
void next_color(int k){
   int i,j;
   x[k]=1; 
//coloring vertex with color1
   for(i=0;i<k;i++){
//checking all k-1 vertices-backtracking
     if(G[i][k]!=0 && x[k]==x[i])  /
/if connected and has same color
       x[k]=x[i]+1; 
//assign higher color than x[i]
   }
}

int main(){
  int n,e,i,j,k,l;
  printf("Enter no. of vertices : ");
  scanf("%d",&n); 
//total vertices
  printf("Enter no. of edges : ");
  scanf("%d",&e); 
//total edges
 
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      G[i][j]=0; 
//assign 0 to all index of adjacency matrix
     
  printf("Enter indexes where value is 1-->\n");
  for(i=0;i<e;i++){
    scanf("%d %d",&k,&l);
    G[k][l]=1;
    G[l][k]=1;
  }
 
  for(i=0;i<n;i++)
    next_color(i); 
//coloring each vertex

  printf("Colors of vertices -->\n");
  for(i=0;i<n;i++) 
//displaying color of each vertex
    printf("Vertex[%d] : %d\n",i+1,x[i]);

  return 0;
}

NOTE : This code is written,compiled and run with GCC compiler under Linux environment Ubuntu12.04LTS Precise Pangolin.
--------------------------------------------------------------------------------------------------------------------------
OUTPUT
--------------------------------------------------------------------------------------------------------------------------
Enter no. of vertices : 4
Colored vertices of Graph G
Enter no. of edges : 5
Enter indexes where value is 1-->
0 1
1 2
1 3
2 3
3 0
Colors of vertices -->
Vertex[1] : 1
Vertex[2] : 2
Vertex[3] : 1
Vertex[4] : 3
--------------------------------------------------------------------------------------------------------------------------
RELATED POSTS
--------------------------------------------------------------------------------------------------------------------------
 To understand m-coloring i.e. to color a graph with all possible m colors (hence known as M-Way Coloring or m-coloring) visit :

29 comments:

  1. thnx for sharing...
    plz post n-queens problem

    ReplyDelete
  2. hello, welch coloring algorithm with the exam schedule will do Powel How can I watch the way, can you help?

    ReplyDelete
  3. I think this is greedy coloring, not backtracking.

    ReplyDelete
    Replies
    1. this is backtracking because of the checking of all previous adjacent nodes for a current node under processing;

      Delete
  4. thank you very very much :)

    ReplyDelete
    Replies
    1. is it excuted and the color display for you ?
      for me the run exit at
      Colors of vertices -->

      Delete
  5. what exactly "Enter indexes where value is 1" mean? i cant get it.

    ReplyDelete
  6. it mean ender the 2 nodes which you want to connect

    ReplyDelete
  7. You idiot !
    Don't you know how to spell a word

    ReplyDelete
  8. dont mess with mee...otherwise..i'll f uhhh.....

    ReplyDelete
  9. Fuck yourself you bloody fucker !!

    ReplyDelete
    Replies
    1. Don't call me a fucker, You moron !

      Delete
    2. STFU, You sucker.!

      Delete
    3. Even after 8 years that spelling mistake keeps bothering me, please do a favor to society and either correct your mistake or delete the comment altogether.
      Thanking You,
      A Well Wisher.

      Delete
    4. Lets relish this fight again after 8 f***ing years

      Delete
  10. go to hell man...!!!!

    ReplyDelete
  11. What is the time complexity of this program

    ReplyDelete
  12. this algorithm giving wrong answer
    eg
    vertices 5
    edges 8
    0 1
    0 2
    1 2
    1 3
    1 4
    2 3
    2 4
    3 4
    answer should be 4 but no. of colors showing 3
    I AM WAITING FOR correction in the code.

    ReplyDelete
  13. Replies
    1. #include


      int mat[50][50]; // " mat " : est un matrice adjacent


      char (*a[50])[10],(*clr[50])[10],(*tmp[50])[10]; // 'clr' , 'a' et 'tmp' : sont des tableaux de chaine des caracteres rempli des colores

      void color(int k,int n) // la fontion 'color' va colorer touts les sommet de facont minimal
      {
      int i;
      clr[k]=a[0]; // initialisation de tableau 'clr' avec la color rouge

      for(i=0;i ");
      scanf("%d",&l); // entrer l'indice ligne par l'utilisateur
      mat[c][l]=1; // donne '1' pour les sommet qui sont adjacent
      mat[l][c]=1; // donne '1' pour les sommet qui sont adjacent
      }

      for(i=0;i<=n;i++) // remplire le tableau 'tmp' 'n' colore
      tmp[i]=a[i];

      for(i=0;i<n;i++)
      color(i,n); // l'appele de la fonction 'color' pour colorer chaque sommet

      printf("\n colore des sommet est : \n\n");
      for(i=0;i<n;i++)
      printf(" sommet[%d] : %s\n",i,clr[i]); // afficher a l'ecran la colore de chaque sommet

      for(i=0;i<n-1;i++)
      {
      for(j=i+1;j<n;j++)
      {
      if(clr[i]==clr[j])
      {
      for(k=j;k<n;k++)
      {
      clr[j]=clr[j+1];
      j=j+1;
      n=n-1;
      }
      }
      }
      }

      printf("\n\n le nbr des sommet est : %d",n ); // affiche le nbre de colore utiliser
      printf("\n\n\n\n\n");

      return 0;
      }

      Delete