{"abstract":"Strong components collapse one-way reachability into equivalence.","category":"Graph algorithm invariants","checks":8,"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.","evaluation_group":"model-c06773e20f425676","failed_approach":"Using either direction of reachability still joins components across a one-way condensation edge.","family":"z-graphs-mutual-reachability","id":"FA-11691","implementations":{"attempt":{"sha256":"857e6514c1e528051931925083c68ababa06466d285a0795e9afcbf12905ec9f","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    adj = {v: set() for v in vertices}\n    for u, v in edges:\n        adj[u].add(v)\n        pass\n    reach = {}\n    for start in vertices:\n        seen, todo = {start}, [start]\n        while todo:\n            for nxt in adj[todo.pop()] - seen:\n                seen.add(nxt)\n                todo.append(nxt)\n        reach[start] = seen\n    left, groups = set(vertices), []\n    while left:\n        v = min(left)\n        group = {u for u in left if u in reach[v] or v in reach[u]}\n        groups.append(sorted(group))\n        left -= group\n    return groups\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [N*10+i for i in range(4)]\ncheck('one way link', solve([a,b], [(a,b)]), [[a],[b]])\ncheck('cycle with outgoing tail', solve([a,b,c], [(a,b),(b,a),(b,c)]), [[a,b],[c]])\ncheck('incoming tail', solve([a,b,c], [(b,a),(b,c),(c,b)]), [[a],[b,c]])\ncheck('single self loop', solve([a], [(a,a)]), [[a]])\ncheck('empty graph', solve([], []), [])\ncheck('isolated vertices', solve([d,a], []), [[a],[d]])\ncheck('long cycle', solve([a,b,c], [(a,b),(b,c),(c,a)]), [[a,b,c]])\ncheck('variable-size directed cycle', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), [list(range(N+2))])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"bf21d1a89b38cb1ea4d367ab1c8b16f7d8b1118e5bb3f850086ec09332abd131","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    adj = {v: set() for v in vertices}\n    for u, v in edges:\n        adj[u].add(v)\n        adj[v].add(u)\n    reach = {}\n    for start in vertices:\n        seen, todo = {start}, [start]\n        while todo:\n            for nxt in adj[todo.pop()] - seen:\n                seen.add(nxt)\n                todo.append(nxt)\n        reach[start] = seen\n    left, groups = set(vertices), []\n    while left:\n        v = min(left)\n        group = {u for u in left if u in reach[v]}\n        groups.append(sorted(group))\n        left -= group\n    return groups\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [N*10+i for i in range(4)]\ncheck('one way link', solve([a,b], [(a,b)]), [[a],[b]])\ncheck('cycle with outgoing tail', solve([a,b,c], [(a,b),(b,a),(b,c)]), [[a,b],[c]])\ncheck('incoming tail', solve([a,b,c], [(b,a),(b,c),(c,b)]), [[a],[b,c]])\ncheck('single self loop', solve([a], [(a,a)]), [[a]])\ncheck('empty graph', solve([], []), [])\ncheck('isolated vertices', solve([d,a], []), [[a],[d]])\ncheck('long cycle', solve([a,b,c], [(a,b),(b,c),(c,a)]), [[a,b,c]])\ncheck('variable-size directed cycle', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), [list(range(N+2))])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"57c56c58c46c87a5a102200c321252cfe450046da4bd84860693558bb4992182","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    adj = {v: set() for v in vertices}\n    for u, v in edges:\n        adj[u].add(v)\n        pass\n    reach = {}\n    for start in vertices:\n        seen, todo = {start}, [start]\n        while todo:\n            for nxt in adj[todo.pop()] - seen:\n                seen.add(nxt)\n                todo.append(nxt)\n        reach[start] = seen\n    left, groups = set(vertices), []\n    while left:\n        v = min(left)\n        group = {u for u in left if u in reach[v] and v in reach[u]}\n        groups.append(sorted(group))\n        left -= group\n    return groups\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [N*10+i for i in range(4)]\ncheck('one way link', solve([a,b], [(a,b)]), [[a],[b]])\ncheck('cycle with outgoing tail', solve([a,b,c], [(a,b),(b,a),(b,c)]), [[a,b],[c]])\ncheck('incoming tail', solve([a,b,c], [(b,a),(b,c),(c,b)]), [[a],[b,c]])\ncheck('single self loop', solve([a], [(a,a)]), [[a]])\ncheck('empty graph', solve([], []), [])\ncheck('isolated vertices', solve([d,a], []), [[a],[d]])\ncheck('long cycle', solve([a,b,c], [(a,b),(b,c),(c,a)]), [[a,b,c]])\ncheck('variable-size directed cycle', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), [list(range(N+2))])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"z-graphs-mutual-reachability","generated_at":"2026-09-29T14:38:50.158821+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"A deterministic in-memory graph model isolates this invariant; no large-graph performance or production graph engine behavior is claimed.","repair":"Require each pair of members to reach one another before assigning a component.","root_cause":"A directed reachability relation is treated as symmetric when grouping vertices.","sha256":"7eaaafe102f27b8b9296e81561517664106e0ac590c401e11f5037ea3e4fc48b","title":"Strong components collapse one-way reachability into equivalence · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":37.988,"exit_code":1,"observations":[{"actual":[[10,11]],"check":"one way link","expected":[[10],[11]],"passed":false},{"actual":[[10,11,12]],"check":"cycle with outgoing tail","expected":[[10,11],[12]],"passed":false},{"actual":[[10,11,12]],"check":"incoming tail","expected":[[10],[11,12]],"passed":false},{"actual":[[10]],"check":"single self loop","expected":[[10]],"passed":true},{"actual":[],"check":"empty graph","expected":[],"passed":true},{"actual":[[10],[13]],"check":"isolated vertices","expected":[[10],[13]],"passed":true},{"actual":[[10,11,12]],"check":"long cycle","expected":[[10,11,12]],"passed":true},{"actual":[[0,1,2]],"check":"variable-size directed cycle","expected":[[0,1,2]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"one way link\", \"actual\": [[10, 11]], \"expected\": [[10], [11]], \"passed\": false}, {\"check\": \"cycle with outgoing tail\", \"actual\": [[10, 11, 12]], \"expected\": [[10, 11], [12]], \"passed\": false}, {\"check\": \"incoming tail\", \"actual\": [[10, 11, 12]], \"expected\": [[10], [11, 12]], \"passed\": false}, {\"check\": \"single self loop\", \"actual\": [[10]], \"expected\": [[10]], \"passed\": true}, {\"check\": \"empty graph\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"isolated vertices\", \"actual\": [[10], [13]], \"expected\": [[10], [13]], \"passed\": true}, {\"check\": \"long cycle\", \"actual\": [[10, 11, 12]], \"expected\": [[10, 11, 12]], \"passed\": true}, {\"check\": \"variable-size directed cycle\", \"actual\": [[0, 1, 2]], \"expected\": [[0, 1, 2]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.47,"exit_code":1,"observations":[{"actual":[[10,11]],"check":"one way link","expected":[[10],[11]],"passed":false},{"actual":[[10,11,12]],"check":"cycle with outgoing tail","expected":[[10,11],[12]],"passed":false},{"actual":[[10,11,12]],"check":"incoming tail","expected":[[10],[11,12]],"passed":false},{"actual":[[10]],"check":"single self loop","expected":[[10]],"passed":true},{"actual":[],"check":"empty graph","expected":[],"passed":true},{"actual":[[10],[13]],"check":"isolated vertices","expected":[[10],[13]],"passed":true},{"actual":[[10,11,12]],"check":"long cycle","expected":[[10,11,12]],"passed":true},{"actual":[[0,1,2]],"check":"variable-size directed cycle","expected":[[0,1,2]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"one way link\", \"actual\": [[10, 11]], \"expected\": [[10], [11]], \"passed\": false}, {\"check\": \"cycle with outgoing tail\", \"actual\": [[10, 11, 12]], \"expected\": [[10, 11], [12]], \"passed\": false}, {\"check\": \"incoming tail\", \"actual\": [[10, 11, 12]], \"expected\": [[10], [11, 12]], \"passed\": false}, {\"check\": \"single self loop\", \"actual\": [[10]], \"expected\": [[10]], \"passed\": true}, {\"check\": \"empty graph\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"isolated vertices\", \"actual\": [[10], [13]], \"expected\": [[10], [13]], \"passed\": true}, {\"check\": \"long cycle\", \"actual\": [[10, 11, 12]], \"expected\": [[10, 11, 12]], \"passed\": true}, {\"check\": \"variable-size directed cycle\", \"actual\": [[0, 1, 2]], \"expected\": [[0, 1, 2]], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":37.466,"exit_code":0,"observations":[{"actual":[[10],[11]],"check":"one way link","expected":[[10],[11]],"passed":true},{"actual":[[10,11],[12]],"check":"cycle with outgoing tail","expected":[[10,11],[12]],"passed":true},{"actual":[[10],[11,12]],"check":"incoming tail","expected":[[10],[11,12]],"passed":true},{"actual":[[10]],"check":"single self loop","expected":[[10]],"passed":true},{"actual":[],"check":"empty graph","expected":[],"passed":true},{"actual":[[10],[13]],"check":"isolated vertices","expected":[[10],[13]],"passed":true},{"actual":[[10,11,12]],"check":"long cycle","expected":[[10,11,12]],"passed":true},{"actual":[[0,1,2]],"check":"variable-size directed cycle","expected":[[0,1,2]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"one way link\", \"actual\": [[10], [11]], \"expected\": [[10], [11]], \"passed\": true}, {\"check\": \"cycle with outgoing tail\", \"actual\": [[10, 11], [12]], \"expected\": [[10, 11], [12]], \"passed\": true}, {\"check\": \"incoming tail\", \"actual\": [[10], [11, 12]], \"expected\": [[10], [11, 12]], \"passed\": true}, {\"check\": \"single self loop\", \"actual\": [[10]], \"expected\": [[10]], \"passed\": true}, {\"check\": \"empty graph\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"isolated vertices\", \"actual\": [[10], [13]], \"expected\": [[10], [13]], \"passed\": true}, {\"check\": \"long cycle\", \"actual\": [[10, 11, 12]], \"expected\": [[10, 11, 12]], \"passed\": true}, {\"check\": \"variable-size directed cycle\", \"actual\": [[0, 1, 2]], \"expected\": [[0, 1, 2]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}