neato port (Graphviz 16.1.0)

Copied at build time from docs/porting/neato.md.

`layout=neato` (and `-Kneato`) now runs a function-by-function port of `lib/neatogen` plus the shared infrastructure the other non-dot engines need. The old stand-in (`force_circular::layout_neato`) is no longer dispatched; `force_circular.rs` still serves fdp, sfdp, twopi, circo, osage and patchwork until their ports land.

Entry point: graphviz_pure_layout::neatogen::neatoinit::neato_layout(&mut Graph).

Fidelity

gv-diff against C 16.1.0 goldens (built-in text metrics, see scripts/gen-golden.sh):

corpus	before	after
tests/neato (438 files; 307 at the start)	62 exact, score 95.97/307 (31%)	438 exact, score 438.0/438 (100%)
main corpus, the two layout=neato files	0/12 nodes, 0/11 edges	both exact
main corpus overall (508 files)	—	no regressions; renderer/gv-diff fixes from this branch add exact files

Node positions, edge splines, label positions, cluster and graph boxes match C within the gv-diff tolerances on every tests/neato file, including mode=hier|ipsep, overlap=ortho*|portho*|vpsc|ipsep and multi-edge routing (see Gap closure).

Full-pipeline -Tsvg byte identity (gv-diff e2e --filter neato/, the 343 files hashed in tests/golden/e2e.json): 335/343. Seven of the rest are the overlap=false arrow graphs (prism’s GTS matrix order, an ulp in a label coordinate flips a printed digit) and one is splines=ortho.

Most layouts are bit-identical to C: floating-point expressions follow the C source as compiled by clang with -ffp-contract=on (an expression a*b + c is computed as fma(a, b, c), a float*float product added to a double is rounded to float first, x - y*z is fma(-y, z, x)), and every random number, sort and container order reproduces macOS libc/cgraph behaviour.

Validation

