Greedy Graph Coloring in Python

Question

Graph Coloring Algorithm (Greedy/ Welsh Powell)

I am trying to learn graphs, and I couldn't find a Python implementation of the Welsh Powell algorithm online, so I tried to write my own. Here are the steps.

1. Order the nodes in descending degree. (Most neighbors ... Least neighbors)
2. For each node, check the colors of neighbor nodes and mark them as unavailable.
3. Choose the lowest available color. (from [0, 1, 2, ..., len(graph) -1])

---

def color_nodes(graph):
 # Order nodes in descending degree
 nodes = sorted(list(graph.keys()), key=lambda x: len(graph[x]), reverse=True)
 color_map = {}
 for node in nodes:
 available_colors = [True] * len(nodes)
 for neighbor in graph[node]:
 if neighbor in color_map:
 color = color_map[neighbor]
 available_colors[color] = False
 for color, available in enumerate(available_colors):
 if available:
 color_map[node] = color
 break
 return color_map
if __name__ == '__main__':
 graph = {
 'a': list('bcd'),
 'b': list('ac'),
 'c': list('abdef'),
 'd': list('ace'),
 'e': list('cdf'),
 'f': list('ce')
 }
 print(color_nodes(graph))
 # {'c': 0, 'a': 1, 'd': 2, 'e': 1, 'b': 2, 'f': 2}

example

For the input graph, it produced the above result. Is the implementation correct?

Answer 1

PEP 8, the official Python style guide, says that indentation should be 4 spaces per level. Since whitespace is significant in Python, that is a pretty strong convention.

The implementation could be less verbose:

• sorted(list(graph.keys()), ...) could be shortened to sorted(graph, ...).
• Instead of defining available_colors as a list of booleans, you could define taken_colors as a set, ideally using a generator expression.
• The loop that assigns color_map[node] can be simplified down to next(generator expression with a condition).

def color_nodes(graph):
 color_map = {}
 # Consider nodes in descending degree 
 for node in sorted(graph, key=lambda x: len(graph[x]), reverse=True):
 neighbor_colors = set(color_map.get(neigh) for neigh in graph[node])
 color_map[node] = next( 
 color for color in range(len(graph)) if color not in neighbor_colors
 )
 return color_map

• Thawsitt: Thank you for your solid feedback! Concise and elegant! I especially like the idea of using a set rather than an array of booleans.