AlgoVerse

Greedy graph colouring

Take the nodes by degree (Welsh–Powell) and give each one the smallest colour none of its neighbours has.

Graph colouring gives every node a colour so that no two neighbours share one (think exam scheduling: courses with a common student must not be at the same time). Finding the fewest colours (the chromatic number) is NP-hard; the greedy method is fast but not always optimal.

Read the full explanation ↓
Input:
V=7 · E=10 · src=APDF export

Seven nodes; the busiest nodes are coloured first and three colours are enough.

  1. def greedy_coloring(graph, src):
  2. # Welsh-Powell: colour the nodes with the most neighbours first.
  3. order = sorted(graph, key=lambda v: -len(graph[v]))
  4. color = {v: 0 for v in graph}
  5. for u in order:
  6. used = set()
  7. for v, _ in graph[u]:
  8. if color[v] != 0:
  9. used.add(color[v])
  10. c = 1
  11. while c in used:
  12. c = c + 1
  13. color[u] = c
  14. return color

Invariant: No two neighbouring nodes that both have a colour share the same colour.

Start

ABCDEFG
  • Current node (u)
  • Shortest-path tree so far
  • Edge being checked

Local variables

src'A'

Orange = changed in this step

graph dict
  • 'A': [('B', 1), ('C', 1)]
  • 'B': [('A', 1), ('C', 1), ('D', 1)]
  • 'C': [('A', 1), ('B', 1), ('D', 1), ('E', 1)]
  • 'D': [('B', 1), ('C', 1), ('F', 1)]
  • 'E': [('C', 1), ('F', 1), ('G', 1)]
  • 'F': [('D', 1), ('E', 1), ('G', 1)]
  • 'G': [('E', 1), ('F', 1)]

Call stack

  1. greedy_coloring()line 1
Step 1 of 113
Black = pick · Orange = key steporder: 0/1 · pick: 0/7 · look: 0/20 · paint: 0/7 · next_color: 0/8

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • look
    • current input (n=7)
    050100481216202428n = number of nodeslook
    Show as a table
    nlook
    410.4
    827.6
    1241.6
    1656
    2070.8
    2474.4
    2894.4
    Explanation

    The idea

    Graph colouring gives every node a colour so that no two neighbours share one (think exam scheduling: courses with a common student must not be at the same time). Finding the fewest colours (the chromatic number) is NP-hard; the greedy method is fast but not always optimal.

    The algorithm

    1. Sort the nodes by degree, largest first (Welsh–Powell).
    2. Take the nodes in that order and give each the smallest colour none of its coloured neighbours has.

    It uses at most Δ + 1 colours (Δ is the largest degree).

    What to watch in the trace

    • The number by each node is its colour (0 means not coloured yet).
    • Try "a bad order": a graph that two colours would do gets four.