Brandes' algorithm in Python
Computes all betweenness scores in O(nm) time using dependency accumulation.
- File
brandes_algorithm.py, 92 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/brandes-algorithm/. The authors are listed in prov/NYWQX3.jsonl.
import heapq
from collections import deque
def brandes_algorithm(adj: list[list[int]], undirected: bool = True) -> list[float]:
"""Return the betweenness centrality of each vertex of a graph without weights.
The vertices are 0 .. n-1 and adj[v] lists the out-neighbours of v. For an
undirected graph each edge is in both lists and undirected=True halves the
sums, so that each unordered pair of end vertices counts once. The graph need
not be connected; pairs with no path add nothing. Time O(nm), space O(n + m).
"""
n = len(adj)
cb = [0.0] * n # @line L1
for s in range(n): # @line L2
stack: list[int] = [] # @line L3
pred: list[list[int]] = [[] for _ in range(n)]
sigma = [0] * n
dist = [-1] * n # -1 stands for infinity
sigma[s] = 1 # @line L4
dist[s] = 0
q = deque([s])
while q: # @line L5
v = q.popleft() # @line L6
stack.append(v)
for w in adj[v]: # @line L7
if dist[w] < 0: # @line L8
dist[w] = dist[v] + 1
q.append(w)
if dist[w] == dist[v] + 1: # @line L9
sigma[w] += sigma[v]
pred[w].append(v)
delta = [0.0] * n # @line L10
while stack: # @line L11
w = stack.pop() # @line L12
for v in pred[w]: # @line L13
delta[v] += sigma[v] / sigma[w] * (1.0 + delta[w])
if w != s: # @line L14
cb[w] += delta[w]
if undirected: # @line L15
cb = [x / 2 for x in cb]
return cb # @line L16
def brandes_weighted(adj: list[list[tuple[int, float]]], undirected: bool = True) -> list[float]:
"""Betweenness with positive edge lengths: adj[v] lists pairs (w, length).
Dijkstra's algorithm replaces the breadth-first search; the stack receives the
vertices in the order in which they are settled. Time O(nm + n^2 log n) with a
binary heap.
"""
n = len(adj)
cb = [0.0] * n
for s in range(n):
stack: list[int] = []
pred: list[list[int]] = [[] for _ in range(n)]
sigma = [0] * n
dist: list[float | None] = [None] * n
done = [False] * n
sigma[s] = 1
dist[s] = 0
heap: list[tuple[float, int]] = [(0, s)]
while heap:
d, v = heapq.heappop(heap)
if done[v] or d != dist[v]:
continue
done[v] = True
stack.append(v)
for w, length in adj[v]:
nd = d + length
dw = dist[w]
if dw is None or nd < dw:
dist[w] = nd
sigma[w] = sigma[v]
pred[w] = [v]
heapq.heappush(heap, (nd, w))
elif nd == dw:
sigma[w] += sigma[v]
pred[w].append(v)
delta = [0.0] * n
while stack:
w = stack.pop()
for v in pred[w]:
delta[v] += sigma[v] / sigma[w] * (1.0 + delta[w])
if w != s:
cb[w] += delta[w]
if undirected:
cb = [x / 2 for x in cb]
return cb
test_brandes_algorithm.py 106 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/brandes-algorithm/. The authors are listed in prov/NYWQX3.jsonl.
import random
from fractions import Fraction
from brandes_algorithm import brandes_algorithm, brandes_weighted
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, arcs: dict[tuple[int, int], int], undirected_graph: bool) -> list[Fraction]:
"""Betweenness by listing every simple path between every ordered pair."""
out: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for (u, v), length in arcs.items():
out[u].append((v, length))
b = [Fraction(0)] * n
for s in range(n):
paths: dict[int, list[tuple[int, list[int]]]] = {}
todo: list[tuple[int, int, list[int]]] = [(s, 0, [s])]
while todo:
u, d, p = todo.pop()
if u != s:
paths.setdefault(u, []).append((d, p))
for v, length in out[u]:
if v not in p:
todo.append((v, d + length, p + [v]))
for t, lst in paths.items():
best = min(d for d, _ in lst)
short = [p for d, p in lst if d == best]
for p in short:
for x in p[1:-1]:
b[x] += Fraction(1, len(short))
if undirected_graph:
b = [x / 2 for x in b]
return b
def close(a: list[float], b: list[Fraction]) -> bool:
return len(a) == len(b) and all(abs(x - float(y)) < 1e-9 for x, y in zip(a, b))
EXAMPLE = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)]
def test_example() -> None:
assert close(brandes_algorithm(undirected(7, EXAMPLE)), [Fraction(x) for x in [0, 2, 2, 9, 8, 0, 0]])
def test_edges() -> None:
assert brandes_algorithm([]) == []
assert brandes_algorithm([[]]) == [0.0]
assert brandes_algorithm(undirected(3, [(0, 1), (1, 2)])) == [0.0, 1.0, 0.0]
star = undirected(5, [(0, v) for v in range(1, 5)])
assert brandes_algorithm(star) == [6.0, 0.0, 0.0, 0.0, 0.0]
c4 = undirected(4, [(0, 1), (1, 2), (2, 3), (3, 0)])
assert brandes_algorithm(c4) == [0.5, 0.5, 0.5, 0.5]
# directed path 0 -> 1 -> 2 and a separate vertex 3
assert brandes_algorithm([[1], [2], [], []], undirected=False) == [0.0, 1.0, 0.0, 0.0]
def test_weighted_example() -> None:
# 0-1-2 by two edges of length 1 against the direct edge 0-2 of length 2: a tie
adj: list[list[tuple[int, float]]] = [[(1, 1), (2, 2)], [(0, 1), (2, 1)], [(1, 1), (0, 2)]]
assert brandes_weighted(adj) == [0.0, 0.5, 0.0]
def test_long_path_no_recursion() -> None:
n = 400
cb = brandes_algorithm(undirected(n, [(i, i + 1) for i in range(n - 1)]))
assert all(cb[i] == i * (n - 1 - i) for i in range(n))
def test_random_against_oracle() -> None:
rng = random.Random(90210)
for _ in range(600):
n = rng.randint(1, 7)
directed = rng.random() < 0.5
weighted = rng.random() < 0.5
p = rng.random()
arcs: dict[tuple[int, int], int] = {}
for u in range(n):
for v in range(n):
if u == v or (not directed and v < u) or rng.random() >= p:
continue
length = rng.randint(1, 3) if weighted else 1
arcs[(u, v)] = length
if not directed:
arcs[(v, u)] = length
want = oracle(n, arcs, not directed)
adj: list[list[int]] = [[] for _ in range(n)]
adjw: list[list[tuple[int, float]]] = [[] for _ in range(n)]
for (u, v), length in arcs.items():
adj[u].append(v)
adjw[u].append((v, length))
for lst in adjw:
rng.shuffle(lst)
assert close(brandes_weighted(adjw, undirected=not directed), want)
if not weighted:
assert close(brandes_algorithm(adj, undirected=not directed), want)
What the next level needs
- the tests did not run in this build