Tomita's maximum clique algorithm in Python
Maximum clique branch-and-bound that prunes with a greedy coloring upper bound.
- File
tomita_maximum_clique.py, 56 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/tomita-maximum-clique/. The authors are listed in prov/B53EJC.jsonl.
from collections.abc import Sequence
def number_sort(r: list[int], nbr: list[set[int]]) -> tuple[list[int], list[int]]:
"""Greedy-color r in its order and return (r sorted by color, colors)."""
classes: list[list[int]] = []
for p in r:
for cls in classes:
if not any(q in nbr[p] for q in cls):
cls.append(p)
break
else:
classes.append([p])
order: list[int] = []
col: list[int] = []
for k, cls in enumerate(classes, start=1):
order.extend(cls)
col.extend([k] * len(cls))
return order, col
def tomita_maximum_clique(adj: Sequence[Sequence[int]]) -> list[int]:
"""Return a maximum clique of a simple undirected graph on vertices 0 .. n-1.
adj[v] lists the neighbours of v. This is Tomita and Seki's MCQ: depth-first
branch and bound in which the candidate set R is greedily colored, the vertex
of largest color is expanded first, and a branch is cut as soon as
|Q| + color <= |best|, since a clique uses each color at most once.
The clique is returned sorted. Worst-case time O(2^n n^2), space O(n^2).
"""
n = len(adj)
nbr = [set(a) for a in adj]
best: list[int] = [] # @line L1
def expand(q: list[int], r: list[int]) -> None:
nonlocal best
r, col = number_sort(r, nbr) # @line L4
while r: # @line L5
p = r[-1] # @line L6
if len(q) + col[-1] <= len(best): # @line L7
return
rp = [x for x in r if x in nbr[p]] # @line L8
if not rp: # @line L9
if len(q) + 1 > len(best):
best = q + [p]
else:
expand(q + [p], rp) # @line L10
r.pop() # @line L11
col.pop()
order = sorted(range(n), key=lambda v: (-len(nbr[v]), v))
expand([], order) # @line L2
return sorted(best) # @line L3
test_tomita_maximum_clique.py 99 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tomita-maximum-clique/. The authors are listed in prov/B53EJC.jsonl.
import itertools
import random
from tomita_maximum_clique import number_sort, tomita_maximum_clique
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 is_clique(adj: list[list[int]], s: list[int]) -> bool:
return all(v in adj[u] for u, v in itertools.combinations(s, 2))
def omega(adj: list[list[int]]) -> int:
n = len(adj)
for k in range(n, 0, -1):
if any(is_clique(adj, list(s)) for s in itertools.combinations(range(n), k)):
return k
return 0
def check(adj: list[list[int]]) -> list[int]:
q = tomita_maximum_clique(adj)
assert q == sorted(set(q))
assert all(0 <= v < len(adj) for v in q)
assert is_clique(adj, q)
assert len(q) == omega(adj)
return q
def complement(n: int, edges: list[tuple[int, int]]) -> list[tuple[int, int]]:
es = {frozenset(e) for e in edges}
return [(i, j) for i in range(n) for j in range(i + 1, n) if frozenset((i, j)) not in es]
def cyc(n: int) -> list[tuple[int, int]]:
return [(i, (i + 1) % n) for i in range(n)]
EXAMPLE = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (5, 6)]
def test_example() -> None:
assert check(make(7, EXAMPLE)) == [0, 1, 2, 3]
def test_number_sort() -> None:
adj = make(5, cyc(5))
nbr = [set(a) for a in adj]
order, col = number_sort([0, 1, 2, 3, 4], nbr)
assert order == [0, 2, 1, 3, 4] and col == [1, 1, 2, 2, 3]
def test_edges() -> None:
assert tomita_maximum_clique([]) == []
assert tomita_maximum_clique([[]]) == [0]
assert len(tomita_maximum_clique([[], [], []])) == 1
for n in range(1, 9):
kn = make(n, [(i, j) for i in range(n) for j in range(i + 1, n)])
assert check(kn) == list(range(n))
for n in (3, 5, 7, 9):
assert len(check(make(n, cyc(n)))) == (3 if n == 3 else 2)
for n in (5, 6, 7, 8):
assert len(check(make(n, complement(n, cyc(n))))) == n // 2
def test_bipartite_and_multipartite() -> None:
kmn = make(7, [(i, j) for i in range(3) for j in range(3, 7)])
assert len(check(kmn)) == 2
k333 = make(9, [(i, j) for i in range(9) for j in range(i + 1, 9) if i // 3 != j // 3])
assert len(check(k333)) == 3
def test_random_against_brute_force() -> None:
rng = random.Random(6061)
for _ in range(700):
n = rng.randint(0, 10)
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))
def test_planted() -> None:
rng = random.Random(77)
for _ in range(30):
n = 40
edges = {(i, j) for i in range(n) for j in range(i + 1, n) if rng.random() < 0.3}
plant = sorted(rng.sample(range(n), 9))
edges |= set(itertools.combinations(plant, 2))
q = tomita_maximum_clique(make(n, sorted(edges)))
assert len(q) >= 9 and is_clique(make(n, sorted(edges)), q)
What the next level needs
- the tests did not run in this build