{"abstract":"Articulation detection compares against one component in a disconnected graph.","category":"Graph algorithm invariants","checks":8,"contract":"Return sorted articulation vertices of an undirected loopless graph. A vertex qualifies only when its deletion and deletion of its incident edges increases the total connected-component count.","evaluation_group":"model-7440a3bb11f5a17c","failed_approach":"Using a non-strict comparison declares cycle vertices critical even though removing them does not disconnect anything further.","family":"z-graphs-articulation-component-baseline","id":"FA-11731","implementations":{"attempt":{"sha256":"3ba4314c4edb79335a6878243171e1577c35d46213c274938a78ae84793a5b33","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    def count(omit):\n        adj = {v:set() for v in vertices if v != omit}\n        for u,v in edges:\n            if u != omit and v != omit: adj[u].add(v); adj[v].add(u)\n        seen, total = set(), 0\n        for root in adj:\n            if root in seen: continue\n            total += 1; seen.add(root); todo = [root]\n            while todo:\n                for v in adj[todo.pop()] - seen:\n                    seen.add(v); todo.append(v)\n        return total\n    baseline = count(None)\n    return [v for v in sorted(vertices) if count(v) >= baseline]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d,e = [10*N+i for i in range(5)]\ncheck('two disjoint edges plus isolate', solve([a,b,c,d,e], [(a,b),(c,d)]), [])\ncheck('cycle vertices are not cuts', solve([a,b,c], [(a,b),(b,c),(c,a)]), [])\ncheck('path middle', solve([a,b,c], [(a,b),(b,c)]), [b])\ncheck('disconnected path', solve([a,b,c,d], [(a,b),(b,c)]), [b])\ncheck('single vertex', solve([a], []), [])\ncheck('empty', solve([], []), [])\ncheck('star root', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), [a])\ncheck('variable-length path cuts', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)]), list(range(1,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":"6528a1714b4a360802d5b193dd82b1c45abc5ce1c060bc4bed2b1d5baeadfe3f","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    def count(omit):\n        adj = {v:set() for v in vertices if v != omit}\n        for u,v in edges:\n            if u != omit and v != omit: adj[u].add(v); adj[v].add(u)\n        seen, total = set(), 0\n        for root in adj:\n            if root in seen: continue\n            total += 1; seen.add(root); todo = [root]\n            while todo:\n                for v in adj[todo.pop()] - seen:\n                    seen.add(v); todo.append(v)\n        return total\n    baseline = 1\n    return [v for v in sorted(vertices) if count(v) > baseline]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d,e = [10*N+i for i in range(5)]\ncheck('two disjoint edges plus isolate', solve([a,b,c,d,e], [(a,b),(c,d)]), [])\ncheck('cycle vertices are not cuts', solve([a,b,c], [(a,b),(b,c),(c,a)]), [])\ncheck('path middle', solve([a,b,c], [(a,b),(b,c)]), [b])\ncheck('disconnected path', solve([a,b,c,d], [(a,b),(b,c)]), [b])\ncheck('single vertex', solve([a], []), [])\ncheck('empty', solve([], []), [])\ncheck('star root', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), [a])\ncheck('variable-length path cuts', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)]), list(range(1,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":"51a68cf2794dcd030726b17591ed51a89b313aaaa83fc7a1cfe0fe10e6c4de70","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    def count(omit):\n        adj = {v:set() for v in vertices if v != omit}\n        for u,v in edges:\n            if u != omit and v != omit: adj[u].add(v); adj[v].add(u)\n        seen, total = set(), 0\n        for root in adj:\n            if root in seen: continue\n            total += 1; seen.add(root); todo = [root]\n            while todo:\n                for v in adj[todo.pop()] - seen:\n                    seen.add(v); todo.append(v)\n        return total\n    baseline = count(None)\n    return [v for v in sorted(vertices) if count(v) > baseline]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d,e = [10*N+i for i in range(5)]\ncheck('two disjoint edges plus isolate', solve([a,b,c,d,e], [(a,b),(c,d)]), [])\ncheck('cycle vertices are not cuts', solve([a,b,c], [(a,b),(b,c),(c,a)]), [])\ncheck('path middle', solve([a,b,c], [(a,b),(b,c)]), [b])\ncheck('disconnected path', solve([a,b,c,d], [(a,b),(b,c)]), [b])\ncheck('single vertex', solve([a], []), [])\ncheck('empty', solve([], []), [])\ncheck('star root', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), [a])\ncheck('variable-length path cuts', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)]), list(range(1,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-articulation-component-baseline","generated_at":"2026-09-29T14:38:50.523105+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":"Compare the post-removal component count against the actual original count and require a strict increase.","root_cause":"The graph is assumed connected, so unrelated preexisting components make every removed vertex appear critical.","sha256":"bf7852e16eabf4dbcb4766edd1f8a8cea28ee4a31802f81f7434781ecb106b9f","title":"Articulation detection compares against one component in a disconnected graph · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":39.439,"exit_code":1,"observations":[{"actual":[10,11,12,13],"check":"two disjoint edges plus isolate","expected":[],"passed":false},{"actual":[10,11,12],"check":"cycle vertices are not cuts","expected":[],"passed":false},{"actual":[10,11,12],"check":"path middle","expected":[11],"passed":false},{"actual":[10,11,12],"check":"disconnected path","expected":[11],"passed":false},{"actual":[],"check":"single vertex","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[10,11,12,13],"check":"star root","expected":[10],"passed":false},{"actual":[0,1,2,3],"check":"variable-length path cuts","expected":[1,2],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"two disjoint edges plus isolate\", \"actual\": [10, 11, 12, 13], \"expected\": [], \"passed\": false}, {\"check\": \"cycle vertices are not cuts\", \"actual\": [10, 11, 12], \"expected\": [], \"passed\": false}, {\"check\": \"path middle\", \"actual\": [10, 11, 12], \"expected\": [11], \"passed\": false}, {\"check\": \"disconnected path\", \"actual\": [10, 11, 12], \"expected\": [11], \"passed\": false}, {\"check\": \"single vertex\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"star root\", \"actual\": [10, 11, 12, 13], \"expected\": [10], \"passed\": false}, {\"check\": \"variable-length path cuts\", \"actual\": [0, 1, 2, 3], \"expected\": [1, 2], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.573,"exit_code":1,"observations":[{"actual":[10,11,12,13,14],"check":"two disjoint edges plus isolate","expected":[],"passed":false},{"actual":[],"check":"cycle vertices are not cuts","expected":[],"passed":true},{"actual":[11],"check":"path middle","expected":[11],"passed":true},{"actual":[10,11,12],"check":"disconnected path","expected":[11],"passed":false},{"actual":[],"check":"single vertex","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[10],"check":"star root","expected":[10],"passed":true},{"actual":[1,2],"check":"variable-length path cuts","expected":[1,2],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"two disjoint edges plus isolate\", \"actual\": [10, 11, 12, 13, 14], \"expected\": [], \"passed\": false}, {\"check\": \"cycle vertices are not cuts\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"path middle\", \"actual\": [11], \"expected\": [11], \"passed\": true}, {\"check\": \"disconnected path\", \"actual\": [10, 11, 12], \"expected\": [11], \"passed\": false}, {\"check\": \"single vertex\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"star root\", \"actual\": [10], \"expected\": [10], \"passed\": true}, {\"check\": \"variable-length path cuts\", \"actual\": [1, 2], \"expected\": [1, 2], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.579,"exit_code":0,"observations":[{"actual":[],"check":"two disjoint edges plus isolate","expected":[],"passed":true},{"actual":[],"check":"cycle vertices are not cuts","expected":[],"passed":true},{"actual":[11],"check":"path middle","expected":[11],"passed":true},{"actual":[11],"check":"disconnected path","expected":[11],"passed":true},{"actual":[],"check":"single vertex","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[10],"check":"star root","expected":[10],"passed":true},{"actual":[1,2],"check":"variable-length path cuts","expected":[1,2],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"two disjoint edges plus isolate\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"cycle vertices are not cuts\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"path middle\", \"actual\": [11], \"expected\": [11], \"passed\": true}, {\"check\": \"disconnected path\", \"actual\": [11], \"expected\": [11], \"passed\": true}, {\"check\": \"single vertex\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"star root\", \"actual\": [10], \"expected\": [10], \"passed\": true}, {\"check\": \"variable-length path cuts\", \"actual\": [1, 2], \"expected\": [1, 2], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}