{"abstract":"Duplicate dependency declarations strand a valid topological vertex.","category":"Graph algorithm invariants","checks":8,"contract":"Treat repeated directed edges as one dependency. Return the lexicographically smallest topological order, or None if any cycle exists. Include isolated vertices.","contract_signature":"vertices, edges","evaluation_group":"model-353e8eda6169378d","failed_approach":"Ignoring a stranded suffix by returning the processed prefix conceals cycles and missing vertices.","family":"z-graphs-topological-edge-accounting","id":"FA-11706","implementations":{"attempt":{"sha256":"81b0cebea6659f9eac2b19938be35b6f26c9e0c311be89fcd26fe66f3b5d495b","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    indegree = {v:0 for v in vertices}\n    for u,v in edges:\n        if v not in adj[u]: indegree[v] += 1\n        adj[u].add(v)\n    ready = sorted(v for v in vertices if indegree[v] == 0)\n    answer = []\n    while ready:\n        u = ready.pop(0); answer.append(u)\n        for v in sorted(adj[u]):\n            indegree[v] -= 1\n            if indegree[v] == 0: ready.append(v)\n        ready.sort()\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('duplicate dependency', solve([a,b], [(a,b),(a,b)]), [a,b])\ncheck('cycle with independent prefix', solve([a,b,c], [(b,c),(c,b)]), None)\ncheck('self cycle', solve([a], [(a,a)]), None)\ncheck('empty', solve([], []), [])\ncheck('isolated lexicographic order', solve([c,a,b], []), [a,b,c])\ncheck('reverse dependency', solve([a,b,c], [(c,a)]), [b,c,a])\ncheck('diamond duplicate', solve([a,b,c], [(a,c),(b,c),(b,c)]), [a,b,c])\ncheck('variable-length dependency chain', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N+1)))\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":"e750dafde75a1135387989754d30075deb966505e52feeb28950d1721bcbb3f5","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    indegree = {v:0 for v in vertices}\n    for u,v in edges:\n        indegree[v] += 1\n        adj[u].add(v)\n    ready = sorted(v for v in vertices if indegree[v] == 0)\n    answer = []\n    while ready:\n        u = ready.pop(0); answer.append(u)\n        for v in sorted(adj[u]):\n            indegree[v] -= 1\n            if indegree[v] == 0: ready.append(v)\n        ready.sort()\n    return answer if len(answer) == len(vertices) else None\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('duplicate dependency', solve([a,b], [(a,b),(a,b)]), [a,b])\ncheck('cycle with independent prefix', solve([a,b,c], [(b,c),(c,b)]), None)\ncheck('self cycle', solve([a], [(a,a)]), None)\ncheck('empty', solve([], []), [])\ncheck('isolated lexicographic order', solve([c,a,b], []), [a,b,c])\ncheck('reverse dependency', solve([a,b,c], [(c,a)]), [b,c,a])\ncheck('diamond duplicate', solve([a,b,c], [(a,c),(b,c),(b,c)]), [a,b,c])\ncheck('variable-length dependency chain', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N+1)))\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-topological-edge-accounting","generated_at":"2026-09-29T14:38:50.321386+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.","root_cause":"Indegree counts duplicate declarations while outgoing adjacency deduplicates them, so decrements cannot balance increments.","sha256":"7e5c1a59b63d177df625c7846993fe6e4cd26297f1a040cf922a482e7183fbdb","title":"Duplicate dependency declarations strand a valid topological vertex · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":38.681,"exit_code":1,"observations":[{"actual":[1,2],"check":"duplicate dependency","expected":[1,2],"passed":true},{"actual":[1],"check":"cycle with independent prefix","expected":null,"passed":false},{"actual":[],"check":"self cycle","expected":null,"passed":false},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[1,2,3],"check":"isolated lexicographic order","expected":[1,2,3],"passed":true},{"actual":[2,3,1],"check":"reverse dependency","expected":[2,3,1],"passed":true},{"actual":[1,2,3],"check":"diamond duplicate","expected":[1,2,3],"passed":true},{"actual":[0,1],"check":"variable-length dependency chain","expected":[0,1],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"duplicate dependency\", \"actual\": [1, 2], \"expected\": [1, 2], \"passed\": true}, {\"check\": \"cycle with independent prefix\", \"actual\": [1], \"expected\": null, \"passed\": false}, {\"check\": \"self cycle\", \"actual\": [], \"expected\": null, \"passed\": false}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"isolated lexicographic order\", \"actual\": [1, 2, 3], \"expected\": [1, 2, 3], \"passed\": true}, {\"check\": \"reverse dependency\", \"actual\": [2, 3, 1], \"expected\": [2, 3, 1], \"passed\": true}, {\"check\": \"diamond duplicate\", \"actual\": [1, 2, 3], \"expected\": [1, 2, 3], \"passed\": true}, {\"check\": \"variable-length dependency chain\", \"actual\": [0, 1], \"expected\": [0, 1], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.217,"exit_code":1,"observations":[{"actual":null,"check":"duplicate dependency","expected":[1,2],"passed":false},{"actual":null,"check":"cycle with independent prefix","expected":null,"passed":true},{"actual":null,"check":"self cycle","expected":null,"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[1,2,3],"check":"isolated lexicographic order","expected":[1,2,3],"passed":true},{"actual":[2,3,1],"check":"reverse dependency","expected":[2,3,1],"passed":true},{"actual":null,"check":"diamond duplicate","expected":[1,2,3],"passed":false},{"actual":[0,1],"check":"variable-length dependency chain","expected":[0,1],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"duplicate dependency\", \"actual\": null, \"expected\": [1, 2], \"passed\": false}, {\"check\": \"cycle with independent prefix\", \"actual\": null, \"expected\": null, \"passed\": true}, {\"check\": \"self cycle\", \"actual\": null, \"expected\": null, \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"isolated lexicographic order\", \"actual\": [1, 2, 3], \"expected\": [1, 2, 3], \"passed\": true}, {\"check\": \"reverse dependency\", \"actual\": [2, 3, 1], \"expected\": [2, 3, 1], \"passed\": true}, {\"check\": \"diamond duplicate\", \"actual\": null, \"expected\": [1, 2, 3], \"passed\": false}, {\"check\": \"variable-length dependency chain\", \"actual\": [0, 1], \"expected\": [0, 1], \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}