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}

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