vyges-stt — rectilinear Steiner minimal trees

Part of the Vyges Loom suite. Install once with vyges install loom, then run vyges loom stt. It’s also a standalone vyges-stt binary on your PATH (the integration contract for flow authors).

vyges-stt answers: given where a net’s pins are, what shape should the wire be? A net with more than two pins has no single answer — the pins can be joined many ways, and the extra corner points that shorten the total wire (Steiner points) have to be chosen. Every routing and timing stage downstream reads that shape: global routing routes it, extraction charges capacitance against it, and timing sees the delay it implies. Getting a different tree is getting a different design.

Two builders sit behind one entry point, and which one runs is a property of the net:

A clock or a long timing-critical net wants a shallow tree even at some cost in wire; alpha is that dial. ⚠️ A Prim-Dijkstra tree is used only if it passes a self-overlap check; otherwise the net silently falls back to FLUTE. --json reports which builder actually answered, which is the one thing the reference does not tell you.

Run it

vyges install loom                                  # one-time
vyges loom stt run net.json                         # -> the tree, as the reference prints it
vyges loom stt run net.json --json                  # -> machine-readable
vyges loom stt batch nets.json -o trees.txt         # many nets, one table load
vyges loom stt check tree.json                      # is this tree self-overlapping?

A job names the pins and, optionally, the driver and the trade-off:

{ "x": [0, 100, 200, 300], "y": [0, 10, 20, 30], "drvr": 0, "alpha": 0.4 }

⚠️ drvr is a pin INDEX into x/y, never a coordinate. Two pins can share a location; the index decides which one the tree is rooted at.

{ "status": "ok", "builder": "prim-dijkstra", "deg": 4, "length": 340, "branches": 6 }

Without --json the output is reportSteinerTree’s own format — the wire length, the path depth, and one line per branch — so it diffs directly against the reference.

See the full CLI reference (generated from --help).

Exit status

⛔ vacuous is not success. The declared assertion passes only on ok, so a run that built nothing fails it rather than signing off a net nothing was computed for.

Correlation

Scored against OpenROAD at the pin this binary reports in --describe, over every tree-producing case in its src/stt/test plus a 41-net gate of ours: 341 of 341 trees byte-identical, comparing the wire length, the path depth and every branch line.

Every net is scored through makeSteinerTree, the public entry point — not through the two builders directly, which would score the builders and leave the branch between them unscored.

⚠️ A number here means nothing without the build. The reference’s own answer moves between OpenROAD commits, so the pin is part of the claim; --describe publishes it.

⚠️ Two transcription details are unwitnessed and --describe says so: the f32 weight arithmetic in the Prim-Dijkstra search, and one tie-break in the heap’s child selection. Neither changes any of the 341 trees, so no input distinguishes them — believed right, not verified.

Where it sits

stt is a computational kernel, not a database pass: it reads pin coordinates and returns a tree, touching no .odb. Global routing, clock-tree synthesis and timing-driven resizing are its consumers.

Licence

Apache-2.0. The FLUTE lookup tables are OpenROAD’s own POWV9/POST9 data, BSD-3-Clause, fetched from the pinned commit at build time rather than vendored.