Compact-forward algorithm in Python
Counts triangles in O(m^1.5) by orienting edges along a degree ordering.
- File
compact_forward_algorithm.py, 45 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/compact-forward-algorithm/. The authors are listed in prov/R006RZ.jsonl.
def compact_forward_algorithm(adj: list[list[int]]) -> list[tuple[int, int, int]]:
"""List every triangle of a simple undirected graph exactly once.
The vertices are 0 .. n-1 and adj[v] lists the neighbours of v; each edge is
in both lists, with no self-loops and no repeated edges. Each triangle is
returned as (a, v, u) with eta(a) < eta(v) < eta(u), where eta numbers the
vertices by non-increasing degree, ties by vertex number. The number of
triangles is the length of the list. Time O(m^(3/2)) after the O(n + m)
preparation, extra space O(n + m).
"""
n = len(adj)
order = sorted(range(n), key=lambda v: (-len(adj[v]), v)) # @line L1
eta = [0] * n
for rank, v in enumerate(order):
eta[v] = rank
nbr: list[list[int]] = [[] for _ in range(n)] # @line L2: lists sorted by eta
for w in order:
for x in adj[w]:
nbr[x].append(w)
triangles: list[tuple[int, int, int]] = [] # @line L3
for v in order: # @line L4
ev = eta[v]
lv = nbr[v]
for u in lv: # @line L5
if eta[u] <= ev:
continue
lu = nbr[u]
i = 0 # @line L6
j = 0
while i < len(lv) and j < len(lu) and eta[lv[i]] < ev and eta[lu[j]] < ev: # @line L7
a = lv[i] # @line L8
b = lu[j]
if eta[a] < eta[b]: # @line L9
i += 1
elif eta[a] > eta[b]: # @line L10
j += 1
else: # @line L11
triangles.append((a, v, u))
i += 1
j += 1
return triangles # @line L12
test_compact_forward_algorithm.py 62 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/compact-forward-algorithm/. The authors are listed in prov/R006RZ.jsonl.
import random
from compact_forward_algorithm import compact_forward_algorithm
def undirected(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 oracle(n: int, edges: list[tuple[int, int]]) -> set[frozenset[int]]:
"""All triangles, by testing every triple of vertices."""
es = {frozenset(e) for e in edges}
out: set[frozenset[int]] = set()
for a in range(n):
for b in range(a + 1, n):
for c in range(b + 1, n):
if {frozenset((a, b)), frozenset((a, c)), frozenset((b, c))} <= es:
out.add(frozenset((a, b, c)))
return out
EXAMPLE = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)]
def test_example() -> None:
tri = compact_forward_algorithm(undirected(7, EXAMPLE))
assert tri == [(1, 2, 3), (1, 2, 0), (4, 5, 6)]
def test_edges() -> None:
assert compact_forward_algorithm([]) == []
assert compact_forward_algorithm([[]]) == []
assert compact_forward_algorithm(undirected(3, [(0, 1), (1, 2)])) == []
assert compact_forward_algorithm(undirected(3, [(0, 1), (1, 2), (0, 2)])) == [(0, 1, 2)]
k5 = [(u, v) for u in range(5) for v in range(u + 1, 5)]
assert len(compact_forward_algorithm(undirected(5, k5))) == 10
star = undirected(6, [(0, v) for v in range(1, 6)])
assert compact_forward_algorithm(star) == []
def test_random_against_oracle() -> None:
rng = random.Random(31337)
for _ in range(700):
n = rng.randint(1, 11)
p = rng.random()
edges = [(u, v) for u in range(n) for v in range(u + 1, n) if rng.random() < p]
rng.shuffle(edges)
adj = undirected(n, edges)
for lst in adj:
rng.shuffle(lst)
tri = compact_forward_algorithm(adj)
sets = [frozenset(t) for t in tri]
assert len(sets) == len(set(sets))
assert all(len(s) == 3 for s in sets)
assert set(sets) == oracle(n, edges)
What the next level needs
- the tests did not run in this build