Expand description
Layered (“Sugiyama-style”) directed graph layout, specialised for control flow graphs.
Implements the algorithm from Towards Better CFG Layouts (Royer,
Tronel and Vinçont, Workshop on Binary Analysis Research 2025). The idea is
that CFGs are not arbitrary graphs: they are built from nested
single-entry/single-exit regions, and laying those out as units — rather
than flattening everything into one layered pass — produces a drawing that
matches how an analyst reads the code. See layout::LayoutMode::Sese.
The original C++ implementation lives at triskellib/triskel.
Pipeline (top-to-bottom, run per weakly-connected component):
cycle— reverse back-edges so the remaining phases see a DAG (rooted at the entry, so the entry stays the top rank). Self-loops are held out of the layered graph bylayoutand drawn as a loop off the node’s right face once it is positioned.rank— assign each node a rank (layer) via network simplex.segment— decompose long edges into Eiglsperger segments (p/q endpoints + one pass-through segment), avoiding a dummy node per layer.order— within-rank ordering / crossing reduction.coordinate— x-coordinate assignment (segment-aware Brandes–Köpf).router— turn the positioned graph into edge waypoints.render— SVG/HTML output.
The public entry point is layout::LayoutBuilder. By default each weak
component runs as one flat layered graph. layout::LayoutMode::Sese is an
opt-in CFG mode: canonical edge-based SESE regions are replaced by sized
proxies, laid out bottom-up, expanded, and then routed through explicit
obstacle-free boundary corridors. Weak components are still packed side by
side.
§Example
use jstd::{Identifier, graph::owning::OwningGraph};
use triskel::layout::{LayoutBuilder, NodeGeometry};
#[derive(Identifier)]
struct NodeId(usize);
#[derive(Identifier)]
struct EdgeId(usize);
// A diamond: entry branches and rejoins.
let mut graph = OwningGraph::<NodeId, EdgeId, (), ()>::default();
let entry = graph.make_node(());
let left = graph.make_node(());
let right = graph.make_node(());
let join = graph.make_node(());
graph.make_edge(entry, left, ());
graph.make_edge(entry, right, ());
graph.make_edge(left, join, ());
graph.make_edge(right, join, ());
let layout = LayoutBuilder::new(&graph)
.root(entry)
.geometry(|_| NodeGeometry { width: 60.0, height: 30.0 })
.build()
.expect("the diamond lays out");
// Every node has coordinates, and the entry is on the top rank.
let entry_box = layout.get_node(entry).unwrap();
for node in [left, right, join] {
assert!(layout.get_node(node).unwrap().y > entry_box.y);
}
let svg = layout.render_svg();
assert!(svg.starts_with("<svg"));Modules§
- coordinate
- X-coordinate assignment via width-aware Brandes–Köpf over the container slot model.
- cycle
- Cycle removal via back-edge gadgets.
- energy
- Deterministic force-directed graph layout.
- layout
- Public layout API and per-component orchestration.
- order
- Within-rank ordering via the Eiglsperger container method.
- rank
- Rank (layer) assignment via the Gansner et al. (TSE93) network simplex.
- render
- SVG / HTML rendering of a
LayoutResult. - router
- Edge routing. Turns the positioned
LayoutGraphinto a waypoint polyline per original edge. - segment
- Eiglsperger long-edge representation.