Bipartiteness testing in Python
Decides whether a graph is two-colorable by running breadth-first search and checking whether any edge joins two vertices in the same layer.
- File
bipartiteness_testing.py, 52 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/bipartiteness-testing/. The authors are listed in prov/S82K2H.jsonl.
from collections import deque
from collections.abc import Sequence
def bipartiteness_testing(adj: Sequence[Sequence[int]]) -> tuple[bool, list[int]]:
"""Test whether the undirected graph with vertices 0 .. n-1 is bipartite.
adj[v] lists the neighbours of v; an undirected edge is in both lists, and a
self-loop {v, v} appears as v in adj[v]. Returns (True, color) with a proper
2-coloring color[v] in {0, 1}, or (False, cycle) where cycle is a list of
vertices of odd length that forms a closed walk (consecutive vertices and the
last and first vertex are adjacent) and, for a simple graph, a simple odd cycle.
Time O(n + m), extra space O(n).
"""
n = len(adj)
color: list[int | None] = [None] * n # @line L1
parent: list[int] = [-1] * n
for s in range(n): # @line L2
if color[s] is not None:
continue
color[s] = 0 # @line L3
q = deque([s])
while q: # @line L4
u = q.popleft() # @line L5
for w in adj[u]: # @line L6
if color[w] is None: # @line L7
color[w] = 1 - color[u] # type: ignore[operator]
parent[w] = u
q.append(w)
elif color[w] == color[u]: # @line L8
return False, _odd_cycle(parent, u, w)
return True, [c if c is not None else 0 for c in color] # @line L9
def _odd_cycle(parent: list[int], u: int, w: int) -> list[int]:
"""The cycle u -> ... -> z <- ... <- w closed by the edge {w, u}.
u and w are in the same BFS layer, so they reach their lowest common
ancestor z after the same number of parent steps.
"""
left = [u] # @line L10
right = [w]
x, y = u, w
while x != y:
x, y = parent[x], parent[y]
left.append(x)
right.append(y)
# left ends with z, right ends with z; drop the second copy of z
return left + right[-2::-1] # @line L11
test_bipartiteness_testing.py 68 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bipartiteness-testing/. The authors are listed in prov/S82K2H.jsonl.
import itertools
import random
from bipartiteness_testing import bipartiteness_testing
def make(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)
if u != v:
adj[v].append(u)
return adj
def brute_two_colorable(n: int, edges: list[tuple[int, int]]) -> bool:
return any(all(c[u] != c[v] for u, v in edges) for c in itertools.product((0, 1), repeat=n))
def check(n: int, edges: list[tuple[int, int]]) -> bool:
ok, out = bipartiteness_testing(make(n, edges))
es = {frozenset(e) for e in edges}
if ok:
assert len(out) == n and all(out[u] != out[v] for u, v in edges)
else:
k = len(out)
assert k % 2 == 1
assert all(frozenset((out[i], out[(i + 1) % k])) in es for i in range(k))
if all(u != v for u, v in edges):
assert len(set(out)) == k # a simple cycle
return ok
EXAMPLE = [(0, 1), (0, 2), (1, 3), (2, 4), (3, 5), (4, 5), (5, 6)]
def test_example() -> None:
adj = make(7, EXAMPLE)
assert bipartiteness_testing(adj) == (True, [0, 1, 1, 0, 0, 1, 0])
adj = make(7, EXAMPLE[:4] + [(3, 5), (3, 4), (4, 5), (5, 6)])
assert bipartiteness_testing(adj) == (False, [3, 1, 0, 2, 4])
def test_edges() -> None:
assert bipartiteness_testing([]) == (True, [])
assert bipartiteness_testing([[]]) == (True, [0])
assert bipartiteness_testing(make(1, [(0, 0)])) == (False, [0])
for k in range(2, 9):
assert check(k, [(i, (i + 1) % k) for i in range(k)] if k > 2 else [(0, 1)]) == (k % 2 == 0 or k == 2)
complete = list(itertools.combinations(range(k), 2))
assert check(k, complete) == (k <= 2)
k33 = [(i, j) for i in range(3) for j in range(3, 6)]
assert check(6, k33)
petersen = [(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
assert not check(10, petersen)
def test_random_against_brute_force() -> None:
rng = random.Random(11)
for _ in range(1500):
n = rng.randrange(0, 9)
p = rng.random() * 0.6
edges = [e for e in itertools.combinations(range(n), 2) if rng.random() < p]
rng.shuffle(edges)
assert check(n, edges) == brute_two_colorable(n, edges)
What the next level needs
- the tests did not run in this build