neato-family multispline router: ties in the triangle shortest path are broken by GTS's pointer-hash face order
Edges with multi-edges or boundary ports (splines=true|spline|polyline) go through makeMultiSpline, which runs Dijkstra (triPath) over the triangles of a constrained Delaunay triangulation. When two triangle paths have exactly the same cost — typically a symmetric layout where the edge can go above or below a node — the winner depends on the face numbering. C numbers the faces in the order gts_surface_foreach_face visits them, which is GTS's GHashTable order of face pointers; the port numbers them in creation order. The port then mirrors the route (here below the head node instead of above it).
Reproducer
graph "G" {
layout=sfdp;
splines="true";
edge [headport="e"];
"n5" [shape="circle", label="→ arrow"];
{"n5"} -- "n12";
}
GVBINDIR=<pango-free plugins> dot -Ksfdp -Tsvg repro.gv # C Graphviz 16.1.0
graphviz-pure -Ksfdp -Tsvg repro.gv # port
C output vs port
--- c.svg
+++ rust.svg
@@ -26 +26 @@
-<path fill="none" stroke="black" d="M85.73,-34.99C137.89,-25.98 228.99,-13.78 306.94,-21.46 317.19,-22.47 321.8,-20.68 329.21,-27.83 334.35,-32.79 334.19,-43.11 334.19,-43.11"/>
+<path fill="none" stroke="black" d="M85.73,-51.44C137.89,-60.45 228.99,-72.65 306.94,-64.97 317.19,-63.96 321.8,-65.75 329.21,-58.6 334.35,-53.64 334.19,-43.31 334.19,-43.31"/>
Root cause
C, lib/neatogen/delaunay.c:447-480 (mkSurface): face indices come from gts_surface_foreach_face(s, cntFace, ...), i.e. GTS's hash-table iteration over face pointers; lib/neatogen/multispline.c:1104-1148 (triPath) keeps the first-found parent on equal distances (N_VAL(pq, adjn) < d).
Port, crates/graphviz-pure-layout/src/neatogen/multispline.rs:263-335 (mk_surface): faces are numbered in creation order (a documented deviation, docs/porting/neato.md, "The makeMultiSpline router's triangulation numbers faces in creation order, not GTS's pointer-hash order").
Confirmed by experiment: dumping C's face order with a DYLD_INSERT_LIBRARIES shim around gts_surface_foreach_face and feeding it to a patched port that renumbers its (identical) triangles in that order makes the port match C byte for byte on all three cases. The order is address-dependent in C: an intermediate minimisation of s33154 gives two different C outputs from run to run, and both are reproduced by the port when given that run's face order.
Why the port does not match: C's result depends on heap addresses of GTS faces, which the port cannot reproduce in general (it would mean modelling GLib's direct-hash bucket order over malloc addresses). The port keeps the deterministic creation order. Suggest closing as wontfix (upstream nondeterminism); revisit only if a cheap model of the hash order turns out to match C for the usual allocation pattern.
Cases
3 fuzz case(s): seeds 23516, 33154, 10372. Regenerate a case with python3 -I scripts/fuzz-gen.py --seed N (checked byte for byte for seed 23516).
Files
tests/fuzz-open/026-neato-multispline-face-order (repro.gv, c.svg, rust.svg, cmd.txt, cases.txt)
C and the port
C onlyport onlyboth: in register
Rasterising…
C ink onlyport ink onlysame pixel, faded
Warning: Warning: no value for width of non-ASCII character 226. Falling back to width of space characterWarning: Warning: no value for width of non-ASCII character 226. Falling back to width of space characterReproduce
graph "G" {layout=sfdp;splines="true";edge [headport="e"];"n5" [shape="circle", label="→ arrow"];{"n5"} -- "n12";}C: GVBINDIR=<pango-free plugins> dot -Ksfdp -Tsvg repro.gvport: graphviz-pure -Ksfdp -Tsvg repro.gvr3/diff/s23516.gv seed=23516r4/diff/s33154.gv seed=33154 # twopir2/diff/s10372.gv seed=10372Files: c.stderr, c.svg, cases.txt, cmd.txt, repro.gv, rust.stderr, rust.svg. Source: tests/fuzz-open/026-neato-multispline-face-order.
