# Map coloring with MRV and Degree heuristics in Python

I am relatively new to Python. I wrote this solution to the well known map coloring problem and also implemented the MRV and Degree heuristics. Here, I am considering the map of Australia - ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T'] and 3 given colors - ['R','G', 'B']

# choosing first node with degree heruistics
# applying MRV with backtracking

from enum import Enum
import pdb

class Color(Enum):
RED = 1
GREEN = 2
BLUE = 3

class Graph:
self.totalNodes = totalNodes
self.color = color
self.nodeSequence = [""]*totalNodes

def isSafe(self, node, c):
return False
return True

def graphColorUtil(self, node, colorLimit):
if node == '':
# check and color any uncolored node
for key, value in self.color.items():
if value == 0:
self.graphColorUtil(key, colorLimit)
return True

# pdb.set_trace()
for c in range(1, colorLimit+1):
if(self.isSafe(node, c) == True):
self.color[node] = c
nextNode = self.getNodeWithMRV(node, colorLimit)
if(self.graphColorUtil(nextNode, colorLimit) == True):
return True
else:
self.color[node] = 0

return False

def graphColoring(self, colorLimit):
# pdb.set_trace()
startNode = self.pickNode('')
if(self.graphColorUtil(startNode, colorLimit) == True):
return True
else:
print("Solution does not exists")
return False

# pick node using MRV
def pickNode(self, initialNode):
maxCount = 0
selectedNode = ''
# the very first node
if (initialNode == ''):
if (len(neighbourList) > maxCount and self.color[node] == 0):
maxCount = len(neighbourList)
selectedNode = node
# the other nodes
else:
if (self.color[childNode] == 0 and len(self.adjacencyList[childNode]) > maxCount):
selectedNode = childNode

return selectedNode

def getNodeWithMRV(self, parentNode, colorLimit):
selectedNode = ''

countColor = 0
for c in range(1, colorLimit+1):
if(self.isSafe(childNode, c) == True):
countColor += 1
if (countColor < minCount):
selectedNode = childNode

return selectedNode

# driver code
def main():
'WA': ['NT', 'SA'],
'NT': ['WA', 'SA', 'Q'],
'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
'Q': ['NT', 'SA', 'NSW'],
'NSW': ['SA', 'Q', 'V'],
'V': ['SA', 'T', 'NSW'],
'T': ['V']
};

color = {
'WA': 0,
'NT': 0,
'SA': 0,
'Q': 0,
'NSW': 0,
'V': 0,
'T': 0
};

colorLimit = 3
g.graphColoring(colorLimit)

for node, color in g.color.items():
print(node, Color(color).name)
main()


What could be the possible ways to refactor this code? I am also interested for feedback on Python code style in general.

• You seem to lose something while copying. How minCount ever changes? – vnp Dec 21 '18 at 18:24
• You mean maxCount in the pickNode() function? – Abrar Dec 22 '18 at 3:19
• No. I mean minCount in getNodeWithMRV – vnp Dec 22 '18 at 3:31
• sorry, minCount is unnecessary there. Updated code. – Abrar Dec 22 '18 at 3:40
• if (countColor < minCount): is still there. – vnp Dec 22 '18 at 4:14

Although not familiar with MRV and degree heuristics, i can make some remarks about the Python code style:

Loops can be made more Pythonic

for i in range(len(self.adjacencyList[initialNode])):


should be written as:

for childNode in self.adjacencyList[initialNode]:


Conditionals

if(self.isSafe(childNode, c) == True):


should be

if self.isSafe(childNode, c):


method isSafe

def isSafe(self, node, c):
return False
return True


could be:

def isSafe(self, node, c):
return False
return True


or even, more Pythonic, but a bit cryptic:

def isSafe(self, node, c):
# return True if all node neighbours colors differ from c


Data structure

The repetition of the keys in the adjacencyList and color suggest a data structure like the following, although this requires a lot changes in the existing code:

nodes = {
'WA' : {'color' : 0, 'neighbours' : ['NT', 'SA']},
'NT' : {'color' : 0, 'neighbours' : ['WA', 'SA', 'Q']},
'SA' : {'color' : 0, 'neighbours' : ['WA', 'NT', 'Q', 'NSW', 'V']},
'Q'  : {'color' : 0, 'neighbours' : ['NT', 'SA', 'NSW']},
'NSW': {'color' : 0, 'neighbours' : ['SA', 'Q', 'V']},
'V'  : {'color' : 0, 'neighbours' : ['SA', 'T', 'NSW']},
'T'  : {'color' : 0, 'neighbours' : ['V']},
}


Others:

• self.nodeSequence is not used
• self.totalNodes is not used
• minCount = 0 was edited out in getNodeWithMRV but should be there, or if (countColor < minCount) should be if (countColor < 0)
• pickNode is called only once with a constant argument '', and can therefor be made simpler
• getNodeWithMRV will always return '' because countColor will never be smaller than 0.
• the ; at the end of adjacencyList = ... and color = ... an origin in another language :-)