Jovian
⭐️
Sign In
Learn data science and machine learning by building real-world projects on Jovian

m Coloring Problem

In [1]:
project_name = "m_coloring_problem"
In [2]:
!pip install jovian --upgrade --quiet
In [3]:
import jovian
In [5]:
jovian.commit(project=project_name)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "siddhantramteke369/m-coloring-problem" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/siddhantramteke369/m-coloring-problem

Problem Statement

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

Source: https://www.geeksforgeeks.org/m-coloring-problem-backtracking-5/

Following is an example of a graph that can be coloured with 3 different colours

image

The Method

Here's the systematic strategy we'll apply for solving problems:

  1. State the problem clearly. Identify the input & output formats.
  2. Come up with some example inputs & outputs. Try to cover all edge cases.
  3. Come up with a correct solution for the problem. State it in plain English.
  4. Implement the solution and test it using example inputs. Fix bugs, if any.
  5. Analyze the algorithm's complexity and identify inefficiencies, if any.
  6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

Let's apply this approach step-by-step.

Solution

1. State the problem clearly. Identify the input & output formats.

Problem

Given a 2D array having 1 at position (i, j) if there is an edge between vertex i and j or 0 if there isn't and an integer m, we have to find the array of colors which represent the color given to ith vertex so that no two neighbour vertices have the same color or output false if the graph cannot be colored with just m colors.


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 the maximum number of colors that can be used.

Output

  1. 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.

Based on the above, we can now create a signature of our function:

In [4]:
def graphColoring():
    pass

Save and upload your work before continuing.

In [8]:
import jovian
In [10]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "siddhantramteke369/m-coloring-problem" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/siddhantramteke369/m-coloring-problem

2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

  1. General case
  2. Graph with all zeros
  3. Graph with all 1s
  4. m with 1
  5. m with 0

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).

In [5]:
test = {
    'input': {
        'graph': [[ 0, 1, 1, 1 ],
                  [ 1, 0, 1, 0 ],
                  [ 1, 1, 0, 1 ],
                  [ 1, 0, 1, 0 ]],
        'm': 3,
        'color': [0 for i in range(4)]
    },
    'output': [1, 2, 3, 2]
}

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

In [6]:
tests = []
In [7]:
tests.append(test)
In [8]:
tests.append({
    'input': {
        'graph': [[ 0, 0, 0, 0 ],
                  [ 0, 0, 0, 0 ],
                  [ 0, 0, 0, 0 ],
                  [ 0, 0, 0, 0 ]],
        'm': 3,
        'color': [0 for i in range(4)]
    },
    'output': [1, 1, 1, 1]
})
In [9]:
tests.append({
    'input': {
        'graph': [[ 1, 1, 1, 1 ],
                  [ 1, 1, 1, 1 ],
                  [ 1, 1, 1, 1 ],
                  [ 1, 1, 1, 1 ]],
        'm': 3,
        'color': [0 for i in range(4)]
    },
    'output': None
})
In [10]:
tests.append({
    'input': {
        'graph': [[ 0, 1, 0, 1 ],
                  [ 1, 0, 1, 0 ],
                  [ 0, 1, 0, 0 ],
                  [ 1, 0, 0, 0 ]],
        'm': 1,
        'color': [0 for i in range(4)]
    },
    'output': None
})
In [11]:
tests.append({
    'input': {
        'graph': [[ 0, 1, 1, 1 ],
                  [ 1, 0, 1, 0 ],
                  [ 1, 1, 0, 0 ],
                  [ 1, 0, 0, 0 ]],
        'm': 0,
        'color': [0 for i in range(4)]
    },
    'output': None
})
In [12]:
tests.append({
    'input': {
        'graph': [[ 0, 1, 0 ],
                  [ 1, 0, 1 ],
                  [ 0, 1, 0 ]],
        'm': 3,
        'color': [0 for i in range(3)]
    },
    'output': [1, 2, 1]
})

3. Come up with a correct solution for the problem. State it in plain English.

Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution. Come with a correct solution and explain it in simple words below:

Bruteforce technique
We will first try the brute force technique where we will try all the possible configurations to find correct solution.

