Ullmann's algorithm in Python
Backtracking search that prunes a candidate-mapping matrix with refinement for subgraph isomorphism.
- File
ullmann_algorithm.py, 114 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/ullmann-algorithm/. The authors are listed in prov/GMKCZG.jsonl.
"""Ullmann's algorithm for subgraph isomorphism, with the refinement procedure.
Graphs are undirected and simple, given as (n, edges) with vertices 0..n-1, and may carry
integer vertex labels. G1 is the pattern (k vertices), G2 the host (n vertices). Rows of the
candidate matrix are Python integers used as bit sets over host vertices. The search uses an
explicit stack instead of recursion.
"""
from collections.abc import Iterator
Graph = tuple[int, list[tuple[int, int]]]
def _adj(n: int, edges: list[tuple[int, int]]) -> list[set[int]]:
a: list[set[int]] = [set() for _ in range(n)]
for u, v in edges:
a[u].add(v)
a[v].add(u)
return a
def refine(m: list[int], adj1: list[set[int]], nbmask2: list[int]) -> bool:
"""Ullmann's refinement in place: clear m[i] bit j when some neighbor x of i has no candidate
among the neighbors of j. Returns False when a row becomes empty.
Cost: O(k * n * d1) bit-set operations per pass, at most k * n passes.
"""
# @line L8
changed = True
while changed:
changed = False
# @line L9
for i in range(len(m)):
row = m[i]
bits = row
while bits:
low = bits & -bits
j = low.bit_length() - 1
bits ^= low
# @line L10
for x in adj1[i]:
if m[x] & nbmask2[j] == 0:
row &= ~low
changed = True
break
m[i] = row
if row == 0:
return False
# @line L11
return True
def ullmann_matches(g1: Graph, g2: Graph, induced: bool = False,
labels1: list[int] | None = None, labels2: list[int] | None = None) -> Iterator[list[int]]:
"""Yield every injective map f (f[i] is the host vertex of pattern vertex i) that keeps edges,
and also non-edges when induced is True. Cost: exponential in the worst case;
O(k^2 n) words of memory for the stack of matrices.
"""
k, e1 = g1
n, e2 = g2
if k > n:
return
if k == 0:
yield []
return
adj1, adj2 = _adj(k, e1), _adj(n, e2)
nbmask2 = [sum(1 << y for y in adj2[j]) for j in range(n)]
lab1 = labels1 if labels1 is not None else [0] * k
lab2 = labels2 if labels2 is not None else [0] * n
# @line L1
m0 = [sum(1 << j for j in range(n) if lab1[i] == lab2[j] and len(adj1[i]) <= len(adj2[j])) for i in range(k)]
# @line L2
if not refine(m0, adj1, nbmask2):
return
# @line L3
stack: list[tuple[int, list[int], int]] = [(0, m0, m0[0])]
while stack:
i, m, todo = stack.pop()
# @line L4
if todo == 0:
continue
low = todo & -todo
j = low.bit_length() - 1
stack.append((i, m, todo ^ low))
# @line L5
m2 = list(m)
m2[i] = low
for r in range(i + 1, k):
m2[r] &= ~low
# @line L6
if not refine(m2, adj1, nbmask2):
continue
# @line L7
if i == k - 1:
f = [m2[r].bit_length() - 1 for r in range(k)]
if all(f[y] in adj2[f[x]] for x, y in e1) and (
not induced or all((f[b] in adj2[f[a]]) == (b in adj1[a])
for a in range(k) for b in range(a + 1, k))):
yield f
continue
stack.append((i + 1, m2, m2[i + 1]))
def ullmann_count(g1: Graph, g2: Graph, induced: bool = False) -> int:
"""Number of embeddings. Cost: as ullmann_matches over the whole search."""
return sum(1 for _ in ullmann_matches(g1, g2, induced))
def ullmann_isomorphic(g1: Graph, g2: Graph) -> bool:
"""Graph isomorphism as an induced embedding between graphs of equal size. Cost: as ullmann_matches."""
if g1[0] != g2[0] or len(g1[1]) != len(g2[1]):
return False
return next(ullmann_matches(g1, g2, True), None) is not None
test_ullmann_algorithm.py 117 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/ullmann-algorithm/. The authors are listed in prov/GMKCZG.jsonl.
import itertools
import random
from ullmann_algorithm import ullmann_count, ullmann_isomorphic, ullmann_matches
Edges = list[tuple[int, int]]
def brute(k: int, e1: Edges, n: int, e2: Edges, induced: bool,
l1: list[int] | None = None, l2: list[int] | None = None) -> set[tuple[int, ...]]:
l1 = l1 or [0] * k
l2 = l2 or [0] * n
s1 = {frozenset(e) for e in e1}
s2 = {frozenset(e) for e in e2}
out = set()
for f in itertools.permutations(range(n), k):
if any(l1[a] != l2[f[a]] for a in range(k)):
continue
good = True
for a, b in itertools.combinations(range(k), 2):
x = frozenset((a, b)) in s1
y = frozenset((f[a], f[b])) in s2
if (x and not y) or (induced and y and not x):
good = False
break
if good:
out.add(f)
return out
def rand_graph(rng: random.Random, n: int, p: float) -> Edges:
return [(u, v) for u in range(n) for v in range(u + 1, n) if rng.random() < p]
def rook4() -> tuple[int, Edges]:
c = [(i, j) for i in range(4) for j in range(4)]
return 16, [(a, b) for a in range(16) for b in range(a + 1, 16) if c[a][0] == c[b][0] or c[a][1] == c[b][1]]
def shrikhande() -> tuple[int, Edges]:
c = [(i, j) for i in range(4) for j in range(4)]
d = {(0, 1), (0, 3), (1, 0), (3, 0), (1, 1), (3, 3)}
return 16, [(a, b) for a in range(16) for b in range(a + 1, 16)
if ((c[b][0] - c[a][0]) % 4, (c[b][1] - c[a][1]) % 4) in d]
def petersen() -> tuple[int, Edges]:
v = list(itertools.combinations(range(5), 2))
return 10, [(i, j) for i in range(10) for j in range(i + 1, 10) if not set(v[i]) & set(v[j])]
def test_page_example() -> None:
paw = (4, [(0, 1), (1, 2), (2, 0), (2, 3)])
host = (6, [(0, 3), (1, 2), (1, 4), (1, 5), (2, 3), (4, 5)])
assert list(ullmann_matches(paw, host)) == [[4, 5, 1, 2], [5, 4, 1, 2]]
assert ullmann_count(paw, host, True) == 2
c5 = (5, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
assert ullmann_count((3, [(0, 1), (1, 2)]), c5) == 10
assert ullmann_count(c5, petersen()) == 120
assert ullmann_count((3, [(0, 1), (1, 2), (0, 2)]), petersen()) == 0
def test_edge_cases() -> None:
assert list(ullmann_matches((0, []), (0, []))) == [[]]
assert ullmann_count((1, []), (3, [])) == 3
assert ullmann_count((3, []), (2, [])) == 0
assert ullmann_count((2, [(0, 1)]), (3, [])) == 0
assert ullmann_count((2, []), (2, [(0, 1)]), True) == 0
assert ullmann_count((2, []), (2, [(0, 1)])) == 2
assert not ullmann_isomorphic((3, [(0, 1)]), (4, [(0, 1)]))
def test_regular_and_strongly_regular_pairs() -> None:
c6 = (6, [(i, (i + 1) % 6) for i in range(6)])
two_k3 = (6, [(0, 1), (1, 2), (0, 2), (3, 4), (4, 5), (3, 5)])
assert not ullmann_isomorphic(c6, two_k3)
assert ullmann_count(c6, two_k3) == 0
assert ullmann_count(two_k3, c6) == 0
r, s = rook4(), shrikhande()
assert not ullmann_isomorphic(r, s)
assert ullmann_count(r, r, True) == 1152
assert ullmann_count(s, s, True) == 192
k4 = (4, [(a, b) for a in range(4) for b in range(a + 1, 4)])
assert ullmann_count(k4, r) == 8 * 24 and ullmann_count(k4, s) == 0
def test_random_against_brute_force() -> None:
rng = random.Random(20261105)
for trial in range(700):
n = rng.randint(1, 7)
k = rng.randint(1, min(n, 5))
p = rng.choice([0.25, 0.5, 0.75])
e2 = rand_graph(rng, n, p)
e1 = rand_graph(rng, k, p)
induced = trial % 2 == 1
l1 = l2 = None
if trial % 5 == 0:
l1 = [rng.randrange(2) for _ in range(k)]
l2 = [rng.randrange(2) for _ in range(n)]
got = [tuple(f) for f in ullmann_matches((k, e1), (n, e2), induced, l1, l2)]
assert len(got) == len(set(got))
assert set(got) == brute(k, e1, n, e2, induced, l1, l2)
def test_isomorphism_random() -> None:
rng = random.Random(11)
for _ in range(200):
n = rng.randint(1, 7)
e = rand_graph(rng, n, 0.5)
perm = list(range(n))
rng.shuffle(perm)
assert ullmann_isomorphic((n, e), (n, [(perm[u], perm[v]) for u, v in e]))
other = rand_graph(rng, n, 0.5)
assert ullmann_isomorphic((n, e), (n, other)) == bool(brute(n, e, n, other, True))
What the next level needs
- the tests did not run in this build