85 lines
4.0 KiB
Python
85 lines
4.0 KiB
Python
"""Cells for tarjan_scc.py (Q85 class): iterative Tarjan over int indices.
|
|
|
|
The module landed with its proof in `__main__` only -- `self_test()` runs a
|
|
brute-force cross-check and prints ALL TESTS PASSED -- so no collected cell
|
|
read it and `check_coverage.py` graded it UNCOVERED (measured 2026-11-02, the
|
|
module's own commit `7659e22`). A proof that only runs when a human types the
|
|
file's name is a transcript, not a gate. These cells port the claim into the
|
|
collected suite: deterministic graphs whose answers can be read by eye, the
|
|
2000-graph brute-force cross-check at a fixed seed, the property that makes the
|
|
output usable (components in reverse topological order), and the two edges the
|
|
`while` loop exists to carry -- a self-loop and a duplicate edge.
|
|
"""
|
|
import random
|
|
import unittest
|
|
|
|
from tarjan_scc import brute_scc, normalize, tarjan_scc
|
|
|
|
|
|
class TestTarjanSCC(unittest.TestCase):
|
|
def test_empty_and_singletons(self):
|
|
self.assertEqual(tarjan_scc(0, []), [])
|
|
self.assertEqual(normalize(tarjan_scc(1, [])), [[0]])
|
|
self.assertEqual(normalize(tarjan_scc(3, [])), [[0], [1], [2]])
|
|
|
|
def test_three_cycle_is_one_component(self):
|
|
cycles = tarjan_scc(3, [(0, 1), (1, 2), (2, 0)])
|
|
self.assertEqual(len(cycles), 1)
|
|
self.assertEqual(sorted(cycles[0]), [0, 1, 2])
|
|
|
|
def test_chain_has_no_component_larger_than_one(self):
|
|
comps = tarjan_scc(3, [(0, 1), (1, 2)])
|
|
self.assertEqual(normalize(comps), [[0], [1], [2]])
|
|
|
|
def test_self_loop_and_duplicate_edge(self):
|
|
# A self-loop must not fold the node into a neighbour, and a repeated
|
|
# edge must not push a node twice: the counter-based `while` pass reads
|
|
# each successor once per adjacency slot, so both are real cells.
|
|
self.assertEqual(normalize(tarjan_scc(1, [(0, 0)])), [[0]])
|
|
self.assertEqual(normalize(tarjan_scc(2, [(0, 1), (0, 1)])), [[0], [1]])
|
|
|
|
def test_two_components_one_edge(self):
|
|
# 0 -> 1, 2 -> 3 -> 2: two SCCs, one of size two.
|
|
comps = normalize(tarjan_scc(4, [(0, 1), (2, 3), (3, 2)]))
|
|
self.assertEqual(comps, [[0], [1], [2, 3]])
|
|
|
|
def test_reverse_topological_order(self):
|
|
# Tarjan emits a component only after every component it can reach, so
|
|
# for an edge u -> v crossing components, v's component comes out first.
|
|
# This is the property callers use to read a condensation order; it is
|
|
# asserted on random graphs, not just the hand-built one.
|
|
random.seed(7)
|
|
for _ in range(40):
|
|
n = random.randint(2, 9)
|
|
edges = [(random.randrange(n), random.randrange(n))
|
|
for _ in range(random.randint(0, 2 * n))]
|
|
comps = tarjan_scc(n, edges)
|
|
where = {node: i for i, comp in enumerate(comps) for node in comp}
|
|
for u, v in edges:
|
|
if where[u] != where[v]:
|
|
self.assertLess(where[v], where[u], (edges, comps))
|
|
|
|
def test_brute_force_cross_check(self):
|
|
# The module's own claim, moved inside the gate: 2000 random graphs at
|
|
# seed 42, compared as sets-of-sets against the O(n^3) reachability
|
|
# closure. normalize() is the module's, so the comparison is its own
|
|
# notion of "same partition".
|
|
random.seed(42)
|
|
for _ in range(2000):
|
|
n = random.randint(1, 12)
|
|
m = random.randint(0, n * n)
|
|
edges = [(random.randrange(n), random.randrange(n)) for _ in range(m)]
|
|
self.assertEqual(normalize(tarjan_scc(n, edges)),
|
|
normalize(brute_scc(n, edges)), (n, edges))
|
|
|
|
def test_only_referenced_nodes_beyond_n_are_not_touched(self):
|
|
# The signature takes n, so an edge into an index >= n is the caller's
|
|
# contract violation; the cells above stay inside [0, n). This one pins
|
|
# that n=0 with no edges is empty rather than an IndexError on the
|
|
# `indices[start]` read -- the loop body never runs.
|
|
self.assertEqual(tarjan_scc(0, []), [])
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main(verbosity=2)
|