Hash-based adjacency in Python
Neighbour sets stored in hash tables for expected constant-time adjacency tests.
- File
hash_based_adjacency.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/hash-based-adjacency/. The authors are listed in prov/NZ1XVJ.jsonl.
from collections.abc import Hashable
class HashAdjacency:
"""A graph whose vertices are hashable keys and whose neighbour sets are hash sets.
adjacent, add_edge, remove_edge and add_vertex take O(1) expected time,
neighbors takes O(d(u) + 1) and remove_vertex O(d(x) + 1), with in-sets
kept for directed graphs. The space is Theta(n + m).
"""
def __init__(self, directed: bool = False) -> None:
self.directed = directed
self.succ: dict[Hashable, set[Hashable]] = {} # @line L1
self.pred: dict[Hashable, set[Hashable]] = {}
def add_vertex(self, x: Hashable) -> None:
if x not in self.succ: # @line L2
self.succ[x] = set()
if self.directed:
self.pred[x] = set()
def add_edge(self, u: Hashable, v: Hashable) -> None:
if not self.directed and u == v:
raise ValueError("an undirected graph has no self-loops")
self.add_vertex(u) # @line L3
self.add_vertex(v)
self.succ[u].add(v) # @line L4
if self.directed: # @line L5
self.pred[v].add(u)
else:
self.succ[v].add(u)
def remove_edge(self, u: Hashable, v: Hashable) -> None:
if u not in self.succ or v not in self.succ:
return
self.succ[u].discard(v) # @line L6
if self.directed: # @line L7
self.pred[v].discard(u)
else:
self.succ[v].discard(u)
def adjacent(self, u: Hashable, v: Hashable) -> bool:
return u in self.succ and v in self.succ[u] # @line L8
def neighbors(self, u: Hashable) -> list[Hashable]:
return list(self.succ[u]) # @line L9
def in_neighbors(self, v: Hashable) -> list[Hashable]:
return list(self.pred[v] if self.directed else self.succ[v])
def degree(self, u: Hashable) -> int:
return len(self.succ[u]) # @line L10
def remove_vertex(self, x: Hashable) -> None:
if x not in self.succ:
return
for y in list(self.succ[x]): # @line L11
(self.pred if self.directed else self.succ)[y].discard(x)
if self.directed:
for y in list(self.pred[x]): # @line L12
self.succ[y].discard(x)
del self.pred[x]
del self.succ[x] # @line L13
def vertices(self) -> list[Hashable]:
return list(self.succ)
def edges(self) -> set[tuple[Hashable, Hashable]] | set[frozenset[Hashable]]:
if self.directed:
return {(u, v) for u, s in self.succ.items() for v in s}
return {frozenset((u, v)) for u, s in self.succ.items() for v in s}
def check_invariant(self) -> None:
keys = set(self.succ)
if self.directed:
assert set(self.pred) == keys
for u, s in self.succ.items():
assert s <= keys
for v in s:
if self.directed:
assert u in self.pred[v]
else:
assert v != u and u in self.succ[v]
if self.directed:
for v, p in self.pred.items():
assert p <= keys
for u in p:
assert v in self.succ[u]
test_hash_based_adjacency.py 106 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/hash-based-adjacency/. The authors are listed in prov/NZ1XVJ.jsonl.
import random
import pytest
from hash_based_adjacency import HashAdjacency
def table(g: HashAdjacency) -> dict:
return {u: sorted(s) for u, s in g.succ.items()}
def test_example() -> None:
g = HashAdjacency()
for x in range(4):
g.add_vertex(x)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(3, 1)
assert table(g) == {0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1]}
g.add_edge(1, 0)
assert table(g) == {0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1]}
assert g.adjacent(0, 2) and not g.adjacent(0, 3)
assert sorted(g.neighbors(1)) == [0, 2, 3] and g.degree(1) == 3
g.remove_edge(1, 0)
assert table(g) == {0: [2], 1: [2, 3], 2: [0, 1], 3: [1]}
g.remove_vertex(2)
assert table(g) == {0: [], 1: [3], 3: [1]}
g.check_invariant()
def test_directed_example() -> None:
g = HashAdjacency(directed=True)
for u, v in [(0, 1), (0, 2), (1, 2), (2, 3), (3, 1), (3, 4)]:
g.add_edge(u, v)
assert table(g) == {0: [1, 2], 1: [2], 2: [3], 3: [1, 4], 4: []}
assert {v: sorted(p) for v, p in g.pred.items()} == {0: [], 1: [0, 3], 2: [0, 1], 3: [2], 4: [3]}
g.remove_vertex(3)
assert table(g) == {0: [1, 2], 1: [2], 2: [], 4: []}
assert {v: sorted(p) for v, p in g.pred.items()} == {0: [], 1: [0], 2: [0, 1], 4: []}
g.check_invariant()
def test_edge_cases() -> None:
g = HashAdjacency()
assert g.edges() == set() and not g.adjacent("a", "b")
with pytest.raises(ValueError):
g.add_edge("a", "a")
g.add_edge("a", ("b", 1))
assert g.adjacent(("b", 1), "a")
g.remove_edge("a", "zzz")
g.remove_vertex("zzz")
d = HashAdjacency(directed=True)
d.add_edge("x", "x")
assert d.adjacent("x", "x") and d.in_neighbors("x") == ["x"]
d.remove_vertex("x")
assert d.vertices() == [] and d.pred == {}
d.check_invariant()
@pytest.mark.parametrize("directed", [False, True])
def test_random_against_set_model(directed: bool) -> None:
rng = random.Random(1117)
for _ in range(300):
g = HashAdjacency(directed)
verts: set[int] = set()
model: set = set()
def key(a: int, b: int):
return (a, b) if directed else frozenset((a, b))
for _ in range(rng.randint(0, 50)):
op = rng.random()
u, v = rng.randrange(8), rng.randrange(8)
if op < 0.1:
g.add_vertex(u)
verts.add(u)
elif op < 0.15:
g.remove_vertex(u)
verts.discard(u)
model = {e for e in model if u not in (e if not directed else e)}
elif op < 0.6:
if not directed and u == v:
continue
g.add_edge(u, v)
verts |= {u, v}
model.add(key(u, v))
elif op < 0.8:
g.remove_edge(u, v)
model.discard(key(u, v))
else:
assert g.adjacent(u, v) == (key(u, v) in model)
g.check_invariant()
assert set(g.vertices()) == verts
assert g.edges() == model
for u in verts:
if directed:
nb = {b for a, b in model if a == u}
ins = {a for a, b in model if b == u}
assert set(g.in_neighbors(u)) == ins
else:
nb = {x for e in model if u in e for x in e if x != u}
assert set(g.neighbors(u)) == nb and g.degree(u) == len(nb)
What the next level needs
- the tests did not run in this build