Skip to content
graphviz-pure

twopi: edge routes on the arrows graphs change from run to run in C (floating-point tie)

Kind
Upstream C behaviour
Severity
medium
Engine
twopi
Category
splines
Cases
8
Seeds
·
Tracking
GitHub issuewon't fix
Labels
fidelityengine:twopiupstream-cwontfix

On the arrows family of graphs (twopi, splines=true), C Graphviz 16.1.0 does not give the same output from one run to the next. Nodes Z, i and I (and their mirror images lower down) are exactly vertically aligned, so the edge between Z and I has a tie: it can run straight, pass the obstacle in between on the left, or pass it on the right. The same C binary gives 3 or 4 different SVGs over 20 runs of each of the 8 files. The port is deterministic. It always produces one of these routes, but its combination of routes for the whole file matches a C run only some of the time (in 20 runs, oldarrows matched 2 of them and the other 7 files matched none). This is why gv-diff shows twopi at 282/289 exact and why gv-diff e2e records the 8 files as unstable and skips them (tests/golden/e2e.json, unstable).

Reproducer

digraph G {
layout=twopi;

  // leave some space for the head/taillabels
  graph [ranksep=1.5 splines=true overlap=false]

  // to avoid confusion, remember this:
  // it's spelt tail/head, but it's read start/end

  // emphasize theatrically
//  edge [arrowsize=2]
  // put head/tail labels farther from the node
  edge [labeldistance=3]

  // not interested in node labels
  node [shape=circle width=0.5 label=""]

  {
    edge [dir=back samehead=ahead]
    a->Z [arrowtail=none taillabel=none]
    b->Z [arrowtail=normal taillabel=normal]
    c->Z [arrowtail=inv taillabel=inv]
    d->Z [arrowtail=dot taillabel=dot]
    e->Z [arrowtail=odot taillabel=odot]
    f->Z [arrowtail=invdot taillabel=invdot]
    g->Z [arrowtail=invodot taillabel=invodot]
    h->Z [arrowtail=open taillabel=open]
    i->Z [arrowtail=halfopen taillabel=halfopen arrowhead=inv headlabel=samehead]
    j->Z [arrowtail=empty taillabel=empty]
    k->Z [arrowtail=invempty taillabel=invempty]
    l->Z [arrowtail=diamond taillabel=diamond]
    m->Z [arrowtail=odiamond taillabel=odiamond]
    n->Z [arrowtail=box taillabel=box]
    o->Z [arrowtail=obox taillabel=obox]
    p->Z [arrowtail=tee taillabel=tee]
    q->Z [arrowtail=crow taillabel=crow]
  }
  {
    edge [dir=forward sametail=atail]
    Z->A [arrowhead=none headlabel=none]
    Z->B [arrowhead=normal headlabel=normal]
    Z->C [arrowhead=inv headlabel=inv]
    Z->D [arrowhead=dot headlabel=dot]
    Z->E [arrowhead=odot headlabel=odot]
    Z->F [arrowhead=invdot headlabel=invdot]
    Z->G [arrowhead=invodot headlabel=invodot]
    Z->H [arrowhead=open headlabel=open]
    Z->I [arrowhead=halfopen headlabel=halfopen arrowtail=inv taillabel=sametail]
    Z->J [arrowhead=empty headlabel=empty]
    Z->K [arrowhead=invempty headlabel=invempty]
    Z->L [arrowhead=diamond headlabel=diamond]
    Z->M [arrowhead=odiamond headlabel=odiamond]
    Z->N [arrowhead=box headlabel=box]
    Z->O [arrowhead=obox headlabel=obox]
    Z->P [arrowhead=tee headlabel=tee]
    Z->Q [arrowhead=crow headlabel=crow]
  }
}

# run several times: C gives 3 different outputs
GVBINDIR=<pango-free plugins> dot -Ktwopi -Tsvg repro.gv
graphviz-pure -Ktwopi -Tsvg repro.gv

