Skip to main content

Crate triskel

Crate triskel 

Source
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):

  1. 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 by layout and drawn as a loop off the node’s right face once it is positioned.
  2. rank — assign each node a rank (layer) via network simplex.
  3. segment — decompose long edges into Eiglsperger segments (p/q endpoints + one pass-through segment), avoiding a dummy node per layer.
  4. order — within-rank ordering / crossing reduction.
  5. coordinate — x-coordinate assignment (segment-aware Brandes–Köpf).
  6. router — turn the positioned graph into edge waypoints.
  7. 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 LayoutGraph into a waypoint polyline per original edge.
segment
Eiglsperger long-edge representation.