FAILURE MAP
← Case archive

FA-11691 / Graph algorithm invariants / Open access

Strong components collapse one-way reachability into equivalence · case 01

Strong components collapse one-way reachability into equivalence.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

A directed reachability relation is treated as symmetric when grouping vertices.

VERIFIED REPAIR

Require each pair of members to reach one another before assigning a component.

Unsuccessful approach: Using either direction of reachability still joins components across a one-way condensation edge.

Case contract

For distinct integer vertices and directed edges among them, return strongly connected components, members sorted and components ordered by smallest member; isolated vertices are singleton components.

Why this case matters

A deterministic in-memory graph model isolates this invariant; no large-graph performance or production graph engine behavior is claimed.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(vertices, edges):
    adj = {v: set() for v in vertices}
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    reach = {}
    for start in vertices:
        seen, todo = {start}, [start]
        while todo:
            for nxt in adj[todo.pop()] - seen:
                seen.add(nxt)
                todo.append(nxt)
        reach[start] = seen
    left, groups = set(vertices), []
    while left:
        v = min(left)
        group = {u for u in left if u in reach[v]}
        groups.append(sorted(group))
        left -= group
    return groups
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [N*10+i for i in range(4)]
check('one way link', solve([a,b], [(a,b)]), [[a],[b]])
check('cycle with outgoing tail', solve([a,b,c], [(a,b),(b,a),(b,c)]), [[a,b],[c]])
check('incoming tail', solve([a,b,c], [(b,a),(b,c),(c,b)]), [[a],[b,c]])
check('single self loop', solve([a], [(a,a)]), [[a]])
check('empty graph', solve([], []), [])
check('isolated vertices', solve([d,a], []), [[a],[d]])
check('long cycle', solve([a,b,c], [(a,b),(b,c),(c,a)]), [[a,b,c]])
check('variable-size directed cycle', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), [list(range(N+2))])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
one way link[[10, 11]][[10], [11]]Failed
cycle with outgoing tail[[10, 11, 12]][[10, 11], [12]]Failed
incoming tail[[10, 11, 12]][[10], [11, 12]]Failed
single self loop[[10]][[10]]Passed
empty graph[][]Passed
isolated vertices[[10], [13]][[10], [13]]Passed
long cycle[[10, 11, 12]][[10, 11, 12]]Passed
variable-size directed cycle[[0, 1, 2]][[0, 1, 2]]Passed

SHA-256 / bf21d1a89b38cb1ea4d367ab1c8b16f7d8b1118e5bb3f850086ec09332abd131

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(vertices, edges):
    adj = {v: set() for v in vertices}
    for u, v in edges:
        adj[u].add(v)
        pass
    reach = {}
    for start in vertices:
        seen, todo = {start}, [start]
        while todo:
            for nxt in adj[todo.pop()] - seen:
                seen.add(nxt)
                todo.append(nxt)
        reach[start] = seen
    left, groups = set(vertices), []
    while left:
        v = min(left)
        group = {u for u in left if u in reach[v] or v in reach[u]}
        groups.append(sorted(group))
        left -= group
    return groups
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [N*10+i for i in range(4)]
check('one way link', solve([a,b], [(a,b)]), [[a],[b]])
check('cycle with outgoing tail', solve([a,b,c], [(a,b),(b,a),(b,c)]), [[a,b],[c]])
check('incoming tail', solve([a,b,c], [(b,a),(b,c),(c,b)]), [[a],[b,c]])
check('single self loop', solve([a], [(a,a)]), [[a]])
check('empty graph', solve([], []), [])
check('isolated vertices', solve([d,a], []), [[a],[d]])
check('long cycle', solve([a,b,c], [(a,b),(b,c),(c,a)]), [[a,b,c]])
check('variable-size directed cycle', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), [list(range(N+2))])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
one way link[[10, 11]][[10], [11]]Failed
cycle with outgoing tail[[10, 11, 12]][[10, 11], [12]]Failed
incoming tail[[10, 11, 12]][[10], [11, 12]]Failed
single self loop[[10]][[10]]Passed
empty graph[][]Passed
isolated vertices[[10], [13]][[10], [13]]Passed
long cycle[[10, 11, 12]][[10, 11, 12]]Passed
variable-size directed cycle[[0, 1, 2]][[0, 1, 2]]Passed

SHA-256 / 857e6514c1e528051931925083c68ababa06466d285a0795e9afcbf12905ec9f

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(vertices, edges):
    adj = {v: set() for v in vertices}
    for u, v in edges:
        adj[u].add(v)
        pass
    reach = {}
    for start in vertices:
        seen, todo = {start}, [start]
        while todo:
            for nxt in adj[todo.pop()] - seen:
                seen.add(nxt)
                todo.append(nxt)
        reach[start] = seen
    left, groups = set(vertices), []
    while left:
        v = min(left)
        group = {u for u in left if u in reach[v] and v in reach[u]}
        groups.append(sorted(group))
        left -= group
    return groups
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [N*10+i for i in range(4)]
check('one way link', solve([a,b], [(a,b)]), [[a],[b]])
check('cycle with outgoing tail', solve([a,b,c], [(a,b),(b,a),(b,c)]), [[a,b],[c]])
check('incoming tail', solve([a,b,c], [(b,a),(b,c),(c,b)]), [[a],[b,c]])
check('single self loop', solve([a], [(a,a)]), [[a]])
check('empty graph', solve([], []), [])
check('isolated vertices', solve([d,a], []), [[a],[d]])
check('long cycle', solve([a,b,c], [(a,b),(b,c),(c,a)]), [[a,b,c]])
check('variable-size directed cycle', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), [list(range(N+2))])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
one way link[[10], [11]][[10], [11]]Passed
cycle with outgoing tail[[10, 11], [12]][[10, 11], [12]]Passed
incoming tail[[10], [11, 12]][[10], [11, 12]]Passed
single self loop[[10]][[10]]Passed
empty graph[][]Passed
isolated vertices[[10], [13]][[10], [13]]Passed
long cycle[[10, 11, 12]][[10, 11, 12]]Passed
variable-size directed cycle[[0, 1, 2]][[0, 1, 2]]Passed

SHA-256 / 57c56c58c46c87a5a102200c321252cfe450046da4bd84860693558bb4992182

Verification & scope

Small explicit graphs only; exhaustive reference algorithms emphasize semantics rather than asymptotic performance. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:38:50.158821+00:00.

Case digest / 7eaaafe102f27b8b9296e81561517664106e0ac590c401e11f5037ea3e4fc48b