m Coloring Problem | Backtracking-5

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 of graph that can be colored with 3 different 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.

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

C/C++

 #include    // Number of vertices in the graph #define V 4    void printSolution(int color[]);    /* A utility function to check if the current color assignment is safe for vertex v i.e. checks whether the edge exists or not (i.e, graph[v][i]==1). If exist then checks whether the color to  be filled in the new vertex(c is sent in the parameter) is already used by its adjacent vertices(i-->adj vertices) or not (i.e, color[i]==c) */ bool isSafe (int v, bool graph[V][V], int color[], int c) {     for (int i = 0; i < V; i++)         if (graph[v][i] && c == color[i])             return false;     return true; }    /* A recursive utility function to solve m coloring problem */ bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {     /* base case: If all vertices are assigned a color then        return true */     if (v == V)         return true;        /* Consider this vertex v and try different colors */     for (int c = 1; c <= m; c++)     {         /* Check if assignment of color c to v is fine*/         if (isSafe(v, graph, color, c))         {            color[v] = c;               /* recur to assign colors to rest of the vertices */            if (graphColoringUtil (graph, m, color, v+1) == true)              return true;                /* If assigning color c doesn't lead to a solution                then remove it */            color[v] = 0;         }     }        /* If no color can be assigned to this vertex then return false */     return false; }    /* This function solves the m Coloring problem using Backtracking.   It mainly uses graphColoringUtil() to solve the problem. It returns   false if the m colors cannot be assigned, otherwise return true and   prints assignments of colors to all vertices. Please note that there   may be more than one solutions, this function prints one of the   feasible solutions.*/ bool graphColoring(bool graph[V][V], int m) {     // Initialize all color values as 0. This initialization is needed     // correct functioning of isSafe()     int *color = new int[V];     for (int i = 0; i < V; i++)        color[i] = 0;        // Call graphColoringUtil() for vertex 0     if (graphColoringUtil(graph, m, color, 0) == false)     {       printf("Solution does not exist");       return false;     }        // Print the solution     printSolution(color);     return true; }    /* A utility function to print solution */ void printSolution(int color[]) {     printf("Solution Exists:"             " Following are the assigned colors ");     for (int i = 0; i < V; i++)       printf(" %d ", color[i]);     printf(" "); }    // driver program to test above function int main() {     /* Create following graph and test whether it is 3 colorable       (3)---(2)        |   / |        |  /  |        | /   |       (0)---(1)     */     bool graph[V][V] = {{0, 1, 1, 1},         {1, 0, 1, 0},         {1, 1, 0, 1},         {1, 0, 1, 0},     };     int m = 3; // Number of colors     graphColoring (graph, m);     return 0; }

Java

 /* Java program for solution of M Coloring problem    using backtracking */ public class mColoringProblem {     final int V = 4;     int color[];        /* A utility function to check if the current        color assignment is safe for vertex v */     boolean isSafe(int v, int graph[][], int color[],                    int c)     {         for (int i = 0; i < V; i++)             if (graph[v][i] == 1 && c == color[i])                 return false;         return true;     }        /* A recursive utility function to solve m        coloring  problem */     boolean graphColoringUtil(int graph[][], int m,                               int color[], int v)     {         /* base case: If all vertices are assigned            a color then return true */         if (v == V)             return true;            /* Consider this vertex v and try different            colors */         for (int c = 1; c <= m; c++)         {             /* Check if assignment of color c to v                is fine*/             if (isSafe(v, graph, color, c))             {                 color[v] = c;                    /* recur to assign colors to rest                    of the vertices */                 if (graphColoringUtil(graph, m,                                       color, v + 1))                     return true;                    /* If assigning color c doesn't lead                    to a solution then remove it */                 color[v] = 0;             }         }            /* If no color can be assigned to this vertex            then return false */         return false;     }        /* This function solves the m Coloring problem using        Backtracking. It mainly uses graphColoringUtil()        to solve the problem. It returns false if the m        colors cannot be assigned, otherwise return true        and  prints assignments of colors to all vertices.        Please note that there  may be more than one        solutions, this function prints one of the        feasible solutions.*/     boolean graphColoring(int graph[][], int m)     {         // Initialize all color values as 0. This         // initialization is needed correct functioning         // of isSafe()         color = new int[V];         for (int i = 0; i < V; i++)             color[i] = 0;            // Call graphColoringUtil() for vertex 0         if (!graphColoringUtil(graph, m, color, 0))         {             System.out.println("Solution does not exist");             return false;         }            // Print the solution         printSolution(color);         return true;     }        /* A utility function to print solution */     void printSolution(int color[])     {         System.out.println("Solution Exists: Following" +                            " are the assigned colors");         for (int i = 0; i < V; i++)             System.out.print(" " + color[i] + " ");         System.out.println();     }        // driver program to test above function     public static void main(String args[])     {         mColoringProblem Coloring = new mColoringProblem();         /* Create following graph and test whether it is            3 colorable           (3)---(2)            |   / |            |  /  |            | /   |           (0)---(1)         */         int graph[][] = {{0, 1, 1, 1},             {1, 0, 1, 0},             {1, 1, 0, 1},             {1, 0, 1, 0},         };         int m = 3; // Number of colors         Coloring.graphColoring(graph, m);     } } // This code is contributed by Abhishek Shankhadhar

Python

 # Python program for solution of M Coloring  # problem using backtracking    class Graph():        def __init__(self, vertices):         self.V = vertices         self.graph = [[0 for column in range(vertices)]                               for row in range(vertices)]        # A utility function to check if the current color assignment     # is safe for vertex v     def isSafe(self, v, colour, c):         for i in range(self.V):             if self.graph[v][i] == 1 and colour[i] == c:                 return False         return True            # A recursive utility function to solve m     # coloring  problem     def graphColourUtil(self, m, colour, v):         if v == self.V:             return True            for c in range(1, m+1):             if self.isSafe(v, colour, c) == True:                 colour[v] = c                 if self.graphColourUtil(m, colour, v+1) == True:                     return True                 colour[v] = 0        def graphColouring(self, m):         colour =  * self.V         if self.graphColourUtil(m, colour, 0) == False:             return False            # Print the solution         print "Solution exist and Following are the assigned colours:"         for c in colour:             print c,         return True    # Driver Code g  = Graph(4) g.graph = [[0,1,1,1], [1,0,1,0], [1,1,0,1], [1,0,1,0]] m=3 g.graphColouring(m)    # This code is contributed by Divyanshu Mehta

Output:

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

References:
http://en.wikipedia.org/wiki/Graph_coloring