Graph coloring is an interesting problem. Variations involve using the fewest number of colors while making each node a unique color, trying to use an equal number of each color, etc. Take for example this map of the United States.
How can we keep the constraint that adjacent states do not have the same color while reducing the number of colors to only four? If you try this by hand you start by picking a state and coloring the states around it alternating colors. You can do this with 3 colors if there an even number of adjacent states.
But if there are an odd number then you need 4 colors.
Then you continue the pattern to other states and introduce a new color only when necessary.
We’re going to do this for the map of 50 U.S. states using the genetic solver from the previous post.
We don’t care about the visual representation per se. We only care about the physical relationships between the states, which we can represent with a graph, or more simply as a set of rules indicating which states cannot have the same color.
We start off with a file containing a list of states and the set of states that are adjacent to each. The row for Tennessee might be as follows:
TN,AL;AR;GA;KY;MO;MS;NC;VA
Next we need to read that file.
def loadData(localFileName):
# expects: AA,BB;CC;DD where BB, CC and DD are the initial column values in other rows
with open(localFileName, mode='r') as infile:
reader = csv.reader(infile)
mydict = {row[0]: row[1].split(';') for row in reader if row}
return mydict
Then we need to build the rules. A Rule connects two states indicating that they are adjacent. We want to be able to put rules in a dictionary and find them in a list so we need to define __hash__ and __eq__. We might also want to be able to display a rule so we’ll add a __str__ implementation.
class Rule:
Item = None
Other = None
Stringified = None
def __init__(self, item, other, stringified):
self.Item = item
self.Other = other
self.Stringified = stringified
def __eq__(self, another):
return hasattr(another, 'Item') and \
hasattr(another, 'Other') and \
self.Item == another.Item and \
self.Other == another.Other
def __hash__(self):
return hash(self.Item) * 397 ^ hash(self.Other)
def __str__(self):
return self.Stringified
Next we’re going to build the set of rules. While we’re doing so we’re going to perform a sanity check on the data. Whenever a state says it is adjacent to another state, the adjacent state should also say it is adjacent to the first state.
def buildLookup(items):
itemToIndex = {}
index = 0
for key in sorted(items):
itemToIndex[key] = index
index += 1
return itemToIndex
def buildRules(items):
itemToIndex = buildLookup(items.keys())
rulesAdded = {}
rules = []
keys = sorted(list(items.keys()))
for key in sorted(items.keys()):
keyIndex = itemToIndex[key]
adjacentKeys = items[key]
for adjacentKey in adjacentKeys:
if adjacentKey == '':
continue
adjacentIndex = itemToIndex[adjacentKey]
temp = keyIndex
if adjacentIndex < temp:
temp, adjacentIndex = adjacentIndex, temp
ruleKey = keys[temp] + "->" + keys[adjacentIndex]
rule = Rule(temp, adjacentIndex, ruleKey)
if rule in rulesAdded:
rulesAdded[rule] += 1
else:
rulesAdded[rule] = 1
rules.append(rule)
for k, v in rulesAdded.items():
if v == 1:
print("rule %s is not bidirectional" % k)
return rules
Now we have the ability to convert a file of node relationships to a set of adjacency rules. Next we need to build the code used by the genetic solver. We’ll start by determining what our genes will be. In this case since we want to four-color the 50 states our geneset will be four color codes.
colors = ["Orange", "Yellow", "Green", "Blue"]
colorLookup = {}
for color in colors:
colorLookup[color[0]] = color
geneset = list(colorLookup.keys())
Our Individuals will have 50 genes, one for each state, in alphabetical order. This lets us use the index into the genes as an index into the set of sorted state codes.
Since the expected optimal situation will be that all adjacent states have different colors we can set the optimal value to the number of rules.
At the end we’ll write out the color of each state.
class GraphColoringTests(unittest.TestCase):
def test(self):
states = loadData("adjacent_states.csv")
rules = buildRules(states)
colors = ["Orange", "Yellow", "Green", "Blue"]
colorLookup = {}
for color in colors:
colorLookup[color[0]] = color
geneset = list(colorLookup.keys())
optimalValue = len(rules)
startTime = datetime.datetime.now()
fnDisplay = lambda candidate: display(candidate, startTime)
fnGetFitness = lambda candidate: getFitness(candidate, rules)
best = genetic.getBest(fnGetFitness, fnDisplay, len(states), optimalValue, geneset)
self.assertEqual(best.Fitness, optimalValue)
keys = sorted(states.keys())
for index in range(len(states)):
print(keys[index] + " is " + colorLookup[best.Genes[index]])
As for display, it should be sufficient to output the color codes.
def display(candidate, startTime):
timeDiff = datetime.datetime.now() - startTime
print("%s\t%i\t%s" % (''.join(map(str, candidate.Genes)), candidate.Fitness, str(timeDiff)))
This gets output like the following. The number to the right of the gene sequence will indicate how many rules this gene sequence satisfies.
YGGBOOGOOBBYGGYYYYGBGYOOGBOYGGOOOYBOYBBGGOBYOGOGOGG 74 0:00:00.001000
Finally we need a fitness function that checks all the rules assuming the states are colored according to the gene sequence.
def getFitness(candidate, rules):
rulesThatPass = 0
for rule in rules:
if candidate[rule.Item] != candidate[rule.Other]:
rulesThatPass += 1
return rulesThatPass
That’s it. Now when we run our main test function we get the following output:
OOYYOBBGYOOYGBBYOOOBOGYGYGGBBYGOGGOYOYGYBBOBOBGOBBG 82 0:00:00 YYBOYGGGGOBYOYBGBOOBOOBBGGBGGYGBBGOBOBYYOGYYBBYOYGO 102 0:00:00.016001 BOOGOGGOGBGYGGBGOOYBYOBYGBBOGBGBBBOYYYGYYOYOOGYBOBY 103 0:00:00.316018 GOBOGGOYGBGOBGOGYBYBOOYYGGBBGOYBYYYOOBGYYOYGBGGOGYY 104 0:00:01.602092 BBBBGGBYGOGYBGOGBBYGOGYYYGYBBOOBYYYOOOGOYGOGOGBBGYB 105 0:00:04.933282 AK is Blue AL is Blue AR is Blue AZ is Blue CA is Green CO is Green CT is Blue DC is Yellow DE is Green FL is Orange GA is Green HI is Yellow IA is Blue ID is Green IL is Orange IN is Green KS is Blue KY is Blue LA is Yellow MA is Green MD is Orange ME is Green MI is Yellow MN is Yellow MO is Yellow MS is Green MT is Yellow NC is Blue ND is Blue NE is Orange NH is Orange NJ is Blue NM is Yellow NV is Yellow NY is Yellow OH is Orange OK is Orange OR is Orange PA is Green RI is Orange SC is Yellow SD is Green TN is Orange TX is Green UT is Orange VA is Green VT is Blue WA is Blue WI is Green WV is Yellow WY is Blue
Which looks like this:
Read more of this series in my eBook Genetic Algorithms with Python
