Map coloring with MRV and Degree heuristics in Python

Question

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:
 def __init__(self, totalNodes, adjacencyList, color):
 self.totalNodes = totalNodes
 self.adjacencyList = adjacencyList
 self.color = color
 self.nodeSequence = [""]*totalNodes
 def isSafe(self, node, c):
 for i in range(len(self.adjacencyList[node])):
 if(self.color[self.adjacencyList[node][i]] == 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 == ''):
 for node, neighbourList in self.adjacencyList.items():
 if (len(neighbourList) > maxCount and self.color[node] == 0):
 maxCount = len(neighbourList)
 selectedNode = node
 # the other nodes
 else:
 for i in range(len(self.adjacencyList[initialNode])):
 childNode = self.adjacencyList[initialNode][i]
 if (self.color[childNode] == 0 and len(self.adjacencyList[childNode]) > maxCount):
 maxCount = len(self.adjacencyList[childNode])
 selectedNode = childNode
 return selectedNode
 def getNodeWithMRV(self, parentNode, colorLimit):
 selectedNode = ''
 for i in range(len(self.adjacencyList[parentNode])):
 childNode = self.adjacencyList[parentNode][i]
 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():
 adjacencyList = {
 '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
 };
 g = Graph(7, adjacencyList, color)
 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.

• vnp: You seem to lose something while copying. How minCount ever changes?
• Abrar: You mean maxCount in the pickNode() function?
• vnp: No. I mean minCount in getNodeWithMRV
• Abrar: sorry, minCount is unnecessary there. Updated code.
• vnp: if (countColor < minCount): is still there.

Answer 1

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])):
 childNode = self.adjacencyList[initialNode][i]

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):
 for i in range(len(self.adjacencyList[node])):
 if(self.color[self.adjacencyList[node][i]] == c):
 return False
 return True

could be:

def isSafe(self, node, c):
 for adjacency in self.adjacencyList[node]:
 if self.color[adjacency] == 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
 return all([self.color[adj] != c for adj in self.adjacencyList[node]]) 

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 :-)