Lawler's chromatic number algorithm in Python
Exact chromatic number by dynamic programming over independent sets, running in about 2.4423^n time.
- File
lawler_chromatic_number.py, 72 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lawler-chromatic-number/. The authors are listed in prov/E447F2.jsonl.
from collections.abc import Iterator, Sequence
def maximal_independent_sets(nbr: Sequence[int], s: int) -> Iterator[int]:
"""Yield each maximal independent set of the subgraph induced by the bitmask s.
nbr[v] is the bitmask of the neighbours of v. This is Bron-Kerbosch on the
complement, with the Tomita pivot, so it takes O(3^(k/3)) steps for k = |s|,
up to a factor polynomial in k. The empty set is yielded once when s is empty.
"""
stack = [(0, s, 0)] # (R, P, X): R is independent, P and X are its candidates
while stack:
r, p, x = stack.pop()
if p == 0:
if x == 0:
yield r
continue
# pivot u in P or X with the most candidates that are not its neighbours,
# that is, the fewest P-vertices left after removing u's non-neighbours
best, u = -1, -1
px = p | x
while px:
w = (px & -px).bit_length() - 1
px &= px - 1
c = (p & ~nbr[w] & ~(1 << w)).bit_count()
if c > best:
best, u = c, w
branch = p & (nbr[u] | (1 << u)) # vertices that are not non-neighbours of u
while branch:
v = (branch & -branch).bit_length() - 1
branch &= branch - 1
keep = ~(nbr[v] | (1 << v))
stack.append((r | (1 << v), p & keep, x & keep))
p &= ~(1 << v)
x |= 1 << v
def lawler_chromatic_number(adj: Sequence[Sequence[int]]) -> tuple[int, list[int]]:
"""Return (chi, c): the chromatic number of the graph and an optimal coloring.
adj[v] lists the neighbours of v in a simple undirected graph on 0 .. n-1.
c[v] is in 1 .. chi and adjacent vertices get different colors. Time
O(2.4423^n) up to a polynomial factor, space Theta(2^n).
"""
n = len(adj)
nbr = [0] * n
for v in range(n):
for w in adj[v]:
nbr[v] |= 1 << w
full = (1 << n) - 1
inf = n + 1
best = [0] * (1 << n) # @line L1: best[0] = 0 for the empty set
choice = [0] * (1 << n)
for s in range(1, full + 1): # @line L2: subsets before supersets
best[s] = inf # @line L3
for i in maximal_independent_sets(nbr, s): # @line L4
if best[s & ~i] + 1 < best[s]: # @line L5
best[s] = best[s & ~i] + 1
choice[s] = i
c = [0] * n
s, k = full, 0
while s:
k += 1
i = choice[s]
for v in range(n):
if i >> v & 1:
c[v] = k
s &= ~i
return best[full], c # @line L6
test_lawler_chromatic_number.py 104 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lawler-chromatic-number/. The authors are listed in prov/E447F2.jsonl.
import itertools
import random
from lawler_chromatic_number import lawler_chromatic_number, maximal_independent_sets
def make(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
adj: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
return adj
def proper(adj: list[list[int]], c: list[int]) -> bool:
return all(c[u] != c[v] for u in range(len(adj)) for v in adj[u])
def chi(adj: list[list[int]]) -> int:
n = len(adj)
for k in range(n + 1):
for col in itertools.product(range(k), repeat=n):
if proper(adj, list(col)):
return k
return n
def check(adj: list[list[int]]) -> int:
k, c = lawler_chromatic_number(adj)
assert proper(adj, c)
assert sorted(set(c)) == list(range(1, k + 1))
return k
def cycle(n: int) -> list[list[int]]:
return make(n, [(i, (i + 1) % n) for i in range(n)])
def complete(n: int) -> list[list[int]]:
return make(n, [(i, j) for i in range(n) for j in range(i + 1, n)])
def test_example() -> None:
assert check(cycle(5)) == 3
nbr = [sum(1 << w for w in row) for row in cycle(5)]
mis = sorted(sorted(v for v in range(5) if i >> v & 1) for i in maximal_independent_sets(nbr, 31))
assert mis == [[0, 2], [0, 3], [1, 3], [1, 4], [2, 4]]
def test_edges() -> None:
assert lawler_chromatic_number([]) == (0, [])
assert check([[]]) == 1
assert check([[], [], [], []]) == 1
for n in range(1, 8):
assert check(complete(n)) == n
for n in (3, 5, 7, 9, 11):
assert check(cycle(n)) == 3
for n in (4, 6, 8, 10):
assert check(cycle(n)) == 2
def test_named_graphs() -> None:
kmn = make(7, [(i, j) for i in range(3) for j in range(3, 7)])
assert check(kmn) == 2
pet = make(10, [(i, (i + 1) % 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)])
assert check(pet) == 3
# Groetzsch graph: Mycielskian of C5, triangle-free with chi = 4
e = [(i, (i + 1) % 5) for i in range(5)]
e += [(5 + i, (i + 1) % 5) for i in range(5)] + [(5 + i, (i - 1) % 5) for i in range(5)]
e += [(10, 5 + i) for i in range(5)]
assert check(make(11, e)) == 4
wheel = make(6, [(i, (i + 1) % 5) for i in range(5)] + [(5, i) for i in range(5)])
assert check(wheel) == 4
def test_mis_count_moon_moser() -> None:
adj = make(9, [(i, j) for i in range(9) for j in range(i + 1, 9) if i // 3 == j // 3])
nbr = [sum(1 << w for w in row) for row in adj]
assert len(list(maximal_independent_sets(nbr, (1 << 9) - 1))) == 27
def test_random_against_brute_force() -> None:
rng = random.Random(9031)
for _ in range(500):
n = rng.randint(0, 7)
p = rng.random()
adj = make(n, [(i, j) for i in range(n) for j in range(i + 1, n) if rng.random() < p])
assert check(adj) == chi(adj)
nbr = [sum(1 << w for w in row) for row in adj]
s = rng.randrange(1 << n)
got = sorted(maximal_independent_sets(nbr, s))
want = []
verts = [v for v in range(n) if s >> v & 1]
for k in range(len(verts) + 1):
for sub in itertools.combinations(verts, k):
m = sum(1 << v for v in sub)
if any(nbr[v] & m for v in sub):
continue
if all(nbr[v] & m for v in verts if not m >> v & 1):
want.append(m)
assert got == sorted(want)
What the next level needs
- the tests did not run in this build
Read the full page about Lawler's chromatic number algorithm