Steps:

  1. We will create a recursive function that takes graph, current index, no. of vertices and output color array
  2. If current index is equal to number of vertices. Check if the output color configuration is safe i.e. check if the adjacent vertices does not have same color. If the condition is true print the configurations and break.
  3. Assign color to a vertex
  4. For every assigned color recursively call the function with next index and number of vertices.
  5. If any recursive function returns true break the loop and return true.
  6. If the current index equals 0 and all the recursive functions returned true return color array.

Let's save and upload our work before continuing.

In [17]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "siddhantramteke369/m-coloring-problem" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/siddhantramteke369/m-coloring-problem

4. Implement the solution and test it using example inputs. Fix bugs, if any.

In [13]:
# Checks if the graph is safe or not (if its acceptable or not)
def isSafe(graph, color):
    l = len(graph)
    for i in range(l):
        for j in range(i + 1, l):
            # if both are adjacent vertices and their color is same
            if (graph[i][j] and color[j] == color[i]):
                return False
    return True

# This function solves the m Coloring problem using recursion.
def graphColoring(graph, m, color, i=0):
    l = len(graph)
    
    if (i==l):
        if (isSafe(graph, color)):
            #print(color)
            return True
        return False
    
    for j in range(1, m + 1):
        color[i] = j
        
        if (graphColoring(graph, m, color,  i + 1)):
            if (i == 0):
                return color
            return True
        color[i] = 0
    return None
In [14]:
graph1 = test['input']['graph']
m = test['input']['m']
color =  test['input']['color']
print('output:', graphColoring(graph1, m, color, 0))
print('actual: ', test['output'])
output: [1, 2, 3, 2] actual: [1, 2, 3, 2]
In [15]:
tests
Out[15]:
[{'input': {'graph': [[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0]],
   'm': 3,
   'color': [1, 2, 3, 2]},
  'output': [1, 2, 3, 2]},
 {'input': {'graph': [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
   'm': 3,
   'color': [0, 0, 0, 0]},
  'output': [1, 1, 1, 1]},
 {'input': {'graph': [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]],
   'm': 3,
   'color': [0, 0, 0, 0]},
  'output': None},
 {'input': {'graph': [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]],
   'm': 1,
   'color': [0, 0, 0, 0]},
  'output': None},
 {'input': {'graph': [[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 0], [1, 0, 0, 0]],
   'm': 0,
   'color': [0, 0, 0, 0]},
  'output': None},
 {'input': {'graph': [[0, 1, 0], [1, 0, 1], [0, 1, 0]],
   'm': 3,
   'color': [0, 0, 0]},
  'output': [1, 2, 1]}]

Evaluate your function against all the test cases together using the evaluate_test_cases (plural) function from jovian.

In [16]:
from jovian.pythondsa import evaluate_test_cases
In [17]:
evaluate_test_cases(graphColoring, tests)
TEST CASE #0 Input: {'graph': [[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0]], 'm': 3, 'color': [1, 2, 3, 2]} Expected Output: [1, 2, 3, 2] Actual Output: [1, 2, 3, 2] Execution Time: 0.064 ms Test Result: PASSED TEST CASE #1 Input: {'graph': [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 'm': 3, 'color': [1, 1, 1, 1]} Expected Output: [1, 1, 1, 1] Actual Output: [1, 1, 1, 1] Execution Time: 0.018 ms Test Result: PASSED TEST CASE #2 Input: {'graph': [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]], 'm': 3, 'color': [0, 0, 0, 0]} Expected Output: None Actual Output: None Execution Time: 0.262 ms Test Result: PASSED TEST CASE #3 Input: {'graph': [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]], 'm': 1, 'color': [0, 0, 0, 0]} Expected Output: None Actual Output: None Execution Time: 0.011 ms Test Result: PASSED TEST CASE #4 Input: {'graph': [[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 0], [1, 0, 0, 0]], 'm': 0, 'color': [0, 0, 0, 0]} Expected Output: None Actual Output: None Execution Time: 0.005 ms Test Result: PASSED TEST CASE #5 Input: {'graph': [[0, 1, 0], [1, 0, 1], [0, 1, 0]], 'm': 3, 'color': [1, 2, 1]} Expected Output: [1, 2, 1] Actual Output: [1, 2, 1] Execution Time: 0.015 ms Test Result: PASSED SUMMARY TOTAL: 6, PASSED: 6, FAILED: 0
Out[17]:
[([1, 2, 3, 2], True, 0.064),
 ([1, 1, 1, 1], True, 0.018),
 (None, True, 0.262),
 (None, True, 0.011),
 (None, True, 0.005),
 ([1, 2, 1], True, 0.015)]
