nordisk/facett

Barnes–Hut force layout — guide

Class: guide · How to use the scalable force layout + the freeze/absorb contract. The shape-we-run is in barnes-hut-layout-design.md.

You get scaling for free

Every facett force layout already routes through the shared Barnes–Hut kernel above facett_core::barnes_hut::BH_THRESHOLD (2000 nodes). You do not call the kernel directly for normal use — just build your graph as before:

// 2-D graph-DB IDE — nothing changes at the call site; 30k nodes now lay out fast.
let nav = facett_graphnav::GraphNav::new("scene", prop_graph);
let pos = nav.positions(); // frozen after the first call

// 3-D cloud
let g = facett_graph3d::Graph3D::new(nodes, edges, facett_graph3d::Layout3D::Force);

Small graphs (< 2000) keep the exact classic algorithm — identical output, determinism preserved.

Freeze — don't re-run the layout every frame

The layout is a pure function of the graph structure, so compute it once and reuse it.

• GraphNav::positions() and Graph3D already freeze internally. Call positions() every frame — it's a cache hit until the graph changes.
• Your own Facet over facett_core::Scene? Embed a facett_core::ForceCache and paint through it:

struct MyView { scene: facett_core::Scene, cache: std::cell::RefCell<facett_core::ForceCache> }

impl MyView {
    fn show(&self, ui: &mut egui::Ui) {
        let (rect, _) = ui.allocate_exact_size(ui.available_size(), egui::Sense::hover());
        let pos = self.cache.borrow_mut().positions(facett_core::Layout::Force, &self.scene, rect);
        facett_core::draw_positions(ui, &self.scene, pos, rect, "empty");
    }
}

cache.is_settled(layout, scene, rect) tells you the next call is a no-op (the sim has frozen) — a tick can early-out on it. cache.invalidate() forces a recompute.

Absorb — stream nodes in without rebuilding

To grow a graph at frame rate, do not rebuild with ::new. Use absorb: existing node positions are kept, new nodes are seeded near their neighbours and locally relaxed.

// graphnav (korp's sync_graph_nav path)
nav.absorb(new_nodes /* Vec<Node> */, new_edges /* Vec<Edge> */);
let pos = nav.positions(); // old positions unchanged, new ones placed

// graph3d
g.absorb(new_nodes /* Vec<(String, Color32)> */, new_edges /* Vec<(usize, usize)> */);

Guarantees: pos[0..old_n] is byte-identical to before; every new node gets a finite, bounded position; the freeze cache is updated so the next positions() is a cache hit.

Calling the kernel directly (custom layouts)

use facett_core::barnes_hut::{repulsion_forces, relax_new, BH_THETA, BH_THRESHOLD};

// One O(n log n) repulsion pass over your own FR loop (2-D shown; ::<3> for 3-D, ::<1> for a line):
let rep: Vec<[f32; 2]> = repulsion_forces::<2>(&positions, k, BH_THETA);
// rep[i] is the net repulsion on node i — add your edge attraction + cooling, integrate.

// Incremental: relax only nodes >= new_lo, freezing the rest.
relax_new::<2>(&mut positions, &edges, new_lo, k, BH_THETA, /*iters*/ 12, /*step*/ 0.05);

k is your Fruchterman–Reingold ideal edge length. Below BH_THRESHOLD a plain double loop is simpler and just as fast — the threshold is where Barnes–Hut wins.

Tuning

• BH_THETA (0.7): higher = faster, coarser. 0 = exact all-pairs (a test/debug knob).
• BH_THRESHOLD (2000): where the switch happens. The exact path below it is there to keep goldens byte-identical, not for speed.
• MDS at scale (callgraph_layouts::Mds): auto-guarded — above MDS_MAX (4000) it takes a landmark embedding instead of the OOM-prone dense n×n matrix. Nothing to do.