3
\$\begingroup\$

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.

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

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 :-)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.