Something went wrong. Try again.
inkfinite (an infinite canvas/whiteboard) monorepo ink.stormlightlabs.org
svelte rust tauri svg canvas perfect-freehand
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430//! Deterministic graph-layout contracts and the native layout adapter.//!//! The document engine owns the graph representation and the normalized result.//! The placement implementation is deliberately kept behind this module so a//! Graphviz adapter can replace it without leaking DOT or engine-specific data//! into document records.
use std::collections::{BTreeMap, BTreeSet, VecDeque};use std::f64::consts::TAU;
use schemars::JsonSchema;use serde::{Deserialize, Serialize};use ts_rs::TS;
use crate::{ShapeId, Vec2};
/// Graph layout algorithm exposed by Inkfinite.#[derive(Clone, Copy, Debug, Eq, JsonSchema, PartialEq, Serialize, Deserialize, TS)]#[serde(rename_all = "snake_case")]pub enum GraphLayoutAlgorithm { /// Layer a directed graph by rank. Flow, /// Layer a directed graph with tree-oriented stable ordering. Tree, /// Place graph ranks on concentric circles. Radial,}
/// Direction of ranked graph layouts.#[derive(Clone, Copy, Debug, Eq, JsonSchema, PartialEq, Serialize, Deserialize, TS)]#[serde(rename_all = "snake_case")]pub enum GraphLayoutDirection { /// Sources appear above their targets. TopToBottom, /// Sources appear to the left of their targets. LeftToRight,}
/// Options shared by graph layout operations.#[derive(Clone, Copy, Debug, JsonSchema, PartialEq, Serialize, Deserialize, TS)]pub struct GraphLayoutOptions { /// Layout algorithm to use. pub algorithm: GraphLayoutAlgorithm, /// Direction for ranked layouts. pub direction: GraphLayoutDirection, /// Space between adjacent nodes in one rank or radial ring. pub node_gap: f64, /// Space between ranked rows or radial rings. pub rank_gap: f64,}
impl Default for GraphLayoutOptions { fn default() -> Self { Self { algorithm: GraphLayoutAlgorithm::Flow, direction: GraphLayoutDirection::TopToBottom, node_gap: 64.0, rank_gap: 96.0, } }}
/// A measured graph node. Positions are returned separately from dimensions.#[derive(Clone, Debug, JsonSchema, PartialEq, Serialize, Deserialize, TS)]pub struct GraphLayoutNode { /// Stable shape identifier. pub id: ShapeId, /// World-space width of the shape's measured bounds. pub width: f64, /// World-space height of the shape's measured bounds. pub height: f64, /// Whether the node is a fixed layout anchor. pub locked: bool,}
/// A directed structured connection between two selected nodes.#[derive(Clone, Debug, Eq, JsonSchema, Ord, PartialEq, PartialOrd, Serialize, Deserialize, TS)]pub struct GraphLayoutEdge { /// Source node identifier. pub source: ShapeId, /// Target node identifier. pub target: ShapeId,}
/// Engine-neutral graph passed to the layout adapter.#[derive(Clone, Debug, JsonSchema, PartialEq, Serialize, Deserialize, TS)]pub struct GraphLayoutGraph { /// Nodes in stable identifier order. pub nodes: Vec<GraphLayoutNode>, /// Directed edges in stable source/target order. pub edges: Vec<GraphLayoutEdge>,}
/// Normalized node placement returned by a graph layout adapter.#[derive(Clone, Debug, JsonSchema, PartialEq, Serialize, Deserialize, TS)]pub struct GraphLayoutResult { /// Top-left world positions relative to the result origin. pub positions: BTreeMap<ShapeId, Vec2>,}
/// Lays out an internal graph without retaining graph-engine state in a document.////// The current adapter provides deterministic ranked and radial placement. Its/// input and output are intentionally independent of DOT so native and browser/// Graphviz adapters can use the same contract when available.////// # Errors////// Returns an error when the graph is empty, has duplicate or missing endpoints,/// contains invalid dimensions, or uses invalid spacing.pub fn layout_graph(graph: &GraphLayoutGraph, options: GraphLayoutOptions) -> Result<GraphLayoutResult, String> { validate_graph(graph, options)?; let positions = match options.algorithm { GraphLayoutAlgorithm::Flow | GraphLayoutAlgorithm::Tree => ranked_positions(graph, options), GraphLayoutAlgorithm::Radial => radial_positions(graph, options), }; Ok(GraphLayoutResult { positions: normalize_positions(positions) })}
fn validate_graph(graph: &GraphLayoutGraph, options: GraphLayoutOptions) -> Result<(), String> { if graph.nodes.is_empty() { return Err("graph layout requires at least one node".into()); } if !options.node_gap.is_finite() || options.node_gap < 0.0 { return Err("graph node gap must be finite and non-negative".into()); } if !options.rank_gap.is_finite() || options.rank_gap < 0.0 { return Err("graph rank gap must be finite and non-negative".into()); } let mut ids = BTreeSet::new(); for node in &graph.nodes { if !node.width.is_finite() || node.width < 0.0 || !node.height.is_finite() || node.height < 0.0 { return Err(format!("graph node {} has invalid dimensions", node.id)); } if !ids.insert(node.id.clone()) { return Err(format!("graph layout contains duplicate node {}", node.id)); } } for edge in &graph.edges { if !ids.contains(&edge.source) || !ids.contains(&edge.target) { return Err(format!( "graph edge {} -> {} refers to a node outside the graph", edge.source, edge.target )); } } Ok(())}
fn ranked_positions(graph: &GraphLayoutGraph, options: GraphLayoutOptions) -> BTreeMap<ShapeId, Vec2> { let node_ids = graph.nodes.iter().map(|node| node.id.clone()).collect::<Vec<_>>(); let index = node_ids .iter() .enumerate() .map(|(index, id)| (id.clone(), index)) .collect::<BTreeMap<_, _>>(); let mut outgoing = vec![Vec::new(); node_ids.len()]; for edge in &graph.edges { let source = index[&edge.source]; let target = index[&edge.target]; if source != target && !outgoing[source].contains(&target) { outgoing[source].push(target); } } for targets in &mut outgoing { targets.sort_by(|left, right| node_ids[*left].cmp(&node_ids[*right])); } let components = strongly_connected_components(&outgoing); let component_count = components.iter().copied().max().map_or(0, |value| value + 1); let mut component_edges = vec![BTreeSet::new(); component_count]; let mut indegree = vec![0usize; component_count]; for (source, targets) in outgoing.iter().enumerate() { for target in targets { let source_component = components[source]; let target_component = components[*target]; if source_component != target_component && component_edges[source_component].insert(target_component) { indegree[target_component] += 1; } } } let mut queue = BTreeSet::new(); for (component, degree) in indegree.iter().enumerate() { if *degree == 0 { queue.insert(component); } } let mut component_rank = vec![0usize; component_count]; while let Some(component) = queue.pop_first() { for target in &component_edges[component] { component_rank[*target] = component_rank[*target].max(component_rank[component] + 1); indegree[*target] -= 1; if indegree[*target] == 0 { queue.insert(*target); } } }
let mut ranks: BTreeMap<usize, Vec<usize>> = BTreeMap::new(); for (node, component) in components.iter().enumerate() { ranks.entry(component_rank[*component]).or_default().push(node); } for nodes in ranks.values_mut() { nodes.sort_by(|left, right| node_ids[*left].cmp(&node_ids[*right])); }
let mut positions = BTreeMap::new(); let mut rank_cursor = 0.0; for nodes in ranks.values() { let rank_extent = nodes .iter() .map(|node| match options.direction { GraphLayoutDirection::TopToBottom => graph.nodes[*node].height, GraphLayoutDirection::LeftToRight => graph.nodes[*node].width, }) .fold(0.0, f64::max); let mut cross_cursor = 0.0; for node in nodes { let extent = match options.direction { GraphLayoutDirection::TopToBottom => graph.nodes[*node].width, GraphLayoutDirection::LeftToRight => graph.nodes[*node].height, }; let offset = match options.direction { GraphLayoutDirection::TopToBottom => Vec2 { x: cross_cursor, y: rank_cursor }, GraphLayoutDirection::LeftToRight => Vec2 { x: rank_cursor, y: cross_cursor }, }; positions.insert(node_ids[*node].clone(), offset); cross_cursor += extent + options.node_gap; } rank_cursor += rank_extent + options.rank_gap; } positions}
fn radial_positions(graph: &GraphLayoutGraph, options: GraphLayoutOptions) -> BTreeMap<ShapeId, Vec2> { let node_ids = graph.nodes.iter().map(|node| node.id.clone()).collect::<Vec<_>>(); let index = node_ids .iter() .enumerate() .map(|(index, id)| (id.clone(), index)) .collect::<BTreeMap<_, _>>(); let mut outgoing = vec![Vec::new(); node_ids.len()]; for edge in &graph.edges { let source = index[&edge.source]; let target = index[&edge.target]; if source != target && !outgoing[source].contains(&target) { outgoing[source].push(target); } } for targets in &mut outgoing { targets.sort_by(|left, right| node_ids[*left].cmp(&node_ids[*right])); } let mut indegree = vec![0usize; node_ids.len()]; for targets in &outgoing { for target in targets { indegree[*target] += 1; } } let mut depths = vec![None; node_ids.len()]; let mut queue = VecDeque::new(); for (index, degree) in indegree.iter().enumerate() { if *degree == 0 { depths[index] = Some(0usize); queue.push_back(index); } } if queue.is_empty() { depths[0] = Some(0); queue.push_back(0); } while let Some(source) = queue.pop_front() { let depth = depths[source].unwrap_or(0); for target in &outgoing[source] { let next_depth = depth + 1; if depths[*target].is_none() { depths[*target] = Some(next_depth); queue.push_back(*target); } } } for depth in &mut depths { if depth.is_none() { *depth = Some(0); } } let max_dimension = graph .nodes .iter() .map(|node| node.width.max(node.height)) .fold(0.0, f64::max); let radius_step = (max_dimension + options.rank_gap).max(options.node_gap + 1.0); let mut rings: BTreeMap<usize, Vec<usize>> = BTreeMap::new(); for (index, depth) in depths.iter().enumerate() { rings.entry(depth.unwrap_or(0)).or_default().push(index); } for nodes in rings.values_mut() { nodes.sort_by(|left, right| node_ids[*left].cmp(&node_ids[*right])); } let mut positions = BTreeMap::new(); for (depth, nodes) in rings { let radius = radius_step * (depth as f64 + f64::from(nodes.len() > 1)); for (offset, node) in nodes.iter().enumerate() { let angle = -std::f64::consts::FRAC_PI_2 + TAU * offset as f64 / nodes.len() as f64; let center = Vec2 { x: radius * angle.cos(), y: radius * angle.sin() }; positions.insert( node_ids[*node].clone(), Vec2 { x: center.x - graph.nodes[*node].width / 2.0, y: center.y - graph.nodes[*node].height / 2.0 }, ); } } positions}
fn normalize_positions(mut positions: BTreeMap<ShapeId, Vec2>) -> BTreeMap<ShapeId, Vec2> { let min_x = positions .values() .map(|position| position.x) .fold(f64::INFINITY, f64::min); let min_y = positions .values() .map(|position| position.y) .fold(f64::INFINITY, f64::min); for position in positions.values_mut() { position.x -= min_x; position.y -= min_y; } positions}
fn strongly_connected_components(outgoing: &[Vec<usize>]) -> Vec<usize> { let mut reverse = vec![Vec::new(); outgoing.len()]; for (source, targets) in outgoing.iter().enumerate() { for target in targets { reverse[*target].push(source); } } for targets in &mut reverse { targets.sort_unstable(); } let mut visited = vec![false; outgoing.len()]; let mut order = Vec::with_capacity(outgoing.len()); for node in 0..outgoing.len() { depth_first_order(node, outgoing, &mut visited, &mut order); } let mut components = vec![usize::MAX; outgoing.len()]; let mut component = 0; for node in order.into_iter().rev() { if components[node] == usize::MAX { assign_component(node, &reverse, &mut components, component); component += 1; } } components}
fn depth_first_order(node: usize, outgoing: &[Vec<usize>], visited: &mut [bool], order: &mut Vec<usize>) { if visited[node] { return; } visited[node] = true; for target in &outgoing[node] { depth_first_order(*target, outgoing, visited, order); } order.push(node);}
fn assign_component(node: usize, reverse: &[Vec<usize>], components: &mut [usize], component: usize) { if components[node] != usize::MAX { return; } components[node] = component; for target in &reverse[node] { assign_component(*target, reverse, components, component); }}
#[cfg(test)]mod tests { use super::*;
fn node(id: &str, width: f64, height: f64) -> GraphLayoutNode { GraphLayoutNode { id: ShapeId::from(id), width, height, locked: false } }
#[test] fn ranked_layout_is_stable_and_respects_direction() { let graph = GraphLayoutGraph { nodes: vec![node("a", 20.0, 10.0), node("b", 30.0, 12.0), node("c", 10.0, 14.0)], edges: vec![ GraphLayoutEdge { source: ShapeId::from("a"), target: ShapeId::from("b") }, GraphLayoutEdge { source: ShapeId::from("a"), target: ShapeId::from("c") }, ], }; let top_to_bottom = layout_graph(&graph, GraphLayoutOptions::default()).unwrap(); assert_eq!(top_to_bottom.positions[&ShapeId::from("a")].y, 0.0); assert!(top_to_bottom.positions[&ShapeId::from("b")].y > 0.0); assert!(top_to_bottom.positions[&ShapeId::from("c")].y > 0.0);
let left_to_right = layout_graph( &graph, GraphLayoutOptions { direction: GraphLayoutDirection::LeftToRight, ..GraphLayoutOptions::default() }, ) .unwrap(); assert_eq!(left_to_right.positions[&ShapeId::from("a")].x, 0.0); assert!(left_to_right.positions[&ShapeId::from("b")].x > 0.0); }
#[test] fn cycles_and_disconnected_nodes_remain_layoutable() { let graph = GraphLayoutGraph { nodes: vec![node("a", 10.0, 10.0), node("b", 10.0, 10.0), node("c", 10.0, 10.0)], edges: vec![ GraphLayoutEdge { source: ShapeId::from("a"), target: ShapeId::from("b") }, GraphLayoutEdge { source: ShapeId::from("b"), target: ShapeId::from("a") }, ], }; let result = layout_graph( &graph, GraphLayoutOptions { algorithm: GraphLayoutAlgorithm::Tree, ..GraphLayoutOptions::default() }, ) .unwrap(); assert_eq!(result.positions.len(), 3); assert!( result .positions .values() .all(|position| position.x.is_finite() && position.y.is_finite()) ); }}