Triskel for graph layout — evaluated, forked, integrated

Outcome. Shipped as the triskel engine behind graph.layout(engine=...), preferred by auto up to 250 blocks, off a local fork (~/dev/triskel, branch idatui, see its PATCHES.md). The library needed six fixes before it could be used from Python at all — including a segfault and a binding bug that made edge routes unreachable. Everything below is the evaluation that led there; docs/GRAPH_VIEW.md documents what shipped.

triskel (MPL-2.0, C++23, 126★) is a CFG layout engine from Inria, the implementation of Towards better CFG layouts. Its idea is genuinely better than ours: before running Sugiyama, split the CFG into Single-Entry Single-Exit (SESE) regions, lay each region out on its own, then paste the region layouts back in as single super-nodes. Divide and conquer, so crossings stay local.

This is what happened when we actually ran it against idatui.graph on the 128-function corpus in .auto/cfg-corpus.json.

Verdict as first written: don't link the library, port the idea. That was reversed after the blockers turned out to be six small, independent patches rather than algorithm work — and one of them (settable spacing) removed the quantisation problem entirely instead of managing it. Reimplementing 350 lines of cycle-equivalence C++ in Python to avoid a #include would have been a poor trade. The licensing note at the end is why the fork stays a fork: MPL-2.0 is file-level copyleft, so linking it costs us nothing, and our changes to their files stay in their repo.

The quality gap is real

Both engines fed identical blocks and identical cell sizes (triskel gets them as "pixels" at 16×32 per cell). Crossings are proper segment intersections counted on each engine's own edge polylines; X is that count, None = above the counting cap.

 blk  edge |  ours ms     ours WxH      X |   tk ms  tk WxH(cells)      X | name
   9    14 |      0.5        89x62      5 |     0.3          81x71      1 | sub_61D0
  10    41 |      1.3        99x80     10 |     0.5         86x105      0 | sub_3500
  17    44 |      1.4      213x144      6 |     0.6        159x171      0 | sub_2FF0
  21    33 |      1.2      724x105     41 |     0.5        782x119      0 | sub_5CA0
  38   150 |      4.7      325x305     32 |     2.8        202x392      1 | sub_2C90
  87   428 |     14.8     1202x444   None |    30.3        850x775   None | main
 109   647 |     25.9      793x476   None |    53.6        363x970   None | sub_69C0
 424  3340 |    145.7    9222x1386   None |  1534.3      1872x3883   None | sub_3720
total ours 207 ms  triskel 1626 ms   (full corpus in /tmp/tk_cmp.py)

Two things to take from that table:

• Crossings collapse to ~0. Every function under 40 blocks lays out with 0 or 1 crossing, where ours has up to 41. That is the SESE decomposition doing exactly what the paper claims.
• Canvases get narrow and tall. sub_69C0: 793×476 → 363×970. sub_3720: 9222×1386 → 1872×3883. For a terminal that is the right trade — vertical scrolling is free, horizontal panning is the thing that makes our graph view feel like peering through a letterbox.

And it costs us on speed above ~40 blocks: 2× slower at 87–109 blocks, 10× slower at 424 (1.5 s vs 145 ms). So it would not let us raise the 400-block cap; it would argue for lowering it.

The output is renderable in character cells

This was the thing that could have killed the idea outright, and it doesn't:

• Every segment is axis-aligned. 0 diagonal segments out of 1708 (main) and 2471 (sub_69C0). Box-drawing characters map straight onto it.
• No edge is routed through a box. The "edge cells inside a box" count comes out at exactly ~1 per edge — that is the polyline's first waypoint, which sits at the source node's centre. Clip the first and last segment to the border and it is clean.
• Quantisation is a knob, not a wall. Triskel packs edges in continuous space, so rounding to cells can drop two edges into one column. How often depends entirely on the px-per-cell we feed it (main, 140 edges):

The gutters are hardcoded constants (X_GUTTER=50, Y_GUTTER=40, EDGE_HEIGHT=30), so px-per-cell is really "how many cells of gutter do I buy". Cheap cells → wider canvas, unambiguous edges. This matters more for us than for a pixel renderer: an ambiguous cell isn't just ugly, it breaks click-to-select-edge and the incident-edge highlight, which assume a cell belongs to one edge. Our lane-packed channels exist to make that impossible.

Why we can't just pip install pytriskel (all fixed in the fork)

