Skip to content
graphviz-pure

sfdp smoothing=rng: C's output changes from run to run (port matches one of C's outputs)

Kind
Upstream C behaviour
Severity
low
Engine
sfdp
Category
layout
Cases
1
Seeds
23510
Tracking
GitHub issuewon't fix
Labels
fidelityfuzzengine:sfdpupstream-cwontfix

With smoothing=rng, C sfdp gives different layouts on repeated runs of the same input (the reproducer gives 2 distinct outputs in 12 runs; the original case 4 in 10). Removing smoothing=rng makes C deterministic (16/16 identical). The port is deterministic and its output equals one of C's outputs, so there is nothing to fix in the port; this records the C nondeterminism so the case is not re-triaged.

Reproducer

graph "fuzz 23510" {
layout=sfdp;
smoothing="rng";
{"v28" "v7" "v39"} -- "v11";
"v1" -- subgraph "s83" {"v42" "v33"};
"v44":"c" -- "v42" [tailport="s"];
"v39" -- "v42" [arrowsize="2.45"];
"v27" -- subgraph "s114" {"v45" "v38" "v1"};
"v20" -- "v11" [label="עברית\lπ\ltab	here\ltab	here\n"];
}

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

The port's output (rust.svg) is identical to C run A (c.svg). Two C runs of the same command differ (first lines of the diff):

--- c.svg (run A)
+++ c-run2.svg (run B)
@@ -6,3 +6,3 @@
-<svg width="739pt" height="285pt"
- viewBox="0.00 0.00 739.00 285.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
-<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 280.63)">
+<svg width="740pt" height="295pt"
+ viewBox="0.00 0.00 740.00 295.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 290.8)">
@@ -10 +10 @@
-<polygon fill="white" stroke="none" points="-4,4 -4,-280.63 734.96,-280.63 734.96,4 -4,4"/>
+<polygon fill="white" stroke="none" points="-4,4 -4,-290.8 735.88,-290.8 735.88,4 -4,4"/>
@@ -14,2 +14,2 @@
-<ellipse fill="none" stroke="black" cx="74.45" cy="-241.04" rx="27" ry="18"/>
-<text xml:space="preserve" text-anchor="middle" x="74.45" y="-236.84" font-family="Times,serif" font-size="14.00">v28</text>
+<ellipse fill="none" stroke="black" cx="75.5" cy="-250.19" rx="27" ry="18"/>
+<text xml:space="preserve" text-anchor="middle" x="75.5" y="-245.99" font-family="Times,serif" font-size="14.00">v28</text>
@@ -20,2 +20,2 @@
-<ellipse fill="none" stroke="black" cx="134.21" cy="-148.3" rx="27" ry="18"/>
-<text xml:space="preserve" text-anchor="middle" x="134.21" y="-144.1" font-family="Times,serif" font-size="14.00">v11</text>
+<ellipse fill="none" stroke="black" cx="134.12" cy="-156.72" rx="27" ry="18"/>
+<text xml:space="preserve" text-anchor="middle" x="134.12" y="-152.52" font-family="Times,serif" font-size="14.00">v11</text>
@@ -26 +26 @@
-<path fill="none" stroke="black" d="M85.14,-224.46C95.95,-207.69 112.57,-181.89 123.42,-165.05"/>

Root cause

C, lib/sfdpgen/post_process.c:968-980: smoothing=rng runs TriangleSmoother_new(A, dim, x, false), which builds its graph with call_tri2 (lib/neatogen/call_tri.c:64, UG_graph from lib/neatogen/delaunay.c, a GTS Delaunay triangulation). The run-to-run dependence is in this path (removing the option removes it); the exact address-dependent step (most likely GTS's pointer-keyed hash iteration, as in neato-multispline-face-order) is root cause not yet confirmed.

Port: crates/graphviz-pure-layout/src/sfdpgen is deterministic. Suggest wontfix (upstream nondeterminism); the fuzz harness already classifies this as c_unstable when it catches two different C runs.

Cases

1 fuzz case(s): seeds 23510. Regenerate a case with python3 -I scripts/fuzz-gen.py --seed N (checked byte for byte for seed 23510).

Files

tests/fuzz-open/030-sfdp-smoothing-rng-c-unstable (repro.gv, c.svg and c-run2.svg — two C runs —, rust.svg, cmd.txt, cases.txt)

C and the port

Comparing…
C Graphviz 16.1.0 output, cyan plategraphviz-pure output, magenta plate

C onlyport onlyboth: in register

c.stderr
Warning: Warning: no value for width of non-ASCII character 215. Falling back to width of space character
Warning: Warning: no value for width of ASCII character 9. Falling back to 0
rust.stderr
Warning: Warning: no value for width of non-ASCII character 215. Falling back to width of space character
Warning: Warning: no value for width of ASCII character 9. Falling back to 0

Reproduce

repro.gv
graph "fuzz 23510" {
layout=sfdp;
smoothing="rng";
{"v28" "v7" "v39"} -- "v11";
"v1" -- subgraph "s83" {"v42" "v33"};
"v44":"c" -- "v42" [tailport="s"];
"v39" -- "v42" [arrowsize="2.45"];
"v27" -- subgraph "s114" {"v45" "v38" "v1"};
"v20" -- "v11" [label="עברית\lπ\ltab  here\ltab  here\n"];
}
cmd.txt
C:    GVBINDIR=<pango-free plugins> dot -Ksfdp -Tsvg repro.gv
port: graphviz-pure -Ksfdp -Tsvg repro.gv
cases.txt
r3/diff/s23510.gv seed=23510  # c_unstable: 4 distinct C outputs in 10 runs; the port matches one

Files: c-run2.svg, c.stderr, c.svg, cases.txt, cmd.txt, repro.gv, rust.stderr, rust.svg. Source: tests/fuzz-open/030-sfdp-smoothing-rng-c-unstable.

All open issues