|
|
Textbook Sugiyama, the same shape IDA's own graph uses: break cycles,
longest-path layering, dummy nodes, median/transposition ordering,
priority x-coords, then port-and-channel edge routing. Pure python -- no
IDA, no Textual, no I/O -- so it is tested offline in milliseconds with no
worker, which is the whole reason the hard part is kept out of the UI.
Dummy nodes are what make routing tractable: a long edge occupies real
horizontal space, so no edge ever has to cross a box. The tests assert
exactly that over a 128-function corpus, and it holds at 0.
Two things cost real time to find. A self-loop never drains its own
in-degree, so it deadlocks the ranking and collapses the graph into three
layers, 280 columns wide -- they are dropped from the layout and drawn as
a marker. And crossing minimisation is the entire runtime: recounting
globally per candidate swap is O(n^3) and took 20.4s on a 424-block
function, against 152ms for Fenwick inversion counting plus a local
O(deg*deg) swap delta.
The result is not a painted canvas -- that function is ~13M cells. It is
an index: per-row runs, bucketed vertical intervals, and point marks,
queried one row at a time.
|
