Adjacency list in Python
Array indexed by vertex, each entry listing that vertex's neighbours; space Θ(V+E).
- File
adjacency_list.py, 95 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/adjacency-list/. The authors are listed in prov/3JK4BH.jsonl.
class AdjacencyList:
"""A graph on the vertices 0, ..., n - 1 stored as one Python list per vertex.
adj[u] holds the neighbours of u (out-neighbours for a directed graph), in
no fixed order. add_edge and add_vertex take O(1) amortized time,
neighbors takes O(d(u)), adjacent takes O(d(u)) and remove_edge takes
O(d(u) + d(v)). The space is Theta(n + m).
"""
def __init__(self, n: int, directed: bool = False) -> None:
if n < 0:
raise ValueError("n must be at least 0")
self.n = n
self.directed = directed
self.adj: list[list[int]] = [[] for _ in range(n)] # @line L1
def _check(self, u: int, v: int) -> None:
if not (0 <= u < self.n and 0 <= v < self.n):
raise IndexError("vertex out of range")
def add_edge(self, u: int, v: int) -> None:
"""Add the edge of u and v, which the caller knows to be absent."""
self._check(u, v)
if not self.directed and u == v:
raise ValueError("an undirected graph has no self-loops")
self.adj[u].append(v) # @line L2
if not self.directed:
self.adj[v].append(u) # @line L3
def add_edge_if_absent(self, u: int, v: int) -> bool:
if self.adjacent(u, v):
return False
self.add_edge(u, v)
return True
@staticmethod
def _delete(lst: list[int], x: int) -> None:
for i, y in enumerate(lst): # @line L6
if y == x:
lst[i] = lst[-1] # @line L7
lst.pop() # @line L8
return
def remove_edge(self, u: int, v: int) -> None:
self._check(u, v)
self._delete(self.adj[u], v) # @line L4
if not self.directed and u != v:
self._delete(self.adj[v], u) # @line L5
def adjacent(self, u: int, v: int) -> bool:
self._check(u, v)
return v in self.adj[u] # @line L9
def neighbors(self, u: int) -> list[int]:
self._check(u, u)
return list(self.adj[u]) # @line L10
def degree(self, u: int) -> int:
self._check(u, u)
return len(self.adj[u]) # @line L11
def add_vertex(self) -> int:
self.adj.append([]) # @line L12
self.n += 1 # @line L13
return self.n - 1
def edges(self) -> list[tuple[int, int]]:
"""Each edge once: (u, v) for directed, (u, v) with u < v for undirected."""
return [
(u, v)
for u in range(self.n)
for v in self.adj[u]
if self.directed or u < v
]
def transpose(self) -> "AdjacencyList":
t = AdjacencyList(self.n, self.directed)
for u in range(self.n):
for v in self.adj[u]:
t.adj[v].append(u)
return t
def check_invariant(self) -> None:
assert len(self.adj) == self.n
for u in range(self.n):
assert len(set(self.adj[u])) == len(self.adj[u])
for v in self.adj[u]:
assert 0 <= v < self.n
if not self.directed:
assert v != u
assert u in self.adj[v]
test_adjacency_list.py 99 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/adjacency-list/. The authors are listed in prov/3JK4BH.jsonl.
import random
import pytest
from adjacency_list import AdjacencyList
def test_example() -> None:
g = AdjacencyList(4)
assert g.adj == [[], [], [], []]
g.add_edge(0, 1)
assert g.adj == [[1], [0], [], []]
g.add_edge(1, 2)
assert g.adj == [[1], [0, 2], [1], []]
g.add_edge(2, 0)
assert g.adj == [[1, 2], [0, 2], [1, 0], []]
g.add_edge(3, 1)
assert g.adj == [[1, 2], [0, 2, 3], [1, 0], [1]]
assert g.adjacent(0, 2)
assert not g.adjacent(0, 3)
assert g.neighbors(1) == [0, 2, 3]
assert g.degree(1) == 3
g.remove_edge(1, 0)
assert g.adj == [[2], [3, 2], [1, 0], [1]]
assert g.add_vertex() == 4
assert g.adj == [[2], [3, 2], [1, 0], [1], []]
g.check_invariant()
def test_directed_example() -> None:
g = AdjacencyList(5, directed=True)
for u, v in [(0, 1), (0, 2), (1, 2), (2, 3), (3, 1), (3, 4)]:
g.add_edge(u, v)
assert g.adj == [[1, 2], [2], [3], [1, 4], []]
assert g.transpose().adj == [[], [0, 3], [0, 1], [2], [3]]
def test_edge_cases() -> None:
g = AdjacencyList(0)
assert g.edges() == []
assert g.add_vertex() == 0
assert g.neighbors(0) == []
with pytest.raises(ValueError):
g.add_edge(0, 0)
with pytest.raises(ValueError):
AdjacencyList(-1)
d = AdjacencyList(1, directed=True)
d.add_edge(0, 0)
assert d.adjacent(0, 0) and d.degree(0) == 1
d.remove_edge(0, 0)
assert d.adj == [[]]
with pytest.raises(IndexError):
d.add_edge(0, 1)
u = AdjacencyList(2)
assert u.add_edge_if_absent(0, 1)
assert not u.add_edge_if_absent(1, 0)
u.remove_edge(0, 1)
u.remove_edge(0, 1)
assert u.edges() == []
@pytest.mark.parametrize("directed", [False, True])
def test_random_against_set_model(directed: bool) -> None:
rng = random.Random(3104)
for _ in range(300):
n = rng.randint(1, 7)
g = AdjacencyList(n, directed)
model: set[tuple[int, int]] = set()
def key(a: int, b: int) -> tuple[int, int]:
return (a, b) if directed else (min(a, b), max(a, b))
for _ in range(rng.randint(0, 40)):
op = rng.random()
u, v = rng.randrange(n), rng.randrange(n)
if op < 0.05:
assert g.add_vertex() == n
n += 1
elif op < 0.5:
if not directed and u == v:
continue
assert g.add_edge_if_absent(u, v) == (key(u, v) not in model)
model.add(key(u, v))
elif op < 0.75:
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 sorted(g.edges()) == sorted(model)
for u in range(n):
nb = {b for a, b in model if a == u}
if not directed:
nb |= {a for a, b in model if b == u}
assert sorted(g.neighbors(u)) == sorted(nb)
assert g.degree(u) == len(nb)
What the next level needs
- the tests did not run in this build