ara_core/
layout.rs

1//! Deterministic layered DAG layout (Sugiyama method) for `Manifest`.
2//!
3//! Produces node positions + bounding rect via `dagre-dgl-rs`. All computation
4//! is pure and wasm-safe (no threads, filesystem, randomness, or `SystemTime`).
5//! The same input yields byte-identical JSON on native and wasm32 targets.
6
7use dagre_dgl_rs::{EdgeLabel, Graph, GraphLabel, NodeLabel as DagreNodeLabel};
8
9use std::collections::BTreeMap;
10
11use crate::manifest::{Link, Manifest, Node, NodeId};
12
13/// A 2D point (center of a node).
14#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize, serde::Deserialize)]
15pub struct Point {
16    pub x: f64,
17    pub y: f64,
18}
19
20/// An axis-aligned rectangle (bounding box).
21#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize, serde::Deserialize)]
22pub struct Rect {
23    pub x: f64,
24    pub y: f64,
25    pub width: f64,
26    pub height: f64,
27}
28
29/// Configuration knobs for layout. All values are pinned for determinism.
30#[derive(Debug, Clone)]
31pub struct LayoutOptions {
32    /// Width of every node box (px). Default: 180.
33    pub node_width: f64,
34    /// Height of every node box (px). Default: 60.
35    pub node_height: f64,
36    /// Minimum separation between adjacent nodes in the same rank. Default: 50.
37    pub node_sep: f64,
38    /// Minimum separation between adjacent ranks. Default: 50.
39    pub rank_sep: f64,
40}
41
42impl Default for LayoutOptions {
43    fn default() -> Self {
44        Self {
45            node_width: 180.0,
46            node_height: 60.0,
47            node_sep: 50.0,
48            rank_sep: 50.0,
49        }
50    }
51}
52
53/// Result of running layout on a manifest.
54#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
55pub struct LayoutResult {
56    pub positions: Vec<NodePosition>,
57    pub bounds: Rect,
58}
59
60/// The computed position for a single node.
61#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
62pub struct NodePosition {
63    pub id: NodeId,
64    pub pos: Point,
65}
66
67/// Computes a layered DAG layout for `manifest` with the given options.
68///
69/// Nodes are inserted in sorted `NodeId` order (the fixed tie-break) so
70/// equal-rank ordering is stable regardless of input shuffling.
71///
72/// # Panics
73///
74/// Debug-asserts that the graph has no cycles (the parse layer already
75/// rejects cycles, so this is a defensive invariant check).
76pub fn layout(manifest: &Manifest, opts: &LayoutOptions) -> LayoutResult {
77    if manifest.nodes.is_empty() {
78        return LayoutResult {
79            positions: Vec::new(),
80            bounds: Rect {
81                x: 0.0,
82                y: 0.0,
83                width: 0.0,
84                height: 0.0,
85            },
86        };
87    }
88
89    let mut g = Graph::default();
90    g.set_graph(GraphLabel {
91        rankdir: Some("TB".to_string()),
92        nodesep: Some(opts.node_sep),
93        ranksep: Some(opts.rank_sep),
94        ..Default::default()
95    });
96
97    // Insert nodes in sorted NodeId order for a stable tie-break.
98    let mut sorted_ids: Vec<&NodeId> = manifest.nodes.iter().map(|n| &n.id).collect();
99    sorted_ids.sort();
100    for id in &sorted_ids {
101        g.set_node(
102            id.as_str(),
103            DagreNodeLabel {
104                width: opts.node_width,
105                height: opts.node_height,
106                ..Default::default()
107            },
108        );
109    }
110
111    // Add edges. Only Child + DependsOn links exist; both are used for ranking.
112    debug_assert!(
113        !has_cycle(&manifest.nodes, &manifest.links),
114        "cycle reached layout — parse should have rejected this"
115    );
116    for link in &manifest.links {
117        g.set_edge(
118            link.from.as_str(),
119            link.to.as_str(),
120            EdgeLabel::default(),
121            None,
122        );
123    }
124
125    dagre_dgl_rs::layout(&mut g);
126
127    // Extract positions and compute bounds.
128    let mut positions = Vec::with_capacity(manifest.nodes.len());
129    let mut min_x = f64::INFINITY;
130    let mut min_y = f64::INFINITY;
131    let mut max_x = f64::NEG_INFINITY;
132    let mut max_y = f64::NEG_INFINITY;
133
134    for node in &manifest.nodes {
135        let nl = g.node(node.id.as_str());
136        let x = canonicalize(nl.x.unwrap_or(0.0));
137        let y = canonicalize(nl.y.unwrap_or(0.0));
138        positions.push(NodePosition {
139            id: node.id.clone(),
140            pos: Point { x, y },
141        });
142
143        let half_w = opts.node_width / 2.0;
144        let half_h = opts.node_height / 2.0;
145        min_x = min_x.min(x - half_w);
146        min_y = min_y.min(y - half_h);
147        max_x = max_x.max(x + half_w);
148        max_y = max_y.max(y + half_h);
149    }
150
151    let bounds = Rect {
152        x: canonicalize(min_x),
153        y: canonicalize(min_y),
154        width: canonicalize(max_x - min_x),
155        height: canonicalize(max_y - min_y),
156    };
157
158    LayoutResult { positions, bounds }
159}
160
161/// Canonicalize an f64: round to 6 decimal places and normalize -0.0 to 0.0.
162fn canonicalize(v: f64) -> f64 {
163    let rounded = (v * 1_000_000.0).round() / 1_000_000.0;
164    if rounded == 0.0 { 0.0 } else { rounded }
165}
166
167/// Cheap cycle check (DFS three-color). Only used in debug_assert.
168fn has_cycle(nodes: &[Node], links: &[Link]) -> bool {
169    let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
170    for link in links {
171        adj.entry(link.from.as_str())
172            .or_default()
173            .push(link.to.as_str());
174    }
175    let mut color: BTreeMap<&str, u8> = BTreeMap::new();
176    for node in nodes {
177        if color.get(node.id.as_str()).copied().unwrap_or(0) == 0
178            && visit_cycle(node.id.as_str(), &adj, &mut color)
179        {
180            return true;
181        }
182    }
183    false
184}
185
186fn visit_cycle<'a>(
187    u: &'a str,
188    adj: &BTreeMap<&'a str, Vec<&'a str>>,
189    color: &mut BTreeMap<&'a str, u8>,
190) -> bool {
191    color.insert(u, 1);
192    if let Some(neighbors) = adj.get(u) {
193        for &v in neighbors {
194            match color.get(v).copied().unwrap_or(0) {
195                0 => {
196                    if visit_cycle(v, adj, color) {
197                        return true;
198                    }
199                }
200                1 => return true,
201                _ => {}
202            }
203        }
204    }
205    color.insert(u, 2);
206    false
207}
208
209#[cfg(test)]
210mod tests {
211    use super::*;
212    use crate::manifest::{Link, LinkKind, Manifest, Node, NodeFields, NodeId, NodeKind};
213
214    fn simple_manifest() -> Manifest {
215        Manifest {
216            nodes: vec![
217                Node {
218                    id: NodeId::new("N01"),
219                    kind: NodeKind::Question,
220                    label: Some("Q?".into()),
221                    support_level: None,
222                    source_refs: vec![],
223                    description: None,
224                    provenance: None,
225                    timestamp: None,
226                    fields: NodeFields::Question,
227                    evidence_notes: vec![],
228                    isolated: false,
229                    pos: None,
230                },
231                Node {
232                    id: NodeId::new("N02"),
233                    kind: NodeKind::Experiment,
234                    label: Some("Exp".into()),
235                    support_level: None,
236                    source_refs: vec![],
237                    description: None,
238                    provenance: None,
239                    timestamp: None,
240                    fields: NodeFields::Experiment {
241                        result: None,
242                        exploration: None,
243                        outcome: None,
244                        status: None,
245                    },
246                    evidence_notes: vec![],
247                    isolated: false,
248                    pos: None,
249                },
250                Node {
251                    id: NodeId::new("N03"),
252                    kind: NodeKind::Decision,
253                    label: Some("Dec".into()),
254                    support_level: None,
255                    source_refs: vec![],
256                    description: None,
257                    provenance: None,
258                    timestamp: None,
259                    fields: NodeFields::Decision {
260                        choice: None,
261                        alternatives: vec![],
262                        rationale: None,
263                    },
264                    evidence_notes: vec![],
265                    isolated: false,
266                    pos: None,
267                },
268            ],
269            links: vec![
270                Link {
271                    from: NodeId::new("N01"),
272                    to: NodeId::new("N02"),
273                    kind: LinkKind::Child,
274                },
275                Link {
276                    from: NodeId::new("N01"),
277                    to: NodeId::new("N03"),
278                    kind: LinkKind::Child,
279                },
280            ],
281            bindings: vec![],
282            claims: vec![],
283            bounds: None,
284            paper: None,
285            related_work: vec![],
286            concepts: vec![],
287            problem: None,
288            recipes: vec![],
289            exhibits: vec![],
290            built_on: vec![],
291            node_exhibits: vec![],
292        }
293    }
294
295    #[test]
296    fn all_positions_finite() {
297        let m = simple_manifest();
298        let result = layout(&m, &LayoutOptions::default());
299        for np in &result.positions {
300            assert!(np.pos.x.is_finite(), "NaN/inf x for {}", np.id);
301            assert!(np.pos.y.is_finite(), "NaN/inf y for {}", np.id);
302        }
303    }
304
305    #[test]
306    fn ranks_monotonic_along_child_edges() {
307        let m = simple_manifest();
308        let result = layout(&m, &LayoutOptions::default());
309        let pos_map: std::collections::HashMap<&str, &Point> = result
310            .positions
311            .iter()
312            .map(|np| (np.id.as_str(), &np.pos))
313            .collect();
314        for link in &m.links {
315            if link.kind == LinkKind::Child {
316                let from_y = pos_map[link.from.as_str()].y;
317                let to_y = pos_map[link.to.as_str()].y;
318                assert!(
319                    from_y < to_y,
320                    "rank not monotonic: {} (y={}) -> {} (y={})",
321                    link.from,
322                    from_y,
323                    link.to,
324                    to_y
325                );
326            }
327        }
328    }
329
330    #[test]
331    fn tie_break_stable_across_input_order() {
332        let m1 = simple_manifest();
333        let mut m2 = simple_manifest();
334        m2.nodes.reverse(); // shuffle input order
335        let r1 = layout(&m1, &LayoutOptions::default());
336        let r2 = layout(&m2, &LayoutOptions::default());
337        // Positions are returned in manifest.nodes order, so sort by id.
338        let mut p1: Vec<_> = r1.positions.clone();
339        let mut p2: Vec<_> = r2.positions.clone();
340        p1.sort_by(|a, b| a.id.cmp(&b.id));
341        p2.sort_by(|a, b| a.id.cmp(&b.id));
342        assert_eq!(p1, p2);
343        assert_eq!(r1.bounds, r2.bounds);
344    }
345
346    #[test]
347    fn empty_manifest_produces_zero_bounds() {
348        let m = Manifest {
349            nodes: vec![],
350            links: vec![],
351            bindings: vec![],
352            claims: vec![],
353            bounds: None,
354            paper: None,
355            related_work: vec![],
356            concepts: vec![],
357            problem: None,
358            recipes: vec![],
359            exhibits: vec![],
360            built_on: vec![],
361            node_exhibits: vec![],
362        };
363        let result = layout(&m, &LayoutOptions::default());
364        assert!(result.positions.is_empty());
365        assert_eq!(result.bounds.width, 0.0);
366        assert_eq!(result.bounds.height, 0.0);
367    }
368
369    #[test]
370    fn single_node_has_finite_pos_and_enclosing_bounds() {
371        let m = Manifest {
372            nodes: vec![Node {
373                id: NodeId::new("N01"),
374                kind: NodeKind::Question,
375                label: None,
376                support_level: None,
377                source_refs: vec![],
378                description: None,
379                provenance: None,
380                timestamp: None,
381                fields: NodeFields::Question,
382                evidence_notes: vec![],
383                isolated: false,
384                pos: None,
385            }],
386            links: vec![],
387            bindings: vec![],
388            claims: vec![],
389            bounds: None,
390            paper: None,
391            related_work: vec![],
392            concepts: vec![],
393            problem: None,
394            recipes: vec![],
395            exhibits: vec![],
396            built_on: vec![],
397            node_exhibits: vec![],
398        };
399        let opts = LayoutOptions::default();
400        let result = layout(&m, &opts);
401        assert_eq!(result.positions.len(), 1);
402        assert!(result.positions[0].pos.x.is_finite());
403        assert!(result.positions[0].pos.y.is_finite());
404        assert!(result.bounds.width >= opts.node_width);
405        assert!(result.bounds.height >= opts.node_height);
406    }
407
408    #[test]
409    fn bounds_enclose_all_node_rects() {
410        let m = simple_manifest();
411        let opts = LayoutOptions::default();
412        let result = layout(&m, &opts);
413        let half_w = opts.node_width / 2.0;
414        let half_h = opts.node_height / 2.0;
415        for np in &result.positions {
416            assert!(np.pos.x - half_w >= result.bounds.x - 1e-9);
417            assert!(np.pos.y - half_h >= result.bounds.y - 1e-9);
418            assert!(np.pos.x + half_w <= result.bounds.x + result.bounds.width + 1e-9);
419            assert!(np.pos.y + half_h <= result.bounds.y + result.bounds.height + 1e-9);
420        }
421    }
422
423    #[test]
424    fn canonicalize_normalizes_negative_zero() {
425        assert_eq!(canonicalize(-0.0), 0.0);
426        assert_eq!(canonicalize(-0.0).to_bits(), 0.0_f64.to_bits());
427    }
428
429    #[test]
430    fn canonicalize_rounds_to_six_decimals() {
431        let v = 1.23456789;
432        assert_eq!(canonicalize(v), 1.234568);
433    }
434
435    #[test]
436    fn layout_twice_identical() {
437        let m = simple_manifest();
438        let opts = LayoutOptions::default();
439        let r1 = layout(&m, &opts);
440        let r2 = layout(&m, &opts);
441        let j1 = serde_json::to_string(&r1).unwrap();
442        let j2 = serde_json::to_string(&r2).unwrap();
443        assert_eq!(j1, j2);
444    }
445}
ara_core/layout.rs

ara_core/
layout.rs
