Bugs in Geodesic.origin_simplification and Geodesic.canonical #14

@Oscfon

Affects combisurf/quad_systems.py on master (f0d5ed6).

Summary

The cyclic reduction of closed walks in a quad system is incorrect. Geodesic.origin_simplification can return a Geodesic whose stored turn sequence does not describe its own path, can leave spurs and brackets in place, and can raise IndexError. Geodesic.canonical raises UnboundLocalError on a large fraction of inputs, which makes the public Walk constructor — and hence Walk.is_homotopic — fail outright.

There is already a failing doctest on master that points at this:

sage -t --force-lib combisurf/quad_systems.py
File "combisurf/quad_systems.py", line 723, in combisurf.quad_systems.Geodesic.origin_simplification
Failed example:
    p
Expected:
    Geodesic "deque([5, 8, 1, 14, 7, 2])" with turns "deque([(2, 2), (7, 1), (2, 1), (6, 1)])"
Got:
    Geodesic "deque([14, 7, 2, 5, 8, 1])" with turns "deque([(2, 1), (6, 1), (2, 3)])"

That particular example is benign on its own — the two walks are the same closed walk at different base points (rotation by 3; the cyclic turn sequences [2,6,2,2,2,7] and [2,2,7,2,6,2] are rotations, and both are cyclically geodesic). Note also that the neighbouring example, whose input is the same walk rotated by one, expects exactly the output the failing one produces.

Below are other examples showing other problems.

Reproducers

All of the following use the genus 2 example

sage: from combisurf import OrientedMap, QuadSystem, Geodesic, Walk
sage: m = OrientedMap(vp=[[0, 2, 4, 6], [5, 8, 10, 12], [3, 11, 13, 7, 1, 9]])
sage: Q = QuadSystem(m)

Every input is a closed walk that is geodesic as a path, i.e. a legitimate input.

1. Stored turn sequence does not match the returned path

sage: p = Geodesic(Q, [0, 7, 10, 5])
sage: p.origin_simplification()
sage: p
Geodesic "deque([7, 10, 5, 0])" with turns "deque([(2, 1), (3, 1), (2, 1)])"

The turn sequence of the path [7, 10, 5, 0] is (2,1)(3,1)(6,1), not (2,1)(3,1)(2,1): the last turn is wrong. The object is internally inconsistent, so anything computed from _turn_sequence afterwards (including canonical) works on a walk that does not exist.

2. IndexError

sage: p = Geodesic(Q, [5, 8, 15, 2])
sage: p.origin_simplification()
Traceback (most recent call last):
...
IndexError: deque index out of range

quad_systems.py:886, in the "bracket containing the origin" branch:

if first_turn == 1 and s[-2][0] == 1:

The preceding while first_turn == 2: loop can reduce s to a single run, after which s[-2] is out of range. The same unguarded s[-2] pattern appears at line 789.

3. A bracket is left in place

sage: p = Geodesic(Q, [0, 7, 10, 13])
sage: p.origin_simplification()
sage: p
Geodesic "deque([0, 7, 10, 13])" with turns "deque([(1, 1), (2, 2)])"

The walk is returned unchanged although its cyclic turn sequence is [1, 2, 2, 2], which is a bracket 1 2^2 1 read cyclically and should have been reduced.

4. Spurs are left in place

sage: p = Geodesic(Q, [4, 13, 14, 9, 12, 9])
sage: p.origin_simplification()
sage: p
Geodesic "deque([0, 1, 0, 11])" with turns "deque([(2, 3)])"

The result has cyclic turn sequence [0, 0, 2, 3] — two spurs. (Its stored turn sequence is wrong as well, cf. 1.)

5. Walk raises — this is the user-facing one

sage: m2 = OrientedMap(vp=[[0, 2, 4, 6], [7, 8, 5], [9, 10, 12, 11], [3, 15, 1, 13, 14]])
sage: Q2 = QuadSystem(m2)
sage: Walk(Q2, [15, 13, 12, 1, 0])
Traceback (most recent call last):
...
UnboundLocalError: cannot access local variable 'e1' where it is not associated with a value

quad_systems.py:1003, in Geodesic.canonical:

l = deque([])
e = geo[0]
for j in range(n2):
    e = geo[1 + j]
    e1 = Q._ep(e)
    l.append(fp[fp[e1]])
x = fp[vp[e1]]          # e1 is unbound when n2 == 0

e1 is assigned only inside the loop, so it is unbound whenever n2 == 0.

Invariants worth asserting in tests

These are what the enumeration above checked, and each is violated on master. They make good check=True assertions and good property tests:

1. rle(turns(p._geodesic)) == p._turn_sequence — the stored turn sequence describes the stored path.
2. The cyclic turn sequence of the result contains no 0 (no spur) and no factor 1 2^k 1 or (d-1)(d-2)^k(d-1) (no bracket).
3. origin_simplification is idempotent.
4. origin_simplification is equivariant under rotation of the input: reducing a rotation gives a rotation of the reduction.
5. The result never grows, and its length has the same parity as the input's.

Notes

• test_KMP (quad_systems.py:327), used by Walk.is_homotopic, is a separate defect and does not terminate on some inputs — e.g. test_KMP([1, 1], [1, 0]) loops forever. The failure table is built with T.append(u[cnd]) instead of T.append(T[cnd]), the inner loop tests u[i] == u[cnd] instead of !=, and cnd += 1 is inside the else branch instead of after the if/else. Probably deserves its own issue.
• LazyGeodesic.__init__ never assigns _last when the turn argument is given (self._first = geo[-1] should be self._last = geo[-1]), and LazyGeodesic.add_edge_left calls self._turn_sequence.appendleft() with no argument when removing a spur whose leading run has multiplicity > 1 (e.g. adding [6, 1, 14, 15, 12, 1, 0] one at a time). Also probably separate issues.