• cargo run --release -p graphviz-pure-diff -- --golden tests/golden/neato --baseline tests/golden/neato-baseline.json tests/neato (ratchet test: crates/graphviz-pure-diff/tests/neato_fidelity.rs).
• Corpus: tests/neato/*.gv is generated by scripts/gen-neato-corpus.py (fixtures and undirected wild graphs with layout=neato forced, plus hand-written cases for modes, models, start, pos/pin, len/weight, overlap modes, sep/esep, splines, pack/packmode, labels, ports, ratio/size, random graphs up to 120 nodes). Goldens: scripts/gen-golden.sh writes tests/golden/neato/. Cases whose C output is not reproducible run to run (start=rand uses the clock; ngk10_4 reads uninitialised memory) and model=circuit mode=KK (segfaults in C 16.1.0) are excluded.
• A locally built, instrumentable C copy lives in ~/src/gv-ref/build-neato (run.sh); it matches Homebrew’s output to the last printed digit on almost all files.

Module ↔ C file map

graphviz_pure_layout::cutil (C library behaviour)

Rust	C
Drand48	POSIX drand48/srand48 (48-bit LCG, exact)
CRand	Apple libc rand/srand (Park–Miller, seed 1)
qsort_by	Apple libc qsort (FreeBSD introsort: isort switch, heapsort fallback). dotgen::qsort::qsort delegates to it
RkState	lib/neatogen/randomkit.c (Mersenne Twister, 64-bit long)
DtTree	lib/cdt dttree.c ordered set/bag (splay insert, dtflatten)
libcxx	libc++ std::sort, make_heap/push_heap/pop_heap (macOS SDK headers)

graphviz_pure_layout::common (lib/common, lib/label)

Rust	C
types	Agraphinfo_t/Agnodeinfo_t/Agedgeinfo_t subset; LGraph, Sub (node-induced subgraph view), cgraph iteration orders
init	graph_init (nodesep, ratio, size, landscape, concentrate, root label), common_init_node, common_init_edge, do_graph_label, setEdgeType/edgeType; LGraph::write_back
shapes	poly_inside, point_inside, record_inside, epsf_inside, star_inside, same_side, ccwrotatepf; vertices come from graphviz_pure_geom::node_geometry
ports	chkPort, poly_port, record_port, html_port/portToTbl, compassPort, compassPoint, closestSide, resolvePort(s)
splines	Bezier, bezier_clip, shape_clip(0), clip_and_install, update_bb_bz, check_control_points, ptToLine2, makeSelfEdge, selfRight/Left/Top/Bottom, makePortLabels, place_portlabel, addEdgeLabels, edgeMidpoint, polylineMidpoint, dotneato_closest, addLabelBB
arrows	arrow_flags, arrow_match_name, arrow_length (+ arrow_type_normal0/crow0/diamond0, miter_shape), arrowStartClip, arrowEndClip
postproc	gv_postprocess, translate_drawing, place_graph_label, place_root_label (rankdir TB, no flip)
xlabels	addXLabels and lib/label (placeLabels, xladjust, xlintersections, Hilbert keys, R-tree index.c/node.c/rectangle.c/split.q.c)
geom, utils	geom.h macros, late_*, mapbool, compute_bb, coord
ns	ns.c network simplex, generic over NsGraph (dot’s fast graph, neato’s NsData)

graphviz_pure_layout::pack (lib/pack)

pccomps, ccomps, getPack, getPackInfo, getPackModeInfo, computeStep, genBox, genPoly, fillLine, fillEdge, fits, placeFixed, placeGraph, polyGraphs, arrayRects, putGraphs, shiftGraphs, packGraphs, putRects, polyRects, packRects. Not ported: packSubgraphs, pack_graph (trivial wrappers), l_aspect mode (C returns failure too).

graphviz_pure_layout::neatogen (lib/neatogen)

Rust	C
neatoinit	neato_layout, neatoLayout, majorization, user_pos, setSeed, checkStart, initRegular, neatoMode, neatoModel, checkExp, addCluster (IPSEPCOLA build), doEdges
stuff	scan_graph_mode, lenattr, initial_positions, diffeq_model, solve_model, choose_node, move_node, D2E, update_arrays, shortest_path/s1 + heap; KK subset_model, mds_model, circuit_model
graphdata	vtx_data, makeGraphData, acyclic/dfsCycle
stress	stress_majorization_kD_mkernel, initLayout, circuitModel, mdsModel, compute_apsp_packed, compute_weighted_apsp_packed, compute_apsp_artificial_weights(_packed), compute_new_weights
smart_ini	sparse_stress_subspace_majorization_kD, embed_graph, center_coordinate, PCA_alloc, iterativePCA_1D, power_iteration, closest_pairs2graph
sgd	sgd, extract_adjacency, fisheryates_shuffle
bfs	bfs, ngdijkstra, dijkstra_f, dijkstra_sgd with C’s heap
conjgrad, matrix_ops, linalg	conjugate_gradient(_f/_mkernel), vector kernels, solve, lu_decompose/lu_solve, matinv, solveCircuit
neatosplines	spline_edges, spline_edges0, splineEdges (equivalence classes), spline_edges_, makeSelfArcs, neato_set_aspect, neato_translate; makeStraightEdge(s), bend, get_cycle_centroid from routespl.c
routing	makeObstacle, vconfig branch of spline_edges_, getPath, makeSpline, makePolyline
multispline	multispline.c (mkRouter, makeMultiSpline, genroute, mkPoly, mkCtrlPts, triPath + fPQ.h, addEndpoint, tweakPath), delaunay.c mkSurface (constrained Delaunay)
constraint	constraint.c cAdjust (mkConstraintG, mkNConstraintG, mapGraphs, constrainX/Y, initItem, intersect*)
quad_prog_vpsc	quad_prog_vpsc.c (initCMajVPSC, constrained_majorization_vpsc, generateNonoverlapConstraints, removeoverlaps, DiG-CoLa levels), unpackMatrix
digcola	constrained_majorization.c stress_majorization_with_hierarchy, quad_prog_solve.c, compute_hierarchy.c, opt_arrangement.c, smart_ini_x.c (IMDS_given_dim)
cola	constrained_majorization_ipsep.c stress_majorization_cola, neatoinit.c cluster_map
legal	Plegal_arrangement (sweep line)
adjust	graphAdjustMode, getAdjustMode, removeOverlapWith, removeOverlapAs, adjustNodes, normalize, simpleScale, sepFactor, esepFactor
scadjust	scAdjust (scale, scalexy, compress), adjust.c vpscAdjust
voronoi	vAdjust, sAdjust (oscale), Fortune sweep (voronoi.c, hedges.c, heap.c, edges.c, site.c, geometry.c, info.c), poly.c
overlap, delaunay	prism: fdpAdjust, remove_overlap, OverlapSmoother_new, get_overlap_graph, overlap_scaling, call_tri, delaunay_tri

graphviz_pure_layout::sparse, graphviz_pure_layout::sfdpgen

lib/sparse subset (SparseMatrix CSR/coord, from_coordinate_arrays, sum_repeat_entries, transpose, is_symmetric, symmetrize, add, remove_diagonal, get_real_adjacency_matrix_symmetrized, multiply_dense/vector, distance, drand) and sfdpgen/post_process.c StressMajorizationSmoother_smooth with sparse_solve.c SparseMatrix_solve.

graphviz_pure_geom::pathplan (lib/pathplan)

Pshortestpath (shortest.c), Proutespline (route.c), solve3 (solvers.c), Pobsopen/Pobspath (cvt.c), visibility, ptVis, directVis, makePath, shortestPath (visibility.c, shortestpth.c), in_poly, ccw, isdiagonal, Ptriangulate, make_polyline, Ppolybarriers. Self-contained; shared with the dot spline work.

Deviations

• overlap=ipsep is a no-op in C’s adjust step (handled during mode=ipsep).
• The makeMultiSpline router’s triangulation numbers faces in creation order, not GTS’s pointer-hash order (see below).
• VPSC’s std::set<Block*> and scanline NodeSet pointer order are modelled as allocation order (see below).
• When IncVPSC::satisfy fails during mode=ipsep (“Cycle Error!”, “Unsatisfied constraint”), C aborts on the uncaught exception. The port, whose block order can fail where C’s heap order does not, reads the positions back and goes on, as before. After more than 500 cycle errors (MAX_CYCLE_ERRORS), it warns and ends the stress loop of that component. Before #197, corpus files that finished within 10 s reached at most 241 (#197; ipsep_vpsc_cycle_error_ends_the_layout in crates/graphviz-pure-cli/tests/cli.rs).
• The VPSC solver reuses the slots of blocks that no variable belongs to and that are not in Blocks. C frees or leaks these; the port kept them all, so memory grew with every split (#197, #222). Block order comes from a creation counter, not the slot.
• Prism’s Delaunay triangulation is a Bowyer–Watson port, not GTS; the edge set matches for points in general position, but ties between co-circular points and the matrix entry order may differ (all prism corpus files are still exact).
• start=random without a seed uses seed 1 (C uses the clock).
• model=mds with mode=KK indexes by layout id where C uses 1-based AGSEQ (undefined behaviour in C).
• Engines/attributes outside neato’s code paths (-n / Nop, dim>2 output via z) are not covered. splines=ortho runs the lib/ortho port through the ortho branch of spline_edges_ (neatosplines::spline_edges_route: makeObstacle(isOrtho), Plegal_arrangement, orthoEdges on the component being routed, addEdgeLabels), shared by neato, twopi, circo, sfdp, fdp and osage (opus5.5/dot-phase3); -Gsplines=ortho over the first 120 files of each of tests/neato, tests/twopi, tests/circo, tests/sfdp matches C except where the layout itself differs.
• Renderer changes made for C parity (graphviz-pure-render): edges without a spline get no pos; arrowhead/arrowtail=none produce no e,/s, point; degenerate graph boxes print as computed; clusters with no layout box get no bb. gv-diff now compares bb only for clusters.

Handoff: shared API for fdp / sfdp / twopi / circo / osage / patchwork

Typical engine skeleton (mirrors neato_layout):

let src = graph.clone();
let mut g = LGraph::new(&src, 2, EdgeType::Line);   // graph_init + node/edge init
// ... compute g.nodes[n].pos (inches) for the nodes of a Sub ...
let (mut ccs, pinned) = pack::pccomps(&g);          // or pack::ccomps
neatogen::adjust::adjust_nodes(&mut g, &sub);       // overlap=... (twopi, circo)
neatogen::adjust::remove_overlap_as(&mut g, &sub, Some(flag)); // fdp
neatogen::neatosplines::spline_edges(&mut g, &mut sub, is_root); // translate + route edges
pack::pack_graphs(&mut g, &mut ccs, &pinfo);         // packGraphs with doSplines
common::utils::compute_bb(&mut g, &mut root, true);
common::postproc::gv_postprocess(&mut g, true);       // labels, xlabels, translation
g.write_back(graph);

Key types and conventions:

• LGraph<'a> borrows the parsed Graph; nodes[i].pos is ND_pos (inches, ndim components), coord is ND_coord (points, set by neato_set_aspect), lw/rw/ht/width/height/shape come from exact C node geometry. edges[e] carries dist, factor, ports, labels, spl.
• Sub is a node-induced subgraph (nodes sorted by sequence, member mask, bb, top-level clusters). g.root_sub() is the root.
• Iteration: g.outs(sub, n) = agfstout..agnxtout (ordered by head sequence, then edge), g.ins, g.all_edges = agfstedge..agnxtedge, g.find_edge = agfindedge.
• Randomness: g.drand (drand48, reseed with srand48), g.crand (rand()), cutil::RkState; sorting with cutil::qsort_by.
• Clusters: g.clusters (LCluster { subgraph, bb, label, label_pos, border, children }) and g.root_clusters are the C GD_clust arrays; write_back copies their boxes, and unregistered clusters keep an input bb attribute.
• Edge routing: neatosplines::spline_edges0 handles splines= line, polyline, spline (pathplan), curved, self loops and multi-edges for any Sub; common::splines::clip_and_install is the generic installer (no ND_rank/virtual-edge logic yet: dot’s port should add that).
• Overlap removal: neatogen::adjust::{graph_adjust_mode, get_adjust_mode, remove_overlap_with} with AdjustData; prism is in neatogen::overlap, Voronoi in neatogen::voronoi, scaling in neatogen::scadjust.
• sfdp can reuse sparse::SparseMatrix and sfdpgen::post_process::StressMajorizationSmoother.

Gap closure (opus5.5/neato-gaps)

Generic network simplex and constraint.c (overlap=ortho*, portho*)

lib/common/ns.c lives once, in common::ns, generic over the NsGraph trait (the node/edge fields ns.c reads: ND_in/out, ND_tree_in/out, ND_rank/low/lim/par/priority/mark/subtree, ED_minlen/weight/cutvalue/ tree_index, GD_nlist, agget). dotgen::ns implements it over dot’s fast graph; NsData is a standalone graph. -Tdot of all 1148 corpus files was byte-identical before and after the move.

neatogen::constraint ports cAdjust: initItem (integer boxes in tenths of a point, fused ROUND), the cdt Dtobag sort (cutil::DtTree, a faithful splay insert: the position of equal keys depends on the tree shape), mkConstraintG (chain over distinct coordinates plus visibility constraints merged through mapGraphs, strict agedge), mkNConstraintG (pairwise constraints, weight 100 on real edges via agfindedge), and rank(cg, 2, INT_MAX). 43 hw3_*ortho* cases.

VPSC (overlap=vpsc) — graphviz_pure_layout::vpsc, neatogen::quad_prog_vpsc

Graphviz only instantiates IncVPSC (newIncVPSC), so the port covers IncVPSC::solve/satisfy/splitBlocks/moveBlocks/mostViolated, Block (merge, split, splitBetween, findMinLM(Between), compute_dfdv(_between), populateSplitBlock, cost), constraint generation (generateX/YConstraints with libc++ std::sort of the scanline events, neighbour sets) and the C bridge. Unreachable: non-incremental VPSC, Blocks::mergeLeft/Right/split, the block constraint heaps, cycle checks. C++ orders that depend on pointers (Blocks : std::set<Block*>, CmpNodePos ties) use allocation order; a block split mid-iteration is visited when it sorts after the current block, as with std::set. A leaked block (C’s satisfy merges into a block it never inserts into bs) is reproduced. removeoverlaps/vpscAdjust run on float coordinates as in C. 11 hw3_vpsc_* cases; one mode=ipsep case whose C output changes run to run (pointer order) is excluded from the corpus.

mode=hier (DiG-CoLa) and mode=ipsep — neatogen::digcola, neatogen::cola

stress_majorization_with_hierarchy: compute_y_coords (CG on uniform weights, init_vec_orth1 with rand()), compute_hierarchy (libc qsort), smart init through IMDS_given_dim (classical MDS power iteration with rand() % 100), levelsgap, and constrained_majorization_new_with_gaps for the y axis (including C’s lev[right] indexing by position). stress_majorization_cola: cluster dummy variables and the extended Laplacian, initCMajVPSC for diredgeconstraints=true|hier (DiG-CoLa level boundaries; C loops forever when there is no boundary, the port skips), overlap=ipsep node-size ramp and overlap=vpsc post-pass, gradient projection in float. cluster_map maps top-level clusters of the root, keeping only the members in the component being laid out (C asserts on a member in another component, #168). generateNonoverlapConstraints sizes its boxes before taking off the cluster dummies, as C does: the overlap=vpsc post-pass passes only the real nodes, so cluster members among the last 2 * nclusters read zeroed boxes. With fewer real nodes than that C segfaults; the port passes the dummies too (#185). 17 hw3_hier_* and 12 hw3_ipsep_* cases.

makeMultiSpline — neatogen::multispline

Homebrew’s build links GTS, so spline_edges_ sends multi-edges and edges with boundary ports (splines=true|polyline) to the router before falling back to per-edge makeSpline/makePolyline. mkSurface is a constrained Delaunay triangulation with exact predicates (Bowyer–Watson inside GTS’s enclosing triangle, Sloan flips for each constraint, Lawson restoration with fixed constraints) and GTS’s hole rule (drop faces whose constraint edges run against the CCW face orientation; interior faces without a constraint side survive, as in C). GTS’s own triangulate_polygon yields the same constrained Delaunay triangulation unless four points are co-circular. Face and neighbour numbering follow creation order, not GTS’s hash order (#35), and each face’s corner order is the port’s own, not GTS’s (#28); both only matter for exact ties in the triangle shortest path. Validated with Pshortestpath/Pobspath interposed into Homebrew’s dot (DYLD_INSERT_LIBRARIES): guiding polygons match C. 13 hw3_ms_* cases (fan-out of 2–4 multi-edges, failing fan-outs, compass ports, random graphs with multi-edges and ports).

gv16_graphs_b15 dynamic record ports

Fixed upstream by the dot-splines branch’s single rankdir-aware common::ports (record field sides for dynamic ports); the main corpus file is exact and hw3_ports_b15(_splines) check the same ports through neato.

Full-pipeline (-Tsvg) fixes found with gv-diff e2e

• Edges whose endpoint is a subgraph (a -> {B A}) are created in node sequence order, as cgraph’s grammar walks agfstnode(subg) (parser).
• Unplaced edge labels (ED_label(e)->set == false) print lp but are not drawn (EdgeData::label_unplaced).
• Clusters the layout did not register (GD_clust) keep their input bb but are not drawn (UNREGISTERED_CLUSTER_KEY).
• RADIANS(d) is d/180*M_PI (fused when added to atan2), not to_radians().

Remaining gaps

• Prism (overlap=false, default for sfdp): GTS’s edge enumeration order (pointer hashing) changes summation order in the solver by an ulp; visible only in printed digits (7 arrow graphs in e2e) and in chaotic cases.
• makeMultiSpline triangle centres (issue #28): triCenter (multispline.c:391) sums a face’s corners in the order gts_triangle_vertices returns them. The GTS manual documents only that this order “respects the orientation of t” and that e1 joins v1 and v2; which corner comes first depends on which edge GTS’s construction stored as t->e1. That is deterministic in C, but it follows GTS’s insertion and flip history, which the port’s CDT does not replay. The port can start at a different corner on every face (all 22 in the repro), so a centre can differ by an ulp. When two triangle paths tie exactly in C (mirror-image obstacles), that ulp picks the other side and tweakEnd can move the end point 0.1pt. With C’s corner order the port’s tri_path picks C’s path, so the tie-break itself matches. See also #35 (face order). Tracked by the ignored test neato_polyline_compass_port_routes_like_c.
• splines=ortho in neato is left to the dot-phase3 branch.
• VPSC/IncVPSC pointer-ordered containers are approximated by allocation order; C itself is not reproducible on some mode=ipsep inputs.

Ratchets at the end of this branch: main 504/508 exact (score 506.08), neato 438/438, sfdp 296/297, circo 279/280, twopi 280/282, fdp 383, osage 178, patchwork 140, render unchanged, e2e 2379/2428 identical.