C Programming-Backtracking Set 5 (m Coloring Problem)

Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.

Input:
1) A 2D array graph[V][V] where V is the number of vertices in graph and graph[V][V] is adjacency matrix representation of the graph. A value graph[i][j] is 1 if there is a direct edge from i to j, otherwise graph[i][j] is 0.
2) An integer m which is maximum number of colors that can be used.

Output:
An array color[V] that should have numbers from 1 to m. color[i] should represent the color assigned to the ith vertex. The code should also return false if the graph cannot be colored with m colors.

Following is an example graph (from Wiki page ) that can be colored with 3 colors.

Naive Algorithm
Generate all possible configurations of colors and print a configuration that satisfies the given constraints.

while there are untried conflagrations
{
   generate the next configuration
   if no adjacent vertices are colored with same color
   {
      print this configuration;
   }
}

There will be V^m configurations of colors.

[ad type=”banner”]

Backtracking Algorithm
The idea is to assign colors one by one to different vertices, starting from the vertex 0. Before assigning a color, we check for safety by considering already assigned colors to the adjacent vertices. If we find a color assignment which is safe, we mark the color assignment as part of solution. If we do not a find color due to clashes then we backtrack and return false.

Implementation of Backtracking solution

[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F%2F%20Number%20of%20vertices%20in%20the%20graph%0A%23define%20V%204%0A%20%0Avoid%20printSolution(int%20color%5B%5D)%3B%0A%20%0A%2F*%20A%20utility%20function%20to%20check%20if%20the%20current%20color%20assignment%0A%20%20%20is%20safe%20for%20vertex%20v%20*%2F%0Abool%20isSafe%20(int%20v%2C%20bool%20graph%5BV%5D%5BV%5D%2C%20int%20color%5B%5D%2C%20int%20c)%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(graph%5Bv%5D%5Bi%5D%20%26%26%20c%20%3D%3D%20color%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20return%20true%3B%0A%7D%0A%20%0A%2F*%20A%20recursive%20utility%20function%20to%20solve%20m%20coloring%20problem%20*%2F%0Abool%20graphColoringUtil(bool%20graph%5BV%5D%5BV%5D%2C%20int%20m%2C%20int%20color%5B%5D%2C%20int%20v)%0A%7B%0A%20%20%20%20%2F*%20base%20case%3A%20If%20all%20vertices%20are%20assigned%20a%20color%20then%0A%20%20%20%20%20%20%20return%20true%20*%2F%0A%20%20%20%20if%20(v%20%3D%3D%20V)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%2F*%20Consider%20this%20vertex%20v%20and%20try%20different%20colors%20*%2F%0A%20%20%20%20for%20(int%20c%20%3D%201%3B%20c%20%3C%3D%20m%3B%20c%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Check%20if%20assignment%20of%20color%20c%20to%20v%20is%20fine*%2F%0A%20%20%20%20%20%20%20%20if%20(isSafe(v%2C%20graph%2C%20color%2C%20c))%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20color%5Bv%5D%20%3D%20c%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F*%20recur%20to%20assign%20colors%20to%20rest%20of%20the%20vertices%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20if%20(graphColoringUtil%20(graph%2C%20m%2C%20color%2C%20v%2B1)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20assigning%20color%20c%20doesn’t%20lead%20to%20a%20solution%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20then%20remove%20it%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20color%5Bv%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20If%20no%20color%20can%20be%20assigned%20to%20this%20vertex%20then%20return%20false%20*%2F%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F*%20This%20function%20solves%20the%20m%20Coloring%20problem%20using%20Backtracking.%0A%20%20It%20mainly%20uses%20graphColoringUtil()%20to%20solve%20the%20problem.%20It%20returns%0A%20%20false%20if%20the%20m%20colors%20cannot%20be%20assigned%2C%20otherwise%20return%20true%20and%0A%20%20prints%20assignments%20of%20colors%20to%20all%20vertices.%20Please%20note%20that%20there%0A%20%20may%20be%20more%20than%20one%20solutions%2C%20this%20function%20prints%20one%20of%20the%0A%20%20feasible%20solutions.*%2F%0Abool%20graphColoring(bool%20graph%5BV%5D%5BV%5D%2C%20int%20m)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20all%20color%20values%20as%200.%20This%20initialization%20is%20needed%0A%20%20%20%20%2F%2F%20correct%20functioning%20of%20isSafe()%0A%20%20%20%20int%20*color%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20color%5Bi%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Call%20graphColoringUtil()%20for%20vertex%200%0A%20%20%20%20if%20(graphColoringUtil(graph%2C%20m%2C%20color%2C%200)%20%3D%3D%20false)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20printf(%22Solution%20does%20not%20exist%22)%3B%0A%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20the%20solution%0A%20%20%20%20printSolution(color)%3B%0A%20%20%20%20return%20true%3B%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20print%20solution%20*%2F%0Avoid%20printSolution(int%20color%5B%5D)%0A%7B%0A%20%20%20%20printf(%22Solution%20Exists%3A%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%20Following%20are%20the%20assigned%20colors%20%5Cn%22)%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20printf(%22%20%25d%20%22%2C%20color%5Bi%5D)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Create%20following%20graph%20and%20test%20whether%20it%20is%203%20colorable%0A%20%20%20%20%20%20(3)—(2)%0A%20%20%20%20%20%20%20%7C%20%20%20%2F%20%7C%0A%20%20%20%20%20%20%20%7C%20%20%2F%20%20%7C%0A%20%20%20%20%20%20%20%7C%20%2F%20%20%20%7C%0A%20%20%20%20%20%20(0)—(1)%0A%20%20%20%20*%2F%0A%20%20%20%20bool%20graph%5BV%5D%5BV%5D%20%3D%20%7B%7B0%2C%201%2C%201%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%7B1%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%7B1%2C%201%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%7B1%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%7D%3B%0A%20%20%20%20int%20m%20%3D%203%3B%20%2F%2F%20Number%20of%20colors%0A%20%20%20%20graphColoring%20(graph%2C%20m)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]

Output:

Solution Exists: Following are the assigned colors
 1  2  3  2

[ad type=”banner”]