FA-88821 / Mesh topology invariants / Open access

Face adjacency counts a neighbour once per shared edge · case 01

Faces sharing two edges report degree 2 for one neighbour.

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

ROOT CAUSE

Neighbours are accumulated in a list, one entry per shared edge.

VERIFIED REPAIR

Collect neighbours in a set.

Unsuccessful approach: Deduplicating by (face, edge) still counts a neighbour per edge.

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=[]
        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.append(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]]], [['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]], ['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]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[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	`[[3, 3], 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 / ed062e9aa1ed4ad399105a6317406def2ad85538ef755f1a22c5ec1cc13fcf6c

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,min(a,b)))
        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]]], [['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]], ['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]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[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	`[[2, 2], 2]`	`[[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 / 9295e6ab35780edcadf22aaef52bcc6dfd8e36ed98dd9d9182e9ff2c7ff13347

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]]], [['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]], ['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]], ['two triangles sharing two edges', [[[0, 1, 2], [1, 0, 2]]], [[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 / ee4de3924f8145fb61bf1d9f2bd9ea9140a6c008938f6670a6e6c0dae5bf7363

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

Case digest / a04128fb5b98bb8f1de218b91e0d641e2b46a79c627fe1f90e1333c7eb70480b