C output vs port (C's most frequent variant vs the port; c-variant2.svg is a second C run, where the same edge is straight)

--- c.svg	2026-10-19 09:18:53
+++ rust.svg	2026-10-19 09:18:53
@@ -128,10 +128,10 @@
 <!-- Z&#45;&gt;I -->
 <g id="edge26" class="edge">
 <title>Z&#45;&gt;I</title>
-<path fill="none" stroke="black" d="M297.2,-306.09C315.04,-347.89 355.19,-459.08 318.19,-540.71 317.14,-543.02 315.67,-545.11 313.93,-546.99"/>
-<polygon fill="black" stroke="black" points="306.48,-553.06 311.39,-543.26 310.2,-550.03 314.23,-546.74 314.23,-546.74 306.48,-553.06"/>
-<text xml:space="preserve" text-anchor="middle" x="319.39" y="-521.99" font-family="Times,serif" font-size="14.00">halfopen</text>
-<text xml:space="preserve" text-anchor="middle" x="319.2" y="-322.28" font-family="Times,serif" font-size="14.00">sametail</text>
+<path fill="none" stroke="black" d="M281.91,-306.09C264.07,-347.89 223.92,-459.08 260.92,-540.71 261.97,-543.02 263.44,-545.11 265.18,-546.99"/>
+<polygon fill="black" stroke="black" points="272.63,-553.06 262.03,-550.23 268.91,-550.03 264.88,-546.74 264.88,-546.74 272.63,-553.06"/>
+<text xml:space="preserve" text-anchor="middle" x="243.7" y="-541.65" font-family="Times,serif" font-size="14.00">halfopen</text>
+<text xml:space="preserve" text-anchor="middle" x="283.39" y="-331.85" font-family="Times,serif" font-size="14.00">sametail</text>
 </g>
 <!-- J -->
 <g id="node28" class="node">

Root cause

The routing happens in the neato spline code that twopi uses: lib/neatogen/neatosplines.c:633-705 (_spline_edges: the visibility-graph path from getPath/Pobspath, then makeSpline at lib/neatogen/neatosplines.c:538). In the port this is crates/graphviz-pure-layout/src/neatogen/neatosplines.rs:135 (spline_edges_route) and crates/graphviz-pure-layout/src/neatogen/routing.rs:193 (make_spline). The node positions are the same in every C run; only the edge routes change. The C output still varies with MallocPreScribble=1 MallocScribble=1, so reads of uninitialised heap memory are unlikely, and the variation probably comes from something that depends on addresses. The exact C statement has not been confirmed yet. One candidate is cmpitems (lib/neatogen/neatosplines.c:124), which orders multi-edge keys by node pointer, but no link from it to the route has been shown. The documentation used to say this tie differs from build to build (docs/porting/circo-twopi.md:32-37). In fact the same build differs from run to run.

Why the port does not match: no single deterministic output can match an output that changes between runs. The port computes the routes in a fixed order and returns the same SVG every time. We propose closing this as upstream C nondeterminism. If the C source is found and turns out to be deterministic under some condition, the port could follow it.

Cases

8 corpus files (all twopi arrows variants): tests/twopi/fx_arrows.gv, tests/twopi/wild_gv16_directed_oldarrows_f70da3.gv, tests/twopi/wild_gv16_graphs_arrows_148b6b.gv, tests/twopi/wild_gv16_graphs_arrowsize_46ccd8.gv, tests/twopi/wild_gv16_graphs_newarrows_769825.gv, tests/twopi/wild_gv16_linux_x86_arrows_dot_1ce23f.gv, tests/twopi/wild_wild_graphs_arrows_a4826e.gv, tests/twopi/wild_wild_graphs_arrowsize_ccef6e.gv.

Files

tests/fuzz-open/032-twopi-arrows-c-nondeterministic-routing

C and the port

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

C onlyport onlyboth: in register

Reproduce

repro.gv
digraph G {
layout=twopi;


  // leave some space for the head/taillabels
  graph [ranksep=1.5 splines=true overlap=false]


  // to avoid confusion, remember this:
  // it's spelt tail/head, but it's read start/end


  // emphasize theatrically
//  edge [arrowsize=2]
  // put head/tail labels farther from the node
  edge [labeldistance=3]


  // not interested in node labels
  node [shape=circle width=0.5 label=""]


  {
    edge [dir=back samehead=ahead]
    a->Z [arrowtail=none taillabel=none]
    b->Z [arrowtail=normal taillabel=normal]
    c->Z [arrowtail=inv taillabel=inv]
    d->Z [arrowtail=dot taillabel=dot]
    e->Z [arrowtail=odot taillabel=odot]
    f->Z [arrowtail=invdot taillabel=invdot]
    g->Z [arrowtail=invodot taillabel=invodot]
    h->Z [arrowtail=open taillabel=open]
    i->Z [arrowtail=halfopen taillabel=halfopen arrowhead=inv headlabel=samehead]
    j->Z [arrowtail=empty taillabel=empty]
    k->Z [arrowtail=invempty taillabel=invempty]
    l->Z [arrowtail=diamond taillabel=diamond]
    m->Z [arrowtail=odiamond taillabel=odiamond]
    n->Z [arrowtail=box taillabel=box]
    o->Z [arrowtail=obox taillabel=obox]
    p->Z [arrowtail=tee taillabel=tee]
    q->Z [arrowtail=crow taillabel=crow]
  }
  {
    edge [dir=forward sametail=atail]
    Z->A [arrowhead=none headlabel=none]
    Z->B [arrowhead=normal headlabel=normal]
    Z->C [arrowhead=inv headlabel=inv]
    Z->D [arrowhead=dot headlabel=dot]
    Z->E [arrowhead=odot headlabel=odot]
    Z->F [arrowhead=invdot headlabel=invdot]
    Z->G [arrowhead=invodot headlabel=invodot]
    Z->H [arrowhead=open headlabel=open]
    Z->I [arrowhead=halfopen headlabel=halfopen arrowtail=inv taillabel=sametail]
    Z->J [arrowhead=empty headlabel=empty]
    Z->K [arrowhead=invempty headlabel=invempty]
    Z->L [arrowhead=diamond headlabel=diamond]
    Z->M [arrowhead=odiamond headlabel=odiamond]
    Z->N [arrowhead=box headlabel=box]
    Z->O [arrowhead=obox headlabel=obox]
    Z->P [arrowhead=tee headlabel=tee]
    Z->Q [arrowhead=crow headlabel=crow]
  }
}
cmd.txt
GVBINDIR=$HOME/src/gv-ref/lutplugins dot -Ktwopi -Tsvg repro.gv   # run it several times: 3 different outputs
graphviz-pure -Ktwopi -Tsvg repro.gv
cases.txt
tests/twopi/fx_arrows.gv
tests/twopi/wild_gv16_directed_oldarrows_f70da3.gv
tests/twopi/wild_gv16_graphs_arrows_148b6b.gv
tests/twopi/wild_gv16_graphs_arrowsize_46ccd8.gv
tests/twopi/wild_gv16_graphs_newarrows_769825.gv
tests/twopi/wild_gv16_linux_x86_arrows_dot_1ce23f.gv
tests/twopi/wild_wild_graphs_arrows_a4826e.gv
tests/twopi/wild_wild_graphs_arrowsize_ccef6e.gv

Files: c-variant2.svg, c.svg, cases.txt, cmd.txt, repro.gv, rust.svg. Source: tests/fuzz-open/032-twopi-arrows-c-nondeterministic-routing.

All open issues