Triangle listing by degree ordering in Python
Orient each edge from lower to higher degree and intersect neighborhoods; runs in O(m^(3/2)) time.
- File
triangle_listing_by_degree.py, 42 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/triangle-listing-by-degree/. The authors are listed in prov/94JZ51.jsonl.
def triangles_by_degree(n: int, edges: list[tuple[int, int]]) -> list[tuple[int, int, int]]:
"""List every triangle of a simple undirected graph exactly once.
The vertices are 0 .. n-1 and edges is a list of pairs {u, v} with u != v
and no repeated edge. Each triangle is returned once, as (u, v, w) with
rank(u) < rank(v) < rank(w), where rank(x) = (degree(x), x).
Time O(n + m^(3/2)) and O(n + a(G) m); extra space O(n + m).
"""
adj: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
if u == v or not (0 <= u < n and 0 <= v < n):
raise ValueError("bad edge")
adj[u].append(v)
adj[v].append(u)
d = [len(adj[v]) for v in range(n)] # @line L1
out = [[w for w in adj[v] if (d[v], v) < (d[w], w)] for v in range(n)] # @line L2
mark = [False] * n # @line L3
tri: list[tuple[int, int, int]] = [] # @line L4
for u in range(n): # @line L5
for v in out[u]: # @line L6
mark[v] = True
for v in out[u]: # @line L7
for w in out[v]: # @line L8
if mark[w]: # @line L9
tri.append((u, v, w))
for v in out[u]: # @line L10
mark[v] = False
return tri # @line L11
def local_counts(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""Return t(v), the number of triangles that contain each vertex v."""
t = [0] * n
for a, b, c in triangles_by_degree(n, edges):
t[a] += 1
t[b] += 1
t[c] += 1
return t
test_triangle_listing_by_degree.py 52 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/triangle-listing-by-degree/. The authors are listed in prov/94JZ51.jsonl.
import itertools
import random
from triangle_listing_by_degree import local_counts, triangles_by_degree
def brute(n: int, edges: list[tuple[int, int]]) -> set[frozenset[int]]:
e = {frozenset(x) for x in edges}
return {
frozenset(t)
for t in itertools.combinations(range(n), 3)
if all(frozenset(p) in e for p in itertools.combinations(t, 2))
}
def test_example() -> None:
edges = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 5), (2, 3), (2, 4), (3, 4)]
tri = triangles_by_degree(6, edges)
assert len(tri) == 6
assert {frozenset(t) for t in tri} == brute(6, edges)
assert local_counts(6, edges) == [5, 2, 4, 3, 3, 1]
assert (3, 4, 2) in tri and (5, 1, 0) in tri
def test_edges() -> None:
assert triangles_by_degree(0, []) == []
assert triangles_by_degree(1, []) == []
assert triangles_by_degree(3, [(0, 1), (1, 2)]) == []
assert len(triangles_by_degree(3, [(0, 1), (1, 2), (0, 2)])) == 1
k = 7
clique = list(itertools.combinations(range(k), 2))
assert len(triangles_by_degree(k, clique)) == 35
star = [(0, i) for i in range(1, 9)]
assert triangles_by_degree(9, star) == []
def test_random_against_brute_force() -> None:
rng = random.Random(9071)
for _ in range(600):
n = rng.randint(0, 11)
pairs = list(itertools.combinations(range(n), 2))
p = rng.random()
edges = [e if rng.random() < 0.5 else (e[1], e[0]) for e in pairs if rng.random() < p]
rng.shuffle(edges)
tri = triangles_by_degree(n, edges)
sets = [frozenset(t) for t in tri]
assert len(sets) == len(set(sets))
assert set(sets) == brute(n, edges)
assert all(len(s) == 3 for s in sets)
What the next level needs
- the tests did not run in this build
Read the full page about Triangle listing by degree ordering