Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Basic implementation of graph coloring
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# INSTRUCTIONS:
#
# 1) Install graphviz (http://www.graphviz.org)
# 2) Run on terminal:
# python graph_coloring.py | dot -Tpng -o graph.png
# or, if you have imagemagick installed:
# python graph_coloring.py | dot -Tpng | display
from __future__ import print_function
import random
PALETTE = ('#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462',
'#b3de69', '#fccde5', '#d9d9d9', '#bc80bd', '#ccebc5', '#ffed6f')
SOUTH_AMERICA_GRAPH = {
'Brasil': ['Uruguay', 'Argentina', 'Paraguay', 'Bolivia', 'Peru',
'Colombia', 'Venezuela', 'Guyana', 'Suriname', 'French Guiana'],
'Uruguay': ['Brasil', 'Argentina'],
'Argentina': ['Chile', 'Bolivia', 'Paraguay', 'Brasil', 'Uruguay'],
'Chile': ['Peru', 'Bolivia', 'Argentina'],
'Bolivia': ['Argentina', 'Paraguay', 'Brasil', 'Peru', 'Chile'],
'Colombia': ['Venezuela', 'Brasil', 'Peru', 'Ecuador'],
'Peru': ['Ecuador', 'Colombia', 'Brasil', 'Bolivia', 'Chile'],
'Ecuador': ['Colombia', 'Peru'],
'Venezuela': ['Guyana', 'Brasil', 'Colombia'],
'Paraguay': ['Brasil', 'Argentina', 'Bolivia'],
'Guyana': ['Suriname', 'Brasil', 'Venezuela'],
'Suriname': ['French Guiana', 'Brasil', 'Guyana'],
'French Guiana': ['Brasil', 'Suriname'],
}
def generate_dot(graph, colors=None, palette=PALETTE):
assert len(set(colors.values())) <= len(palette), (
"Too few colors in the palette")
edges = []
for node, adjacents in graph.items():
for n in adjacents:
if not ((node, n) in edges or (n, node) in edges):
edges.append((node, n))
result = 'graph {\n'
result += ''.join(' "{}" -- "{}";\n'.format(*e) for e in edges)
if colors:
style = ' "{}" [style="filled",fillcolor="{}",shape=box];\n'
result += ''.join(style.format(node, palette[color])
for node, color in colors.items())
result += '}\n'
return result
def try_coloring(graph, num_colors):
"""Try coloring a graph using given maximum number of colors
>>> grafo = {
... 'A': ['B', 'C'],
... 'B': ['A'],
... 'C': ['A'],
... }
>>> try_coloring(grafo, 1)
>>> try_coloring(grafo, 2)
{'A': 0, 'C': 1, 'B': 1}
"""
assert num_colors > 0, "Invalid number of colors: %s" % num_colors
colors = {}
def neighbors_have_different_colors(nodes, color):
return all(color != colors.get(n) for n in nodes)
for node, adjacents in graph.items():
found_color = False
for color in range(num_colors):
if neighbors_have_different_colors(adjacents, color):
found_color = True
colors[node] = color
break
if not found_color:
return None
return colors
def find_graph_colors(graph):
for num_colors in range(1, len(graph)):
colors = try_coloring(graph, num_colors)
if colors:
return colors
def get_random_palette():
random_palette = list(PALETTE)
random.shuffle(random_palette)
return random_palette
if __name__ == '__main__':
graph = SOUTH_AMERICA_GRAPH
colors = find_graph_colors(graph)
# random palette just for fun
palette = get_random_palette()
print(generate_dot(graph, colors, palette))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.