facett-graphnav/src/lib.rs
//! **facett-graphnav** — the **GRAPH NAVIGATOR**: a full graph-DB IDE surface
//! (V.G = G.V(), à la gdotv) built over [`facett_graphview`]. One [`GraphNav`] Facet
//! composes every panel of the IDE, each with **serialisable state** and a
//! **robot-drivable** message surface:
//!
//! - **query bar** ([`query`]) — a Cypher-/Gremlin-ish browse language;
//! - **result canvas** — the laid-out, styled, clickable graph;
//! - **node/edge inspector** — the selected element's label + properties;
//! - **layout switcher** ([`layout`]) — force / hierarchical / circular / grid;
//! - **styling by property** ([`style`]) — colour nodes by label or any field;
//! - **expand / collapse neighbourhoods** — grow or prune the visible set;
//! - **fuzzy search + property filter** — narrow to matching nodes;
//! - **shortest-path highlighting** — via [`facett_graphview::analysis::pathfinding`];
//! - **cycle browser** — elementary directed cycles + acyclicity, via
//! [`facett_graphview::analysis::cycles`];
//! - **similar-node panel** — neighbourhood-overlap (link-prediction) nodes most similar
//! to the selection, via [`facett_graphview::analysis::similarity`];
//! - **schema / overview panel** — the entity-relationship model;
//! - **minimap** — the whole-graph bounds + the viewport;
//! - **export** — JSON / DOT / CSV of the current graph.
//!
//! FC contract: [`GraphNav`] is its own Elm `Model` (every field round-trips through
//! serde), mutation flows only through [`GraphNav::update`], and [`GraphNav::render`]
//! is a pure function of `&self` returning the frame's [`Msg`]s.
pub mod appearance;
pub mod layout;
pub mod model;
pub mod io;
pub mod query;
pub mod style;
pub mod table;
/// **Legibility at scale** — collision-avoiding labels, a per-screen-cell edge ink
/// budget, the spatial [`legible::HoverIndex`] (hover that costs a neighbourhood, not
/// the dataset), and the opt-in shared instanced GPU cloud. See [`legible`].
pub mod legible;
use std::collections::{BTreeMap, BTreeSet};
use std::hash::{Hash, Hasher};
use egui::{Align2, Color32, CornerRadius, FontId, Sense, Stroke, vec2};
use facett_core::{a11y, theme, Facet, FacetCaps};
use serde::{Deserialize, Serialize};
pub use appearance::{Metric, Partition};
pub use layout::{bounds, layout as layout_positions, LayoutKind};
/// **The one call a host makes to put large force layouts on the GPU without ever
/// blocking its UI thread** — lend the navigator the `(Device, Queue)` the host's
/// `egui_wgpu::RenderState` already holds:
///
/// ```ignore
/// if let Some(rs) = cc.wgpu_render_state.as_ref() {
/// facett_graphnav::install_layout_device(&rs.device, &rs.queue);
/// }
/// ```
///
/// Re-exported here so a host that mounts `GraphNav` does not also have to know that
/// the compute lane lives in `facett-graphview`. NATIVE hosts want this as much as the
/// browser does, for a different reason: without it the `gpu` feature's native arm
/// (`layout::force_selected`) creates a SECOND device and WAITS on it inside
/// `positions()` — on the paint path — so a 30k-node graph freezes the window for the
/// length of the converge. With a lent device the same layout runs as a job across a
/// few frames. Returns `false` if the device cannot bind the layout pipeline.
#[cfg(feature = "gpu")]
pub use facett_graphview::gpu_layout::install_host_device as install_layout_device;
pub use model::{Edge, Node, PropGraph, Schema, SchemaTriple};
pub use query::{run as run_query, QueryResult, ResultKind};
pub use style::{StyleBy, Styling};
pub use table::{edge_batch, node_batch};
use facett_graphview::analysis::{pathfinding, Adjacency};
/// The **sample query** shown as the query-bar hint text. Deliberately **Cypher-only**:
/// FalkorDB (the common graph backend behind this navigator) speaks Cypher/openCypher,
/// so `MATCH (n) RETURN n` runs there while a Gremlin `g.V()` does not — advertising
/// `g.V()` was a wrong-engine footgun. The Gremlin-ish subset is still PARSED (see
/// [`query`]) for power users who type it; it is just no longer the surfaced sample.
/// Exposed so a consumer (e.g. korp's FalkorDB tab) can assert the sample stays Cypher.
pub const QUERY_HINT: &str = "MATCH (n) RETURN n";
/// The pan/zoom/select **camera** the navigator reuses from [`facett_graphpan`].
///
/// NOTE on convention: graphnav interprets the camera's `pan` in **normalised world
/// units** (the `[-1, 1]²` layout space), not screen pixels. Projection is
/// `screen = rect.center() + (world · zoom + pan) · scale`, so `Fit`/`ZoomToSelection`
/// are computed rect-independently (and thus headless-testable). `zoom` and `selected`
/// keep their graphpan meaning.
pub use facett_graphpan::GraphView as Camera;
/// The computed per-node visual encoding (see [`GraphNav::appearance`]).
#[derive(Clone, Debug, PartialEq)]
pub struct AppearanceResult {
/// Node radius (screen px), indexed like `graph.nodes`.
pub radii: Vec<f32>,
/// Node RGB fill, indexed like `graph.nodes`.
pub colors: Vec<[u8; 3]>,
/// A description of the colour encoding (`partition:…` / `metric:…` / `style:…`).
pub color_mode: String,
/// Number of distinct partition classes (0 when not partitioned).
pub partition_count: usize,
}
/// Zoom level [`Msg::ZoomToSelection`] snaps to.
const FOCUS_ZOOM: f32 = 2.6;
/// Camera zoom clamp (mirrors graphpan's own guard).
const ZOOM_MIN: f32 = 0.25;
const ZOOM_MAX: f32 = 4.0;
/// Upper bound on the elementary cycles the analysis toolbox enumerates — a guard for
/// dense graphs (Gephi/gdotv likewise cap their cycle browsers).
const CYCLE_LIMIT: usize = 64;
/// **Analytics scale guard** — the node count at/above which the SUPERLINEAR whole-graph
/// analytics refuse to run on the render/load path, the same discipline as
/// `facett-graph3d`'s `MDS_MAX` (which likewise sizes its guard at `4_000` before the
/// classical O(n²) MDS falls back to the landmark embedding). Above it:
/// elementary-cycle enumeration ([`GraphNav::cycles`], superlinear) is skipped unless the
/// user explicitly clicks *compute anyway*; the all-pairs `diameter` + `average_path_length`
/// ([`GraphNav::stats`]) are dropped (`n/a`) while the cheap scalars still compute; and a
/// superlinear colour/size metric ([`Metric::heavy_at_scale`] — betweenness / closeness,
/// O(V·E)) is skipped in [`GraphNav::appearance`]. Below it, every analytic runs exactly as
/// before (goldens unmoved). This is the fix for the single-core freeze a ~30 000-node graph
/// hit on load — Barnes–Hut made the LAYOUT cheap, leaving these unguarded analytics as the
/// last superlinear wall (CORE-SATURATION LAW: no single-core superlinear work at scale).
const ANALYTICS_SCALE_GUARD: usize = 4_000;
/// How many similar nodes the "similar to the selection" panel returns by default.
const SIMILAR_TOP_K: usize = 5;
/// Cycle-browser highlight (warm amber) + the similar-node ring (teal).
const CYCLE_COL: Color32 = Color32::from_rgb(240, 150, 60);
const SIMILAR_COL: Color32 = Color32::from_rgb(90, 206, 214);
/// Export serialisation formats the navigator can emit.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum ExportFormat {
Json,
Dot,
Csv,
/// GEXF 1.2 (Gephi's native interchange format).
Gexf,
/// GraphML (yEd / NetworkX / igraph).
GraphMl,
}
impl ExportFormat {
#[must_use]
pub fn key(self) -> &'static str {
match self {
ExportFormat::Json => "json",
ExportFormat::Dot => "dot",
ExportFormat::Csv => "csv",
ExportFormat::Gexf => "gexf",
ExportFormat::GraphMl => "graphml",
}
}
pub const ALL: [ExportFormat; 5] =
[ExportFormat::Json, ExportFormat::Dot, ExportFormat::Csv, ExportFormat::Gexf, ExportFormat::GraphMl];
/// Parse from a key.
#[must_use]
pub fn from_key(k: &str) -> Option<ExportFormat> {
ExportFormat::ALL.into_iter().find(|f| f.key() == k)
}
}
/// A robot-/CLI-addressable control message. Applied by [`GraphNav::update`].
#[derive(Clone, Debug, PartialEq)]
pub enum Msg {
/// Set the query-bar text (no evaluation yet).
SetQuery(String),
/// Evaluate the current query text into the result set.
RunQuery,
/// Select a node by id.
SelectNode(String),
/// Select an edge by index.
SelectEdge(usize),
/// Clear the selection.
ClearSelection,
/// Switch the canvas layout.
SetLayout(LayoutKind),
/// **Set the place column** — one [`layout::Place`] per node, index-aligned with the
/// graph's nodes, ALREADY projected by the host's own map projection. An empty
/// column removes it. See [`GraphNav::with_places`].
SetPlaces(Vec<layout::Place>),
/// Set the fuzzy-search text (recomputes the match set).
SetSearch(String),
/// Filter the canvas to one node label (`None` = all labels).
SetFilterLabel(Option<String>),
/// Reveal a node's neighbours on the canvas.
ExpandNeighborhood(String),
/// Hide a node's leaf neighbours from the canvas.
CollapseNeighborhood(String),
/// Highlight the shortest path between two node ids (`None` = clear).
SetPath(Option<(String, String)>),
/// Set the node-colouring rule.
SetStyle(StyleBy),
/// Record an export in the given format (the text is available via [`GraphNav::export`]).
Export(ExportFormat),
/// **Save** the current query text under a name (pins it for recall).
SaveQuery(String),
/// **Recall** a saved query by name into the query bar (no evaluation yet).
RecallQuery(String),
/// Clear the recent-query **history** (leaves saved queries intact).
ClearHistory,
/// **Extract** the ego-network within `radius` undirected hops of the *selected*
/// node as its own subgraph (surfaced in `state_json["subgraph"]`). No-op with
/// nothing selected.
ExtractSubgraph(usize),
/// Clear the active subgraph extraction.
ClearSubgraph,
/// **Pan** the camera by a world-space delta (a drag gesture, already divided by
/// the on-screen scale so it feels 1:1).
CameraPan([f32; 2]),
/// **Zoom** the camera by a multiplicative factor (scroll-zoom), clamped.
CameraZoom(f32),
/// **Fit** the whole graph to the viewport (reset pan to origin, zoom to 1).
FitView,
/// **Zoom to the selection** — centre the selected node and snap zoom in. No-op
/// with nothing selected.
ZoomToSelection,
/// **Size nodes** by a ranking metric (`None` = uniform).
SetSizeBy(Option<Metric>),
/// **Colour nodes** by a continuous metric on a sequential ramp (`None` = off).
SetColorMetric(Option<Metric>),
/// **Colour nodes** by a partition (`None` = off). Takes precedence over the
/// continuous colour metric and the categorical [`StyleBy`].
SetPartition(Option<Partition>),
/// **Highlight the `i`-th elementary cycle** on the canvas (`None` = clear). An
/// out-of-range index clears the highlight. The directed-cycle browser.
HighlightCycle(Option<usize>),
/// **Find the nodes most similar** to the *selected* node (neighbourhood overlap /
/// link-prediction), keeping the top `k`. No-op with nothing selected.
FindSimilar(usize),
/// Clear the active similar-node result.
ClearSimilar,
/// **Compute cycles anyway** — the explicit opt-in that overrides the
/// [`ANALYTICS_SCALE_GUARD`] cycle skip on a large graph (the "compute anyway" button
/// the cycle panel shows at scale). Runs the superlinear enumeration the user asked for.
ForceCycles,
/// **Fold / unfold the ⚙ settings surface** (the "modes & look" collapsible that holds
/// the layout / colour / size / ramp / partition + analysis controls). Toggles
/// [`GraphNav::settings_open`]; the default is folded so the graph canvas dominates on
/// open. A pure chrome-layout toggle — no graph behaviour changes.
ToggleSettings,
}
/// **Converge-once-then-freeze** position cache (not observable state). A force
/// layout is a pure function of `(layout kind, node count, edge set)`, so the
/// converged positions are computed once and reused every frame until that signature
/// changes — this is what stops the (now Barnes–Hut, O(n log n)) layout from re-running
/// on every `positions()` call in the render path, the freeze half of scaling to
/// 30 000 nodes. Kept OUT of the serde Model and made to compare/serialise as if
/// absent, so it never perturbs the observable `Model` equality or `state_json`.
#[derive(Default)]
struct LayoutCache(std::cell::RefCell<PosCache>);
#[derive(Default, Clone)]
struct PosCache {
sig: u64,
pos: Vec<[f32; 2]>,
/// Which lane produced `pos` — `"cpu"`, `"gpu-job"`, or `""` before any layout.
/// A readout, so "did the browser really lay this out on the GPU" is a question
/// with an answer rather than an inference from a feature flag.
lane: &'static str,
/// The in-flight non-blocking GPU layout, if any (feature `gpu`).
#[cfg(feature = "gpu")]
job: JobSlot,
}
/// The pending [`facett_graphview::gpu_layout::LayoutJob`] for one structural signature,
/// with the placeholder painted while it runs. `Clone` yields an EMPTY slot on purpose:
/// a job is VRAM buffers plus a map callback, and a cloned navigator re-deriving its
/// layout is correct where two navigators polling one readback would not be.
#[cfg(feature = "gpu")]
#[derive(Default)]
struct JobSlot {
sig: u64,
job: Option<Box<facett_graphview::gpu_layout::LayoutJob>>,
placeholder: Vec<[f32; 2]>,
/// A signature whose job FAILED — it takes the CPU lane and is not retried, so a
/// lost device costs one fallback rather than a job restarted every frame.
failed_sig: Option<u64>,
/// Why it failed, for the readout. Empty when no job has failed.
failed_why: &'static str,
/// The repulsion kernel the last started job runs (`"grid"` / `"all-pairs"`).
kernel: &'static str,
}
#[cfg(feature = "gpu")]
impl Clone for JobSlot {
fn clone(&self) -> Self {
JobSlot { failed_sig: self.failed_sig, failed_why: self.failed_why, ..JobSlot::default() }
}
}
impl Clone for LayoutCache {
fn clone(&self) -> Self {
LayoutCache(std::cell::RefCell::new(self.0.borrow().clone()))
}
}
impl std::fmt::Debug for LayoutCache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("LayoutCache(..)")
}
}
// Derived state — two navigators with equal observable state are equal regardless of
// whether either has warmed its cache, so it must never affect Model equality.
impl PartialEq for LayoutCache {
fn eq(&self, _: &Self) -> bool {
true
}
}
/// **Converge-once-then-freeze** analytics cache (not observable state) — the same
/// discipline as [`LayoutCache`], applied to the whole-graph ANALYTICS the render path
/// recomputes on every frame. Cycle enumeration ([`cycles`](GraphNav::cycles), superlinear
/// on dense graphs), the stats-panel scalars ([`stats`](GraphNav::stats): all-pairs
/// diameter, Louvain modularity, clustering — O(V·E)+), and the per-node appearance
/// encoding ([`appearance`](GraphNav::appearance): pagerank / betweenness centrality — up
/// to O(V³)) are pure functions of the graph structure — and, for appearance, of the
/// active style/metric/partition selection. Barnes–Hut made the LAYOUT cheap, which
/// exposed that these were still re-run every paint (free on a 10-node demo, tens of ms
/// each on a real ~300-node graph). They are computed once and reused every frame until
/// the relevant signature changes. Kept OUT of the serde Model and neutral in equality
/// (exactly like [`LayoutCache`]), so it never perturbs `Model` equality or `state_json`.
#[derive(Default)]
struct AnalyticsCache(std::cell::RefCell<AnalyticsData>);
#[derive(Default, Clone)]
struct AnalyticsData {
/// Structure-keyed stats (`(node count, edges)` signature).
stats_sig: u64,
stats: Option<serde_json::Value>,
/// Structure-keyed elementary cycles.
cycles_sig: u64,
cycles: Option<Vec<Vec<String>>>,
/// Structure-keyed acyclicity (`is_acyclic`, read by every `cycles_json`).
acyclic_sig: u64,
acyclic: Option<bool>,
/// **Compute-anyway override** for the [`ANALYTICS_SCALE_GUARD`] cycle skip: `false`
/// keeps the enumeration off above the guard (the default at scale); set `true` by
/// [`Msg::ForceCycles`] when the user explicitly opts in. A view-only toggle, so it
/// lives in this serde-skipped, equality-neutral cache and never perturbs `state_json`.
force_cycles: bool,
/// Structure + active style/metric/partition-keyed appearance.
appearance_sig: u64,
appearance: Option<AppearanceResult>,
/// **Miss counters** — how many times each expensive analytic actually RAN (a cache
/// hit does NOT bump them). Derived/observability-only; the RED-when-broken freeze
/// tests assert these stay flat across repeated calls for an unchanged graph and step
/// exactly once when the signature changes.
stats_computes: u64,
cycles_computes: u64,
appearance_computes: u64,
}
impl Clone for AnalyticsCache {
fn clone(&self) -> Self {
AnalyticsCache(std::cell::RefCell::new(self.0.borrow().clone()))
}
}
impl std::fmt::Debug for AnalyticsCache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("AnalyticsCache(..)")
}
}
// Derived state — never affects Model equality (same rationale as [`LayoutCache`]).
impl PartialEq for AnalyticsCache {
fn eq(&self, _: &Self) -> bool {
true
}
}
/// **Chrome-layout telemetry** — the screen rect the canvas actually claimed and the
/// viewport it was laid out in, recorded by [`GraphNav::render`] each frame. This is what
/// lets the robot prove the *canvas-first* layout: `state_json["chrome"]["canvas"]` reports
/// the canvas rect + its fraction of the viewport, so a test fails RED if the toolbar ever
/// squeezes the canvas to the bottom again. Derived observability only — kept OUT of the
/// serde `Model` and neutral in equality (exactly like [`LayoutCache`] / [`AnalyticsCache`]),
/// so it never perturbs `Model` equality or a golden.
#[derive(Default)]
struct ChromeCache(std::cell::Cell<ChromeMetrics>);
#[derive(Default, Clone, Copy)]
struct ChromeMetrics {
/// Last painted canvas rect `[x, y, w, h]` in screen px.
canvas: [f32; 4],
/// Last render viewport size `[w, h]` in screen px (the rect `render` was handed).
view: [f32; 2],
}
impl Clone for ChromeCache {
fn clone(&self) -> Self {
ChromeCache(std::cell::Cell::new(self.0.get()))
}
}
impl std::fmt::Debug for ChromeCache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("ChromeCache(..)")
}
}
// Derived state — never affects Model equality (same rationale as [`LayoutCache`]).
impl PartialEq for ChromeCache {
fn eq(&self, _: &Self) -> bool {
true
}
}
/// The hover index + the last frame's legibility report. Derived observability +
/// an ephemeral cache — serde-skipped and equality-neutral, exactly like
/// [`LayoutCache`] / [`AnalyticsCache`] / [`ChromeCache`], so it never perturbs Model
/// equality or a golden.
#[derive(Default)]
struct LegibilityCache(std::cell::RefCell<(legible::HoverIndex, legible::NavReport)>);
impl Clone for LegibilityCache {
fn clone(&self) -> Self {
// A cache is rebuilt on demand; cloning a navigator clones no stale index.
LegibilityCache::default()
}
}
impl std::fmt::Debug for LegibilityCache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("LegibilityCache(..)")
}
}
impl PartialEq for LegibilityCache {
fn eq(&self, _: &Self) -> bool {
true
}
}
/// Nodes above which the canvas takes its SCALE road when the GPU cloud draws: the
/// discs and edges are resident on the GPU, and the CPU loops only over the nodes the
/// user is pointing at (selection, hover and its neighbours, path, search matches,
/// cycle, similar set). Below it, every visible node keeps its own a11y widget.
pub const SCALE_NODES: usize = 5_000;
/// **Everything the canvas reads every frame that depends only on the model** — built
/// once per model change instead of once per frame.
///
/// MEASURED 2026-09-28 (oden, native): at 10 000 nodes the canvas rebuilt, EVERY frame,
/// a `BTreeMap` of node ids for `edge_indices` (twice — layout signature and appearance
/// signature), an id→index `HashMap`, an id→neighbours `HashMap`, the schema, and it
/// asked the `BTreeSet<String>` visible set once per node and four times per edge. At
/// 100 000 nodes that is a few hundred milliseconds of string hashing per frame before
/// anything is drawn. Here each of those is a flat array, rebuilt when [`FrameKey`]
/// moves.
#[derive(Default)]
struct FrameIndex {
key: FrameKey,
/// `graph.edge_indices()` — the resolved `(from, to)` of every edge that resolves.
edge_indices: Vec<(usize, usize)>,
/// Per edge in `graph.edges` order: its endpoints, `u32::MAX` when unresolved.
edge_idx: Vec<(u32, u32)>,
/// Per edge: endpoints when BOTH are visible, else `(u32::MAX, u32::MAX)`.
edge_pairs: Vec<(u32, u32)>,
/// Per edge: its `weight` property, and the largest of them.
ew: Vec<f32>,
ew_max: f32,
/// Undirected, de-duplicated adjacency (CSR): `adj[adj_off[i]..adj_off[i+1]]`.
adj_off: Vec<u32>,
adj: Vec<u32>,
/// Per node: in the visible set; on the highlighted path; a search match; on the
/// highlighted cycle; in the similar-to-selection set; caption length in chars.
visible: Vec<bool>,
path: Vec<bool>,
matched: Vec<bool>,
cycle: Vec<bool>,
similar: Vec<bool>,
caption_chars: Vec<u16>,
/// The flagged nodes (path ∪ matched ∪ cycle ∪ similar ∪ selected), in index order.
special: Vec<usize>,
selected: Option<usize>,
/// `schema().node_labels.len()` / `.edge_types.len()` for the footer.
label_count: usize,
etype_count: usize,
/// `graph.schema()` itself — built here anyway for the two counts above, and read by
/// every `state_json` (80 ms of label/type counting at 100 000 nodes per read when
/// it was recomputed there, MEASURED 2026-09-29 dwarf).
schema: Option<model::Schema>,
/// `structure_sig(key, n, edge_indices)` per cache key (`"force"`, `"appearance"`,
/// `"stats"`, …), computed once per index. The sig hashes every resolved edge, and
/// `positions()` + `appearance()` asked for it on EVERY frame: 2 × 206 250 edges
/// hashed per frame at 100k, for an answer that only moves with the model
/// (lane M, 2026-10-02).
sigs: std::cell::RefCell<Vec<(String, u64)>>,
}
impl FrameIndex {
/// The memoised `structure_sig(key, n, &self.edge_indices)`.
fn sig(&self, key: &str, n: usize) -> u64 {
if let Some(&(_, v)) = self.sigs.borrow().iter().find(|(k, _)| k == key) {
return v;
}
let v = facett_core::barnes_hut::structure_sig(key, n, &self.edge_indices);
self.sigs.borrow_mut().push((key.to_string(), v));
v
}
}
/// What a [`FrameIndex`] was built from. The graph is compared by length and buffer
/// address (a replaced or grown `Vec` moves), and every model change made through
/// [`GraphNav::update`] or [`GraphNav::absorb`] bumps `version`. A caller that edits
/// `graph` in place through the public field without changing its length must call
/// [`GraphNav::touch`].
#[derive(Default, Clone, Copy, PartialEq, Eq)]
struct FrameKey {
nodes: usize,
edges: usize,
nodes_ptr: usize,
edges_ptr: usize,
version: u64,
}
#[derive(Default)]
struct FrameCache {
version: std::cell::Cell<u64>,
idx: std::cell::RefCell<FrameIndex>,
/// The cloud model generation last handed to the GPU (0 = never).
uploaded: std::cell::Cell<u64>,
}
impl Clone for FrameCache {
fn clone(&self) -> Self {
FrameCache::default()
}
}
impl std::fmt::Debug for FrameCache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("FrameCache(..)")
}
}
impl PartialEq for FrameCache {
fn eq(&self, _: &Self) -> bool {
true
}
}
/// The GRAPH NAVIGATOR [`Facet`] — its own Elm `Model`.
#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
pub struct GraphNav {
pub title: String,
pub graph: PropGraph,
/// The query-bar text.
query_text: String,
/// The matched node ids of the last run query.
result_nodes: Vec<String>,
/// The matched edge indices of the last run query.
result_edges: Vec<usize>,
/// The last query's kind key ("nodes"/"edges"/"search"/"empty").
result_kind: String,
/// The last query's error, if any.
result_error: Option<String>,
layout_kind: LayoutKind,
/// **Where each node IS**, on the HOST's own map plane — one [`layout::Place`] per
/// node, index-aligned with `graph.nodes`. Empty (the default) for every graph that
/// is not anywhere, which is most of them.
///
/// The host projects, this crate does not: see [`LayoutKind::Geographic`]. Set it
/// with [`GraphNav::with_places`] / [`Msg::SetPlaces`], and the switcher grows a
/// `geographic` chip exactly when the column covers every node.
places: Vec<layout::Place>,
selected_node: Option<String>,
selected_edge: Option<usize>,
search_text: String,
filter_label: Option<String>,
/// The node ids currently drawn on the canvas (expand/collapse + filter mutate it).
visible: BTreeSet<String>,
/// The highlighted shortest-path endpoints + the resolved node id path.
path_endpoints: Option<(String, String)>,
path_nodes: Vec<String>,
/// The node-colouring rule (serialised via its key form).
style_key: String,
/// **Ontology palette override** — a caller-pinned `label → RGB` map that wins over
/// the first-seen wheel / hashed [`style::label_color`] when colouring by
/// [`StyleBy::Label`]. Lets a consumer (korp) freeze a FIXED ontology palette
/// (`Person`/`Vessel`/`Aircraft`/`Company`/`Address` always the same hue) so colours
/// never reshuffle between queries. Un-overridden labels keep the existing rule.
/// Empty (the default) ⇒ colouring is byte-identical to before this knob existed.
/// Stored as raw RGB so the Model stays serde-clean (no egui-serde feature needed).
#[serde(default, skip_serializing_if = "BTreeMap::is_empty")]
label_color_overrides: BTreeMap<String, [u8; 3]>,
/// The last export format requested (for observability).
last_export: Option<ExportFormat>,
/// The **query history** — the distinct queries actually run, most-recent last
/// (capped at [`QUERY_HISTORY_CAP`]). The gdotv "recent queries" recall list.
#[serde(default)]
query_history: Vec<String>,
/// **Saved queries** — a name → query-text book the user pins for one-click recall.
#[serde(default)]
saved_queries: BTreeMap<String, String>,
/// The **subgraph-extraction radius** around the selected node (`None` = no
/// extraction active). Set via [`Msg::ExtractSubgraph`]; the induced ego-network is
/// surfaced in `state_json["subgraph"]`. The gdotv "extract a neighbourhood as its
/// own graph" gesture.
#[serde(default)]
subgraph_radius: Option<usize>,
/// The pan/zoom/select **camera** (from [`facett_graphpan`]). Its `pan` is in
/// normalised world units (see [`Camera`]). Survives frames + round-trips serde.
#[serde(default)]
camera: Camera,
/// **Size nodes by** this ranking metric (`None` = uniform radius).
#[serde(default)]
size_metric: Option<Metric>,
/// **Colour nodes by** this continuous metric on a sequential ramp (`None` = off).
#[serde(default)]
color_metric: Option<Metric>,
/// **Colour nodes by** this partition (`None` = off). Precedence over `color_metric`.
#[serde(default)]
partition: Option<Partition>,
/// The index (into [`GraphNav::cycles`]) of the elementary cycle currently
/// **highlighted** on the canvas (`None` = none). Set via [`Msg::HighlightCycle`].
#[serde(default)]
highlight_cycle: Option<usize>,
/// The active **similar-to-the-selection** top-k (`None` = the panel is off). Set
/// via [`Msg::FindSimilar`]; anchored on the current node selection.
#[serde(default)]
similarity_k: Option<usize>,
/// The frozen layout positions (see [`LayoutCache`]). Not part of the observable
/// Model — skipped by serde and neutral in equality; rebuilt lazily on demand.
#[serde(skip)]
layout_cache: LayoutCache,
/// The frozen whole-graph analytics (see [`AnalyticsCache`]). Not part of the
/// observable Model — skipped by serde and neutral in equality; rebuilt lazily.
#[serde(skip)]
analytics_cache: AnalyticsCache,
/// **Fold state of the ⚙ settings surface** (the "modes & look" collapsible holding the
/// layout / colour / size / ramp / partition + analysis controls). `false` = folded, the
/// default, so the graph canvas is the main attraction on open; toggled by
/// [`Msg::ToggleSettings`]. Surfaced in `state_json["chrome"]["settings_open"]`.
#[serde(default)]
settings_open: bool,
/// Chrome-layout telemetry (canvas rect + viewport), recorded each frame (see
/// [`ChromeCache`]). Serde-skipped, equality-neutral; feeds the canvas-dominance proof.
#[serde(skip)]
chrome_cache: ChromeCache,
/// **Legibility switches** — label collision, the edge ink budget, and the opt-in
/// shared GPU cloud. Part of the observable Model (a robot can drive them);
/// `#[serde(default)]` so an older saved navigator loads with the defaults.
#[serde(default)]
pub legibility: legible::LegibilityOpts,
/// The hover index + the last frame's legibility report (see [`LegibilityCache`]).
#[serde(skip)]
legibility_cache: LegibilityCache,
/// The per-model flat arrays the canvas reads every frame (see [`FrameIndex`]).
#[serde(skip)]
frame_cache: FrameCache,
}
/// How many recent queries the [`GraphNav::query_history`] keeps.
const QUERY_HISTORY_CAP: usize = 50;
impl GraphNav {
/// Build a navigator over a property graph (all nodes visible, force layout).
pub fn new(title: impl Into<String>, graph: PropGraph) -> Self {
let visible = graph.nodes.iter().map(|n| n.id.clone()).collect();
Self {
title: title.into(),
graph,
query_text: String::new(),
result_nodes: Vec::new(),
result_edges: Vec::new(),
result_kind: "empty".into(),
result_error: None,
layout_kind: LayoutKind::Force,
selected_node: None,
selected_edge: None,
search_text: String::new(),
filter_label: None,
visible,
path_endpoints: None,
path_nodes: Vec::new(),
style_key: "label".into(),
label_color_overrides: BTreeMap::new(),
last_export: None,
query_history: Vec::new(),
saved_queries: BTreeMap::new(),
subgraph_radius: None,
camera: Camera::default(),
size_metric: None,
color_metric: None,
partition: None,
highlight_cycle: None,
similarity_k: None,
layout_cache: LayoutCache::default(),
analytics_cache: AnalyticsCache::default(),
settings_open: false,
chrome_cache: ChromeCache::default(),
places: Vec::new(),
legibility: legible::LegibilityOpts::default(),
legibility_cache: LegibilityCache::default(),
frame_cache: FrameCache::default(),
}
}
/// Declare the model changed: the next frame rebuilds its per-model arrays. Every
/// change made through [`update`](Self::update) or [`absorb`](Self::absorb) does
/// this already; call it after editing [`graph`](Self::graph) in place through the
/// public field without changing its length.
pub fn touch(&self) {
self.frame_cache.version.set(self.frame_cache.version.get().wrapping_add(1));
}
fn frame_key(&self) -> FrameKey {
FrameKey {
nodes: self.graph.nodes.len(),
edges: self.graph.edges.len(),
nodes_ptr: self.graph.nodes.as_ptr() as usize,
edges_ptr: self.graph.edges.as_ptr() as usize,
version: self.frame_cache.version.get(),
}
}
/// The per-model arrays, rebuilt when the model moved (see [`FrameIndex`]).
fn frame_index(&self) -> std::cell::Ref<'_, FrameIndex> {
let key = self.frame_key();
if self.frame_cache.idx.borrow().key != key {
let built = self.build_frame_index(key);
*self.frame_cache.idx.borrow_mut() = built;
}
self.frame_cache.idx.borrow()
}
fn build_frame_index(&self, key: FrameKey) -> FrameIndex {
let n = self.graph.nodes.len();
let index: std::collections::HashMap<&str, u32> =
self.graph.nodes.iter().enumerate().map(|(i, nd)| (nd.id.as_str(), i as u32)).collect();
let look = |id: &str| index.get(id).copied().unwrap_or(u32::MAX);
let flags = |ids: &mut dyn Iterator<Item = &str>| {
let mut f = vec![false; n];
for id in ids {
if let Some(&i) = index.get(id) {
f[i as usize] = true;
}
}
f
};
let visible: Vec<bool> = self.graph.nodes.iter().map(|nd| self.visible.contains(&nd.id)).collect();
let edge_idx: Vec<(u32, u32)> = self.graph.edges.iter().map(|e| (look(&e.from), look(&e.to))).collect();
let edge_indices: Vec<(usize, usize)> = edge_idx
.iter()
.filter(|&&(a, b)| a != u32::MAX && b != u32::MAX)
.map(|&(a, b)| (a as usize, b as usize))
.collect();
let edge_pairs: Vec<(u32, u32)> = edge_idx
.iter()
.map(|&(a, b)| {
if a != u32::MAX && b != u32::MAX && visible[a as usize] && visible[b as usize] {
(a, b)
} else {
(u32::MAX, u32::MAX)
}
})
.collect();
let ew: Vec<f32> = (0..self.graph.edges.len()).map(|i| self.edge_weight(i)).collect();
let ew_max = ew.iter().copied().fold(1e-6_f32, f32::max);
// Undirected CSR, de-duplicated like `PropGraph::adjacency`.
let mut deg = vec![0u32; n + 1];
for &(a, b) in &edge_indices {
if a != b {
deg[a] += 1;
deg[b] += 1;
}
}
let mut adj_off = vec![0u32; n + 1];
for i in 0..n {
adj_off[i + 1] = adj_off[i] + deg[i];
}
let mut fill = adj_off.clone();
let mut adj = vec![0u32; adj_off[n] as usize];
for &(a, b) in &edge_indices {
if a != b {
adj[fill[a] as usize] = b as u32;
fill[a] += 1;
adj[fill[b] as usize] = a as u32;
fill[b] += 1;
}
}
let mut dedup_off = vec![0u32; n + 1];
let mut dedup = Vec::with_capacity(adj.len());
for i in 0..n {
let s = &mut adj[adj_off[i] as usize..adj_off[i + 1] as usize];
s.sort_unstable();
let start = dedup.len();
for &t in s.iter() {
if dedup.len() == start || *dedup.last().unwrap_or(&u32::MAX) != t {
dedup.push(t);
}
}
dedup_off[i + 1] = dedup.len() as u32;
}
let path = flags(&mut self.path_nodes.iter().map(String::as_str));
let matches = self.search_matches();
let matched = flags(&mut matches.iter().map(String::as_str));
let cyc = self.cycle_nodes();
let cycle = flags(&mut cyc.iter().map(String::as_str));
let sim: Vec<String> = match (self.similarity_k, self.selected_node.as_deref()) {
(Some(k), Some(c)) => self.similar(c, k).into_iter().map(|(id, _)| id).collect(),
_ => Vec::new(),
};
let similar = flags(&mut sim.iter().map(String::as_str));
let selected = self.selected_node.as_deref().and_then(|s| index.get(s).map(|&i| i as usize));
let special: Vec<usize> = (0..n)
.filter(|&i| path[i] || matched[i] || cycle[i] || similar[i] || selected == Some(i))
.collect();
let caption_chars = self.graph.nodes.iter().map(|nd| nd.caption().chars().count().min(u16::MAX as usize) as u16).collect();
let schema = self.graph.schema();
FrameIndex {
key,
edge_indices,
edge_idx,
edge_pairs,
ew,
ew_max,
adj_off: dedup_off,
adj: dedup,
visible,
path,
matched,
cycle,
similar,
caption_chars,
special,
selected,
label_count: schema.node_labels.len(),
etype_count: schema.edge_types.len(),
schema: Some(schema),
sigs: std::cell::RefCell::default(),
}
}
/// A self-contained demo navigator over [`PropGraph::demo`].
#[must_use]
pub fn demo() -> Self {
Self::new("graphnav", PropGraph::demo())
}
/// **Tell the navigator where its nodes are** — one [`layout::Place`] per node, in
/// `graph.nodes` order, on the HOST's own map plane (already projected: this crate
/// owns no projection, see [`LayoutKind::Geographic`]).
///
/// With a column that covers every node the switcher offers `geographic` and a road
/// network draws as a road network. With none — the default — nothing changes.
#[must_use]
pub fn with_places(mut self, places: Vec<layout::Place>) -> Self {
self.places = places;
self
}
/// Does this graph carry a place for EVERY node (so the geographic layout is
/// available)? The one predicate, `layout::places_cover`, so the switcher and the
/// layout cannot disagree about whether the lane exists.
#[must_use]
pub fn has_places(&self) -> bool {
layout::places_cover(self.graph.nodes.len(), &self.places)
}
// ── read accessors ───────────────────────────────────────────────────────
#[must_use]
pub fn layout_kind(&self) -> LayoutKind {
self.layout_kind
}
#[must_use]
pub fn selected(&self) -> Option<&str> {
self.selected_node.as_deref()
}
#[must_use]
pub fn visible_count(&self) -> usize {
self.visible.len()
}
/// The live pan/zoom [`Camera`].
#[must_use]
pub fn camera(&self) -> &Camera {
&self.camera
}
/// The metric nodes are **sized** by (`None` = uniform).
#[must_use]
pub fn size_metric(&self) -> Option<Metric> {
self.size_metric
}
/// The metric nodes are **colour-ramped** by (`None` = off).
#[must_use]
pub fn color_metric(&self) -> Option<Metric> {
self.color_metric
}
/// The **partition** nodes are coloured by (`None` = off).
#[must_use]
pub fn partition(&self) -> Option<Partition> {
self.partition
}
/// The current node-colouring rule.
#[must_use]
pub fn style_by(&self) -> StyleBy {
parse_style(&self.style_key)
}
// ── ontology palette override (the fixed-palette knob korp pins) ──────────────
/// **Pin a fixed ontology palette.** Builder form of [`set_label_color`](Self::set_label_color):
/// consume `overrides` (`label → Color32`) so a caller freezes the hue of specific
/// labels — e.g. `Person`/`Vessel`/`Aircraft`/`Company`/`Address` always the same
/// colour, invariant to which query ran or in what order labels are first seen. Under
/// [`StyleBy::Label`] these hues win over the first-seen wheel / hashed
/// [`style::label_color`]; un-overridden labels keep the existing rule. With no
/// overrides set, node colouring is byte-identical to before this knob existed.
#[must_use]
pub fn with_label_colors(
mut self,
overrides: impl IntoIterator<Item = (impl Into<String>, Color32)>,
) -> Self {
for (label, color) in overrides {
self.set_label_color(label, color);
}
self
}
/// Pin one label's ontology colour (see [`with_label_colors`](Self::with_label_colors)).
/// Overwrites any prior override for `label`.
pub fn set_label_color(&mut self, label: impl Into<String>, color: Color32) {
self.label_color_overrides
.insert(label.into(), [color.r(), color.g(), color.b()]);
}
/// Remove a single label's override (no-op if absent); returns whether one was removed.
pub fn clear_label_color(&mut self, label: &str) -> bool {
self.label_color_overrides.remove(label).is_some()
}
/// The pinned ontology palette as `label → Color32` (empty when no overrides set).
#[must_use]
pub fn label_color_overrides(&self) -> BTreeMap<String, Color32> {
self.label_color_overrides
.iter()
.map(|(k, [r, g, b])| (k.clone(), Color32::from_rgb(*r, *g, *b)))
.collect()
}
/// The RGB override for node `i` **iff** an ontology-label palette pin applies: the
/// current styling must be by label (`styling.stable`) and node `i`'s label must be
/// in the override map. `None` (the common path — empty map short-circuits) means "use
/// the existing wheel / hashed rule", keeping the default byte-identical.
fn label_override_rgb(&self, styling: &style::Styling, i: usize) -> Option<[u8; 3]> {
if self.label_color_overrides.is_empty() || !styling.stable {
return None;
}
let cat = styling.of.get(i).copied().flatten()?;
self.label_color_overrides
.get(&styling.categories[cat])
.copied()
}
/// The search match set (node ids) for the current search text.
#[must_use]
pub fn search_matches(&self) -> Vec<String> {
if self.search_text.trim().is_empty() {
Vec::new()
} else {
query::search(&self.graph, &self.search_text).nodes
}
}
/// Apply a [`Msg`]. Returns `true` if it changed observable state.
pub fn update(&mut self, msg: Msg) -> bool {
// Any model change rebuilds the per-frame arrays; a camera move is the one
// message a drag sends every frame, and it moves nothing they hold.
if !matches!(msg, Msg::CameraPan(_) | Msg::CameraZoom(_)) {
self.touch();
}
match msg {
Msg::SetQuery(q) => {
let changed = self.query_text != q;
self.query_text = q;
changed
}
Msg::RunQuery => {
let r = query::run(&self.graph, &self.query_text);
self.result_kind = r.kind().key().to_string();
self.result_error = r.error.clone();
self.result_nodes = r.nodes;
self.result_edges = r.edges;
// Record the run in the recent-query history (skip empties + repeats of
// the immediately-preceding query), capped at QUERY_HISTORY_CAP.
let q = self.query_text.trim();
if !q.is_empty() && self.query_history.last().map(String::as_str) != Some(q) {
self.query_history.push(q.to_string());
if self.query_history.len() > QUERY_HISTORY_CAP {
let overflow = self.query_history.len() - QUERY_HISTORY_CAP;
self.query_history.drain(0..overflow);
}
}
true
}
Msg::SelectNode(id) => {
if self.graph.node(&id).is_some() && self.selected_node.as_deref() != Some(&id) {
self.selected_node = Some(id);
self.selected_edge = None;
true
} else {
false
}
}
Msg::SelectEdge(i) => {
if i < self.graph.edges.len() && self.selected_edge != Some(i) {
self.selected_edge = Some(i);
self.selected_node = None;
true
} else {
false
}
}
Msg::ClearSelection => {
let had = self.selected_node.is_some() || self.selected_edge.is_some();
self.selected_node = None;
self.selected_edge = None;
had
}
Msg::SetPlaces(p) => {
let changed = self.places != p;
self.places = p;
if changed {
// The cache is keyed on `(layout, n, edges)`, and a place column is
// none of those — a new column with the same structure would keep
// the OLD positions and the canvas would not move. Drop it.
self.layout_cache.0.borrow_mut().pos.clear();
}
changed
}
Msg::SetLayout(k) => {
let changed = self.layout_kind != k;
self.layout_kind = k;
changed
}
Msg::SetSearch(s) => {
let changed = self.search_text != s;
self.search_text = s;
changed
}
Msg::SetFilterLabel(l) => {
let changed = self.filter_label != l;
self.filter_label = l;
self.recompute_visible();
changed
}
Msg::ExpandNeighborhood(id) => {
let before = self.visible.len();
for nb in self.graph.neighbours(&id) {
self.visible.insert(nb);
}
self.visible.insert(id);
self.visible.len() != before
}
Msg::CollapseNeighborhood(id) => {
let before = self.visible.len();
// Remove leaf neighbours whose only visible attachment is `id`.
let nbrs = self.graph.neighbours(&id);
for nb in nbrs {
if self.selected_node.as_deref() == Some(nb.as_str()) {
continue;
}
let others: Vec<String> =
self.graph.neighbours(&nb).into_iter().filter(|o| *o != id && self.visible.contains(o)).collect();
if others.is_empty() {
self.visible.remove(&nb);
}
}
self.visible.len() != before
}
Msg::SetPath(ep) => {
let changed = self.path_endpoints != ep;
self.path_endpoints = ep;
self.recompute_path();
changed
}
Msg::SetStyle(by) => {
let key = by.key();
let changed = self.style_key != key;
self.style_key = key;
changed
}
Msg::Export(fmt) => {
let changed = self.last_export != Some(fmt);
self.last_export = Some(fmt);
changed
}
Msg::SaveQuery(name) => {
if name.trim().is_empty() {
return false;
}
let prev = self.saved_queries.insert(name, self.query_text.clone());
prev.as_deref() != Some(self.query_text.as_str())
}
Msg::RecallQuery(name) => match self.saved_queries.get(&name) {
Some(q) if *q != self.query_text => {
self.query_text = q.clone();
true
}
_ => false,
},
Msg::ClearHistory => {
let had = !self.query_history.is_empty();
self.query_history.clear();
had
}
Msg::ExtractSubgraph(radius) => {
// Extraction is anchored on the current selection.
if self.selected_node.is_none() {
return false;
}
let changed = self.subgraph_radius != Some(radius);
self.subgraph_radius = Some(radius);
changed
}
Msg::ClearSubgraph => {
let had = self.subgraph_radius.is_some();
self.subgraph_radius = None;
had
}
Msg::CameraPan([dx, dy]) => {
if dx == 0.0 && dy == 0.0 {
return false;
}
self.camera.pan += vec2(dx, dy);
true
}
Msg::CameraZoom(factor) => {
let z = (self.camera.zoom * factor).clamp(ZOOM_MIN, ZOOM_MAX);
let changed = (z - self.camera.zoom).abs() > f32::EPSILON;
self.camera.zoom = z;
changed
}
Msg::FitView => {
let changed = self.camera.pan != vec2(0.0, 0.0) || (self.camera.zoom - 1.0).abs() > f32::EPSILON;
self.camera.fit();
changed
}
Msg::ZoomToSelection => {
let Some(id) = self.selected_node.clone() else { return false };
let Some(i) = self.graph.index_of(&id) else { return false };
let pos = self.positions();
let w = pos[i];
// Centre the node: screen = center + (w·zoom + pan)·scale ⇒ pan = -w·zoom.
let new_pan = vec2(-w[0] * FOCUS_ZOOM, -w[1] * FOCUS_ZOOM);
let changed = self.camera.pan != new_pan || (self.camera.zoom - FOCUS_ZOOM).abs() > f32::EPSILON;
self.camera.pan = new_pan;
self.camera.zoom = FOCUS_ZOOM;
changed
}
Msg::SetSizeBy(m) => {
let changed = self.size_metric != m;
self.size_metric = m;
changed
}
Msg::SetColorMetric(m) => {
// The continuous ramp and a partition are mutually-exclusive colour channels.
let changed = self.color_metric != m || (m.is_some() && self.partition.is_some());
self.color_metric = m;
if m.is_some() {
self.partition = None;
}
changed
}
Msg::SetPartition(p) => {
let changed = self.partition != p || (p.is_some() && self.color_metric.is_some());
self.partition = p;
if p.is_some() {
self.color_metric = None;
}
changed
}
Msg::HighlightCycle(idx) => {
// Clamp to an existing cycle; an out-of-range index clears the highlight.
let idx = idx.filter(|&i| i < self.cycles().len());
let changed = self.highlight_cycle != idx;
self.highlight_cycle = idx;
changed
}
Msg::FindSimilar(k) => {
// Anchored on the selection (like ExtractSubgraph); no selection ⇒ no-op.
if self.selected_node.is_none() || k == 0 {
return false;
}
let changed = self.similarity_k != Some(k);
self.similarity_k = Some(k);
changed
}
Msg::ClearSimilar => {
let had = self.similarity_k.is_some();
self.similarity_k = None;
had
}
Msg::ForceCycles => {
// View-only opt-in stored in the (equality-neutral) analytics cache, so it
// never perturbs Model equality / state_json. Invalidate the cached empty
// result so the next `cycles()` actually enumerates.
let mut c = self.analytics_cache.0.borrow_mut();
let was = c.force_cycles;
c.force_cycles = true;
if !was {
c.cycles_sig = 0;
c.cycles = None;
}
!was
}
Msg::ToggleSettings => {
self.settings_open = !self.settings_open;
true
}
}
}
/// The **computed appearance** — per-node radius + RGB fill under the current
/// ranking/partition/categorical rules, plus a legend describing the encoding.
/// The single source both the painter and `state_json` read.
#[must_use]
pub fn appearance(&self) -> AppearanceResult {
let sig = self.appearance_sig();
{
let c = self.analytics_cache.0.borrow();
if c.appearance_sig == sig && let Some(a) = &c.appearance {
return a.clone();
}
}
let a = self.compute_appearance();
let mut c = self.analytics_cache.0.borrow_mut();
c.appearance_sig = sig;
c.appearance = Some(a.clone());
c.appearance_computes += 1;
a
}
/// The cache key for [`appearance`](Self::appearance): the graph structure PLUS the
/// active encoding selection (categorical style, size metric, colour metric,
/// partition). Any of those changing — a structural mutation, an [`absorb`](Self::absorb),
/// or a style/metric/partition switch via [`update`](Self::update) — flips the
/// signature and invalidates the frozen encoding.
fn appearance_sig(&self) -> u64 {
let fi = self.frame_index();
let mut h = std::collections::hash_map::DefaultHasher::new();
fi.sig("appearance", self.graph.nodes.len()).hash(&mut h);
self.style_key.hash(&mut h);
// The ontology palette override changes the categorical colours, so it must flip
// the cache signature (BTreeMap iterates in sorted key order → deterministic hash).
for (label, rgb) in &self.label_color_overrides {
label.hash(&mut h);
rgb.hash(&mut h);
}
self.size_metric.map(|m| m.key()).hash(&mut h);
self.color_metric.map(|m| m.key()).hash(&mut h);
self.partition.map(|p| p.key()).hash(&mut h);
h.finish()
}
/// The uncached appearance computation (pagerank / betweenness / partition assignment).
/// Reached only on a cache miss in [`appearance`](Self::appearance).
fn compute_appearance(&self) -> AppearanceResult {
let n = self.graph.nodes.len();
let big = n >= ANALYTICS_SCALE_GUARD;
// ── ANALYTICS SCALE GUARD ──────────────────────────────────────────────────
// A superlinear metric ([`Metric::heavy_at_scale`]: betweenness / closeness, the
// all-pairs O(V·E) ones) would freeze a single core at scale. It's cached, so it
// runs at most once per selection — but even once is unacceptable at 30k, so above
// the guard we SKIP it (uniform radius / categorical colour) and flag the encoding
// `scale-limited`. Degree / pagerank / eigenvector / k-core are near-linear and
// stay enabled at any scale. Below the guard, unchanged.
// Radius by size metric, else uniform.
let radii = match self.size_metric {
Some(m) if !(big && m.heavy_at_scale()) => appearance::radii(&m.values(&self.graph)),
_ => vec![6.0; n],
};
// Colour precedence: partition > continuous metric > categorical styling.
let styling = self.styling();
let (colors, color_mode, part_count) = if let Some(p) = self.partition {
let (of, count) = p.assign(&self.graph);
let cols = of.iter().map(|&c| style::wheel(c)).collect();
(cols, format!("partition:{}", p.key()), count)
} else if let Some(m) = self.color_metric {
if big && m.heavy_at_scale() {
// Superlinear colour metric skipped at scale → categorical fallback.
let cols = (0..n)
.map(|i| self.label_override_rgb(&styling, i).unwrap_or_else(|| styling.color(i, [150, 155, 170])))
.collect();
(cols, format!("metric:{} (scale-limited >{ANALYTICS_SCALE_GUARD})", m.key()), styling.categories.len())
} else {
let norm = appearance::normalize(&m.values(&self.graph));
let cols = norm.iter().map(|&t| appearance::ramp(t)).collect();
(cols, format!("metric:{}", m.key()), 0)
}
} else {
// Categorical (ontology-label) colouring — the ontology-palette override wins
// here for pinned labels; un-pinned labels fall back to the wheel/hashed rule.
let cols = (0..n)
.map(|i| self.label_override_rgb(&styling, i).unwrap_or_else(|| styling.color(i, [150, 155, 170])))
.collect();
(cols, format!("style:{}", self.style_key), styling.categories.len())
};
AppearanceResult { radii, colors, color_mode, partition_count: part_count }
}
/// The **node table** as an Arrow `RecordBatch` (`id, label, caption, degree,
/// pagerank, betweenness, community`), row order = `graph.nodes`. Feed it to
/// [`facett_grid::Grid::from_record_batch`](https://docs.rs/facett-grid).
#[must_use]
pub fn node_batch(&self) -> arrow_array::RecordBatch {
table::node_batch(&self.graph)
}
/// The **edge table** as an Arrow `RecordBatch` (`src, dst, type, weight`), row
/// order = `graph.edges`.
#[must_use]
pub fn edge_batch(&self) -> arrow_array::RecordBatch {
table::edge_batch(&self.graph)
}
/// **Two-way sync**: select the node at node-table `row` (the grid → canvas leg).
/// Returns the [`Msg`] to apply, or `None` if `row` is out of range.
#[must_use]
pub fn select_node_row(&self, row: usize) -> Option<Msg> {
self.graph.nodes.get(row).map(|n| Msg::SelectNode(n.id.clone()))
}
/// **Two-way sync**: select the edge at edge-table `row`.
#[must_use]
pub fn select_edge_row(&self, row: usize) -> Option<Msg> {
(row < self.graph.edges.len()).then_some(Msg::SelectEdge(row))
}
/// **Two-way sync**: the node-table row index of the current node selection (the
/// canvas → grid leg), if a node is selected.
#[must_use]
pub fn selected_node_row(&self) -> Option<usize> {
self.selected_node.as_deref().and_then(|id| self.graph.index_of(id))
}
/// **Two-way sync**: the edge-table row index of the current edge selection.
#[must_use]
pub fn selected_edge_row(&self) -> Option<usize> {
self.selected_edge
}
/// **Whole-graph statistics** — the stats panel's scalars: node/edge counts,
/// density, average degree, connected-component count, global modularity (Louvain),
/// average clustering coefficient, transitivity, diameter, and average path length.
#[must_use]
pub fn stats(&self) -> serde_json::Value {
// Structure-only signature (layout-independent) — a structural mutation or
// [`absorb`](Self::absorb) changes it and invalidates the frozen scalars.
let sig = self.structure_sig("stats");
{
let c = self.analytics_cache.0.borrow();
if c.stats_sig == sig && let Some(v) = &c.stats {
return v.clone();
}
}
let v = self.compute_stats();
let mut c = self.analytics_cache.0.borrow_mut();
c.stats_sig = sig;
c.stats = Some(v.clone());
c.stats_computes += 1;
v
}
/// The uncached whole-graph statistics (all-pairs diameter, Louvain modularity,
/// clustering — O(V·E)+). Reached only on a cache miss in [`stats`](Self::stats).
fn compute_stats(&self) -> serde_json::Value {
use facett_graphview::analysis::{components, stats};
let n = self.graph.nodes.len();
let m = self.graph.edges.len();
let edges = self.graph.edge_indices();
let g = Adjacency::from_edges(n, &edges);
// Density of a directed simple graph: m / (n·(n−1)).
let density = if n > 1 { m as f64 / (n as f64 * (n as f64 - 1.0)) } else { 0.0 };
let avg_degree = if n > 0 { 2.0 * m as f64 / n as f64 } else { 0.0 };
let comps = components::connected(&g);
let louvain = facett_graphview::community::louvain(n, &edges);
// ── ANALYTICS SCALE GUARD ──────────────────────────────────────────────────
// `diameter` + `average_path_length` are ALL-PAIRS shortest paths (O(V·E)+),
// single-threaded and brutal at scale. Above the guard drop them (`n/a` → null)
// and keep only the cheap scalars the prompt whitelists (counts / density /
// avg-degree / components / modularity / clustering). Below the guard, unchanged.
let (diameter, avg_path_length) = if n >= ANALYTICS_SCALE_GUARD {
(serde_json::Value::Null, serde_json::Value::Null)
} else {
(serde_json::json!(stats::diameter(&g)), serde_json::json!(stats::average_path_length(&g)))
};
serde_json::json!({
"nodes": n,
"edges": m,
"density": density,
"avg_degree": avg_degree,
"components": comps.count,
"largest_component": comps.largest(),
"modularity": louvain.modularity,
"communities": louvain.count,
"avg_clustering": stats::average_clustering(&g),
"transitivity": stats::transitivity(&g),
"diameter": diameter,
"avg_path_length": avg_path_length,
})
}
/// The weight of edge `i` — its `weight` property parsed as `f32`, else `1.0`.
#[must_use]
pub fn edge_weight(&self, i: usize) -> f32 {
self.graph
.edges
.get(i)
.and_then(|e| e.props.get("weight"))
.and_then(|w| w.parse::<f32>().ok())
.filter(|w| w.is_finite() && *w > 0.0)
.unwrap_or(1.0)
}
/// The **ego-network subgraph**: every node within `radius` undirected hops of
/// `center`, plus the edges induced on that node set. `center` is included at hop 0;
/// an unknown `center` yields an empty graph.
#[must_use]
pub fn subgraph(&self, center: &str, radius: usize) -> PropGraph {
let mut reached: BTreeSet<String> = BTreeSet::new();
if self.graph.node(center).is_some() {
reached.insert(center.to_string());
let mut frontier = vec![center.to_string()];
for _ in 0..radius {
let mut next = Vec::new();
for id in &frontier {
for nb in self.graph.neighbours(id) {
if reached.insert(nb.clone()) {
next.push(nb);
}
}
}
if next.is_empty() {
break;
}
frontier = next;
}
}
let mut sub = PropGraph::new();
for n in &self.graph.nodes {
if reached.contains(&n.id) {
sub.add_node(n.clone());
}
}
for e in &self.graph.edges {
if reached.contains(&e.from) && reached.contains(&e.to) {
sub.add_edge(e.clone());
}
}
sub
}
/// The active extraction as JSON (`Null` when none / nothing selected): the induced
/// ego-network's centre, radius, node ids, and edge count.
#[must_use]
pub fn subgraph_json(&self) -> serde_json::Value {
let (Some(center), Some(radius)) = (self.selected_node.as_deref(), self.subgraph_radius) else {
return serde_json::Value::Null;
};
let sub = self.subgraph(center, radius);
serde_json::json!({
"center": center,
"radius": radius,
"nodes": sub.nodes.iter().map(|n| n.id.clone()).collect::<Vec<_>>(),
"node_count": sub.nodes.len(),
"edge_count": sub.edges.len(),
})
}
/// The **elementary directed cycles** of the graph — each a list of node ids (the
/// closing edge back to the first node implicit), enumerated up to [`CYCLE_LIMIT`].
/// Reuses [`facett_graphview::analysis::cycles::find_cycles`].
#[must_use]
pub fn cycles(&self) -> Vec<Vec<String>> {
// ── ANALYTICS SCALE GUARD ──────────────────────────────────────────────────
// Elementary-cycle enumeration is superlinear (seconds-to-minutes on a dense
// 30k graph, single-threaded). At/above the guard SKIP it entirely — no compute,
// no counter bump — unless the user forced it via `Msg::ForceCycles`. This is the
// primary fix for the single-core load freeze: the render toolbar no longer pays it.
if self.graph.nodes.len() >= ANALYTICS_SCALE_GUARD && !self.analytics_cache.0.borrow().force_cycles {
return Vec::new();
}
// Structure-only signature — a structural mutation or [`absorb`](Self::absorb)
// invalidates the frozen enumeration. `cycle_nodes()` rides this cache too.
// NOT `self.structure_sig`: `build_frame_index` reaches here (via `cycle_nodes`),
// and the frame index cannot be read while it is being built.
let sig = facett_core::barnes_hut::structure_sig("cycles", self.graph.nodes.len(), &self.graph.edge_indices());
{
let c = self.analytics_cache.0.borrow();
if c.cycles_sig == sig && let Some(v) = &c.cycles {
return v.clone();
}
}
let v = self.compute_cycles();
let mut c = self.analytics_cache.0.borrow_mut();
c.cycles_sig = sig;
c.cycles = Some(v.clone());
c.cycles_computes += 1;
v
}
/// The uncached elementary-cycle enumeration (superlinear on dense graphs). Reached
/// only on a cache miss in [`cycles`](Self::cycles).
fn compute_cycles(&self) -> Vec<Vec<String>> {
let g = Adjacency::from_edges(self.graph.nodes.len(), &self.graph.edge_indices());
facett_graphview::analysis::cycles::find_cycles(&g, CYCLE_LIMIT)
.into_iter()
.map(|c| c.into_iter().map(|i| self.graph.nodes[i].id.clone()).collect())
.collect()
}
/// Whether the directed graph is **acyclic** (a DAG) —
/// [`facett_graphview::analysis::cycles::has_cycle`] inverted.
#[must_use]
pub fn is_acyclic(&self) -> bool {
// Structure-keyed like `stats`: `cycles_json` reads this on every `state_json`,
// and rebuilding the adjacency + a DFS was ~150 ms per read at 100 000 nodes.
let sig = self.structure_sig("acyclic");
{
let c = self.analytics_cache.0.borrow();
if let (true, Some(a)) = (c.acyclic_sig == sig, c.acyclic) {
return a;
}
}
let a = {
let fi = self.frame_index();
let g = Adjacency::from_edges(self.graph.nodes.len(), &fi.edge_indices);
!facett_graphview::analysis::cycles::has_cycle(&g)
};
let mut c = self.analytics_cache.0.borrow_mut();
c.acyclic_sig = sig;
c.acyclic = Some(a);
a
}
/// `structure_sig(key, n, edges)` over the FRAME INDEX's resolved edges — the same
/// `(from, to)` list `graph.edge_indices()` returns (see [`FrameIndex`]), without
/// rebuilding a 100 000-key string map to get it. That rebuild was most of a cache
/// HIT in `stats()` (~100 ms per `state_json` at 100 000 nodes, MEASURED 2026-09-29).
fn structure_sig(&self, key: &str) -> u64 {
self.frame_index().sig(key, self.graph.nodes.len())
}
/// The node ids on the currently-highlighted cycle (empty when none / out of range).
fn cycle_nodes(&self) -> BTreeSet<String> {
match self.highlight_cycle {
Some(i) => self.cycles().into_iter().nth(i).unwrap_or_default().into_iter().collect(),
None => BTreeSet::new(),
}
}
/// The **cycle-browser panel** as JSON: acyclicity, the (capped) elementary-cycle
/// count, whether the cap was hit, the highlighted index, and its node ids.
#[must_use]
pub fn cycles_json(&self) -> serde_json::Value {
let cycles = self.cycles();
let count = cycles.len();
let nodes = self.highlight_cycle.and_then(|i| cycles.into_iter().nth(i)).unwrap_or_default();
let mut v = serde_json::json!({
"acyclic": self.is_acyclic(),
"count": count,
"capped": count >= CYCLE_LIMIT,
"highlighted": self.highlight_cycle,
"nodes": nodes,
});
// Above the [`ANALYTICS_SCALE_GUARD`] the enumeration is skipped — advertise the
// "n/a at this scale" affordance. Added ONLY when limited, so below-guard
// `state_json` stays byte-identical (L2 goldens unmoved).
if self.graph.nodes.len() >= ANALYTICS_SCALE_GUARD && !self.analytics_cache.0.borrow().force_cycles {
v["scale_limited"] = serde_json::json!(true);
v["scale_guard"] = serde_json::json!(ANALYTICS_SCALE_GUARD);
}
v
}
/// The **most similar nodes** to `center` by undirected neighbourhood overlap
/// (Jaccard), top `top_k`, as `(id, score)` descending. Reuses
/// [`facett_graphview::analysis::similarity::most_similar`].
#[must_use]
pub fn similar(&self, center: &str, top_k: usize) -> Vec<(String, f32)> {
let Some(ci) = self.graph.index_of(center) else { return Vec::new() };
let g = Adjacency::from_edges(self.graph.nodes.len(), &self.graph.edge_indices());
facett_graphview::analysis::similarity::most_similar(&g, ci, top_k)
.into_iter()
.map(|(i, s)| (self.graph.nodes[i].id.clone(), s))
.collect()
}
/// The **similar-node panel** as JSON (`Null` when inactive / nothing selected): the
/// anchor node id, `k`, and the ranked similar node ids with their Jaccard scores.
#[must_use]
pub fn similarity_json(&self) -> serde_json::Value {
let (Some(center), Some(k)) = (self.selected_node.as_deref(), self.similarity_k) else {
return serde_json::Value::Null;
};
let results = self.similar(center, k);
serde_json::json!({
"center": center,
"k": k,
"count": results.len(),
"results": results.iter().map(|(id, s)| serde_json::json!({ "id": id, "score": s })).collect::<Vec<_>>(),
})
}
/// The recent-query **history** (most-recent last).
#[must_use]
pub fn query_history(&self) -> &[String] {
&self.query_history
}
/// The **saved queries** book (name → query text).
#[must_use]
pub fn saved_queries(&self) -> &BTreeMap<String, String> {
&self.saved_queries
}
/// Reset `visible` to the label-filtered node set.
fn recompute_visible(&mut self) {
self.visible = self
.graph
.nodes
.iter()
.filter(|n| self.filter_label.as_ref().is_none_or(|l| &n.label == l))
.map(|n| n.id.clone())
.collect();
}
/// Resolve the highlighted shortest path (undirected) into node ids.
fn recompute_path(&mut self) {
self.path_nodes.clear();
let Some((a, b)) = self.path_endpoints.clone() else { return };
let (Some(ia), Some(ib)) = (self.graph.index_of(&a), self.graph.index_of(&b)) else { return };
// Undirected search: double every edge so direction doesn't block the path.
let mut edges = self.graph.edge_indices();
let rev: Vec<(usize, usize)> = edges.iter().map(|&(x, y)| (y, x)).collect();
edges.extend(rev);
let g = Adjacency::from_edges(self.graph.nodes.len(), &edges);
if let Some(path) = pathfinding::shortest_path(&g, ia, ib) {
self.path_nodes = path.into_iter().map(|i| self.graph.nodes[i].id.clone()).collect();
}
}
/// The layout positions of every node (indexed like `graph.nodes`).
///
/// **Converge-once-then-freeze:** the result is cached and only recomputed when the
/// structural signature `(layout, node count, edges)` changes. This is called in
/// the render path every frame, so without the cache the (now Barnes–Hut, O(n log n))
/// force layout would re-run on every paint — the freeze is what makes a
/// 30 000-node graph paint at frame rate. A structural change (node/edge mutation,
/// [`absorb`](Self::absorb), a layout switch) invalidates it automatically via the
/// signature.
#[must_use]
pub fn positions(&self) -> Vec<[f32; 2]> {
let n = self.graph.nodes.len();
let fi = self.frame_index();
let edges = &fi.edge_indices;
let sig = fi.sig(self.layout_kind.key(), n);
{
let c = self.layout_cache.0.borrow();
if c.sig == sig && c.pos.len() == n {
return c.pos.clone();
}
}
#[cfg(feature = "gpu")]
if let Some(pos) = self.positions_via_host_gpu(sig, n, edges) {
return pos;
}
let pos = layout::layout_with(self.layout_kind, n, edges, &self.places);
let mut c = self.layout_cache.0.borrow_mut();
c.sig = sig;
c.pos = pos.clone();
c.lane = "cpu";
pos
}
/// **The resident GPU cloud** for a graph above [`SCALE_NODES`]: every visible
/// node and edge lives on the GPU, uploaded when the model, the layout or the
/// colouring changes, and each frame sends only the 48-byte camera. `false` when
/// the cloud is off or no renderer is installed — the CPU painter then draws, as
/// with the per-frame lane.
///
/// The per-frame lane rebuilds and re-uploads one instance per node and edge every
/// frame — 12 MB at 100 000 nodes and 200 000 edges, and the CPU loop that builds
/// it. Here a drag costs the GPU a redraw and the CPU nothing per node. The price:
/// one disc radius for the whole cloud (the appearance radius of the first nodes),
/// and edges coloured by their tail node, as in the 3-D cloud.
#[cfg(feature = "wgpu")]
#[allow(clippy::too_many_arguments)]
fn draw_resident_cloud(
&self,
ui: &egui::Ui,
rect: egui::Rect,
fi: &FrameIndex,
positions: &[[f32; 2]],
appear: &AppearanceResult,
center: egui::Pos2,
scale: f32,
zoom: f32,
pan: egui::Vec2,
) -> bool {
use facett_core::render::gpu::graphcloud::{cloud, CloudCamera, CloudEdge, CloudPoint};
if !self.legibility.gpu_cloud || !cloud::cloud_renderer_installed() {
return false;
}
let n = positions.len().min(fi.visible.len());
// The model generation: what the uploaded points are a picture of.
let generation = {
let mut h = std::collections::hash_map::DefaultHasher::new();
fi.key.version.hash(&mut h);
fi.key.nodes.hash(&mut h);
fi.key.edges.hash(&mut h);
{
let c = self.layout_cache.0.borrow();
c.sig.hash(&mut h);
c.lane.hash(&mut h);
}
self.layout_pending().hash(&mut h);
self.analytics_cache.0.borrow().appearance_sig.hash(&mut h);
h.finish() | 1
};
// Re-send when another pane replaced the ONE resident model too (a tab switch
// between two navigators at scale), not only when this pane's model moved.
let upload = self.frame_cache.uploaded.get() != generation || cloud::resident_generation() != generation;
let model = upload.then(|| {
let mut remap = vec![u32::MAX; n];
let mut pts: Vec<CloudPoint> = Vec::with_capacity(n);
for i in 0..n {
if fi.visible[i] {
remap[i] = pts.len() as u32;
let [r, g, b] = appear.colors.get(i).copied().unwrap_or([150, 155, 170]);
let p = positions[i];
// The cloud's projection is `centre + (x, −y) · scale`; the canvas's is
// `centre + (x, y) · scale`, so y goes in negated.
pts.push(CloudPoint::new([p[0], -p[1], 0.0], Color32::from_rgb(r, g, b)));
}
}
let edges: Vec<CloudEdge> = fi
.edge_pairs
.iter()
.filter(|&&(a, b)| a != u32::MAX && (a as usize) < n && (b as usize) < n)
.map(|&(a, b)| [remap[a as usize], remap[b as usize]])
.collect();
(pts, edges)
});
let ppp = ui.ctx().pixels_per_point();
let c = (center - rect.min + pan * scale) * ppp;
let head = appear.radii.len().clamp(1, 1024);
let radius = appear.radii.iter().take(head).sum::<f32>() / head as f32;
let cam = CloudCamera {
viewport: [rect.width() * ppp, rect.height() * ppp, c.x, c.y],
// yaw 0 (a plane), world→px scale, emissive peak, disc radius over the
// shader's 5.5 px base.
cam: [0.0, zoom * scale * ppp, 2.5, (radius.max(1.0) * ppp) / 5.5],
// half-width px, edge radiance gain
edge: [0.6 * ppp, 0.6, 0.0, 0.0],
};
let drew = cloud::draw_cloud_model(ui, rect, generation, model, cam);
if drew && upload {
self.frame_cache.uploaded.set(generation);
}
drew
}
#[cfg(not(feature = "wgpu"))]
#[allow(clippy::too_many_arguments, clippy::unused_self)]
fn draw_resident_cloud(
&self,
_ui: &egui::Ui,
_rect: egui::Rect,
_fi: &FrameIndex,
_positions: &[[f32; 2]],
_appear: &AppearanceResult,
_center: egui::Pos2,
_scale: f32,
_zoom: f32,
_pan: egui::Vec2,
) -> bool {
false
}
/// **The non-blocking GPU lane** — `Some(positions)` when this layout is being (or
/// was just) laid out on the HOST's borrowed device, `None` to take the CPU lane.
///
/// Taken whenever the layout resolves to force-directed, the graph has nodes, and a
/// host has lent a device. There is no size floor: the GPU ruling (owner, 2026-09-28)
/// sends GPU-able work to the GPU, and a small-graph floor (`BH_THRESHOLD`, until
/// 2026-09-29) left every gallery-sized graphnav and lineage in the browser reading
/// `layout_lane: "cpu"` on a Radeon 890M (lane A, t14s). A host that lent a device (`gpu_layout::install_host_device`). No device
/// installed — every native host today, every test — and this returns `None` before
/// touching anything, so the CPU lane and its goldens are exactly as they were.
///
/// While the job runs this returns a cheap GRID placeholder and does NOT settle the
/// cache, so [`layout_settled`](Self::layout_settled) stays `false` and
/// [`layout_pending`](Self::layout_pending) tells the painter to keep repainting.
/// On wasm32 that is the difference between a graph that appears a few frames late
/// and a tab frozen for the length of a single-threaded Barnes–Hut converge.
#[cfg(feature = "gpu")]
fn positions_via_host_gpu(&self, sig: u64, n: usize, edges: &[(usize, usize)]) -> Option<Vec<[f32; 2]>> {
use facett_graphview::gpu_layout::{self, JobState, LayoutJob};
let force = match self.layout_kind {
LayoutKind::Force => true,
LayoutKind::Geographic => !layout::places_cover(n, &self.places),
_ => false,
};
if !force || n == 0 || !gpu_layout::host_device_installed() {
return None;
}
let mut c = self.layout_cache.0.borrow_mut();
if c.job.failed_sig == Some(sig) {
return None;
}
if c.job.job.is_none() || c.job.sig != sig {
let job = gpu_layout::with_host_device(|d, _| LayoutJob::start(d, n, edges, layout::FORCE_ITERS_GPU))?;
c.job.sig = sig;
c.job.kernel = job.kernel();
c.job.job = Some(Box::new(job));
c.job.placeholder = layout::layout(LayoutKind::Grid, n, edges);
}
let state = {
let job = c.job.job.as_mut()?;
gpu_layout::with_host_device(|d, q| job.poll(d, q))?
};
match state {
JobState::Pending => Some(c.job.placeholder.clone()),
JobState::Ready(pos) => {
c.job.job = None;
c.job.placeholder = Vec::new();
c.sig = sig;
c.pos = pos.clone();
c.lane = "gpu-job";
Some(pos)
}
JobState::Failed(why) => {
c.job.job = None;
c.job.placeholder = Vec::new();
c.job.failed_sig = Some(sig);
c.job.failed_why = why;
None
}
}
}
/// Whether a non-blocking GPU layout is in flight — the painter requests a repaint
/// while this holds, because a job only advances when it is polled. Always `false`
/// without the `gpu` feature.
#[must_use]
pub fn layout_pending(&self) -> bool {
#[cfg(feature = "gpu")]
{
self.layout_cache.0.borrow().job.job.is_some()
}
#[cfg(not(feature = "gpu"))]
{
false
}
}
/// Why the GPU layout job fell back to the CPU lane — `""` when it did not. The
/// other half of [`layout_lane`](Self::layout_lane): `"cpu"` alone cannot tell "the
/// GPU lane was never eligible" from "it was tried and failed", and those need
/// opposite fixes.
/// Which GPU repulsion kernel laid (or is laying) the graph out: `"grid"` above
/// `facett_graphview::gpu_layout::GRID_MIN_NODES`, `"all-pairs"` below, `""` when no
/// GPU job ran.
#[must_use]
pub fn layout_kernel(&self) -> &'static str {
#[cfg(feature = "gpu")]
{
self.layout_cache.0.borrow().job.kernel
}
#[cfg(not(feature = "gpu"))]
{
""
}
}
#[must_use]
pub fn layout_fallback(&self) -> &'static str {
#[cfg(feature = "gpu")]
{
self.layout_cache.0.borrow().job.failed_why
}
#[cfg(not(feature = "gpu"))]
{
""
}
}
/// What the last painted frame's legibility work did (the `legibility.frame` of
/// [`state_json`](facett_core::Facet::state_json)), without building the rest of the
/// state — at 100 000 nodes the full state is 100 000 JSON objects.
#[must_use]
pub fn legibility_frame_json(&self) -> serde_json::Value {
self.legibility_cache.0.borrow().1.state_json()
}
/// Which lane produced the settled layout: `"cpu"`, `"gpu-job"`, or `""` if nothing
/// has settled yet. A READOUT — so a robot in a browser can assert the GPU lane ran
/// instead of inferring it from how the bundle was compiled.
#[must_use]
pub fn layout_lane(&self) -> &'static str {
self.layout_cache.0.borrow().lane
}
/// Whether [`positions`](Self::positions) is **settled** (the next call is a cache
/// hit — a no-op relayout) for the current graph + layout. A host `tick` can assert
/// this to know the force sim has frozen and needs no further work.
#[must_use]
pub fn layout_settled(&self) -> bool {
let n = self.graph.nodes.len();
let fi = self.frame_index();
let sig = fi.sig(self.layout_kind.key(), n);
let c = self.layout_cache.0.borrow();
c.sig == sig && c.pos.len() == n
}
/// TEST HOOK: how many times each expensive analytic actually RAN — `(stats, cycles,
/// appearance)`. A cache hit does not bump these; the freeze tests assert they stay
/// flat across repeated calls for an unchanged graph and step exactly once on a
/// signature change.
#[cfg(test)]
fn analytics_computes(&self) -> (u64, u64, u64) {
let c = self.analytics_cache.0.borrow();
(c.stats_computes, c.cycles_computes, c.appearance_computes)
}
/// **Incremental absorb** — grow the graph by `nodes` + `edges` while KEEPING every
/// existing node's position, seeding each new node at its already-placed
/// neighbours' centroid and relaxing only a few LOCAL force iterations. The frozen
/// positions are written straight into the layout cache, so a consumer (korp's
/// `sync_graph_nav`) can stream nodes into the scene WITHOUT the full O(n log n)
/// rebuild `::new` would do.
///
/// For the deterministic layouts (grid/circular/hierarchical/radial) there is no
/// incremental state to preserve — the cache is simply invalidated and the next
/// [`positions`](Self::positions) recomputes the (cheap, O(n+e)) placement. The
/// incremental seed-and-relax path applies to [`LayoutKind::Force`].
pub fn absorb(&mut self, nodes: Vec<Node>, edges: Vec<Edge>) {
if nodes.is_empty() && edges.is_empty() {
return;
}
self.touch();
// Snapshot the current (frozen) positions before the graph grows.
let old_pos = self.positions();
let old_n = self.graph.nodes.len();
for node in nodes {
self.graph.nodes.push(node);
}
for edge in edges {
self.graph.edges.push(edge);
}
let new_n = self.graph.nodes.len();
let eidx = self.graph.edge_indices();
if self.layout_kind != LayoutKind::Force || new_n <= old_n {
// Deterministic layout (or no new nodes): drop the cache, recompute lazily.
let mut c = self.layout_cache.0.borrow_mut();
c.sig = 0;
c.pos.clear();
return;
}
// Seed the new nodes near their already-placed neighbours (centroid), falling
// back to a small deterministic ring around the graph centroid when a new node
// has no placed neighbour yet.
let mut pos = old_pos;
pos.resize(new_n, [0.0, 0.0]);
let centroid = {
let mut c = [0.0f32; 2];
if old_n > 0 {
for p in &pos[..old_n] {
c[0] += p[0];
c[1] += p[1];
}
c[0] /= old_n as f32;
c[1] /= old_n as f32;
}
c
};
for i in old_n..new_n {
let mut sum = [0.0f32; 2];
let mut cnt = 0.0f32;
for &(a, b) in &eidx {
let other = if a == i && b < i {
Some(b)
} else if b == i && a < i {
Some(a)
} else {
None
};
if let Some(o) = other {
sum[0] += pos[o][0];
sum[1] += pos[o][1];
cnt += 1.0;
}
}
if cnt > 0.0 {
// Neighbour centroid + a tiny deterministic jitter so coincident seeds separate.
let j = (i as f32 * 12.9898).sin() * 0.01;
pos[i] = [sum[0] / cnt + j, sum[1] / cnt + j];
} else {
let a = std::f32::consts::TAU * (i - old_n) as f32 / (new_n - old_n).max(1) as f32;
pos[i] = [centroid[0] + 0.05 * a.cos(), centroid[1] + 0.05 * a.sin()];
}
}
// Relax only the new nodes (existing layout frozen), then freeze into the cache.
let k = (4.0 / new_n as f32).sqrt();
facett_core::barnes_hut::relax_new::<2>(&mut pos, &eidx, old_n, k, facett_core::barnes_hut::BH_THETA, 12, 0.05);
let sig = facett_core::barnes_hut::structure_sig(self.layout_kind.key(), new_n, &eidx);
// ── L4 functional-status: the incremental absorb path RAN, keeping old nodes ──
#[cfg(feature = "testmatrix")]
{
let frozen_ok = pos.iter().take(old_n).all(|p| p[0].is_finite() && p[1].is_finite());
let new_ok = pos[old_n..].iter().all(|p| p[0].is_finite() && p[1].is_finite());
facett_core::testmatrix::emit(
"facett-graphnav::GraphNav::absorb",
"incremental_absorb",
frozen_ok && new_ok,
&format!("kept={old_n} added={} layout={}", new_n - old_n, self.layout_kind.key()),
);
}
let mut c = self.layout_cache.0.borrow_mut();
c.sig = sig;
c.pos = pos;
}
/// The current [`Styling`] over the graph.
#[must_use]
pub fn styling(&self) -> Styling {
style::compute(&self.graph, &self.style_by())
}
/// **Export** the current graph as `fmt`. JSON is the full property graph; DOT is a
/// Graphviz digraph; CSV is a node list + an edge list.
#[must_use]
pub fn export(&self, fmt: ExportFormat) -> String {
match fmt {
ExportFormat::Json => serde_json::to_string_pretty(&self.graph).unwrap_or_default(),
ExportFormat::Dot => {
let mut s = String::from("digraph G {\n");
for n in &self.graph.nodes {
s.push_str(&format!(" \"{}\" [label=\"{}\"];\n", n.id, n.caption()));
}
for e in &self.graph.edges {
s.push_str(&format!(" \"{}\" -> \"{}\" [label=\"{}\"];\n", e.from, e.to, e.etype));
}
s.push_str("}\n");
s
}
ExportFormat::Csv => {
let mut s = String::from("# nodes\nid,label\n");
for n in &self.graph.nodes {
s.push_str(&format!("{},{}\n", n.id, n.label));
}
s.push_str("# edges\nfrom,to,type\n");
for e in &self.graph.edges {
s.push_str(&format!("{},{},{}\n", e.from, e.to, e.etype));
}
s
}
ExportFormat::Gexf => io::to_gexf(&self.graph, &self.metric_columns()),
ExportFormat::GraphMl => io::to_graphml(&self.graph, &self.metric_columns()),
}
}
/// The computed-metric attribute columns exported into GEXF/GraphML attvalues:
/// degree / PageRank / betweenness / Louvain community, one string value per node.
#[must_use]
fn metric_columns(&self) -> Vec<io::ExtraColumn<'static>> {
let fmt = |v: &[f32]| v.iter().map(|x| format!("{x:.6}")).collect::<Vec<_>>();
let (community, _) = Partition::Louvain.assign(&self.graph);
vec![
("degree", fmt(&Metric::Degree.values(&self.graph))),
("pagerank", fmt(&Metric::PageRank.values(&self.graph))),
("betweenness", fmt(&Metric::Betweenness.values(&self.graph))),
("community", community.iter().map(|c| c.to_string()).collect()),
]
}
/// **Import** a graph from a GEXF/GraphML/JSON document into a fresh navigator.
/// (DOT/CSV import is not supported — Gephi's front door is GEXF/GraphML.)
///
/// # Errors
/// Returns `Err` if the document can't be parsed into a graph, or `fmt` is a
/// write-only format (DOT/CSV).
pub fn import(title: impl Into<String>, fmt: ExportFormat, text: &str) -> Result<GraphNav, String> {
let graph = match fmt {
ExportFormat::Gexf => io::from_gexf(text)?,
ExportFormat::GraphMl => io::from_graphml(text)?,
ExportFormat::Json => serde_json::from_str(text).map_err(|e| e.to_string())?,
ExportFormat::Dot | ExportFormat::Csv => {
return Err(format!("import from {} is not supported", fmt.key()));
}
};
Ok(GraphNav::new(title, graph))
}
/// The selected element as JSON (node props / edge endpoints) — the inspector panel.
fn inspector_json(&self) -> serde_json::Value {
if let Some(id) = &self.selected_node && let Some(n) = self.graph.node(id) {
return serde_json::json!({
"kind": "node",
"id": n.id,
"label": n.label,
"caption": n.caption(),
"props": n.props,
"degree": self.graph.neighbours(id).len(),
});
}
if let Some(i) = self.selected_edge && let Some(e) = self.graph.edges.get(i) {
return serde_json::json!({
"kind": "edge",
"index": i,
"from": e.from,
"to": e.to,
"type": e.etype,
"props": e.props,
});
}
serde_json::Value::Null
}
}
/// Parse a [`StyleBy`] from its key form.
fn parse_style(key: &str) -> StyleBy {
match key {
"none" => StyleBy::None,
"label" => StyleBy::Label,
other => other.strip_prefix("prop:").map(|p| StyleBy::Property(p.to_string())).unwrap_or(StyleBy::Label),
}
}
impl Facet for GraphNav {
fn title(&self) -> &str {
&self.title
}
fn caps(&self) -> FacetCaps {
FacetCaps::NONE.themeable().selectable().resizable()
}
fn kind(&self) -> &'static str {
"graphnav"
}
fn ui(&mut self, ui: &mut egui::Ui) {
facett_core::navgraph::declare_own_draw_order(ui); // atoms follow the data order (navgraph §9)
for m in self.render(ui) {
self.update(m);
}
}
fn selection_json(&self) -> serde_json::Value {
self.inspector_json()
}
fn state_json(&self) -> serde_json::Value {
let positions = self.positions();
let styling = self.styling();
let appear = self.appearance();
let schema = self.frame_index().schema.clone().unwrap_or_else(|| self.graph.schema());
let matches = self.search_matches();
let bounds = layout::bounds(&positions);
let cycle_set = self.cycle_nodes();
let similar_set: BTreeSet<String> = match (self.similarity_k, self.selected_node.as_deref()) {
(Some(k), Some(c)) => self.similar(c, k).into_iter().map(|(id, _)| id).collect(),
_ => BTreeSet::new(),
};
let canvas_nodes: Vec<serde_json::Value> = self
.graph
.nodes
.iter()
.enumerate()
.filter(|(_, n)| self.visible.contains(&n.id))
.map(|(i, n)| {
serde_json::json!({
"id": n.id,
"label": n.label,
"x": positions[i][0],
"y": positions[i][1],
"color": appear.colors[i],
"radius": appear.radii[i],
"on_path": self.path_nodes.contains(&n.id),
"matched": matches.contains(&n.id),
"on_cycle": cycle_set.contains(&n.id),
"similar": similar_set.contains(&n.id),
})
})
.collect();
// Chrome layout: the fold state + the rect the canvas actually claimed last frame.
// `dominant_frac` = canvas height / viewport height — the canvas-first proof (≈1.0
// when folded so the graph dominates; the RED-when-broken test asserts a large
// fraction, which the old toolbar-stacked layout could never satisfy).
let cm = self.chrome_cache.0.get();
let dominant_frac = if cm.view[1] > 0.0 { cm.canvas[3] / cm.view[1] } else { 0.0 };
serde_json::json!({
"title": self.title,
"chrome": {
"settings_open": self.settings_open,
"canvas": {
"x": cm.canvas[0],
"y": cm.canvas[1],
"w": cm.canvas[2],
"h": cm.canvas[3],
},
"view": { "w": cm.view[0], "h": cm.view[1] },
"dominant_frac": dominant_frac,
},
// What the last painted frame's legibility work did, as DATA: how many
// labels were drawn vs suppressed, how much edge ink was budgeted away, and
// — the pointer-cost witness — how many nodes one hover probe actually
// distance-tested. The pre-index behaviour reported the whole node count.
"legibility": {
"opts": {
"thin_labels": self.legibility.thin_labels,
"thin_edges": self.legibility.thin_edges,
"gpu_cloud": self.legibility.gpu_cloud,
},
"frame": self.legibility_cache.0.borrow().1.state_json(),
},
"query": {
"text": self.query_text,
"kind": self.result_kind,
"result_nodes": self.result_nodes.len(),
"result_edges": self.result_edges.len(),
"error": self.result_error,
},
"canvas": {
"layout": self.layout_kind.key(),
// Which lane laid this out ("cpu" | "gpu-job"), and whether a
// non-blocking GPU job is still in flight. The wasm wheel compiles a
// GPU layout in; this is the only way to ask, from a browser, whether
// it actually RAN — a feature flag says it could have.
"layout_lane": self.layout_lane(),
"layout_pending": self.layout_pending(),
"layout_fallback": self.layout_fallback(),
"layout_kernel": self.layout_kernel(),
"visible_count": self.visible.len(),
"total_nodes": self.graph.nodes.len(),
"total_edges": self.graph.edges.len(),
"nodes": canvas_nodes,
},
"camera": {
"pan": [self.camera.pan.x, self.camera.pan.y],
"zoom": self.camera.zoom,
},
"appearance": {
"size_by": self.size_metric.map(|m| m.key()),
"color_metric": self.color_metric.map(|m| m.key()),
"partition": self.partition.map(|p| p.key()),
"color_mode": appear.color_mode,
"partition_count": appear.partition_count,
"metrics": Metric::ALL.iter().map(|m| m.key()).collect::<Vec<_>>(),
"partitions": Partition::ALL.iter().map(|p| p.key()).collect::<Vec<_>>(),
},
"layout": {
"current": self.layout_kind.key(),
// What the switcher OFFERS, which is the switcher's own roster plus the
// data-gated layouts this graph can actually be put into.
"options": LayoutKind::EVERY
.iter()
.filter(|l| !l.needs_places() || self.has_places())
.map(|l| l.key())
.collect::<Vec<_>>(),
// Does every node carry a place? The one predicate the switcher uses.
"has_places": self.has_places(),
"placed_nodes": self.places.iter().filter(|p| p.is_some()).count(),
},
"inspector": self.inspector_json(),
"stats": self.stats(),
"table": {
"node_columns": table::node_schema().fields().iter().map(|f| f.name().clone()).collect::<Vec<_>>(),
"node_rows": self.graph.nodes.len(),
"edge_columns": table::edge_schema().fields().iter().map(|f| f.name().clone()).collect::<Vec<_>>(),
"edge_rows": self.graph.edges.len(),
"selected_node_row": self.selected_node_row(),
"selected_edge_row": self.selected_edge_row(),
},
"style": {
"by": self.style_key,
"categories": styling.categories,
},
"search": {
"text": self.search_text,
"match_count": matches.len(),
"matches": matches,
},
"history": {
"recent": self.query_history,
"count": self.query_history.len(),
"saved": self.saved_queries,
},
"subgraph": self.subgraph_json(),
"cycles": self.cycles_json(),
"similarity": self.similarity_json(),
"filter": { "label": self.filter_label },
"path": {
"from": self.path_endpoints.as_ref().map(|(a, _)| a.clone()),
"to": self.path_endpoints.as_ref().map(|(_, b)| b.clone()),
"nodes": self.path_nodes,
"length": self.path_nodes.len().saturating_sub(1),
},
"schema": {
"node_labels": schema.node_labels,
"edge_types": schema.edge_types,
"triples": schema.triples.iter().map(|t| format!("{}-[{}]->{}", t.from, t.etype, t.to)).collect::<Vec<_>>(),
},
"minimap": bounds.map(|(x0, y0, x1, y1)| serde_json::json!({ "min": [x0, y0], "max": [x1, y1] })),
"export": {
"formats": ExportFormat::ALL.iter().map(|f| f.key()).collect::<Vec<_>>(),
"last": self.last_export.map(|f| f.key()),
},
})
}
}
// ── Elm bridge (FC-2 / FC-9) ─────────────────────────────────────────────────
impl facett_core::Elm for GraphNav {
type Model = GraphNav;
type Msg = Msg;
type Effect = ();
fn title(&self) -> &str {
&self.title
}
fn state(&self) -> &GraphNav {
self
}
fn update(&mut self, msg: Msg) -> Vec<()> {
GraphNav::update(self, msg);
Vec::new()
}
fn view(&self, ui: &mut egui::Ui) -> Vec<Msg> {
self.render(ui)
}
}
impl GraphNav {
/// **The pure view** (FC-9): paint the navigator + return the frame's [`Msg`]s.
pub fn render(&self, ui: &mut egui::Ui) -> Vec<Msg> {
let mut msgs = Vec::new();
let th = theme(ui);
// The viewport handed to this frame, captured BEFORE any panel bites into it — the
// denominator of the canvas-dominance proof recorded into `chrome_cache` below.
let view = ui.available_size();
let chrome_id = ui.id().with("graphnav_chrome");
// ── CHROME (top panel) ────────────────────────────────────────────────────────
// The always-visible query/search bar plus a FOLDED-BY-DEFAULT ⚙ settings surface.
// Canvas-first layout: the chrome takes only what it needs off the TOP; the graph
// canvas claims the whole CentralPanel below and can never be pushed off-screen by a
// growing stack of controls.
egui::Panel::top(chrome_id).show(ui, |ui| {
// ── query bar (primary, always visible) ──────────────────────────────
ui.horizontal_wrapped(|ui| {
let mut q = self.query_text.clone();
// The query-bar SAMPLE is Cypher-only ([`QUERY_HINT`]) — never a Gremlin
// `g.V()`, which FalkorDB cannot run.
let te = ui.add(egui::TextEdit::singleline(&mut q).hint_text(QUERY_HINT).desired_width(240.0));
if te.changed() {
msgs.push(Msg::SetQuery(q));
}
if ui.button("Run").clicked() {
msgs.push(Msg::RunQuery);
}
ui.separator();
let mut s = self.search_text.clone();
if ui.add(egui::TextEdit::singleline(&mut s).hint_text("search").desired_width(120.0)).changed() {
msgs.push(Msg::SetSearch(s));
}
});
// ── ⚙ FOLDABLE settings: modes & look + analysis (FOLDED BY DEFAULT) ─────────────
// Reuses egui's own `CollapsingHeader` (L5 — no hand-rolled fold widget), driven by
// `self.settings_open` so the fold state is observable + robot-addressable via
// `Msg::ToggleSettings`. When folded it is just this one small ⚙ header row, so the
// canvas dominates on open. The content wraps horizontally (proportional to the X
// width, never a square box) and is height-capped by a `ScrollArea` so that even
// fully expanded the chrome cannot devour the canvas.
let settings = egui::CollapsingHeader::new(egui::RichText::new("⚙ modes & look").color(th.text_dim))
.id_salt(chrome_id.with("settings"))
.open(Some(self.settings_open))
.show(ui, |ui| {
egui::ScrollArea::vertical().max_height((view.y * 0.42).max(120.0)).show(ui, |ui| {
// ── layout switcher + style + export ─────────────────────────────────
ui.horizontal_wrapped(|ui| {
ui.label(egui::RichText::new("layout:").color(th.text_dim));
// The switcher's own roster, PLUS the data-gated ones this graph can
// actually be put into. `geographic` appears only when every node carries a
// place — a chip that draws a hairball when clicked would be a lie.
for k in LayoutKind::EVERY
.into_iter()
.filter(|k| !k.needs_places() || self.has_places())
{
if ui.selectable_label(self.layout_kind == k, k.key()).clicked() {
msgs.push(Msg::SetLayout(k));
}
}
ui.separator();
ui.label(egui::RichText::new("color:").color(th.text_dim));
for (lbl, by) in [("none", StyleBy::None), ("label", StyleBy::Label), ("age", StyleBy::Property("age".into()))] {
if ui.selectable_label(self.style_by() == by, lbl).clicked() {
msgs.push(Msg::SetStyle(by));
}
}
ui.separator();
if ui.button("⊙ fit").on_hover_text("Fit the whole graph to view").clicked() {
msgs.push(Msg::FitView);
}
if ui.add_enabled(self.selected_node.is_some(), egui::Button::new("⊹ focus")).clicked() {
msgs.push(Msg::ZoomToSelection);
}
ui.separator();
for f in ExportFormat::ALL {
if ui.button(format!("⭳{}", f.key())).clicked() {
msgs.push(Msg::Export(f));
}
}
});
// ── appearance: size-by / colour-by-metric / colour-by-partition ─────
ui.horizontal_wrapped(|ui| {
ui.label(egui::RichText::new("size:").color(th.text_dim));
if ui.selectable_label(self.size_metric.is_none(), "•").clicked() {
msgs.push(Msg::SetSizeBy(None));
}
for m in Metric::ALL {
if ui.selectable_label(self.size_metric == Some(m), m.key()).clicked() {
msgs.push(Msg::SetSizeBy(Some(m)));
}
}
ui.separator();
ui.label(egui::RichText::new("ramp:").color(th.text_dim));
if ui.selectable_label(self.color_metric.is_none() && self.partition.is_none(), "•").clicked() {
msgs.push(Msg::SetColorMetric(None));
msgs.push(Msg::SetPartition(None));
}
for m in Metric::ALL {
if ui.selectable_label(self.color_metric == Some(m), m.key()).clicked() {
msgs.push(Msg::SetColorMetric(Some(m)));
msgs.push(Msg::SetPartition(None));
}
}
ui.separator();
ui.label(egui::RichText::new("partition:").color(th.text_dim));
for p in Partition::ALL {
if ui.selectable_label(self.partition == Some(p), p.key()).clicked() {
msgs.push(Msg::SetPartition(Some(p)));
msgs.push(Msg::SetColorMetric(None));
}
}
});
// ── analysis toolbox: cycle browser (panel-gated) + similar-to-selection ──
// The cycle browser lives in a collapsing panel so `self.cycles()` — superlinear
// enumeration — runs ONLY when the user opens it, never every frame (the primary
// load-freeze fix). Above ANALYTICS_SCALE_GUARD even opening it shows an "n/a at
// this scale" affordance with an explicit *compute anyway* opt-in, rather than
// enumerating; below the guard it browses exactly as before.
let scale_limited_cycles =
self.graph.nodes.len() >= ANALYTICS_SCALE_GUARD && !self.analytics_cache.0.borrow().force_cycles;
ui.collapsing("🔄 cycles", |ui| {
if scale_limited_cycles {
ui.horizontal_wrapped(|ui| {
ui.label(
egui::RichText::new(format!("n/a at this scale (>{ANALYTICS_SCALE_GUARD} nodes)"))
.color(th.text_dim)
.monospace(),
);
if ui
.button("compute anyway")
.on_hover_text("Enumerate elementary cycles — superlinear, may stall on a large graph")
.clicked()
{
msgs.push(Msg::ForceCycles);
}
});
return;
}
ui.horizontal_wrapped(|ui| {
let cycles = self.cycles();
if ui.selectable_label(self.highlight_cycle.is_none(), "•").clicked() {
msgs.push(Msg::HighlightCycle(None));
}
if cycles.is_empty() {
ui.label(egui::RichText::new("(acyclic)").color(th.text_dim).monospace());
} else {
for i in 0..cycles.len().min(8) {
if ui.selectable_label(self.highlight_cycle == Some(i), format!("{}", i + 1)).clicked() {
msgs.push(Msg::HighlightCycle(Some(i)));
}
}
}
});
});
ui.horizontal_wrapped(|ui| {
ui.label(egui::RichText::new("similar:").color(th.text_dim));
let has_sel = self.selected_node.is_some();
if ui
.add_enabled(has_sel, egui::Button::new(format!("≈ top-{SIMILAR_TOP_K}")))
.on_hover_text("Nodes most similar to the selection (neighbourhood overlap)")
.clicked()
{
msgs.push(Msg::FindSimilar(SIMILAR_TOP_K));
}
if ui.add_enabled(self.similarity_k.is_some(), egui::Button::new("clear")).clicked() {
msgs.push(Msg::ClearSimilar);
}
});
// ── stats panel — whole-graph scalars ────────────────────────────────
ui.collapsing("📊 stats", |ui| {
let s = self.stats();
let f = |k: &str| s[k].as_f64().unwrap_or(0.0);
// Above ANALYTICS_SCALE_GUARD the all-pairs diameter / avg-path are `null`
// (skipped) — render them as "n/a" instead of a bogus 0.
let diameter = s["diameter"].as_u64().map_or_else(|| "n/a".to_string(), |d| d.to_string());
let avg_path =
s["avg_path_length"].as_f64().map_or_else(|| "n/a".to_string(), |a| format!("{a:.2}"));
ui.label(
egui::RichText::new(format!(
"nodes {} · edges {} · density {:.3} · avg-deg {:.2} · components {} · modularity {:.3} · clustering {:.3} · diameter {diameter} · avg-path {avg_path}",
s["nodes"].as_u64().unwrap_or(0),
s["edges"].as_u64().unwrap_or(0),
f("density"),
f("avg_degree"),
s["components"].as_u64().unwrap_or(0),
f("modularity"),
f("avg_clustering"),
))
.color(th.text_dim)
.monospace(),
);
});
}); // settings ScrollArea
}); // ⚙ settings CollapsingHeader
// Clicking the ⚙ header toggles the fold through the Msg surface (the state lives on
// the model, so `.open(Some(..))` fully drives visibility — robot-addressable).
if settings.header_response.clicked() {
msgs.push(Msg::ToggleSettings);
}
}); // TopBottomPanel (chrome)
// ── CANVAS (central panel) — THE MAIN ATTRACTION ──────────────────────────────────
// The graph fills the entire remaining rect. It claims `ui.available_size()` INSIDE
// the CentralPanel, so it is always fully visible + pannable/draggable no matter how
// much chrome sits above; it is never an appended row after unbounded content.
egui::CentralPanel::default().show(ui, |ui| {
// ── canvas ───────────────────────────────────────────────────────────
let positions = self.positions();
// A non-blocking GPU layout only advances when it is polled, and it is polled
// from `positions()`. Without this an idle page would show the grid placeholder
// until the pointer moved.
if self.layout_pending() {
ui.ctx().request_repaint();
}
let appear = self.appearance();
// The per-model flat arrays (visible / path / matched / cycle / similar flags,
// resolved edges, adjacency, weights) — rebuilt when the model moves, not per
// frame (see `FrameIndex`).
let fi = self.frame_index();
let n_nodes = self.graph.nodes.len();
let (rect, resp) = ui.allocate_exact_size(ui.available_size().max(vec2(360.0, 300.0)), Sense::click_and_drag());
// Canvas-dominance telemetry: what the canvas actually claimed vs the frame viewport.
// `state_json["chrome"]["canvas"]` reads this back so the robot proves the graph — not
// the toolbar — owns the dominant area (RED if the chrome ever squeezes it low again).
self.chrome_cache.0.set(ChromeMetrics {
canvas: [rect.min.x, rect.min.y, rect.width(), rect.height()],
view: [view.x, view.y],
});
let painter = ui.painter_at(rect);
painter.rect_filled(rect, CornerRadius::ZERO, th.bg);
let center = rect.center();
let scale = rect.size().min_elem() * 0.44;
// Camera: pan is in world units, zoom multiplies. screen = center + (w·zoom + pan)·scale.
let zoom = self.camera.zoom.max(0.01);
let cam_pan = self.camera.pan;
let project = |p: [f32; 2]| center + (vec2(p[0], p[1]) * zoom + cam_pan) * scale;
// ── VIEWPORT CULL ──────────────────────────────────────────────────────────
// The egui canvas tessellates every painted shape on the UI thread (single core).
// At 30k nodes/edges that single-core tessellation dominates pan/zoom even with the
// layout frozen. `facett-graphview::clip` is the OFFSCREEN-raster cull lane (it emits
// an rgba `Frame`, not egui shapes), so it can't drop into this `egui::Painter` path;
// this is its in-lane equivalent — the same "does the geometry's AABB overlap the
// widget rect" discipline (`clip::aabb_overlaps`) expressed on egui geometry, with a
// node-radius margin so a chip straddling the border still paints. Off-screen geometry
// is never tessellated / registered for picking. `state_json` is unaffected (it lists
// every visible node regardless of on-screen position), and the minimap still plots all.
let cull_rect = rect.expand(32.0);
// Drag pans the camera (world delta = screen delta / (scale·zoom)); scroll zooms.
let dragging = resp.dragged();
if dragging {
let d = resp.drag_delta() / (scale * zoom).max(1e-3);
if d != vec2(0.0, 0.0) {
msgs.push(Msg::CameraPan([d.x, d.y]));
}
}
if resp.hovered() {
let sd = ui.input(|i| i.smooth_scroll_delta.y);
if sd != 0.0 {
msgs.push(Msg::CameraZoom(1.0 + sd * 0.001));
}
}
// ── HOVER, through the SPATIAL INDEX ─────────────────────────────────────────
// This used to iterate EVERY node in the graph, project it and take a distance
// — on every mouse move, including nodes far off-screen. The paint loop below
// was already viewport-culled, so the pointer half of the frame scaled with the
// DATASET while the paint half scaled with the SCREEN: the same shape
// facett-geomap's PointGrid was caught in. The index is rebuilt only when the
// projection or the visible set changed, and a probe touches a neighbourhood.
// `state_json["legibility"]["hover_candidates"]` publishes how many nodes were
// actually distance-tested, so the claim is a number and not a sentence.
//
// While the canvas is being DRAGGED the camera moves every frame, so the index
// would be rebuilt every frame for a hover nobody can see — at 100 000 nodes that
// rebuild is the largest CPU cost of a drag. A drag has no hover; the index is
// brought up to date on the first frame after the drag ends.
let hover_pos = if dragging { None } else { resp.hover_pos() };
let index_key = {
let mut h = std::collections::hash_map::DefaultHasher::new();
self.graph.nodes.len().hash(&mut h);
self.visible.len().hash(&mut h);
center.x.to_bits().hash(&mut h);
center.y.to_bits().hash(&mut h);
scale.to_bits().hash(&mut h);
zoom.to_bits().hash(&mut h);
cam_pan.x.to_bits().hash(&mut h);
cam_pan.y.to_bits().hash(&mut h);
positions.len().hash(&mut h);
h.finish()
};
let hovered: Option<usize> = if dragging {
None
} else {
let mut cache = self.legibility_cache.0.borrow_mut();
let (hindex, _) = &mut *cache;
hindex.ensure(
index_key,
(0..n_nodes).filter(|&i| fi.visible[i]).map(|i| (i, project(positions[i]))),
);
hover_pos.and_then(|hp| hindex.hover(hp, 10.0))
};
// The hovered node's neighbours, off the cached adjacency (no per-frame map).
let mut is_nb = vec![false; if hovered.is_some() { n_nodes } else { 0 }];
let mut hover_nb: Vec<usize> = Vec::new();
if let Some(h) = hovered {
for &t in &fi.adj[fi.adj_off[h] as usize..fi.adj_off[h + 1] as usize] {
is_nb[t as usize] = true;
hover_nb.push(t as usize);
}
}
let nb = |i: usize| is_nb.get(i).copied().unwrap_or(false);
// ── THE LEGIBILITY PLAN ──────────────────────────────────────────────────────
// What is worth drawing this frame: which edges survive the per-cell ink budget
// and which labels win their pixels. Pure (`legible::plan_nav`), so a bench
// times exactly this and a test asserts exactly this.
let centres: Vec<egui::Pos2> = positions.iter().map(|&p| project(p)).collect();
let show_all_labels = self.visible.len() <= 40 || zoom >= 1.6;
let label_chars: Vec<usize> = (0..n_nodes)
.map(|i| {
let wanted = show_all_labels
|| fi.selected == Some(i)
|| hovered == Some(i)
|| nb(i)
|| fi.path[i]
|| fi.matched[i];
if wanted { usize::from(fi.caption_chars[i]) } else { 0 }
})
.collect();
// Pinned = the labels the user is actively pointing at or has selected: those
// are the answer to their question and must never be dropped.
let label_pinned: Vec<bool> = (0..n_nodes)
.map(|i| fi.selected == Some(i) || hovered == Some(i) || fi.path[i] || fi.matched[i])
.collect();
// Rank the rest by how connected they are — in a graph, the hub is the label
// worth reading when only some can be read.
let label_priority: Vec<f32> = (0..n_nodes)
.map(|i| (if nb(i) { 500.0 } else { 0.0 }) + (fi.adj_off[i + 1] - fi.adj_off[i]) as f32)
.collect();
// ── the shared instanced GPU cloud (opt-in; falls back, never blank) ─────────
// Pushed BEFORE the plan: when the GPU draws the edges, the plan has no edge
// budget to compute. Above `SCALE_NODES` the cloud is the RESIDENT model — the
// points and edges are uploaded when they change and each frame sends only the
// camera; below it the per-frame instance lane keeps per-node radii and dimming.
let at_scale = n_nodes > SCALE_NODES;
let drew_on_gpu = if at_scale {
self.draw_resident_cloud(ui, rect, &fi, &positions, &appear, center, scale, zoom, cam_pan)
} else {
legible::draw_gpu_cloud(
ui,
rect,
¢res,
&appear.radii,
&appear.colors.iter().map(|&[r, g, b]| Color32::from_rgb(r, g, b)).collect::<Vec<_>>(),
&fi.visible,
&fi.edge_pairs,
th.text_dim.gamma_multiply(0.42),
self.legibility.gpu_cloud,
)
};
let no_edges: [(u32, u32); 0] = [];
let no_flags: [bool; 0] = [];
let edge_always: Vec<bool> = if drew_on_gpu {
Vec::new()
} else {
fi.edge_idx
.iter()
.map(|&(a, b)| {
if a == u32::MAX || b == u32::MAX {
return false;
}
let (a, b) = (a as usize, b as usize);
let on_path = fi.path[a] && fi.path[b];
let on_cycle = fi.cycle[a] && fi.cycle[b];
let touches_hover = hovered.is_some_and(|h| h == a || h == b);
on_path || on_cycle || touches_hover
})
.collect()
};
let plan = legible::plan_nav(
&legible::NavFrame {
centres: ¢res,
visible: &fi.visible,
label_chars: &label_chars,
label_pinned: &label_pinned,
label_priority: &label_priority,
edges: if drew_on_gpu { &no_edges } else { &fi.edge_pairs },
edge_always: if drew_on_gpu { &no_flags } else { &edge_always },
edge_weight: &fi.ew,
viewport: cull_rect,
font_px: 10.0,
},
self.legibility,
);
{
let mut cache = self.legibility_cache.0.borrow_mut();
let hover_candidates = cache.0.last_candidates;
let hover_indexed = cache.0.len();
let (hover_builds, hover_probes) = (cache.0.builds, cache.0.probes);
cache.1 = legible::NavReport {
gpu_cloud: drew_on_gpu,
hover_candidates,
hover_indexed,
hover_builds,
hover_probes,
..plan.report.clone()
};
}
let thinned_labels = plan.labels().is_some();
if !drew_on_gpu {
let edge_order: Vec<u32> = match plan.edges() {
Some(keep) => keep.clone(),
None => (0..self.graph.edges.len() as u32).collect(),
};
for ei in edge_order.into_iter().map(|i| i as usize) {
let Some(&(ia, ib)) = fi.edge_pairs.get(ei) else { continue };
// Unresolved or not visible at either end.
if ia == u32::MAX {
continue;
}
let (ia, ib) = (ia as usize, ib as usize);
let (pa, pb) = (project(positions[ia]), project(positions[ib]));
// Viewport cull: skip edges whose segment AABB misses the visible rect (a long
// edge crossing the viewport with both ends off-screen is kept — its AABB overlaps).
if !cull_rect.intersects(egui::Rect::from_two_pos(pa, pb)) {
continue;
}
let wfac = 0.6 + 1.4 * (fi.ew[ei] / fi.ew_max);
let on_path = fi.path[ia] && fi.path[ib];
let on_cycle = fi.cycle[ia] && fi.cycle[ib];
let touches_hover = hovered.is_some_and(|h| h == ia || h == ib);
let col = if on_path {
th.accent
} else if on_cycle {
CYCLE_COL
} else if touches_hover {
th.text.gamma_multiply(0.8)
} else {
th.text_dim.gamma_multiply(0.42)
};
let w = if on_path {
2.5
} else if on_cycle {
2.2
} else if touches_hover {
1.8
} else {
1.0 * wfac
};
painter.line_segment([pa, pb], Stroke::new(w, col));
}
}
// nodes + AccessKit
//
// On the SCALE road (resident GPU cloud above `SCALE_NODES`) every disc is
// already on screen, and giving each of 100 000 discs its own widget would cost
// more than the whole GPU frame. The CPU then walks only the nodes the user is
// pointing at — selection, hover + neighbours, path, matches, cycle, similar —
// and a click picks through the hover index instead of a widget per node.
let base_id = ui.id().with("gn-nodes");
let mut clicked: Option<String> = None;
let scale_road = drew_on_gpu && at_scale;
let walk: Vec<usize> = if scale_road {
let mut w: Vec<usize> = fi.special.iter().copied().chain(hovered).chain(hover_nb.iter().copied()).collect();
w.sort_unstable();
w.dedup();
w
} else {
(0..n_nodes).collect()
};
if scale_road && resp.clicked() && let Some(h) = hovered {
clicked = Some(self.graph.nodes[h].id.clone());
}
for i in walk {
let n = &self.graph.nodes[i];
if !fi.visible[i] {
continue;
}
let p = project(positions[i]);
// Viewport cull: an off-screen chip is neither tessellated nor registered for
// picking/AccessKit — it can't be hovered or clicked while off the visible rect.
if !cull_rect.contains(p) {
continue;
}
let [r, g, b] = appear.colors[i];
let mut col = Color32::from_rgb(r, g, b);
let is_sel = fi.selected == Some(i);
let on_path = fi.path[i];
let matched = fi.matched[i];
if matched {
painter.circle_filled(p, 12.0, Color32::from_rgb(240, 210, 80).gamma_multiply(0.35));
}
let is_hovered = hovered == Some(i);
let is_neighbour = nb(i);
// Dim nodes that are neither the hovered node nor its neighbours (focus mode).
if hovered.is_some() && !is_hovered && !is_neighbour {
col = col.gamma_multiply(0.5);
}
let base_r = appear.radii[i];
let radius = if is_sel { base_r + 2.0 } else if is_hovered { base_r + 1.5 } else { base_r };
if on_path {
col = th.accent;
}
if !drew_on_gpu {
// With the GPU cloud up the discs are already on screen; the CPU keeps
// the thin overlays (rings, labels, a11y) but not the node cloud.
painter.circle_filled(p, radius, col);
}
if is_sel {
painter.circle_stroke(p, radius + 3.0, Stroke::new(2.0_f32, th.accent));
}
if is_neighbour {
painter.circle_stroke(p, radius + 2.0, Stroke::new(1.5_f32, th.text.gamma_multiply(0.7)));
}
if fi.cycle[i] {
painter.circle_stroke(p, radius + 3.0, Stroke::new(2.0_f32, CYCLE_COL));
}
if fi.similar[i] {
painter.circle_stroke(p, radius + 4.5, Stroke::new(1.5_f32, SIMILAR_COL));
}
if !scale_road {
let nrect = egui::Rect::from_center_size(p, vec2(radius * 2.0 + 8.0, radius * 2.0 + 8.0));
let sem = a11y::Semantics::button(format!("{} · {}", n.caption(), n.label)).selected(is_sel);
let resp = a11y::node(ui, base_id, i, Sense::click(), nrect, sem);
if resp.clicked() {
clicked = Some(n.id.clone());
}
}
// Labels appear when the graph is small, or as you zoom in, or for the
// hovered node + its neighbours + the selection/path (progressive
// disclosure). That rule alone is NOT enough at scale: past zoom 1.6 with
// 100 000 visible nodes it paints 100 000 labels on top of each other, and
// "every label is drawn" is indistinguishable from "no label is readable".
// With collision avoidance on, the surviving labels are painted once, below,
// at the boxes the placer chose.
if !thinned_labels {
let show_label = self.visible.len() <= 40
|| zoom >= 1.6
|| is_sel
|| is_hovered
|| is_neighbour
|| on_path
|| matched;
if show_label && rect.contains(p) {
painter.text(p + vec2(0.0, -(radius + 3.0)), Align2::CENTER_BOTTOM, n.caption(), FontId::proportional(10.0), th.text);
}
}
}
// The labels that won their pixels, painted once each.
if let Some(placed) = plan.labels() {
for pl in &placed.placed {
let Some(n) = self.graph.nodes.get(pl.index) else { continue };
let r = appear.radii.get(pl.index).copied().unwrap_or(4.0);
// `slot == 0` means the placer kept the label at its anchor, so it can
// sit in its natural spot above the node; a displaced label is drawn at
// the box it actually won, or it would collide again.
let at = if pl.slot == 0 {
centres[pl.index] + vec2(0.0, -(r + 3.0))
} else {
pl.rect.center()
};
if rect.contains(at) {
painter.text(at, Align2::CENTER_BOTTOM, n.caption(), FontId::proportional(10.0), th.text);
}
}
}
if let Some(id) = clicked {
if self.selected_node.as_deref() == Some(id.as_str()) {
msgs.push(Msg::ClearSelection);
} else {
msgs.push(Msg::SelectNode(id));
}
}
// ── inspector + schema footer ────────────────────────────────────────
if let Some(id) = &self.selected_node
&& let Some(n) = fi.selected.and_then(|i| self.graph.nodes.get(i)).filter(|n| &n.id == id)
{
let mut lines = vec![format!("{} ({})", n.caption(), n.label)];
for (k, v) in &n.props {
lines.push(format!(" {k}: {v}"));
}
painter.text(rect.left_top() + vec2(8.0, 8.0), Align2::LEFT_TOP, lines.join("\n"), FontId::monospace(11.0), th.text);
}
let footer = format!(
"{} nodes · {} edges · {} labels · {} rel-types · layout={}",
self.graph.nodes.len(),
self.graph.edges.len(),
fi.label_count,
fi.etype_count,
self.layout_kind.key(),
);
painter.text(rect.left_bottom() + vec2(8.0, -6.0), Align2::LEFT_BOTTOM, footer, FontId::proportional(11.0), th.text_dim);
// minimap corner box — at most MINIMAP_DOTS dots, strided over the visible
// nodes, so the thumbnail costs the same at 100 000 nodes as at 4 000.
if let Some((x0, y0, x1, y1)) = layout::bounds(&positions) {
const MINIMAP_DOTS: usize = 4_000;
let mm = egui::Rect::from_min_size(rect.right_top() + vec2(-92.0, 8.0), vec2(84.0, 64.0));
painter.rect_filled(mm, CornerRadius::same(3), th.bg.gamma_multiply(1.4));
painter.rect_stroke(mm, CornerRadius::same(3), Stroke::new(1.0_f32, th.text_dim), egui::StrokeKind::Inside);
let (sw, sh) = ((x1 - x0).max(1e-3), (y1 - y0).max(1e-3));
let stride = n_nodes.div_ceil(MINIMAP_DOTS).max(1);
for i in (0..n_nodes).step_by(stride) {
if !fi.visible[i] {
continue;
}
let fx = (positions[i][0] - x0) / sw;
let fy = (positions[i][1] - y0) / sh;
let mp = mm.min + vec2(fx * mm.width(), fy * mm.height());
painter.circle_filled(mp, 1.2, th.text_dim);
}
}
drop(fi);
#[cfg(feature = "testmatrix")]
facett_core::testmatrix::emit(
"facett-graphnav::GraphNav::ui",
"ui_render",
!self.graph.nodes.is_empty(),
&format!("visible={} layout={}", self.visible.len(), self.layout_kind.key()),
);
}); // CentralPanel (canvas)
msgs
}
}
#[cfg(test)]
mod tests {
use super::*;
/// **RED-when-broken: the query-bar SAMPLE is Cypher, never Gremlin.** FalkorDB (the
/// graph backend behind this navigator, e.g. korp's) speaks Cypher/openCypher, where
/// `MATCH (n) RETURN n` runs but a Gremlin `g.V()` does not. The surfaced hint must
/// therefore stay Cypher-only — if it ever advertises `g.V()` again this is red. (The
/// Gremlin-ish subset is still PARSED for power users; only the SAMPLE is Cypher.)
#[test]
fn query_hint_sample_is_cypher_not_gremlin() {
assert!(QUERY_HINT.contains("MATCH") && QUERY_HINT.contains("RETURN"), "sample is Cypher: {QUERY_HINT:?}");
assert!(!QUERY_HINT.contains("g.V"), "sample must not advertise a Gremlin g.V(): {QUERY_HINT:?}");
// The Gremlin subset still parses (a power-user feature, just not the sample).
let g = model::PropGraph::demo();
assert_eq!(query::run(&g, "g.V()").nodes.len(), g.nodes.len(), "g.V() still parses when typed");
}
#[test]
fn query_history_and_saved_queries() {
let mut nav = GraphNav::demo();
// Running queries records distinct, non-empty history (no consecutive dupes).
nav.update(Msg::SetQuery("g.V().hasLabel('Person')".into()));
nav.update(Msg::RunQuery);
nav.update(Msg::RunQuery); // repeat of the same query → not re-recorded
nav.update(Msg::SetQuery("g.V().hasLabel('Company')".into()));
nav.update(Msg::RunQuery);
assert_eq!(nav.query_history().len(), 2, "two distinct queries in history");
assert_eq!(nav.state_json()["history"]["count"], 2);
assert_eq!(nav.state_json()["history"]["recent"][1], "g.V().hasLabel('Company')");
// Save the current query, then change + recall it.
assert!(nav.update(Msg::SaveQuery("companies".into())));
nav.update(Msg::SetQuery("something-else".into()));
assert!(nav.update(Msg::RecallQuery("companies".into())));
assert_eq!(nav.state_json()["query"]["text"], "g.V().hasLabel('Company')");
assert_eq!(nav.state_json()["history"]["saved"]["companies"], "g.V().hasLabel('Company')");
// Recalling an unknown name is a no-op.
assert!(!nav.update(Msg::RecallQuery("nope".into())));
// Clearing history leaves saved queries intact.
assert!(nav.update(Msg::ClearHistory));
assert_eq!(nav.query_history().len(), 0);
assert_eq!(nav.saved_queries().len(), 1, "saved queries survive a history clear");
}
#[test]
fn subgraph_extraction_around_the_selection() {
let mut nav = GraphNav::demo();
// No selection ⇒ ExtractSubgraph is a no-op and state stays Null.
assert!(!nav.update(Msg::ExtractSubgraph(1)));
assert!(nav.state_json()["subgraph"].is_null());
// Select the bridge node p3, extract its 1-hop ego-network.
nav.update(Msg::SelectNode("p3".into()));
assert!(nav.update(Msg::ExtractSubgraph(1)));
let sg = nav.state_json()["subgraph"].clone();
assert_eq!(sg["center"], "p3");
assert_eq!(sg["radius"], 1);
// p3 + its neighbours p1, p2, p4 → 4 nodes.
assert_eq!(sg["node_count"], 4, "1-hop ego-net of p3 is {{p3,p1,p2,p4}}");
let ids = sg["nodes"].as_array().unwrap();
assert!(ids.iter().any(|v| v == "p3") && ids.iter().any(|v| v == "p4"));
assert!(sg["edge_count"].as_u64().unwrap() >= 3, "induced edges are present");
// Radius 2 reaches strictly more of the graph than radius 1.
let n1 = sg["node_count"].as_u64().unwrap();
nav.update(Msg::ExtractSubgraph(2));
let n2 = nav.state_json()["subgraph"]["node_count"].as_u64().unwrap();
assert!(n2 > n1, "a wider radius reaches more nodes ({n1} → {n2})");
// Clearing drops the extraction.
assert!(nav.update(Msg::ClearSubgraph));
assert!(nav.state_json()["subgraph"].is_null());
}
#[test]
fn demo_state_covers_every_panel() {
let v = GraphNav::demo();
let st = v.state_json();
assert_eq!(st["canvas"]["total_nodes"], 8);
assert_eq!(st["layout"]["current"], "force");
// A placeless graph is offered exactly the five switchable layouts.
assert_eq!(st["layout"]["options"].as_array().unwrap().len(), 5);
assert_eq!(st["layout"]["has_places"], false);
assert!(st["schema"]["node_labels"]["Person"].as_u64().unwrap() == 6);
assert!(st["schema"]["triples"].as_array().unwrap().iter().any(|t| t.as_str().unwrap().contains("WORKS_AT")));
assert!(st["minimap"].is_object());
assert_eq!(st["export"]["formats"].as_array().unwrap().len(), 5);
}
/// **A placed graph is offered the geographic layout, and an unplaced one is not.**
///
/// The switcher chip and the layout itself read the SAME predicate
/// (`layout::places_cover`), so a chip can never offer a lane that would fall back to
/// force the moment it is clicked. And a new place column MOVES the canvas — the
/// layout cache is keyed on `(layout, n, edges)`, none of which a place column
/// changes, so `SetPlaces` has to drop it or the picture stays put.
#[test]
fn a_placed_graph_is_offered_the_geographic_layout_and_moves_when_it_gets_one() {
let mut nav = GraphNav::demo();
let n = nav.state_json()["canvas"]["total_nodes"].as_u64().unwrap() as usize;
assert!(!nav.has_places());
assert!(!nav.state_json()["layout"]["options"]
.as_array()
.unwrap()
.iter()
.any(|o| o == "geographic"));
// Places the HOST projected (a diagonal line — nothing a force layout produces).
let places: Vec<layout::Place> =
(0..n).map(|i| Some([i as f64 * 0.01, i as f64 * 0.02])).collect();
let before = nav.positions();
assert!(nav.update(Msg::SetPlaces(places.clone())));
assert!(nav.has_places());
let st = nav.state_json();
assert_eq!(st["layout"]["has_places"], true);
assert_eq!(st["layout"]["placed_nodes"], n);
assert!(st["layout"]["options"].as_array().unwrap().iter().any(|o| o == "geographic"));
// Still force, so the picture must NOT have moved — a place column is not a
// layout change.
assert_eq!(nav.positions(), before, "places alone do not move a force layout");
// Switch: now it must be the line, not the blob.
assert!(nav.update(Msg::SetLayout(LayoutKind::Geographic)));
let after = nav.positions();
assert_ne!(after, before, "the geographic layout is not the force layout");
// Collinear, because the places were: cross product ~0 across the whole set.
let (a, b) = (after[0], after[n - 1]);
for p in &after {
let cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]);
assert!(cross.abs() < 1e-4, "the drawn set is the line it was handed: {cross}");
}
// Take the places away and the chip goes with them, byte-identically to force.
assert!(nav.update(Msg::SetPlaces(Vec::new())));
assert!(!nav.has_places());
assert_eq!(nav.positions(), before, "no places is the force layout again");
}
#[test]
fn query_bar_runs_and_reports_the_result() {
let mut v = GraphNav::demo();
v.update(Msg::SetQuery("MATCH (n:Person) RETURN n".into()));
assert!(v.update(Msg::RunQuery));
let st = v.state_json();
assert_eq!(st["query"]["kind"], "nodes");
assert_eq!(st["query"]["result_nodes"], 6);
}
#[test]
fn layout_switch_is_observable() {
let mut v = GraphNav::demo();
assert!(v.update(Msg::SetLayout(LayoutKind::Grid)));
assert_eq!(v.layout_kind(), LayoutKind::Grid);
assert_eq!(v.state_json()["canvas"]["layout"], "grid");
// Grid and circular give different positions.
let g = layout::layout(LayoutKind::Grid, 8, &v.graph.edge_indices());
let c = layout::layout(LayoutKind::Circular, 8, &v.graph.edge_indices());
assert_ne!(g, c);
}
#[test]
fn selection_feeds_the_inspector() {
let mut v = GraphNav::demo();
assert!(v.update(Msg::SelectNode("p1".into())));
let insp = &v.state_json()["inspector"];
assert_eq!(insp["kind"], "node");
assert_eq!(insp["caption"], "Alice");
assert_eq!(insp["props"]["age"], "42");
// Selecting an edge switches the inspector.
assert!(v.update(Msg::SelectEdge(0)));
assert_eq!(v.state_json()["inspector"]["kind"], "edge");
}
#[test]
fn search_highlights_matches() {
let mut v = GraphNav::demo();
v.update(Msg::SetSearch("acme".into()));
let st = v.state_json();
assert_eq!(st["search"]["match_count"], 1);
assert_eq!(st["search"]["matches"][0], "c1");
}
#[test]
fn path_highlight_runs_shortest_path() {
let mut v = GraphNav::demo();
assert!(v.update(Msg::SetPath(Some(("p1".into(), "p6".into())))));
let st = v.state_json();
let path = st["path"]["nodes"].as_array().unwrap();
assert!(path.len() >= 3, "a cross-cluster path exists: {path:?}");
assert_eq!(path.first().unwrap(), "p1");
assert_eq!(path.last().unwrap(), "p6");
}
#[test]
fn filter_and_expand_collapse_change_visibility() {
let mut v = GraphNav::demo();
// Filter to companies only → 2 visible.
v.update(Msg::SetFilterLabel(Some("Company".into())));
assert_eq!(v.visible_count(), 2);
// Expand c1's neighbourhood → its employees appear.
v.update(Msg::ExpandNeighborhood("c1".into()));
assert!(v.visible_count() > 2);
}
#[test]
fn export_formats_produce_text() {
let v = GraphNav::demo();
assert!(v.export(ExportFormat::Dot).contains("digraph"));
assert!(v.export(ExportFormat::Csv).contains("from,to,type"));
assert!(v.export(ExportFormat::Json).contains("\"nodes\""));
}
#[test]
fn model_round_trips_through_serde() {
let mut v = GraphNav::demo();
v.update(Msg::SetLayout(LayoutKind::Hierarchical));
v.update(Msg::SelectNode("p3".into()));
v.update(Msg::SetPath(Some(("p1".into(), "p4".into()))));
let j = serde_json::to_string(&v).unwrap();
let back: GraphNav = serde_json::from_str(&j).unwrap();
assert_eq!(back, v, "the whole navigator Model round-trips");
}
#[test]
fn cycle_browser_detects_and_highlights_directed_cycles() {
let mut nav = GraphNav::demo();
// The demo's two KNOWS triangles are directed 3-cycles ⇒ not a DAG.
assert!(!nav.is_acyclic(), "the KNOWS triangles are directed cycles");
let cycles = nav.cycles();
assert_eq!(cycles.len(), 2, "two elementary cycles (the two triangles): {cycles:?}");
assert_eq!(nav.state_json()["cycles"]["acyclic"], false);
assert_eq!(nav.state_json()["cycles"]["count"], 2);
// Highlight the first cycle → its nodes surface + the paint flag flips.
assert!(nav.update(Msg::HighlightCycle(Some(0))));
let cj = nav.state_json()["cycles"].clone();
assert_eq!(cj["highlighted"], 0);
assert_eq!(cj["nodes"].as_array().unwrap().len(), 3, "a triangle has three nodes");
let on_cycle = nav.state_json()["canvas"]["nodes"]
.as_array()
.unwrap()
.iter()
.filter(|n| n["on_cycle"] == true)
.count();
assert_eq!(on_cycle, 3, "three nodes marked on_cycle");
// An out-of-range index clears the highlight (no panic).
assert!(nav.update(Msg::HighlightCycle(Some(99))));
assert!(nav.state_json()["cycles"]["nodes"].as_array().unwrap().is_empty());
}
#[test]
fn similar_panel_ranks_the_selection_neighbourhood_twins() {
let mut nav = GraphNav::demo();
// Inactive until a node is selected.
assert!(nav.state_json()["similarity"].is_null());
assert!(!nav.update(Msg::FindSimilar(5)), "no selection ⇒ no-op");
nav.update(Msg::SelectNode("p1".into()));
assert!(nav.update(Msg::FindSimilar(5)));
let sj = nav.state_json()["similarity"].clone();
assert_eq!(sj["center"], "p1");
assert!(sj["count"].as_u64().unwrap() >= 1, "p1 has neighbourhood-overlap peers");
// Scores are in [0,1] and ranked descending.
let scores: Vec<f64> =
sj["results"].as_array().unwrap().iter().map(|r| r["score"].as_f64().unwrap()).collect();
assert!(scores.windows(2).all(|w| w[0] >= w[1]), "ranked descending: {scores:?}");
assert!(scores.iter().all(|&s| (0.0..=1.0).contains(&s)));
// The similar nodes are ringed on the canvas.
let similar = nav.state_json()["canvas"]["nodes"]
.as_array()
.unwrap()
.iter()
.filter(|n| n["similar"] == true)
.count();
assert!(similar >= 1, "at least one similar node ringed on the canvas");
// Clearing turns the panel off.
assert!(nav.update(Msg::ClearSimilar));
assert!(nav.state_json()["similarity"].is_null());
}
#[test]
fn analysis_fields_round_trip_through_serde() {
let mut v = GraphNav::demo();
v.update(Msg::SelectNode("p1".into()));
v.update(Msg::FindSimilar(3));
v.update(Msg::HighlightCycle(Some(1)));
let j = serde_json::to_string(&v).unwrap();
let back: GraphNav = serde_json::from_str(&j).unwrap();
assert_eq!(back, v, "cycle + similarity state round-trips");
}
/// Build a ring+chord property graph of `n` nodes (an O(n)-edge structure that
/// exercises the force layout at scale).
fn big_graph(n: usize) -> PropGraph {
let mut g = PropGraph::new();
for i in 0..n {
g.add_node(Node::new(format!("n{i}"), "N"));
}
for i in 0..n {
g.add_edge(Edge::new(format!("n{i}"), format!("n{}", (i + 1) % n), "R"));
if i % 11 == 0 {
g.add_edge(Edge::new(format!("n{i}"), format!("n{}", (i + 313) % n), "R"));
}
}
g
}
/// Build `⌈min_nodes/3⌉` **disjoint directed triangles** — a graph with the given node
/// count (rounded up to a multiple of 3) whose every elementary cycle is length 3. Used
/// where a test must actually enumerate cycles at scale: the ring `big_graph` has a single
/// giant cycle that would recurse the enumerator to a stack overflow (the very reason the
/// scale guard exists), whereas short triangles enumerate shallowly.
fn triangles_graph(min_nodes: usize) -> PropGraph {
let mut g = PropGraph::new();
let k = min_nodes.div_ceil(3);
for t in 0..k {
let (a, b, c) = (format!("t{t}a"), format!("t{t}b"), format!("t{t}c"));
g.add_node(Node::new(a.clone(), "T"));
g.add_node(Node::new(b.clone(), "T"));
g.add_node(Node::new(c.clone(), "T"));
g.add_edge(Edge::new(a.clone(), b.clone(), "R"));
g.add_edge(Edge::new(b, c.clone(), "R"));
g.add_edge(Edge::new(c, a, "R"));
}
g
}
/// **Scale (RED-when-broken):** a 30 000-node force layout must produce a finite,
/// bounded position for every node under a wall-clock budget. The old O(n²)
/// all-pairs repulsion blows this (and hung the viewer); Barnes–Hut O(n log n)
/// meets it. A regression to quadratic repulsion trips the time bound.
#[test]
fn force_layout_scales_to_thirty_thousand_nodes() {
let n = 30_000;
assert!(n >= facett_core::barnes_hut::BH_THRESHOLD, "on the Barnes–Hut path");
let nav = GraphNav::new("big", big_graph(n));
let t0 = std::time::Instant::now();
let pos = nav.positions();
let ms = t0.elapsed().as_secs_f64() * 1000.0;
assert_eq!(pos.len(), n, "every node placed");
for p in &pos {
assert!(p[0].is_finite() && p[1].is_finite(), "finite");
assert!(p[0].abs() <= 1.01 && p[1].abs() <= 1.01, "bounded in the box: {p:?}");
}
assert!(ms < 30_000.0, "30k force layout must be sub-quadratic; took {ms:.0} ms");
}
/// **Freeze:** a second `positions()` call for an unchanged graph is a cache hit —
/// no relayout. Proven by `layout_settled()` flipping true after the first compute
/// and the second call returning byte-identical positions far faster.
#[test]
fn positions_freeze_after_first_compute() {
let nav = GraphNav::new("big", big_graph(5_000));
assert!(!nav.layout_settled(), "cold cache is not settled");
let a = nav.positions();
assert!(nav.layout_settled(), "settled after the first converge");
let b = nav.positions();
assert_eq!(a, b, "frozen positions are stable (no re-run drift)");
}
/// **No host device ⇒ the CPU lane, untouched.** The non-blocking GPU lane is
/// opt-in by INSTALL, not by feature: with `gpu` compiled in but nothing lent, a
/// large force layout must settle on the first call, report `"cpu"`, and never be
/// pending. This is the guarantee that the native hosts and every golden are
/// exactly where they were.
#[cfg(feature = "gpu")]
#[test]
fn without_a_host_device_the_cpu_lane_is_unchanged() {
facett_graphview::gpu_layout::clear_host_device();
let nav = GraphNav::new("big", big_graph(5_000));
let a = nav.positions();
assert!(nav.layout_settled(), "the CPU lane settles on the first call");
assert!(!nav.layout_pending());
assert_eq!(nav.layout_lane(), "cpu");
assert_eq!(a, nav.positions());
}
/// **With a lent device, a large force layout runs as a non-blocking job** — the
/// whole browser road, driven natively: first call returns the grid placeholder and
/// is NOT settled; polling (what repaints do) completes it; the result is the GPU
/// lane's layout, cached and frozen like any other. A small graph takes the same
/// lane (no size floor since 2026-09-29).
#[cfg(feature = "gpu")]
#[test]
fn a_lent_device_lays_large_graphs_out_without_blocking() {
use facett_graphview::gpu_layout as gl;
let _gpu = facett_core::render::gputurn::hold();
let Some((device, queue)) = gl::compute_device() else {
eprintln!("no wgpu adapter — skipping");
return;
};
assert!(gl::install_host_device(&device, &queue));
let small = GraphNav::new("small", big_graph(200));
let _ = small.positions();
assert!(small.layout_pending(), "a small graph with a lent device starts a GPU job too");
while small.layout_pending() {
let _ = small.positions();
}
assert_eq!(small.layout_lane(), "gpu-job", "no size floor on the GPU lane");
let n = 5_000;
let nav = GraphNav::new("big", big_graph(n));
let first = nav.positions();
assert_eq!(first.len(), n);
assert!(nav.layout_pending(), "the first call starts a job instead of converging inline");
assert!(!nav.layout_settled(), "a placeholder must not read as a settled layout");
let grid = layout::layout(LayoutKind::Grid, n, &nav.graph.edge_indices());
assert_eq!(first, grid, "the placeholder is the cheap deterministic grid");
let mut calls = 0usize;
while nav.layout_pending() {
calls += 1;
assert!(calls < 100_000, "the job never completed");
let _ = nav.positions();
}
assert!(nav.layout_settled());
assert_eq!(nav.layout_lane(), "gpu-job");
let settled = nav.positions();
assert_ne!(settled, grid, "the settled layout is the GPU's, not the placeholder");
assert!(settled.iter().all(|p| p[0].is_finite() && p[1].is_finite()));
// …and it IS the blocking GPU lane's layout: one algorithm, two schedulers.
let blocking = gl::force_layout_gpu_on(&device, &queue, n, &nav.graph.edge_indices(), layout::FORCE_ITERS_GPU);
assert_eq!(settled, blocking);
assert_eq!(settled, nav.positions(), "frozen after settling");
gl::clear_host_device();
}
/// **Absorb:** streaming nodes in keeps every existing node's position and places
/// the new ones finitely — the incremental contract korp's sync path relies on.
#[test]
fn absorb_keeps_existing_positions_and_places_new() {
let mut nav = GraphNav::new("g", big_graph(3_000));
let before = nav.positions();
let old_n = before.len();
// Stream in 200 new nodes, each wired to an existing neighbour.
let mut nodes = Vec::new();
let mut edges = Vec::new();
for i in 0..200 {
let id = format!("x{i}");
nodes.push(Node::new(id.clone(), "X"));
edges.push(Edge::new(id, format!("n{}", (i * 7) % old_n), "R"));
}
nav.absorb(nodes, edges);
let after = nav.positions();
assert_eq!(after.len(), old_n + 200, "graph grew by exactly the absorbed nodes");
for i in 0..old_n {
assert_eq!(after[i], before[i], "existing node {i} kept its frozen position");
}
for (i, p) in after.iter().enumerate().skip(old_n) {
assert!(p[0].is_finite() && p[1].is_finite(), "new node {i} placed finitely");
}
}
/// **Analytics freeze (RED-when-broken):** the whole-graph analytics the render path
/// recomputes every frame — `stats()` (all-pairs diameter, Louvain, clustering),
/// `cycles()` (elementary-cycle enumeration), and `appearance()` (betweenness
/// centrality) — must compute ONCE for an unchanged graph and be served from cache on
/// every subsequent paint. A regression that drops the cache re-runs each analytic per
/// call, tripping the flat-counter assertions below. A structural change (here an
/// `absorb`) must invalidate all three.
#[test]
fn analytics_freeze_after_first_compute() {
let mut nav = GraphNav::new("g", big_graph(200));
// Drive an expensive colour metric so appearance's O(V·E)+ path is on the hook.
nav.update(Msg::SetColorMetric(Some(Metric::Betweenness)));
assert_eq!(nav.analytics_computes(), (0, 0, 0), "cold cache: nothing computed yet");
let s1 = nav.stats();
let c1 = nav.cycles();
let a1 = nav.appearance();
assert_eq!(nav.analytics_computes(), (1, 1, 1), "first touch computes each analytic once");
// Repeated frames on the unchanged graph are pure cache hits — no recompute.
for _ in 0..5 {
assert_eq!(nav.stats(), s1, "stats stable across frames");
assert_eq!(nav.cycles(), c1, "cycles stable across frames");
assert_eq!(nav.appearance(), a1, "appearance stable across frames");
}
assert_eq!(nav.analytics_computes(), (1, 1, 1), "frozen: unchanged graph never re-runs analytics");
// A structural change (streaming a node in) invalidates all three via the signature.
nav.absorb(vec![Node::new("z", "Z")], vec![Edge::new("z", "n0", "R")]);
let _ = (nav.stats(), nav.cycles(), nav.appearance());
assert_eq!(nav.analytics_computes(), (2, 2, 2), "structural mutation re-runs each analytic once");
}
/// **Appearance keys on the encoding selection:** switching the colour metric (a
/// non-structural change) must invalidate ONLY the appearance cache, since the encoding
/// depends on the active style/metric/partition — not just the graph structure.
#[test]
fn appearance_cache_keys_on_selection() {
let mut nav = GraphNav::new("g", big_graph(150));
let _ = nav.appearance();
assert_eq!(nav.analytics_computes().2, 1, "first appearance computes once");
let _ = nav.appearance();
assert_eq!(nav.analytics_computes().2, 1, "same selection → cache hit");
nav.update(Msg::SetColorMetric(Some(Metric::PageRank)));
let _ = nav.appearance();
assert_eq!(nav.analytics_computes().2, 2, "changed colour metric invalidates appearance");
}
/// **Analytics scale guard — skips the superlinear path above the threshold
/// (RED-when-broken):** at/above [`ANALYTICS_SCALE_GUARD`] the render/load path must
/// NOT enumerate elementary cycles, must NOT run the all-pairs diameter / avg-path, and
/// must NOT run a superlinear colour metric — the single-core walls that froze the owner's
/// 30k graph on load. A regression that drops any guard re-runs that O(V·E)+ work and
/// trips these assertions (reusing the `analytics_computes()` miss counters from the
/// freeze work: the cycle counter proves `find_cycles` never ran).
#[test]
fn analytics_scale_guard_skips_superlinear_above_threshold() {
let n = ANALYTICS_SCALE_GUARD + 1_000; // just over the guard
let mut nav = GraphNav::new("big", big_graph(n));
// cycles(): enumeration SKIPPED — empty result, and the miss counter never bumps.
assert!(nav.cycles().is_empty(), "no elementary-cycle enumeration above the guard");
assert_eq!(nav.analytics_computes().1, 0, "find_cycles never ran above the guard");
// …and the panel advertises the n/a-at-scale affordance.
assert_eq!(nav.cycles_json()["scale_limited"], serde_json::json!(true));
assert_eq!(nav.cycles_json()["scale_guard"], serde_json::json!(ANALYTICS_SCALE_GUARD));
// stats(): cheap scalars still compute, but the all-pairs diameter / avg-path are n/a.
let s = nav.stats();
assert!(s["nodes"].is_u64() && s["density"].is_number(), "cheap scalars present");
assert!(s["diameter"].is_null(), "all-pairs diameter skipped above the guard");
assert!(s["avg_path_length"].is_null(), "all-pairs avg-path skipped above the guard");
// appearance(): a superlinear colour metric (betweenness) is skipped + flagged, never run.
nav.update(Msg::SetColorMetric(Some(Metric::Betweenness)));
let a = nav.appearance();
assert!(
a.color_mode.contains("scale-limited"),
"superlinear colour metric skipped at scale, got: {}",
a.color_mode
);
// The explicit opt-in ("compute anyway") DOES run the enumeration once. Assert it on a
// >guard graph of disjoint TRIANGLES (short cycles) — the ring's single 5000-long cycle
// would recurse the enumerator's stack to death, which is precisely why the guard exists.
let mut forced = GraphNav::new("tri", triangles_graph(ANALYTICS_SCALE_GUARD)); // 4002 nodes
assert!(forced.cycles().is_empty(), "skipped above the guard before forcing");
assert_eq!(forced.analytics_computes().1, 0, "not enumerated before forcing");
forced.update(Msg::ForceCycles);
let cs = forced.cycles();
assert!(!cs.is_empty(), "compute-anyway enumerates the (short) cycles");
assert_eq!(forced.analytics_computes().1, 1, "compute-anyway runs the enumeration exactly once");
assert_eq!(forced.cycles_json().get("scale_limited"), None, "forced: no longer scale-limited");
}
/// **Below the guard the full analytics still run** (no false gating): a small graph
/// enumerates cycles, computes the all-pairs diameter / avg-path, and runs a superlinear
/// colour metric exactly as before the guard existed — the additive-below-threshold half
/// of the RED-when-broken pair.
#[test]
fn analytics_below_guard_runs_full_suite() {
let n = ANALYTICS_SCALE_GUARD - 1_000; // comfortably under the guard (short cycles)
let mut nav = GraphNav::new("small", triangles_graph(n));
let cs = nav.cycles();
assert!(!cs.is_empty(), "cycles enumerated below the guard");
assert_eq!(nav.analytics_computes().1, 1, "cycles enumerated below the guard");
assert_eq!(nav.cycles_json().get("scale_limited"), None, "no scale-limit flag below the guard");
let s = nav.stats();
assert!(s["diameter"].is_u64(), "all-pairs diameter computed below the guard");
assert!(s["avg_path_length"].is_number(), "all-pairs avg-path computed below the guard");
nav.update(Msg::SetColorMetric(Some(Metric::Betweenness)));
let a = nav.appearance();
assert_eq!(a.color_mode, "metric:betweenness", "superlinear metric runs below the guard");
}
/// Build a nav over nodes with the given `labels` in that order (one node each).
fn nav_over(labels: &[&str]) -> GraphNav {
let mut g = PropGraph::new();
for (i, lbl) in labels.iter().enumerate() {
g.add_node(Node::new(format!("n{i}"), *lbl));
}
GraphNav::new("t", g)
}
/// The RGB `appearance()` assigned to the (single) node carrying `label`.
fn colour_of(nav: &GraphNav, label: &str) -> [u8; 3] {
let idx = nav
.graph
.nodes
.iter()
.position(|n| n.label == label)
.expect("label present");
nav.appearance().colors[idx]
}
/// **RED-when-broken — the ontology-palette override knob (JOB 2, korp's fix).** With
/// a pinned palette `{Person→blue, Vessel→amber}`, those labels must resolve to EXACTLY
/// those hues regardless of first-seen order (fed as two opposite orderings), while an
/// un-pinned label (`Company`) still gets its wheel/hashed colour — and that fallback is
/// itself order-stable. Breaking the override (or letting first-seen order leak back in)
/// flips one of these. `functional_status: ontology_palette_override`.
#[test]
fn label_color_override_pins_hues_across_node_order() {
let blue = Color32::from_rgb(30, 90, 220);
let amber = Color32::from_rgb(240, 190, 70);
let pins = [("Person", blue), ("Vessel", amber)];
// Two OPPOSITE first-seen orderings of the same label set.
let a = nav_over(&["Person", "Vessel", "Company"]).with_label_colors(pins);
let b = nav_over(&["Company", "Vessel", "Person"]).with_label_colors(pins);
// Pinned labels resolve to EXACTLY the override hue in BOTH orderings.
assert_eq!(colour_of(&a, "Person"), [30, 90, 220], "Person pinned blue (order A)");
assert_eq!(colour_of(&b, "Person"), [30, 90, 220], "Person pinned blue (order B)");
assert_eq!(colour_of(&a, "Vessel"), [240, 190, 70], "Vessel pinned amber (order A)");
assert_eq!(colour_of(&b, "Vessel"), [240, 190, 70], "Vessel pinned amber (order B)");
// The un-pinned label keeps the stable hashed wheel colour — and is order-stable.
let company = style::label_color("Company");
assert_eq!(colour_of(&a, "Company"), company, "Company un-pinned → wheel/hash colour");
assert_eq!(colour_of(&b, "Company"), company, "…same colour regardless of order");
assert_ne!(colour_of(&a, "Company"), [30, 90, 220], "un-pinned label is NOT an override hue");
assert_ne!(colour_of(&a, "Company"), [240, 190, 70]);
}
/// **Default byte-identity.** With NO overrides set, `appearance()` colours are exactly
/// what the pre-knob wheel/hash rule produced — the knob must not perturb the default.
#[test]
fn no_override_is_byte_identical_to_the_wheel_rule() {
let nav = nav_over(&["Person", "Vessel", "Company"]);
assert!(nav.label_color_overrides().is_empty(), "no overrides by default");
for lbl in ["Person", "Vessel", "Company"] {
assert_eq!(colour_of(&nav, lbl), style::label_color(lbl), "{lbl}: default == label_color");
}
}
}