Carraghan-Pardalos algorithm in Python
Branch-and-bound search for a maximum clique by extending partial cliques one vertex at a time.
- File
carraghan_pardalos_algorithm.py, 36 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/carraghan-pardalos-algorithm/. The authors are listed in prov/F3SXV2.jsonl.
from collections.abc import Sequence
def carraghan_pardalos_algorithm(adj: Sequence[Sequence[int]]) -> list[int]:
"""Return a maximum clique of a simple undirected graph, as a sorted list.
adj[v] lists the neighbours of v (vertices 0 .. n-1, each edge in both lists,
no self-loops). Vertices are ordered by non-decreasing degree, ties by index.
The search takes the candidates in this order and cuts a branch as soon as
the current clique plus all remaining candidates cannot beat the best clique.
Among several maximum cliques it returns the first one found.
"""
n = len(adj)
nb = [set(adj[v]) for v in range(n)]
order = sorted(range(n), key=lambda v: (len(nb[v]), v)) # @line L1
best: list[int] = [] # @line L2
def expand(c: list[int], p: list[int]) -> None:
nonlocal best
p = list(p)
while p: # @line L5
if len(c) + len(p) <= len(best): # @line L6
return
v = p.pop(0) # @line L7
q = [w for w in p if w in nb[v]] # @line L8
if not q: # @line L9
if len(c) + 1 > len(best):
best = c + [v]
else:
expand(c + [v], q) # @line L10
expand([], order) # @line L3
return sorted(best) # @line L4
test_carraghan_pardalos_algorithm.py 61 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/carraghan-pardalos-algorithm/. The authors are listed in prov/F3SXV2.jsonl.
import itertools
import random
from carraghan_pardalos_algorithm import carraghan_pardalos_algorithm
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(k: list[int], edges: list[tuple[int, int]]) -> bool:
es = {frozenset(e) for e in edges}
return all(frozenset(p) in es for p in itertools.combinations(k, 2))
def omega(n: int, edges: list[tuple[int, int]]) -> int:
for r in range(n, 0, -1):
if any(is_clique(list(s), edges) for s in itertools.combinations(range(n), r)):
return r
return 0
def test_example() -> None:
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5), (0, 6), (5, 6),
(1, 4), (6, 7)]
assert carraghan_pardalos_algorithm(make(8, edges)) == [1, 2, 3, 4]
def test_edges() -> None:
assert carraghan_pardalos_algorithm([]) == []
assert carraghan_pardalos_algorithm([[]]) == [0]
assert carraghan_pardalos_algorithm(make(4, [])) == [0]
assert carraghan_pardalos_algorithm(make(2, [(0, 1)])) == [0, 1]
for n in range(1, 9):
assert carraghan_pardalos_algorithm(make(n, list(itertools.combinations(range(n), 2)))) == list(range(n))
for n in range(4, 10):
got = carraghan_pardalos_algorithm(make(n, [(i, (i + 1) % n) for i in range(n)]))
assert len(got) == 2
k333 = [(u, v) for u, v in itertools.combinations(range(9), 2) if u // 3 != v // 3]
got = carraghan_pardalos_algorithm(make(9, k333))
assert len(got) == 3 and is_clique(got, k333)
def test_random_against_brute_force() -> None:
rng = random.Random(11)
for _ in range(700):
n = rng.randrange(0, 10)
p = rng.random()
edges = [e for e in itertools.combinations(range(n), 2) if rng.random() < p]
got = carraghan_pardalos_algorithm(make(n, edges))
assert got == sorted(set(got))
assert all(0 <= v < n for v in got)
assert is_clique(got, edges)
assert len(got) == omega(n, edges)
What the next level needs
- the tests did not run in this build