basic_simplify output depends on identity-hashed set.pop() order

[balancedscorpion]

Summary

basic_simplify constructs set(link.crossings) and repeatedly calls set.pop(). Crossing objects use identity hashing, so RI/RII selection depends on allocator state. The resulting reduced PD can change even for the same input in one Python/Spherogram build.

The copied RI-only reducer spherogram.links.bands.search.remove_reidemeister_I has the same pattern.

Tested with Spherogram 2.4.1, Python 3.13.5, macOS arm64.

Minimal reproducer

import hashlib, json
from spherogram import Link
from spherogram.links.links_base import Crossing

pd = [
    [16,22,17,21], [0,14,1,13], [3,21,4,20], [17,11,18,10],
    [15,14,16,15], [18,6,19,5], [19,8,20,9], [7,7,8,6],
    [9,4,10,5], [25,25,0,24], [1,3,2,2], [23,12,24,13],
    [22,12,23,11],
]

def run(perturb):
    retained = [Crossing(f"p{i}") for i in range(perturb)]
    link = Link(pd)
    link.simplify("basic")
    out = [[int(v) for v in crossing] for crossing in link.PD_code()]
    digest = hashlib.sha256(
        json.dumps(out, separators=(",", ":")).encode()
    ).hexdigest()
    assert len(retained) == perturb
    return digest, out

for perturb in (0, 2):
    print(perturb, run(perturb))

Observed hashes:

0 bfb12a1e3c333c2932aac894fb527628a6a30a20804c541d23cbaa0d9ecb60df
2 45bee572f46c38cc1f25127458a7c37907d38d92eb6fa61af246544a42594dbf

Both results have four crossings and represent the same knot; the issue is that the concrete PD returned by an ostensibly serial simplification is allocator-order dependent. That breaks replay certificates and can also change which locally irreducible RI/RII representative feeds later heuristic simplifiers.

Source sites

In spherogram/links/simplify.py, basic_simplify currently does:

if to_visit is None:
    to_visit = set(link.crossings)
...
while to_visit:
    crossing = to_visit.pop()

links/bands/search.py::remove_reidemeister_I independently copies the same set/pop worklist.

Suggested direction

Assign a stable rank from the input link.crossings sequence and always select/enqueue affected crossings by that rank. RI/RII only removes crossings, so every changed crossing already has an input rank. The same treatment can be applied to the RI-only band-search reducer. A transcript-friendly implementation can then record the selected rank and eliminated crossings for each move.

[culler]

If you are a human, please explain in your own words what you are attempting to do and why the current behavior of Spherogram is a problem for you. Knot projections do not have unique PD codes. The code depends on an ordering of the edges of each component, and any starting edge is allowed. The list of X-terms in the PD code really is a set, not a list. There is no canonical order for those terms.

Moreover, there is no canonical order in which to apply Reidemeister moves when simplifying a knot. There can be advantages to doing simplifications in random order. Why should we not be allowed to benefit from that?