facett-graphnav/src/model.rs
//! The **property graph** the navigator browses — the graph-DB data model: nodes with
//! a `label` (their type) + a bag of string properties, and directed edges with a
//! relationship `type` + properties. Plus [`Schema`] extraction (the entity-
//! relationship overview a graph-DB IDE shows).
//!
//! Dependency-free (serde + std only) — the portability seam, like the rest of facett's
//! `model` cores.
use std::collections::BTreeMap;
use serde::{Deserialize, Serialize};
/// A node: a stable string `id`, a `label` (its type / class, e.g. `Person`), and a
/// sorted property bag (kept `BTreeMap` so serialisation + iteration are deterministic).
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Node {
pub id: String,
pub label: String,
pub props: BTreeMap<String, String>,
}
impl Node {
pub fn new(id: impl Into<String>, label: impl Into<String>) -> Self {
Self { id: id.into(), label: label.into(), props: BTreeMap::new() }
}
/// Builder: attach a property.
#[must_use]
pub fn with(mut self, key: impl Into<String>, val: impl Into<String>) -> Self {
self.props.insert(key.into(), val.into());
self
}
/// A display caption: the `name`/`title` property if present, else the id.
#[must_use]
pub fn caption(&self) -> &str {
self.props.get("name").or_else(|| self.props.get("title")).map(String::as_str).unwrap_or(&self.id)
}
}
/// A directed relationship: `from → to` by node id, a relationship `etype`
/// (e.g. `KNOWS`), and a property bag.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Edge {
pub from: String,
pub to: String,
pub etype: String,
pub props: BTreeMap<String, String>,
}
impl Edge {
pub fn new(from: impl Into<String>, to: impl Into<String>, etype: impl Into<String>) -> Self {
Self { from: from.into(), to: to.into(), etype: etype.into(), props: BTreeMap::new() }
}
#[must_use]
pub fn with(mut self, key: impl Into<String>, val: impl Into<String>) -> Self {
self.props.insert(key.into(), val.into());
self
}
}
/// The whole property graph: nodes + directed edges.
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
pub struct PropGraph {
pub nodes: Vec<Node>,
pub edges: Vec<Edge>,
}
impl PropGraph {
#[must_use]
pub fn new() -> Self {
Self::default()
}
/// Add a node (chainable).
pub fn add_node(&mut self, n: Node) -> &mut Self {
self.nodes.push(n);
self
}
/// Add an edge (chainable).
pub fn add_edge(&mut self, e: Edge) -> &mut Self {
self.edges.push(e);
self
}
/// The index of node `id`, if present. **A LINEAR SCAN** — fine for the one-off
/// lookups (a selection, a path endpoint, a hover), wrong inside a loop over the
/// graph: see [`index_map`](Self::index_map).
#[must_use]
pub fn index_of(&self, id: &str) -> Option<usize> {
self.nodes.iter().position(|n| n.id == id)
}
/// **The id → index map, in one pass.** The bulk form of
/// [`index_of`](Self::index_of), and the one a per-frame loop must use.
///
/// `index_of` is `nodes.iter().position(..)`, so resolving both endpoints of every
/// edge with it is `O(V · E)` string compares — per frame. MEASURED on oden
/// 2026-09-03: korp's navigator on the live 89 130-node / 91 998-edge Sweden road
/// slice did exactly that twice a frame (~1.6·10^10 compares) and the host stopped
/// repainting. Same idiom [`edge_indices`](Self::edge_indices) already used;
/// `tests/render_index_scales.rs` holds the budget.
#[must_use]
pub fn index_map(&self) -> std::collections::HashMap<&str, usize> {
self.nodes.iter().enumerate().map(|(i, n)| (n.id.as_str(), i)).collect()
}
/// **The undirected adjacency, in one pass** — the bulk form of
/// [`neighbours`](Self::neighbours), with the same de-duplication and the same
/// both-directions rule. `neighbours` walks every edge for ONE node, so a degree
/// per node costs `O(V · E)`; this costs `O(E)` for all of them.
#[must_use]
pub fn adjacency(&self) -> std::collections::HashMap<&str, Vec<&str>> {
let mut adj: std::collections::HashMap<&str, Vec<&str>> = std::collections::HashMap::new();
for e in &self.edges {
let (f, t) = (e.from.as_str(), e.to.as_str());
let out = adj.entry(f).or_default();
if !out.contains(&t) {
out.push(t);
}
let inc = adj.entry(t).or_default();
if !inc.contains(&f) {
inc.push(f);
}
}
adj
}
/// The node with `id`, if present.
#[must_use]
pub fn node(&self, id: &str) -> Option<&Node> {
self.nodes.iter().find(|n| n.id == id)
}
/// The **index-based edge list** `(from_idx, to_idx)` — the shape
/// [`facett_graphview::analysis`] consumes. Edges referencing missing nodes are
/// dropped.
#[must_use]
pub fn edge_indices(&self) -> Vec<(usize, usize)> {
let idx: BTreeMap<&str, usize> = self.nodes.iter().enumerate().map(|(i, n)| (n.id.as_str(), i)).collect();
self.edges.iter().filter_map(|e| Some((*idx.get(e.from.as_str())?, *idx.get(e.to.as_str())?))).collect()
}
/// Direct neighbours of `id` (undirected: both out- and in-edges), as node ids.
#[must_use]
pub fn neighbours(&self, id: &str) -> Vec<String> {
let mut out = Vec::new();
for e in &self.edges {
if e.from == id && !out.contains(&e.to) {
out.push(e.to.clone());
}
if e.to == id && !out.contains(&e.from) {
out.push(e.from.clone());
}
}
out
}
/// The **schema**: distinct node labels + edge types with counts, and the observed
/// `(from-label) -[type]-> (to-label)` relationship triples — the entity-
/// relationship overview.
#[must_use]
pub fn schema(&self) -> Schema {
let mut node_labels: BTreeMap<String, usize> = BTreeMap::new();
for n in &self.nodes {
*node_labels.entry(n.label.clone()).or_default() += 1;
}
let mut edge_types: BTreeMap<String, usize> = BTreeMap::new();
let mut triples: BTreeMap<(String, String, String), usize> = BTreeMap::new();
// ONE id index, not a `node(&id)` linear scan per endpoint per edge — that was
// `O(V · E)`, and `GraphNav::render` calls this EVERY FRAME. MEASURED on oden
// 2026-09-03: on the live 89 130-node Sweden road slice the main thread sat in
// `PropGraph::schema` → `__memcmp_avx2_movbe` and the pane stopped repainting.
let idx = self.index_map();
for e in &self.edges {
*edge_types.entry(e.etype.clone()).or_default() += 1;
let f = idx.get(e.from.as_str()).and_then(|&i| self.nodes.get(i));
let t = idx.get(e.to.as_str()).and_then(|&i| self.nodes.get(i));
if let (Some(f), Some(t)) = (f, t) {
*triples.entry((f.label.clone(), e.etype.clone(), t.label.clone())).or_default() += 1;
}
}
Schema {
node_labels,
edge_types,
triples: triples.into_iter().map(|((f, t, to), c)| SchemaTriple { from: f, etype: t, to, count: c }).collect(),
}
}
/// A self-contained **demo social graph**: people who KNOW each other, WORK_AT
/// companies, in two clusters bridged by one edge — exercises labels, properties,
/// communities, paths, and the schema.
#[must_use]
pub fn demo() -> Self {
let mut g = PropGraph::new();
let people = [
("p1", "Alice", "42"),
("p2", "Bob", "35"),
("p3", "Carol", "29"),
("p4", "Dan", "51"),
("p5", "Eve", "38"),
("p6", "Frank", "44"),
];
for (id, name, age) in people {
g.add_node(Node::new(id, "Person").with("name", name).with("age", age));
}
g.add_node(Node::new("c1", "Company").with("name", "Acme"));
g.add_node(Node::new("c2", "Company").with("name", "Globex"));
// Cluster A: p1-p2-p3 triangle.
g.add_edge(Edge::new("p1", "p2", "KNOWS").with("since", "2019"));
g.add_edge(Edge::new("p2", "p3", "KNOWS").with("since", "2020"));
g.add_edge(Edge::new("p3", "p1", "KNOWS").with("since", "2021"));
// Cluster B: p4-p5-p6 triangle.
g.add_edge(Edge::new("p4", "p5", "KNOWS").with("since", "2018"));
g.add_edge(Edge::new("p5", "p6", "KNOWS").with("since", "2022"));
g.add_edge(Edge::new("p6", "p4", "KNOWS").with("since", "2017"));
// Bridge between the clusters.
g.add_edge(Edge::new("p3", "p4", "KNOWS").with("since", "2023"));
// Employment.
g.add_edge(Edge::new("p1", "c1", "WORKS_AT"));
g.add_edge(Edge::new("p2", "c1", "WORKS_AT"));
g.add_edge(Edge::new("p4", "c2", "WORKS_AT"));
g.add_edge(Edge::new("p5", "c2", "WORKS_AT"));
g
}
}
/// The graph **schema** / entity-relationship overview.
#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
pub struct Schema {
/// Node label → count.
pub node_labels: BTreeMap<String, usize>,
/// Edge type → count.
pub edge_types: BTreeMap<String, usize>,
/// Observed `(from-label) -[type]-> (to-label)` triples with counts.
pub triples: Vec<SchemaTriple>,
}
/// One entity-relationship triple in the [`Schema`].
#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
pub struct SchemaTriple {
pub from: String,
pub etype: String,
pub to: String,
pub count: usize,
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn demo_graph_has_people_companies_and_bridges() {
let g = PropGraph::demo();
assert_eq!(g.nodes.len(), 8);
assert!(g.edges.len() >= 11);
assert_eq!(g.node("p1").unwrap().caption(), "Alice");
// Undirected neighbours of the bridge node p3: p2, p1, p4.
let mut nb = g.neighbours("p3");
nb.sort();
assert_eq!(nb, vec!["p1", "p2", "p4"]);
}
#[test]
fn edge_indices_map_to_the_analysis_shape() {
let g = PropGraph::demo();
let idx = g.edge_indices();
assert_eq!(idx.len(), g.edges.len(), "every demo edge references live nodes");
// Feed straight into the analysis toolbox: two KNOWS-triangles + a bridge.
let comps = facett_graphview::analysis::components::connected(
&facett_graphview::analysis::Adjacency::from_edges(g.nodes.len(), &idx),
);
assert_eq!(comps.count, 1, "the demo graph is one connected component");
}
#[test]
fn schema_extracts_labels_types_and_triples() {
let g = PropGraph::demo();
let s = g.schema();
assert_eq!(s.node_labels["Person"], 6);
assert_eq!(s.node_labels["Company"], 2);
assert!(s.edge_types.contains_key("KNOWS"));
assert!(s.edge_types.contains_key("WORKS_AT"));
// (Person)-[WORKS_AT]->(Company) is an observed triple.
assert!(s
.triples
.iter()
.any(|t| t.from == "Person" && t.etype == "WORKS_AT" && t.to == "Company"));
}
#[test]
fn roundtrips_through_serde() {
let g = PropGraph::demo();
let j = serde_json::to_string(&g).unwrap();
let back: PropGraph = serde_json::from_str(&j).unwrap();
assert_eq!(back, g);
}
}