Vizing's algorithm in Python
Constructive proof that colors the edges of a simple graph with at most Delta plus one colors.
- File
vizing_algorithm.py, 82 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/vizing-algorithm/. The authors are listed in prov/5TRSEH.jsonl.
from collections.abc import Sequence
def vizing_algorithm(n: int, edges: Sequence[tuple[int, int]]) -> list[int]:
"""Color the edges of a simple graph with at most Delta + 1 colors (Misra and Gries).
The vertices are 0 .. n-1 and edges lists the edges (u, v) with u != v and no
repeats. Returns a list col with col[i] in 1 .. Delta + 1 the color of edges[i],
such that edges with a common end get different colors. Edges are colored one
at a time: build a maximal fan at u, flip the path of colors c and d that starts
at u, rotate a prefix of the fan and color the last edge of it with d.
Time O(m (n + Delta^2)), space O(n + m).
"""
deg = [0] * n
for u, v in edges:
deg[u] += 1
deg[v] += 1
k = max(deg, default=0) + 1
at: list[dict[int, int]] = [{} for _ in range(n)] # at[x][color] = other end
color: dict[tuple[int, int], int] = {}
def get(x: int, y: int) -> int:
return color.get((x, y), 0)
def put(x: int, y: int, c: int) -> None:
old = color.pop((x, y), 0)
color.pop((y, x), None)
if old:
del at[x][old]
del at[y][old]
if c:
color[(x, y)] = color[(y, x)] = c
at[x][c] = y
at[y][c] = x
def free(x: int) -> int:
return next(c for c in range(1, k + 1) if c not in at[x])
nbrs: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
nbrs[u].append(v)
nbrs[v].append(u)
for u, v in edges: # @line L1
fan = [v] # @line L2: a maximal fan of u starting at v
in_fan = {v}
grown = True
while grown:
grown = False
for x in nbrs[u]:
cx = get(u, x)
if x not in in_fan and cx and cx not in at[fan[-1]]:
fan.append(x)
in_fan.add(x)
grown = True
break
c = free(u) # @line L3
d = free(fan[-1])
path: list[tuple[int, int]] = [] # @line L4: flip the cd-path from u
x, want = u, d
while want in at[x]:
y = at[x][want]
path.append((x, y))
x, want = y, (c if want == d else d)
old = [get(a, b) for a, b in path]
for a, b in path:
put(a, b, 0)
for (a, b), o in zip(path, old):
put(a, b, c if o == d else d)
j = 0 # @line L5: first w such that fan[..w] is a fan and d is free at w
while d in at[fan[j]]:
j += 1
assert get(u, fan[j]) not in at[fan[j - 1]]
for i in range(j): # @line L6: rotate fan[0 .. j]
nxt = get(u, fan[i + 1])
put(u, fan[i + 1], 0)
put(u, fan[i], nxt)
put(u, fan[j], d) # @line L7
return [get(u, v) for u, v in edges] # @line L8
test_vizing_algorithm.py 101 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/vizing-algorithm/. The authors are listed in prov/5TRSEH.jsonl.
import itertools
import random
from vizing_algorithm import vizing_algorithm
def max_degree(n: int, edges: list[tuple[int, int]]) -> int:
deg = [0] * n
for u, v in edges:
deg[u] += 1
deg[v] += 1
return max(deg, default=0)
def proper(edges: list[tuple[int, int]], col: list[int]) -> bool:
for (e, a), (f, b) in itertools.combinations(zip(edges, col), 2):
if a == b and set(e) & set(f):
return False
return True
def chromatic_index(n: int, edges: list[tuple[int, int]]) -> int:
m = len(edges)
for k in range(m + 1):
for col in itertools.product(range(k), repeat=m):
if proper(edges, list(col)):
return k
return m
def check(n: int, edges: list[tuple[int, int]]) -> list[int]:
col = vizing_algorithm(n, edges)
delta = max_degree(n, edges)
assert len(col) == len(edges)
assert all(1 <= c <= delta + 1 for c in col)
assert proper(edges, col)
return col
def complete(n: int) -> list[tuple[int, int]]:
return [(i, j) for i in range(n) for j in range(i + 1, n)]
def cyc(n: int) -> list[tuple[int, int]]:
return [(i, (i + 1) % n) for i in range(n)]
PETERSEN = cyc(5) + [(i, i + 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
EXAMPLE = [(0, 2), (2, 3), (0, 1), (0, 3)]
def test_example() -> None:
assert check(4, EXAMPLE) == [3, 1, 1, 2]
other = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4), (0, 4)]
assert check(5, other) == [2, 1, 3, 1, 4, 2, 4]
def test_edges() -> None:
assert vizing_algorithm(0, []) == []
assert vizing_algorithm(3, []) == []
assert check(2, [(0, 1)]) == [1]
for n in range(2, 9):
check(n, complete(n))
for n in (3, 5, 7):
assert len(set(check(n, cyc(n)))) == 3
assert len(set(check(10, PETERSEN))) == 4
def test_bipartite() -> None:
kmn = [(i, j) for i in range(3) for j in range(3, 7)]
check(7, kmn)
star = [(0, i) for i in range(1, 8)]
assert sorted(check(8, star)) == list(range(1, 8))
def test_random_against_brute_force() -> None:
rng = random.Random(9133)
for _ in range(600):
n = rng.randint(0, 6)
p = rng.random()
edges = [(i, j) for i in range(n) for j in range(i + 1, n) if rng.random() < p]
rng.shuffle(edges)
edges = [(b, a) if rng.random() < 0.5 else (a, b) for a, b in edges]
col = check(n, edges)
if len(edges) <= 9:
chi1 = chromatic_index(n, edges)
assert max_degree(n, edges) <= chi1 <= max(col, default=0)
def test_random_larger() -> None:
rng = random.Random(515)
for _ in range(200):
n = rng.randint(5, 40)
p = rng.random()
edges = [(i, j) for i in range(n) for j in range(i + 1, n) if rng.random() < p]
rng.shuffle(edges)
check(n, edges)
What the next level needs
- the tests did not run in this build