FA-11706 / Graph algorithm invariants / Open access

Duplicate dependency declarations strand a valid topological vertex · case 01

Duplicate dependency declarations strand a valid topological vertex.

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

ROOT CAUSE

Indegree counts duplicate declarations while outgoing adjacency deduplicates them, so decrements cannot balance increments.

THE FAILURE

Indegree counts duplicate declarations while outgoing adjacency deduplicates them, so decrements cannot balance increments.

Unsuccessful approach: Ignoring a stranded suffix by returning the processed prefix conceals cycles and missing vertices.

Case contract

Treat repeated directed edges as one dependency. Return the lexicographically smallest topological order, or None if any cycle exists. Include isolated vertices.

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}
    indegree = {v:0 for v in vertices}
    for u,v in edges:
        indegree[v] += 1
        adj[u].add(v)
    ready = sorted(v for v in vertices if indegree[v] == 0)
    answer = []
    while ready:
        u = ready.pop(0); answer.append(u)
        for v in sorted(adj[u]):
            indegree[v] -= 1
            if indegree[v] == 0: ready.append(v)
        ready.sort()
    return answer if len(answer) == len(vertices) else None
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c = N,N+1,N+2
check('duplicate dependency', solve([a,b], [(a,b),(a,b)]), [a,b])
check('cycle with independent prefix', solve([a,b,c], [(b,c),(c,b)]), None)
check('self cycle', solve([a], [(a,a)]), None)
check('empty', solve([], []), [])
check('isolated lexicographic order', solve([c,a,b], []), [a,b,c])
check('reverse dependency', solve([a,b,c], [(c,a)]), [b,c,a])
check('diamond duplicate', solve([a,b,c], [(a,c),(b,c),(b,c)]), [a,b,c])
check('variable-length dependency chain', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N+1)))
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 fixture	Actual	Expected	Outcome
duplicate dependency	`None`	`[1, 2]`	Failed
cycle with independent prefix	`None`	`None`	Passed
self cycle	`None`	`None`	Passed
empty	`[]`	`[]`	Passed
isolated lexicographic order	`[1, 2, 3]`	`[1, 2, 3]`	Passed
reverse dependency	`[2, 3, 1]`	`[2, 3, 1]`	Passed
diamond duplicate	`None`	`[1, 2, 3]`	Failed
variable-length dependency chain	`[0, 1]`	`[0, 1]`	Passed

SHA-256 / e750dafde75a1135387989754d30075deb966505e52feeb28950d1721bcbb3f5

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}
    indegree = {v:0 for v in vertices}
    for u,v in edges:
        if v not in adj[u]: indegree[v] += 1
        adj[u].add(v)
    ready = sorted(v for v in vertices if indegree[v] == 0)
    answer = []
    while ready:
        u = ready.pop(0); answer.append(u)
        for v in sorted(adj[u]):
            indegree[v] -= 1
            if indegree[v] == 0: ready.append(v)
        ready.sort()
    return answer
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c = N,N+1,N+2
check('duplicate dependency', solve([a,b], [(a,b),(a,b)]), [a,b])
check('cycle with independent prefix', solve([a,b,c], [(b,c),(c,b)]), None)
check('self cycle', solve([a], [(a,a)]), None)
check('empty', solve([], []), [])
check('isolated lexicographic order', solve([c,a,b], []), [a,b,c])
check('reverse dependency', solve([a,b,c], [(c,a)]), [b,c,a])
check('diamond duplicate', solve([a,b,c], [(a,c),(b,c),(b,c)]), [a,b,c])
check('variable-length dependency chain', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N+1)))
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 fixture	Actual	Expected	Outcome
duplicate dependency	`[1, 2]`	`[1, 2]`	Passed
cycle with independent prefix	`[1]`	`None`	Failed
self cycle	`[]`	`None`	Failed
empty	`[]`	`[]`	Passed
isolated lexicographic order	`[1, 2, 3]`	`[1, 2, 3]`	Passed
reverse dependency	`[2, 3, 1]`	`[2, 3, 1]`	Passed
diamond duplicate	`[1, 2, 3]`	`[1, 2, 3]`	Passed
variable-length dependency chain	`[0, 1]`	`[0, 1]`	Passed

SHA-256 / 81b0cebea6659f9eac2b19938be35b6f26c9e0c311be89fcd26fe66f3b5d495b

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

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.321386+00:00.

Case digest / 7e5c1a59b63d177df625c7846993fe6e4cd26297f1a040cf922a482e7183fbdb