FA-88836 / Mesh topology invariants / Open access

Adjacent pair count uses interior edges · case 01

Face pairs sharing two edges or fins are miscounted.

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

ROOT CAUSE

The pair total counts edges with two incident faces instead of distinct face pairs.

VERIFIED REPAIR

Halve the sum of distinct degrees.

Unsuccessful approach: Summing degrees without halving counts every pair twice.

Case contract

Input: polygon faces. Two faces are adjacent when they share an undirected edge (fins give every pair on the edge). Return [distinct adjacent face count per face, number of adjacent face pairs].

Why this case matters

Mesh processing pipelines (remeshing, export, simulation, printing) trust these topological counts and adjacency answers; a wrong invariant silently accepts broken meshes or rejects valid ones.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    ef={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            a,b=f[i],f[(i+1)%n]
            ef.setdefault((min(a,b),max(a,b)),[]).append(fi)
    deg=[]
    for fi,f in enumerate(faces):
        n=len(f)
        nbs=set()
        for i in range(n):
            a,b=f[i],f[(i+1)%n]
            for g in ef[(min(a,b),max(a,b))]:
                if g!=fi: nbs.add(g)
        deg.append(len(nbs))
    return [deg,len([k for k,v in ef.items() if len(v)==2])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]]], [['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], [[0, 0], 0]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]], ['single face', [[[0, 1, 2]]], [[0], 0]]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['single face', [[[0, 1, 2]]], [[0], 0]]], [['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], [[0, 0], 0]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
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
tetrahedron	`[[3, 3, 3, 3], 6]`	`[[3, 3, 3, 3], 6]`	Passed
book	`[[2, 2, 2], 0]`	`[[2, 2, 2], 3]`	Failed
flipped pair	`[[1, 1], 1]`	`[[1, 1], 1]`	Passed
two triangles sharing two edges	`[[1, 1], 3]`	`[[1, 1], 1]`	Failed
quad grid	`[[2, 2, 2, 2], 4]`	`[[2, 2, 2, 2], 4]`	Passed
disk	`[[2, 2, 2, 2, 2], 5]`	`[[2, 2, 2, 2, 2], 5]`	Passed
cube	`[[4, 4, 4, 4, 4, 4], 12]`	`[[4, 4, 4, 4, 4, 4], 12]`	Passed

SHA-256 / 54a87a9d4f44dc7c5d7ae309103726900d1551f4fe9cceb58ac31bb1a0bb57a2

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    ef={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            a,b=f[i],f[(i+1)%n]
            ef.setdefault((min(a,b),max(a,b)),[]).append(fi)
    deg=[]
    for fi,f in enumerate(faces):
        n=len(f)
        nbs=set()
        for i in range(n):
            a,b=f[i],f[(i+1)%n]
            for g in ef[(min(a,b),max(a,b))]:
                if g!=fi: nbs.add(g)
        deg.append(len(nbs))
    return [deg,sum(deg)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]]], [['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], [[0, 0], 0]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]], ['single face', [[[0, 1, 2]]], [[0], 0]]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['single face', [[[0, 1, 2]]], [[0], 0]]], [['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], [[0, 0], 0]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
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
tetrahedron	`[[3, 3, 3, 3], 12]`	`[[3, 3, 3, 3], 6]`	Failed
book	`[[2, 2, 2], 6]`	`[[2, 2, 2], 3]`	Failed
flipped pair	`[[1, 1], 2]`	`[[1, 1], 1]`	Failed
two triangles sharing two edges	`[[1, 1], 2]`	`[[1, 1], 1]`	Failed
quad grid	`[[2, 2, 2, 2], 8]`	`[[2, 2, 2, 2], 4]`	Failed
disk	`[[2, 2, 2, 2, 2], 10]`	`[[2, 2, 2, 2, 2], 5]`	Failed
cube	`[[4, 4, 4, 4, 4, 4], 24]`	`[[4, 4, 4, 4, 4, 4], 12]`	Failed

SHA-256 / d7cb77fc7ff5b3e837a21c36af959095bc5ad8a8b347dbb354a0f47c8dbc965d

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces=x
    ef={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            a,b=f[i],f[(i+1)%n]
            ef.setdefault((min(a,b),max(a,b)),[]).append(fi)
    deg=[]
    for fi,f in enumerate(faces):
        n=len(f)
        nbs=set()
        for i in range(n):
            a,b=f[i],f[(i+1)%n]
            for g in ef[(min(a,b),max(a,b))]:
                if g!=fi: nbs.add(g)
        deg.append(len(nbs))
    return [deg,sum(deg)//2]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]]], [['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], [[0, 0], 0]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]], ['single face', [[[0, 1, 2]]], [[0], 0]]], [['tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [[3, 3, 3, 3], 6]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [[1, 1], 1]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[1, 1], 1]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['single face', [[[0, 1, 2]]], [[0], 0]]], [['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], [[2, 2, 2], 3]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [[2, 2, 2, 2], 4]], ['disk', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]]], [[2, 2, 2, 2, 2], 5]], ['cube', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [[4, 4, 4, 4, 4, 4], 12]], ['bowtie', [[[0, 1, 2], [0, 3, 4]]], [[0, 0], 0]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [[2, 2, 2], 3]], ['quad torus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0], [3, 6, 7, 4], [4, 7, 8, 5], [5, 8, 6, 3], [6, 0, 1, 7], [7, 1, 2, 8], [8, 2, 0, 6]]], [[4, 4, 4, 4, 4, 4, 4, 4, 4], 18]]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
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
tetrahedron	`[[3, 3, 3, 3], 6]`	`[[3, 3, 3, 3], 6]`	Passed
book	`[[2, 2, 2], 3]`	`[[2, 2, 2], 3]`	Passed
flipped pair	`[[1, 1], 1]`	`[[1, 1], 1]`	Passed
two triangles sharing two edges	`[[1, 1], 1]`	`[[1, 1], 1]`	Passed
quad grid	`[[2, 2, 2, 2], 4]`	`[[2, 2, 2, 2], 4]`	Passed
disk	`[[2, 2, 2, 2, 2], 5]`	`[[2, 2, 2, 2, 2], 5]`	Passed
cube	`[[4, 4, 4, 4, 4, 4], 12]`	`[[4, 4, 4, 4, 4, 4], 12]`	Passed

SHA-256 / c54087370652ea8cf05f9c98109d9a7f518372e1f61e5182871a1df7f6a39744

Verification & scope

Pure combinatorial teaching model over integer face lists with a stipulated contract; no geometry kernel or file format is implied. 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:51:11.687210+00:00.

Case digest / 28d70b89d074497a7cb2e08dbc1f6ada176838d04ed58f56527c1946128932e2