In [104]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "siddhantramteke369/m-coloring-problem" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/siddhantramteke369/m-coloring-problem

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

Time Complexity:
Since each node can be coloured using any of the m available colours, the total number of colour configurations possible are m^V.
So the time complexity is O(m^V).

In [18]:
time_complexity_brute = 'O(m^V)'

Space Complexity:
Recursive Stack of graphColoring(…) function will require O(V) space.

In [19]:
space_complexity_brute = 'O(V)'

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

Backtracking Algorithms

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.

Backtracking Method:

The idea is to assign colors one by one to different vertices, starting from the vertex 0. Before assigning a color, check for safety by considering already assigned colors to the adjacent vertices i.e check if the adjacent vertices have the same color or not. If there is any color assignment that does not violate the conditions, mark the color assignment as part of the solution. If no assignment of color is possible then backtrack and return false.

7. Come up with a optimized solution for the problem. State it in plain English.

Steps:

  1. Create a recursive function that takes the graph, current index, number of vertices and output color array.
  2. If the current index is equal to number of vertices. Print the color configuration in output array.
  3. Assign color to a vertex (1 to m).
  4. For every assigned color, check if the configuration is safe, (i.e. check if the adjacent vertices do not have the same color) recursively call the function with next index and number of vertices
  5. If any recursive function returns true break the loop and return true.
  6. If no recusive function returns true then return None.

Let's save and upload our work before continuing.

In [24]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "siddhantramteke369/m-coloring-problem" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/siddhantramteke369/m-coloring-problem

8. Implement the solution and test it using example inputs. Fix bugs, if any.

In [28]:
class Graph():
    
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]
          
    def isSafe(self, v, color, c):
        for i in range(self.V):
            if self.graph[v][i] == 1 and color[i]==c:
                return False
        return True
    
    def graphColorUtil(self, m, color, v):
        if v == self.V:
            return True
        
        for c in range(1, m + 1):
            if self.isSafe(v, color, c) == True:
                color[v] = c
                if self.graphColorUtil(m, color, v + 1) == True:
                    return True
                color[v] = 0
                
    def graphColoring(self, m):
        color = [0] * self.V
        if self.graphColorUtil(m, color, 0) == None:
            return None
        
        #print(color)
        return color
In [21]:
g = Graph(4)
g.graph = test['input']['graph']
m = test['input']['m']
color =  test['input']['color']
print('Output:', g.graphColoring(m))
print('Actual:', test['output'])
Output: [1, 2, 3, 2] Actual: [1, 2, 3, 2]

Evaluate on all the test cases

In [22]:
passed, failed = 0, 0

for i in range(len(tests)):
    gt = Graph(len(tests[i]['input']['color']))
    gt.graph = tests[i]['input']['graph']
    m = tests[i]['input']['m']
    color =  tests[i]['input']['color']
    print('Output:', gt.graphColoring(m))
    print('Actual:', tests[i]['output'])
    
    if (gt.graphColoring(m) == tests[i]['output']):
        print(gt.graphColoring(m) == tests[i]['output'], '\n')
        passed += 1
    else:
        print(gt.graphColoring(m) == tests[i]['output'], '\n')
        failed += 1
    
    if (i == len(tests)-1):
        print('Total:', passed+failed, 'Passed:', passed, 'Failed:', failed)
Output: [1, 2, 3, 2] Actual: [1, 2, 3, 2] True Output: [1, 1, 1, 1] Actual: [1, 1, 1, 1] True Output: None Actual: None True Output: None Actual: None True Output: None Actual: None True Output: [1, 2, 1] Actual: [1, 2, 1] True Total: 6 Passed: 6 Failed: 0

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

Time Complexity:
Since each node can be coloured using any of the m available colours, the total number of colour configurations possible are m^V.
So time complexity is O(m^V).
The upperbound time complexity remains the same but the average time taken will be less.

In [23]:
time_complexity_bt = 'O(m^V)'

Space Complexity:
Recursive Stack of graphColoring(…) function will require O(V) space.

In [24]:
space_complexity_bt = 'O(V)'
In [ ]:
jovian.commit()
[jovian] Attempting to save notebook..