FA-88826 / Mesh topology invariants / Open access

Face is counted as its own neighbour · case 01

Every face degree is one too high.

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

ROOT CAUSE

The face itself is not excluded from the edge incidence list.

VERIFIED REPAIR

Skip g == fi.

Unsuccessful approach: Keeping only later faces halves the adjacency of earlier faces.

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))]:
                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]], ['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]]], [['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]], ['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]], ['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]]], [['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]], ['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]]]]
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	`[[4, 4, 4, 4], 8]`	`[[3, 3, 3, 3], 6]`	Failed
book	`[[3, 3, 3], 4]`	`[[2, 2, 2], 3]`	Failed
flipped pair	`[[2, 2], 2]`	`[[1, 1], 1]`	Failed
two triangles sharing two edges	`[[2, 2], 2]`	`[[1, 1], 1]`	Failed
quad grid	`[[3, 3, 3, 3], 6]`	`[[2, 2, 2, 2], 4]`	Failed
disk	`[[3, 3, 3, 3, 3], 7]`	`[[2, 2, 2, 2, 2], 5]`	Failed
cube	`[[5, 5, 5, 5, 5, 5], 15]`	`[[4, 4, 4, 4, 4, 4], 12]`	Failed

SHA-256 / 15175c595868548e7854a8cc961c58858d26c7c0f87efa52fe4fa2ed4765bbc6

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)//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]], ['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]]], [['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]], ['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]], ['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]]], [['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]], ['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]]]]
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, 2, 1, 0], 3]`	`[[3, 3, 3, 3], 6]`	Failed
book	`[[2, 1, 0], 1]`	`[[2, 2, 2], 3]`	Failed
flipped pair	`[[1, 0], 0]`	`[[1, 1], 1]`	Failed
two triangles sharing two edges	`[[1, 0], 0]`	`[[1, 1], 1]`	Failed
quad grid	`[[2, 1, 1, 0], 2]`	`[[2, 2, 2, 2], 4]`	Failed
disk	`[[2, 1, 1, 1, 0], 2]`	`[[2, 2, 2, 2, 2], 5]`	Failed
cube	`[[4, 4, 2, 1, 1, 0], 6]`	`[[4, 4, 4, 4, 4, 4], 12]`	Failed

SHA-256 / 78c28cc2e139d6916272aac4cbbef74a96c0216e78bae0536ef8ca23d03f3312

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]], ['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]]], [['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]], ['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]], ['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]]], [['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]], ['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]]]]
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 / d9106b7725ca2b249b0ae0c5bb7bc5951912688c71fa755c8c504713c6efcf68

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

Case digest / a84990fe7d21a6824f73d0b390fbf1c48e4a086bbfbab133db129459fdfa675d