Edge list in Python
Array of all edges as vertex pairs (with weights if any); space Θ(E).
- File
edge_list.py, 89 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/edge-list/. The authors are listed in prov/SX5BWH.jsonl.
class EdgeList:
"""A graph on the vertices 0, ..., n - 1 stored as one list of pairs (u, v).
add_edge and add_vertex take O(1) amortized time; adjacent, neighbors,
degree and remove_edge scan the list in O(m) time. The space is Theta(m)
beyond the number n.
"""
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.edges_: list[tuple[int, int]] = [] # @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 _match(self, e: tuple[int, int], u: int, v: int) -> bool:
return e == (u, v) or (not self.directed and e == (v, u)) # @line L6
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.edges_.append((u, v)) # @line L2
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
def remove_edge(self, u: int, v: int) -> None:
self._check(u, v)
lst = self.edges_
for i, e in enumerate(lst): # @line L3
if self._match(e, u, v):
lst[i] = lst[-1] # @line L4
lst.pop() # @line L5
return
def adjacent(self, u: int, v: int) -> bool:
self._check(u, v)
return any(self._match(e, u, v) for e in self.edges_) # @line L7
def neighbors(self, u: int) -> list[int]:
self._check(u, u)
out = []
for x, y in self.edges_: # @line L8
if x == u: # @line L9
out.append(y)
elif not self.directed and y == u: # @line L10
out.append(x)
return out
def degree(self, u: int) -> int:
return len(self.neighbors(u)) # @line L11
def add_vertex(self) -> int:
self.n += 1 # @line L12
return self.n - 1
def edges(self) -> list[tuple[int, int]]:
return list(self.edges_)
def to_adjacency_lists(self) -> list[list[int]]:
adj: list[list[int]] = [[] for _ in range(self.n)]
for x, y in self.edges_:
adj[x].append(y)
if not self.directed:
adj[y].append(x)
return adj
def check_invariant(self) -> None:
seen = set()
for x, y in self.edges_:
assert 0 <= x < self.n and 0 <= y < self.n
k = (x, y) if self.directed else (min(x, y), max(x, y))
if not self.directed:
assert x != y
assert k not in seen
seen.add(k)
test_edge_list.py 97 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/edge-list/. The authors are listed in prov/SX5BWH.jsonl.
import random
import pytest
from edge_list import EdgeList
def test_example() -> None:
g = EdgeList(4)
assert g.edges() == []
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(3, 1)
assert g.edges() == [(0, 1), (1, 2), (2, 0), (3, 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.edges() == [(3, 1), (1, 2), (2, 0)]
assert g.add_vertex() == 4
assert g.n == 5
g.check_invariant()
def test_directed_example() -> None:
g = EdgeList(5, directed=True)
es = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 1), (3, 4)]
for u, v in es:
g.add_edge(u, v)
assert [g.degree(v) for v in range(5)] == [2, 1, 1, 2, 0]
assert g.to_adjacency_lists() == [[1, 2], [2], [3], [1, 4], []]
assert not g.adjacent(1, 0)
def test_edge_cases() -> None:
g = EdgeList(0)
assert g.add_vertex() == 0
assert g.neighbors(0) == []
with pytest.raises(ValueError):
g.add_edge(0, 0)
with pytest.raises(ValueError):
EdgeList(-1)
d = EdgeList(1, directed=True)
d.add_edge(0, 0)
assert d.neighbors(0) == [0]
d.remove_edge(0, 0)
assert d.edges() == []
with pytest.raises(IndexError):
d.adjacent(0, 3)
u = EdgeList(2)
assert u.add_edge_if_absent(1, 0)
assert not u.add_edge_if_absent(0, 1)
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(5847)
for _ in range(300):
n = rng.randint(1, 7)
g = EdgeList(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 {key(a, b) for a, b in g.edges()} == model
adj = g.to_adjacency_lists()
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) == sorted(adj[u])
What the next level needs
- the tests did not run in this build