1. No wheel we can use. All ten releases ship manylinux_2_34_x86_64 wheels for cp37–cp313 and no sdist. Our venv is Python 3.14 → pip install finds nothing. It is also x86_64-Linux only: no macOS, no arm64, no Windows.
2. The Python bindings can't return edge routes at all. pytriskel.cpp never includes <pybind11/stl.h>, so get_waypoints() raises Unable to convert function return value to a Python type on every published version. The .pyi stub gives it away: get_waypoints(self, arg0: int) -> .... From the shipped wheel you can get node coordinates and save a PNG — that is it. A one-line patch fixes it (verified locally).
3. Building from source works but is heavy. Verified here: clone, cmake -DENABLE_CAIRO=ON -DBUILD_BINDINGS=ON, ~2 minutes, produces a working pytriskel.cpython-314-*.so. But BUILD_BINDINGS is gated on ENABLE_CAIRO, so a user installing a TUI would need cmake, a C++23 compiler, fmt and cairo dev headers to draw boxes made of ─.
4. It crashes the process on degenerate input. - empty graph → segfault (not an exception — it takes the interpreter with it, and with it your session) - disconnected graph → RuntimeError: EMPTY BL, an internal bracket-list assertion leaking out. IDA flowcharts do contain unreachable blocks.

Self-loops, parallel edges and 2-cycles are all handled fine. 5. Rough edges in the API. make_node(float height, float width) is documented in the Python stub as "with a width and height" — the arguments are the other way round (this cost us a benchmark run). get_height is bound twice, once over get_width, so graph width is unreachable from Python. Node sizes can't be read back, and the SESE tree isn't exposed.

What we'd also lose

graph.py doesn't just return coordinates. It returns ranks and per-layer order, which w/b navigation, the minimap and the RPC graph show verb all read. Triskel exposes neither — we'd re-derive ordering from y coordinates. And the whole engine is currently pure Python with no I/O, which is why tests/test_graph.py runs offline in milliseconds against a 128-function corpus. Linking a native layout engine costs us that property.

What integration actually cost

Six patches to the fork (~/dev/triskel/PATCHES.md) and one new module, idatui/graph_triskel.py. The patch that mattered most was making X_GUTTER / Y_GUTTER / EDGE_HEIGHT settable: feeding the engine cells instead of pixels (3 / 1 / 1) makes its output integral, so the whole quantisation section above stops applying. Measured after the fact on the real pipeline, the fear was backwards — cells claimed by more than one edge across the small-corpus functions: native 131, triskel 35.

Three things stayed on our side of the boundary because they are the caller's job, not the library's: self-loops (never passed — they throw), disconnected components (laid out separately and stacked — they throw), and the one corpus edge triskel routes through a block (detoured, then re-verified, else the whole layout falls back to native).

The canvas also had to learn that edges can live outside the boxes' bounding box: triskel routes a loop around the side of the graph, and sizing the canvas on nodes alone — which is exact for the native engine, since its dummy nodes reserve the space — clipped exactly the edges that make its layouts worth having.

The road not taken: port the idea, not the code

The win is the SESE decomposition, and that is ~350 lines of C++ (lib/src/analysis/sese.cpp, cycle equivalence / program structure tree, plus udfs.cpp) and the region orchestration in layout.cpp. In Python, on top of the pipeline we already have, that is roughly:

1. undirected DFS + cycle equivalence → the program structure tree (~200 lines)
2. per-region layout: run our existing steps 2–5 on the region subgraph
3. collapse each region into a super-node in its parent, then translate

Steps 2 and 3 reuse _assign_ranks / _order_layers / _assign_x unchanged, and — this is the point — our cell-native router and lane packing survive, so we keep the 0-edge-cells-inside-a-box guarantee and unambiguous edge ownership instead of inheriting a quantisation problem.

On licensing: MPL-2.0 is file-level copyleft. Linking the library unmodified imposes nothing on our code; copying their source into graph.py would arguably make that file MPL. Implementing from the paper and citing it keeps this clean.

Worth doing regardless, as upstream is friendly and we may want the library later: file the missing <pybind11/stl.h>, the empty-graph segfault, and the make_node docstring order.

Reproducing

The throwaway scripts that produced the tables above (/tmp/tk_*.py, driving pytriskel directly) have been replaced by one that drives the shipping pipeline:

python3 experiments/graph_compare.py .auto/cfg-corpus.json --real-sizer

and the engines are exercised side by side, on every invariant, by tests/test_graph.py — which runs its whole suite once per available engine, so "triskel draws no edge through a box" is checked on 128 real functions rather than asserted here.