Recursive largest first in Python
Builds one color class at a time as a maximal independent set, starting from the most constrained vertices.
- File
recursive_largest_first.py, 63 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/recursive-largest-first/. The authors are listed in prov/8E77R4.jsonl.
from collections.abc import Sequence
def recursive_largest_first(adj: Sequence[Sequence[int]]) -> list[int]:
"""Color the vertices 0 .. n-1 of a simple undirected graph by Leighton's RLF rule.
adj[v] lists the neighbours of v (each edge is in both lists). Color classes are
built one at a time. U holds the uncolored vertices, P the candidates for the
current class and W the uncolored vertices that already have a neighbour in it.
The first member is the vertex of P with the most neighbours in U; each later
member is the vertex of P with the most neighbours in W, ties broken by the
fewest neighbours in P and then by the smaller index. Returns the colors 1 .. k.
Time O(n^2 + k m) for k colors, extra space O(n).
"""
n = len(adj)
c = [0] * n
in_u = [True] * n
u_size = n
k = 0 # @line L1
where = [0] * n # 0: not in U, 1: in P, 2: in W
d_w = [0] * n # neighbours in W
d_p = [0] * n # neighbours in P
while u_size > 0: # @line L2
k += 1 # @line L3: P <- U, W <- empty
for x in range(n):
where[x] = 1 if in_u[x] else 0
d_w[x] = 0
for x in range(n):
d_p[x] = sum(1 for y in adj[x] if in_u[y])
p_size = u_size
v = -1 # @line L4: most neighbours in U (= in P now), smaller index first
for x in range(n):
if where[x] == 1 and (v < 0 or d_p[x] > d_p[v]):
v = x
while True: # @line L5
c[v] = k # @line L6
where[v] = 0
in_u[v] = False
u_size -= 1
p_size -= 1
for y in adj[v]:
d_p[y] -= 1
for x in adj[v]: # @line L7
if where[x] == 1:
where[x] = 2
p_size -= 1
for y in adj[x]:
d_p[y] -= 1
d_w[y] += 1
if p_size == 0: # @line L8
break
v = -1 # @line L9
for x in range(n):
if where[x] == 1 and (
v < 0
or d_w[x] > d_w[v]
or (d_w[x] == d_w[v] and d_p[x] < d_p[v])
):
v = x
return c # @line L10
test_recursive_largest_first.py 114 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/recursive-largest-first/. The authors are listed in prov/8E77R4.jsonl.
import itertools
import random
from recursive_largest_first import recursive_largest_first
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 reference(adj: list[list[int]]) -> list[int]:
"""Direct transcription of RLF with sets, recounting at every step."""
n = len(adj)
nb = [set(a) for a in adj]
c = [0] * n
u = set(range(n))
k = 0
while u:
k += 1
p, w = set(u), set()
v = min(p, key=lambda x: (-len(nb[x] & u), x))
while True:
c[v] = k
p.discard(v)
u.discard(v)
moved = nb[v] & p
p -= moved
w |= moved
if not p:
break
v = min(p, key=lambda x: (-len(nb[x] & w), len(nb[x] & p), x))
return c
def check(adj: list[list[int]]) -> list[int]:
c = recursive_largest_first(adj)
n = len(adj)
assert c == reference(adj)
assert proper(adj, c)
k = max(c, default=0)
assert set(c) == set(range(1, k + 1))
for v in range(n):
# every class is maximal in what was left: v has a neighbour in each earlier class
assert {c[w] for w in adj[v] if c[w] < c[v]} == set(range(1, c[v]))
assert c[v] <= len(adj[v]) + 1
return c
EXAMPLE = [(0, 2), (0, 4), (0, 5), (0, 6), (1, 3), (2, 3), (2, 4), (3, 4), (4, 6)]
def test_example() -> None:
assert check(make(7, EXAMPLE)) == [1, 2, 3, 1, 2, 2, 3]
def test_edges() -> None:
assert recursive_largest_first([]) == []
assert recursive_largest_first([[]]) == [1]
assert recursive_largest_first([[], [], []]) == [1, 1, 1]
for n in range(1, 8):
kn = make(n, [(i, j) for i in range(n) for j in range(i + 1, n)])
assert sorted(check(kn)) == list(range(1, n + 1))
for n in (3, 5, 7, 9):
assert max(check(make(n, [(i, (i + 1) % n) for i in range(n)]))) == 3
for n in (4, 6, 8):
assert max(check(make(n, [(i, (i + 1) % n) for i in range(n)]))) == 2
def test_bipartite() -> None:
kmn = make(7, [(i, j) for i in range(3) for j in range(3, 7)])
assert max(check(kmn)) == 2
t = 5
crown = make(2 * t, [(2 * i, 2 * j + 1) for i in range(t) for j in range(t) if i != j])
assert max(check(crown)) == 2
def test_random_against_brute_force() -> None:
rng = random.Random(8779)
for _ in range(600):
n = rng.randint(0, 7)
p = rng.random()
edges = [(i, j) for i in range(n) for j in range(i + 1, n) if rng.random() < p]
adj = make(n, edges)
c = check(adj)
assert max(c, default=0) >= chi(adj)
def test_random_larger() -> None:
rng = random.Random(2201)
for _ in range(100):
n = rng.randint(8, 30)
p = rng.random()
edges = [(i, j) for i in range(n) for j in range(i + 1, n) if rng.random() < p]
check(make(n, edges))
What the next level needs
- the tests did not run in this build