Lexicographic breadth-first search in Python
A BFS variant that orders vertices by lexicographic labels, used in chordal graph recognition.
- File
lexicographic_bfs.py, 70 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/lexicographic-bfs/. The authors are listed in prov/SYYZ0S.jsonl.
class _Class:
"""One class of the partition: an ordered set of vertices in a doubly linked list."""
__slots__ = ("items", "prev", "next", "stamp", "split")
def __init__(self) -> None:
self.items: dict[int, None] = {}
self.prev: "_Class | None" = None
self.next: "_Class | None" = None
self.stamp = -1
self.split: "_Class | None" = None
def lexicographic_bfs(adj: list[list[int]]) -> list[int]:
"""Return a lexicographic breadth-first search ordering of a simple undirected graph.
The graph has the vertices 0 .. n-1 and the adjacency lists adj, with each edge in
both lists and no loops or parallel edges. The search starts at vertex 0. Ties are
broken by taking the first vertex of the first class, where the first class starts
as 0 .. n-1 and a new class keeps the order in which its vertices were moved.
Partition refinement gives time O(n + m) and extra space O(n).
"""
n = len(adj)
if n == 0:
return []
head = _Class() # @line L1
head.items = dict.fromkeys(range(n))
cls: list[_Class | None] = [head] * n
order: list[int] = []
for i in range(n): # @line L2
first = head
assert first is not None
v = next(iter(first.items)) # @line L3
del first.items[v]
cls[v] = None
if not first.items:
head = first.next
if head is not None:
head.prev = None
order.append(v) # @line L4
for w in adj[v]: # @line L5
d = cls[w]
if d is None:
continue
if d.stamp != i: # @line L6
new = _Class() # @line L7
new.prev, new.next = d.prev, d
if d.prev is not None:
d.prev.next = new
else:
head = new
d.prev = new
d.stamp, d.split = i, new
new = d.split
assert new is not None
del d.items[w] # @line L8
new.items[w] = None
cls[w] = new
if not d.items:
if d.prev is not None:
d.prev.next = d.next
if d.next is not None:
d.next.prev = d.prev
if head is d:
head = d.next
return order # @line L9
test_lexicographic_bfs.py 131 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lexicographic-bfs/. The authors are listed in prov/SYYZ0S.jsonl.
import itertools
import random
from lexicographic_bfs import lexicographic_bfs
def make(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
adj: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
for lst in adj:
lst.sort()
return adj
def is_lexbfs(adj: list[list[int]], order: list[int]) -> bool:
"""Check the definition: each chosen vertex has a largest label at its step.
The label of an unvisited vertex is the set of its visited neighbours; a label is
larger if the earliest visited vertex in the symmetric difference belongs to it.
"""
n = len(adj)
if sorted(order) != list(range(n)) or (n and order[0] != 0):
return False
pos = {v: i for i, v in enumerate(order)}
nbr = [set(lst) for lst in adj]
for i, v in enumerate(order):
def key(x: int) -> list[int]:
return sorted(pos[u] for u in nbr[x] if pos[u] < i)
for x in order[i + 1 :]:
a, b = set(key(v)), set(key(x))
diff = sorted(a ^ b)
if diff and diff[0] in b:
return False
return True
def reverse_is_peo(adj: list[list[int]], order: list[int]) -> bool:
pos = {v: i for i, v in enumerate(order)}
nbr = [set(lst) for lst in adj]
for v in order:
earlier = [u for u in adj[v] if pos[u] < pos[v]]
if any(y not in nbr[x] for x, y in itertools.combinations(earlier, 2)):
return False
return True
def is_chordal(adj: list[list[int]]) -> bool:
"""Independent oracle: repeatedly delete a simplicial vertex."""
alive = set(range(len(adj)))
nbr = [set(lst) for lst in adj]
while alive:
for v in alive:
nv = nbr[v] & alive
if all(y in nbr[x] for x, y in itertools.combinations(nv, 2)):
alive.remove(v)
break
else:
return False
return True
EXAMPLE = [(0, 3), (1, 2), (1, 3), (1, 6), (2, 6), (3, 4), (3, 6), (4, 5), (4, 6), (5, 6)]
def test_example() -> None:
adj = make(7, EXAMPLE)
order = lexicographic_bfs(adj)
assert order == [0, 3, 1, 6, 4, 2, 5]
assert reverse_is_peo(adj, order)
def test_four_cycle() -> None:
adj = make(4, [(0, 1), (1, 2), (2, 3), (3, 0)])
order = lexicographic_bfs(adj)
assert order == [0, 1, 3, 2]
assert not reverse_is_peo(adj, order)
def test_small_cases() -> None:
assert lexicographic_bfs([]) == []
assert lexicographic_bfs([[]]) == [0]
assert lexicographic_bfs([[], [], []]) == [0, 1, 2]
assert lexicographic_bfs(make(3, [(1, 2)])) == [0, 1, 2]
assert lexicographic_bfs(make(3, [(0, 2)])) == [0, 2, 1]
def test_long_path() -> None:
n = 100000
adj = make(n, [(i, i + 1) for i in range(n - 1)])
order = lexicographic_bfs(adj)
assert order == list(range(n))
assert reverse_is_peo(adj, order)
def random_chordal(rng: random.Random, n: int) -> list[tuple[int, int]]:
edges: set[tuple[int, int]] = set()
for v in range(1, n):
if rng.random() < 0.15:
continue
clique = [rng.randrange(v)]
for w in range(v):
if w not in clique and rng.random() < 0.5:
if all((min(w, x), max(w, x)) in edges for x in clique):
clique.append(w)
edges.update((x, v) for x in clique)
perm = list(range(n))
rng.shuffle(perm)
return [(perm[a], perm[b]) for a, b in edges]
def test_random_against_definition_and_chordality() -> None:
rng = random.Random(1976)
for trial in range(600):
n = rng.randint(1, 9)
if trial % 2 == 0:
edges = random_chordal(rng, n)
else:
pairs = [(a, b) for a in range(n) for b in range(a + 1, n)]
edges = [p for p in pairs if rng.random() < 0.4]
adj = make(n, edges)
for lst in adj:
rng.shuffle(lst)
order = lexicographic_bfs(adj)
assert is_lexbfs(adj, order)
assert reverse_is_peo(adj, order) == is_chordal(adj)
What the next level needs
- the tests did not run in this build