Skip to content
graphviz-pure

fdp, osage and patchwork ports (Graphviz 16.1.0)

Copied at build time from docs/porting/fdp-osage-patchwork.md.

`layout=fdp`, `layout=osage` and `layout=patchwork` now run function-by-function ports of `lib/fdpgen`, `lib/osage` and `lib/patchwork`. They are built on the shared neato-family infrastructure (`common`, `pack`, `neatogen` overlap removal and edge routing, `pathplan`, `ortho`; see `docs/porting/neato.md`). The old approximations in `force_circular.rs` are gone.

Entry points:

  • graphviz_pure_layout::fdpgen::layout::fdp_layout(&mut Graph)
  • graphviz_pure_layout::osage::osage_layout(&mut Graph)
  • graphviz_pure_layout::patchwork::patchwork_layout(&mut Graph)

Fidelity

Section titled “Fidelity”

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

corpus before (force_circular) after
tests/fdp (383 files; 377 at the start) 68 exact, score 102.6/377 (27%) 383 exact (100%)
tests/osage (178 files; 176 at the start) 1 exact, score 20.9/176 (12%) 178 exact (100%)
tests/patchwork (140 files) 14 bb ok, score 20.4/140 (15%) 140 exact (100%)
main corpus (508 files) 250 exact at branch start 504 exact with the other merged ports; every fdp/osage/patchwork file exact, never a regression

Layouts are bit-identical to C wherever checked: floating-point expressions follow clang’s -ffp-contract=on code generation (a*b + c is fma(a, b, c); for a*b + c*d the first product is fused), checked against the disassembly of the C objects. Random numbers (drand48 reseeded per component, libc rand() for coincident points), the Apple qsort, cgraph node/edge orders and cdt grid order are reproduced.

Validation

Section titled “Validation”
  • cargo run --release -p graphviz-pure-diff -- --golden tests/golden/<engine> --baseline tests/golden/<engine>-baseline.json tests/<engine> (ratchets: crates/graphviz-pure-diff/tests/{fdp,osage,patchwork}_fidelity.rs).
  • Corpora are generated by scripts/gen-<engine>-corpus.py: fixtures plus wild graphs (fdp: undirected or clustered; osage, patchwork: clustered) with the engine forced, and hand-written cases (fdp: clusters, nesting, cluster-crossing edges, cluster edges, K, maxiter, T0, start, pos/pin, coords, overlap modes and n: tries, sep/esep, every splines value incl. compound and ortho, pack, packmode; osage: clusters, labels, sortv, pack, all array modes, ortho; patchwork: area, inset, nested and empty clusters, fontsize).
  • Excluded inputs: splines=compound cases where C 16.1.0 aborts in compoundEdges (list index assertion).
  • GVDBG=1..6 (fdp) prints traces line-compatible with an instrumented C copy in ~/src/gv-ref/build-fop (run.sh): derived positions after tLayout and xLayout, xLayout forces, derived node addresses, cluster ports, embedder iterations, embedder forces.

Module ↔ C file map

Section titled “Module ↔ C file map”
Rust C
fdpgen::mod (mk_clusters, ClusterTree, is_a_cluster) mkClusters (shared by fdp, osage, patchwork), is_a_cluster
fdpgen::layout layout.c: fdp_layout, fdpLayout, layout, deriveGraph, chkPos, getEdgeList, genPorts, expandCluster, finalCC, setClustNodes, evalPositions, setBB, fdpSplines; plus spline_edges_ for EDGETYPE_ORTHO and makeObstacle(isOrtho)
fdpgen::tlayout tlayout.c: fdp_initParams, init_params, initPositions, doRep, applyRep, applyAttr, doNeighbor, gridRepulse, updatePos, gAdjust, adjust, fdp_tLayout; setSeed; fdpParms defaults from globals.c
fdpgen::grid grid.c (ordered cell set, prepended node lists)
fdpgen::xlayout xlayout.c: xinit_params, overlap, cntOverlaps, doRep, applyAttr, adjust, x_layout, fdp_xLayout (then neatogen removeOverlapAs)
fdpgen::comp comp.c: findCComp
fdpgen::fdpinit fdpinit.c: init_edge, initialPositions; get_inputscale
fdpgen::clusteredges clusteredges.c: makeClustObs, addGraphObjs, raiseLevel, objectList, compoundEdges; getPath/makeSpline with chkPts=false
common::cluster_edges utils.c: processClusterEdges, checkCompound, clustNode, cloneEdge, undoClusterEdges
osage::mod osageinit.c: osage_layout, cluster_init_graph, mkClusters (+do_graph_label), layout, reposition
patchwork::patchworkinit patchworkinit.c: patchwork_layout, init; finishNode
patchwork::patchwork patchwork.c: mkTree, mkTreeNode, getArea, fullArea, layoutTree, walkTree, patchworkLayout
patchwork::tree_map tree_map.c: squarify (tail recursion as a loop), tree_map

Derived graphs

Section titled “Derived graphs”

Each graph (root or cluster) is laid out through a derived graph DG with one node per own node, child cluster and inherited boundary port. Shared code that works on an LGraph (packing, removeOverlapAs, compute_bb) runs on an LGraph built from the derived nodes by layout::with_lgraph, which copies the positions back. Only overlap, sep and K are copied into a derived graph, so normalize, scale and esep have no effect inside fdp’s overlap removal, as in C.

cgraph orients derived edges (hd > tl), orders multi-edge ports (n < other) and port edges (dn > m) by Agnode_t address. NodeHeap models macOS’s allocator for that size class: slots of a freed derived graph are handed back LIFO to the next one, then fresh increasing addresses. With cluster edges, processClusterEdges frees memory of other zones that C’s derived nodes later reuse; creation order matches C on those inputs, so the model does not recycle there.

Cluster edges

Section titled “Cluster edges”

processClusterEdges mutates the graph in C. The port builds the modified graph (ClusterEdges::work: cluster-named nodes deleted, one __0:<cluster> node per cluster — C’s name counter never advances — and cloned edges) and maps the layout back. The deleted nodes keep default attributes and carry graphviz_pure_core::CLUST_NODE_KEY, which tells the renderers neither to draw them nor to print layout attributes; edges of deleted nodes that were not re-attached are removed, as in C.

Gaps and differences

Section titled “Gaps and differences”
  • start=regular, start=self and start=random without a number seed C’s generator from the clock; the port uses seed 1.
  • C’s address-dependent orders are not reproducible run to run on some inputs (e.g. many nested clusters with splines=compound): two C runs can differ, and the port matches one of them or neither. No corpus file is affected.
  • splines=compound in osage falls back to polylines (C’s spline_edges_ treats it the same way).
  • With cluster edges and splines=true, C warns and draws lines; the port does the same. A partial compoundEdges failure keeps the routed edges as C’s Nop = 2 does, but their boxes may grow the graph box slightly differently.