{"abstract":"Parallel edges are all removed when testing a single bridge.","category":"Graph algorithm invariants","checks":8,"contract":"Return input indices of bridges in an undirected multigraph. Self loops and parallel edges are allowed. Removing exactly one bridge increases the number of connected components.","evaluation_group":"model-bdd8c01da6bf4c10","failed_approach":"Deduplicating parallel edges before deletion still invents bridges absent from the multigraph.","family":"z-graphs-bridge-edge-identity","id":"FA-11696","implementations":{"attempt":{"sha256":"3d29a29ec723fde99667257bc97bc3eee4085cf98b56dcbaa02511787a25b82e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    def components(es):\n        adj = {v:set() for v in vertices}\n        for u,v in es:\n            adj[u].add(v); adj[v].add(u)\n        seen, count = set(), 0\n        for v in vertices:\n            if v in seen: continue\n            count += 1; seen.add(v); todo = [v]\n            while todo:\n                for w in adj[todo.pop()] - seen:\n                    seen.add(w); todo.append(w)\n        return count\n    baseline = components(edges)\n    answer = []\n    for i,(u,v) in enumerate(edges):\n        remaining = [tuple(p) for p in {tuple(sorted(e)) for j,e in enumerate(edges) if j != i} if set(p) != {u,v}]\n        if components(remaining) > baseline:\n            answer.append(i)\n    return answer\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c = N,N+1,N+2\ncheck('parallel pair', solve([a,b], [(a,b),(a,b)]), [])\ncheck('opposite endpoint order', solve([a,b], [(a,b),(b,a)]), [])\ncheck('parallel pair with tail', solve([a,b,c], [(a,b),(a,b),(b,c)]), [2])\ncheck('single edge', solve([a,b], [(a,b)]), [0])\ncheck('self loop', solve([a], [(a,a)]), [])\ncheck('empty', solve([], []), [])\ncheck('disconnected forest', solve([a,b,c], [(a,b)]), [0])\ncheck('variable-length forest', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N)))\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":"eac0fa6cb18da1bbcb14f76470e5ed219968428d5226733ad299c97fdc22e11e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    def components(es):\n        adj = {v:set() for v in vertices}\n        for u,v in es:\n            adj[u].add(v); adj[v].add(u)\n        seen, count = set(), 0\n        for v in vertices:\n            if v in seen: continue\n            count += 1; seen.add(v); todo = [v]\n            while todo:\n                for w in adj[todo.pop()] - seen:\n                    seen.add(w); todo.append(w)\n        return count\n    baseline = components(edges)\n    answer = []\n    for i,(u,v) in enumerate(edges):\n        remaining = [(a,b) for a,b in edges if {a,b} != {u,v}]\n        if components(remaining) > baseline:\n            answer.append(i)\n    return answer\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c = N,N+1,N+2\ncheck('parallel pair', solve([a,b], [(a,b),(a,b)]), [])\ncheck('opposite endpoint order', solve([a,b], [(a,b),(b,a)]), [])\ncheck('parallel pair with tail', solve([a,b,c], [(a,b),(a,b),(b,c)]), [2])\ncheck('single edge', solve([a,b], [(a,b)]), [0])\ncheck('self loop', solve([a], [(a,a)]), [])\ncheck('empty', solve([], []), [])\ncheck('disconnected forest', solve([a,b,c], [(a,b)]), [0])\ncheck('variable-length forest', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N)))\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":"5390da12544d7019cb2f8a58d1cfede952ea651e4e4d1e1b2ecfe1c19bd04285","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    def components(es):\n        adj = {v:set() for v in vertices}\n        for u,v in es:\n            adj[u].add(v); adj[v].add(u)\n        seen, count = set(), 0\n        for v in vertices:\n            if v in seen: continue\n            count += 1; seen.add(v); todo = [v]\n            while todo:\n                for w in adj[todo.pop()] - seen:\n                    seen.add(w); todo.append(w)\n        return count\n    baseline = components(edges)\n    answer = []\n    for i,(u,v) in enumerate(edges):\n        remaining = edges[:i] + edges[i+1:]\n        if components(remaining) > baseline:\n            answer.append(i)\n    return answer\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c = N,N+1,N+2\ncheck('parallel pair', solve([a,b], [(a,b),(a,b)]), [])\ncheck('opposite endpoint order', solve([a,b], [(a,b),(b,a)]), [])\ncheck('parallel pair with tail', solve([a,b,c], [(a,b),(a,b),(b,c)]), [2])\ncheck('single edge', solve([a,b], [(a,b)]), [0])\ncheck('self loop', solve([a], [(a,a)]), [])\ncheck('empty', solve([], []), [])\ncheck('disconnected forest', solve([a,b,c], [(a,b)]), [0])\ncheck('variable-length forest', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N)))\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-bridge-edge-identity","generated_at":"2026-09-29T14:38:50.233349+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":"Remove precisely the indexed edge and compare component counts against the original graph.","root_cause":"Endpoint pairs substitute for edge identities, so a single-edge deletion removes every parallel edge.","sha256":"9e5698ad7a32d8dc216724c270b8a5ca1dd7fb8112646992a77edfe593bd0478","title":"Parallel edges are all removed when testing a single bridge · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.502,"exit_code":1,"observations":[{"actual":[0,1],"check":"parallel pair","expected":[],"passed":false},{"actual":[0,1],"check":"opposite endpoint order","expected":[],"passed":false},{"actual":[0,1,2],"check":"parallel pair with tail","expected":[2],"passed":false},{"actual":[0],"check":"single edge","expected":[0],"passed":true},{"actual":[],"check":"self loop","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[0],"check":"disconnected forest","expected":[0],"passed":true},{"actual":[0],"check":"variable-length forest","expected":[0],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"parallel pair\", \"actual\": [0, 1], \"expected\": [], \"passed\": false}, {\"check\": \"opposite endpoint order\", \"actual\": [0, 1], \"expected\": [], \"passed\": false}, {\"check\": \"parallel pair with tail\", \"actual\": [0, 1, 2], \"expected\": [2], \"passed\": false}, {\"check\": \"single edge\", \"actual\": [0], \"expected\": [0], \"passed\": true}, {\"check\": \"self loop\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"disconnected forest\", \"actual\": [0], \"expected\": [0], \"passed\": true}, {\"check\": \"variable-length forest\", \"actual\": [0], \"expected\": [0], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.418,"exit_code":1,"observations":[{"actual":[0,1],"check":"parallel pair","expected":[],"passed":false},{"actual":[0,1],"check":"opposite endpoint order","expected":[],"passed":false},{"actual":[0,1,2],"check":"parallel pair with tail","expected":[2],"passed":false},{"actual":[0],"check":"single edge","expected":[0],"passed":true},{"actual":[],"check":"self loop","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[0],"check":"disconnected forest","expected":[0],"passed":true},{"actual":[0],"check":"variable-length forest","expected":[0],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"parallel pair\", \"actual\": [0, 1], \"expected\": [], \"passed\": false}, {\"check\": \"opposite endpoint order\", \"actual\": [0, 1], \"expected\": [], \"passed\": false}, {\"check\": \"parallel pair with tail\", \"actual\": [0, 1, 2], \"expected\": [2], \"passed\": false}, {\"check\": \"single edge\", \"actual\": [0], \"expected\": [0], \"passed\": true}, {\"check\": \"self loop\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"disconnected forest\", \"actual\": [0], \"expected\": [0], \"passed\": true}, {\"check\": \"variable-length forest\", \"actual\": [0], \"expected\": [0], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":39.642,"exit_code":0,"observations":[{"actual":[],"check":"parallel pair","expected":[],"passed":true},{"actual":[],"check":"opposite endpoint order","expected":[],"passed":true},{"actual":[2],"check":"parallel pair with tail","expected":[2],"passed":true},{"actual":[0],"check":"single edge","expected":[0],"passed":true},{"actual":[],"check":"self loop","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[0],"check":"disconnected forest","expected":[0],"passed":true},{"actual":[0],"check":"variable-length forest","expected":[0],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"parallel pair\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"opposite endpoint order\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"parallel pair with tail\", \"actual\": [2], \"expected\": [2], \"passed\": true}, {\"check\": \"single edge\", \"actual\": [0], \"expected\": [0], \"passed\": true}, {\"check\": \"self loop\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"disconnected forest\", \"actual\": [0], \"expected\": [0], \"passed\": true}, {\"check\": \"variable-length forest\", \"actual\": [0], \"expected\": [0], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}