nordisk/facett

facett-graphview — Elite Graph Engine

Moving facett-graphview (+ facett-helix) from "D3 / Three.js algorithms ported to Rust" into an enterprise-grade graph engine. The nordisk domain is primarily structured directional dataflows — SCIP call graphs, skade lineage, ordning plan-DAGs, modgunn dep graphs, execution/pipeline DAGs — so the engine optimises for directed / layered / temporal graphs first, while the GPU force layout covers the general arbitrary-web case so nothing chokes.

Two curses to beat: the hairball (edge density) and layout perf at scale.

This branch (agent/graphview-elite) lands the foundation. Below is the endorsed plan (the "Gemini consult"), then exactly what landed, what spiked, and the roadmap for each technique, with the concrete approaches.

The plan (endorsed)

All four pure cores are deterministic (FC-7) and assert their results as DATA (positions / metrics / partition), not screenshots. The GPU paths self-skip without an adapter. Reused GPU stack: facett-core gpu::particles (boids compute + storage ping-pong + additive HDR bloom), facett-graph3d instanced emissive lane, facett-helix rubberband Catmull-Rom / elastic splines, injected-clock easing.

1. GPU-compute layout — LANDED (src/gpu_layout.rs, src/layout.wgsl)

Approach. A wgpu compute-shader n-body layout. The graph is held in CSR (GraphCsr { offsets, targets, weights }), which is the upload format — the three Vecs map 1:1 onto GPU storage buffers, streamed straight from an Arrow edge batch (GraphCsr::from_arrow, feature arrow: Int64 src/dst + an optional Float64 weight column). GpuLayout::new uploads the CSR + a deterministic golden-angle seed; iterate runs the cs_layout kernel entirely in VRAM (ping-pong src→dst, no per-step readback); read_positions copies the settled [f32;2] positions back as DATA.

The force model is Fruchterman-Reingold, velocity-integrated:

• all-pairs repulsion rep·wᵢ·wⱼ/dist² (the (pᵢ−pⱼ) numerator carries one dist, so the magnitude is the FR k/d),
• Hooke springs attr·(dist−ideal) along CSR neighbours,
• centring gravity, integrated with mass = node weight (heavy nodes move slower).

The all-pairs repulsion is the same O(n²) compute shape as the boids in facett_core::render::gpu::particles — same @workgroup_size(64), same storage ping-pong, same headless request_adapter probe. The CPU step_cpu/relax_cpu is the no-GPU fallback and the parity reference the WGSL mirrors line-for-line.

Tests (DATA): CSR symmetry/dedup, deterministic seed + bit-identical step, energy-decay convergence (the metric drops an order of magnitude), the analytic single-edge equilibrium d=(1+√3)/2, mass-weighted motion, Arrow ingestion, and a GPU↔CPU parity proof (gpu_layout_matches_cpu_reference, self-skips without a device — passes on this host).

Roadmap (the 100k case). The O(n²) repulsion is the foundation. To reach 10k–100k nodes in real time:

• GPU Barnes-Hut: build a Morton-code-sorted spatial index on the GPU (radix sort over quantised positions), build the quadtree's centre-of-mass per cell, and replace the all-pairs loop with a tree walk (open a cell if s/d > θ). Drops it to O(n log n). The kernel structure (storage buffers + workgroup dispatch) is already in place — this swaps the inner loop.
• Cheaper interim: uniform-grid binning (hash positions to cells, only repulse within a neighbourhood) — O(n) for bounded density, far less code than the tree.
• Stress-majorization alternative for layered/DAG inputs (better edge-length uniformity than FR); the CSR + VRAM-iterate harness is layout-agnostic.
• Keep CPU layouts (Sugiyama/radial/cluster) as the no-GPU fallback.

2. Force-directed edge bundling — LANDED (src/fdeb.rs)

Approach. Holten & van Wijk FDEB. Each edge becomes a flexible wire subdivided into control points; compatibility Ca·Cs·Cp (angle · scale · position) is precomputed and pruned, then a force loop runs electrostatic attraction between compatible wires' matching points (cohesion → bundles) balanced by a spring keeping each wire's own points evenly spaced (the rubberband). Compatible edges collapse into shared "information highways" that split near the endpoints. The force is the same boids/n-body shape as #1 — cohesion to compatible neighbours.

Tests (DATA): endpoints stay pinned, determinism, parallel wires converge in the middle, perpendicular wires stay unbundled, and the occlusion metric (occupancy, grid-cell ink coverage) drops >20% vs straight edges on a bipartite hairball — the de-hairballing proven as DATA.

