Batagelj-Zaversnik algorithm in Python
Computes all core numbers in O(m) time by peeling minimum-degree nodes.
- File
batagelj_zaversnik_algorithm.py, 50 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/batagelj-zaversnik-algorithm/. The authors are listed in prov/HTAYEM.jsonl.
def batagelj_zaversnik_algorithm(adj: list[list[int]]) -> list[int]:
"""Return the core number of each vertex of a simple undirected graph.
The vertices are 0 .. n-1 and adj[v] lists the neighbours of v; each edge
{u, v} is in both lists, with no self-loops and no repeated edges. The core
number of v is the largest k such that v lies in a subgraph in which every
vertex has degree at least k. Vertices are kept in an array sorted by their
current degree, with one bucket per degree, so the time is O(n + m) and the
extra space is O(n).
"""
n = len(adj)
deg = [len(adj[v]) for v in range(n)] # @line L1
md = max(deg, default=0) # @line L2
bucket = [0] * (md + 1) # @line L3: bucket[d] counts the vertices of degree d
for v in range(n):
bucket[deg[v]] += 1
start = 0 # @line L4: bucket[d] becomes the first index of degree d
for d in range(md + 1):
num = bucket[d]
bucket[d] = start
start += num
pos = [0] * n # @line L5: place the vertices in vert, sorted by degree
vert = [0] * n
for v in range(n):
pos[v] = bucket[deg[v]]
vert[pos[v]] = v
bucket[deg[v]] += 1
for d in range(md, 0, -1): # @line L6: restore the bucket starts
bucket[d] = bucket[d - 1]
bucket[0] = 0
for i in range(n): # @line L7
v = vert[i] # @line L8: v has the least current degree among vert[i:]
for u in adj[v]: # @line L9
if deg[u] > deg[v]: # @line L10
du = deg[u] # @line L11: w is the first vertex of the bucket of u
pu = pos[u]
pw = bucket[du]
w = vert[pw]
if u != w: # @line L12: swap u and w
pos[u] = pw
vert[pu] = w
pos[w] = pu
vert[pw] = u
bucket[du] += 1 # @line L13: u moves to the bucket of degree du - 1
deg[u] -= 1
return deg # @line L14
test_batagelj_zaversnik_algorithm.py 66 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/batagelj-zaversnik-algorithm/. The authors are listed in prov/HTAYEM.jsonl.
import random
from batagelj_zaversnik_algorithm import batagelj_zaversnik_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(adj: list[list[int]]) -> list[int]:
"""Core numbers from the definition: the best minimum degree over all vertex sets."""
n = len(adj)
core = [0] * n
for mask in range(1, 1 << n):
members = [v for v in range(n) if mask >> v & 1]
low = min(sum(1 for u in adj[v] if mask >> u & 1) for v in members)
for v in members:
if low > core[v]:
core[v] = low
return core
EXAMPLE = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6), (4, 7)]
def test_example() -> None:
adj = undirected(9, EXAMPLE)
assert batagelj_zaversnik_algorithm(adj) == [3, 3, 3, 3, 2, 2, 2, 1, 0]
def test_edges() -> None:
assert batagelj_zaversnik_algorithm([]) == []
assert batagelj_zaversnik_algorithm([[]]) == [0]
assert batagelj_zaversnik_algorithm(undirected(2, [(0, 1)])) == [1, 1]
path = undirected(5, [(0, 1), (1, 2), (2, 3), (3, 4)])
assert batagelj_zaversnik_algorithm(path) == [1] * 5
k5 = undirected(5, [(u, v) for u in range(5) for v in range(u + 1, 5)])
assert batagelj_zaversnik_algorithm(k5) == [4] * 5
star = undirected(6, [(0, v) for v in range(1, 6)])
assert batagelj_zaversnik_algorithm(star) == [1] * 6
def test_long_path_no_recursion() -> None:
n = 100000
adj = undirected(n, [(i, i + 1) for i in range(n - 1)])
assert batagelj_zaversnik_algorithm(adj) == [1] * n
def test_random_against_oracle() -> None:
rng = random.Random(7713)
for _ in range(700):
n = rng.randint(1, 10)
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)
assert batagelj_zaversnik_algorithm(adj) == oracle(adj)
What the next level needs
- the tests did not run in this build