Roadmap.

• GPU port: the control points are particles; compatibility is the neighbour kernel — it drops straight onto particles.wgsl's storage-ping-pong (each subdivision point a particle, compatibility weighting the attraction). The CPU reference here is the parity oracle, exactly as #1's step_cpu.
• Cycle refinement schedule (the full FDEB): start at 1 subdivision, double each cycle while halving the step — sharper trunks, smoother splits. The fixed-m loop that landed is the inner step of this.
• Directional bundling: bundle only co-directed edges (respect the DAG arrow) so the "information highways" read as dataflow, not undirected ink — a Cv (visibility) + a direction term on the compatibility.
• Render: paint BundledEdge.path as glowing additive splines through the facett-graph3d emissive lane (the helix already feeds it).

3. Topological semantic zoom — LANDED (level-1) (src/community.rs)

Approach. Louvain modularity local-moving detects communities; meta_graph collapses each community into a meta-node (centroid + member count) and aggregates crossing edges. fracture_t(zoom, …, ease) maps zoom to a fracture parameter t∈[0,1] through an injected easing curve (the same dependency-injection seam helix uses); fractured_positions lerps members from the meta-centroid (collapsed, t=0) to their real positions (open, t=1) — the meta-node blooms apart instead of popping. visible_count is the LOD: meta-count when out, node-count when in.

Tests (DATA): two-cluster detection with Q>0.3, determinism, meta-node count < node count at low zoom, fracture eases collapsed→open monotonically, fractured positions lerp as DATA.

Roadmap.

• Recursive Louvain (multi-level aggregation): after local-moving, contract each community into a super-node and recurse — yields a hierarchy of zoom levels, so semantic zoom has many tiers, not one. The level-1 louvain + meta_graph is the base case; recursion reuses both.
• Leiden refinement: guarantees well-connected communities (Louvain can leave a community internally disconnected). Slots in behind louvain without touching the meta-graph / fracture API.
• On-the-fly incrementality: re-run only the touched neighbourhood when the graph changes, so communities are stable frame-to-frame — pairs naturally with #4's anchor constraints (anchor the meta-node centroids).
• Fracture animation driver: wire fracture_t to the live DecoratedGraphView scroll-zoom + the injected clock so the bloom runs on real wheel input.

4. Mental-map stability (helix) — LANDED (facett-helix/src/stability.rs)

Approach. Dynamic-graph layout stability via anchor constraints. Per node per timestep we minimise ‖pₜ−rawₜ‖² + λ‖pₜ−pₜ₋₁‖²; the closed-form minimiser is the one-line anchor pₜ = (rawₜ + λ·pₜ₋₁)/(1+λ), so per-step travel is bounded by ‖rawₜ−pₜ₋₁‖/(1+λ) — what moves is what changed, preserving the user's spatial memory instead of teleporting. The angular coordinate eases along the shortest arc (wrap-aware). The time axis maps to helix depth: each timestep is a cross-section stacked along the axis, and a node's anchored positions across the steps are the control points of a rubberband spline (trajectory_world → catmull_rom_chain) — the user flies through structural history and sees how a node migrated across system boundaries over commits/runs.

Tests (DATA): λ=0 reproduces the from-scratch baseline; anchored per-step travel is bounded by Δ/(1+λ) and >2× below the from-scratch teleport; an unchanged node stays exactly put; the trajectory advances monotonically through the time-depth; determinism.

Roadmap.

• Global anchored stress instead of per-node exponential smoothing: solve the whole-frame stress-majorization with an L2 anchor term to the previous frame (better global shape preservation than the local closed form). The metric + trajectory API is unchanged.
• Foresight layout: lay out the union of all timesteps once, then reveal per step — maximal stability for a known finite history (the commit log).
• Live wiring: feed snapshots from modgunn dep-graph runs / SCIP re-ingests into anchor_sequence, render the trajectories through the helix's emissive spline lane, and scrub the time-depth with the injected clock.

Build / test notes

• All landed code builds with cargo build/cargo test (no benches). facett-graphview default (CPU) is always built; the GPU layout + Arrow ingestion are behind the gpu / arrow features; the GPU parity proof self-skips without an adapter.
• Worktree caveat (not committed): bench/facett-demo drag ../../knut → ../../../facett/* (the main checkout), colliding with the worktree's own crates in lock resolution. Build the elite-engine crates with a reduced workspace (facett-core, facett-graph3d, facett-graphview, facett-helix); the full members list is restored on commit.