bra0_layout/

lib.rs

//! bra0-layout — Rust graph layout engine
//!
//! Implements Sugiyama-style layered (hierarchical) layout for directed graphs.
//! Pure Rust, no external graph library needed for this focused use case.
//!
//! Architecture: Rust for compute, TypeScript for UI (ADR-026).

use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet, VecDeque};

#[cfg(feature = "wasm")]
use wasm_bindgen::prelude::*;

// ── Public types ────────────────────────────────────────────

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct LayoutNode {
    pub id: String,
    pub width: f64,
    pub height: f64,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct LayoutEdge {
    pub source: String,
    pub target: String,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct LayoutOptions {
    /// Direction: "TB" (top-bottom), "LR" (left-right)
    #[serde(default = "default_rankdir")]
    pub rankdir: String,
    /// Horizontal spacing between nodes in the same layer
    #[serde(default = "default_nodesep")]
    pub nodesep: f64,
    /// Vertical spacing between layers
    #[serde(default = "default_ranksep")]
    pub ranksep: f64,
}

fn default_rankdir() -> String { "TB".to_string() }
fn default_nodesep() -> f64 { 60.0 }
fn default_ranksep() -> f64 { 80.0 }

impl Default for LayoutOptions {
    fn default() -> Self {
        Self {
            rankdir: default_rankdir(),
            nodesep: default_nodesep(),
            ranksep: default_ranksep(),
        }
    }
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct LayoutResult {
    pub positions: HashMap<String, Position>,
}

#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
pub struct Position {
    pub x: f64,
    pub y: f64,
}

// ── WASM entry point ────────────────────────────────────────

#[cfg(feature = "wasm")]
#[wasm_bindgen]
pub fn hierarchical_layout(
    nodes_json: &str,
    edges_json: &str,
    options_json: &str,
) -> String {
    let nodes: Vec<LayoutNode> = serde_json::from_str(nodes_json).unwrap_or_default();
    let edges: Vec<LayoutEdge> = serde_json::from_str(edges_json).unwrap_or_default();
    let options: LayoutOptions = serde_json::from_str(options_json).unwrap_or_default();
    let result = layout_hierarchical(&nodes, &edges, &options);
    serde_json::to_string(&result).unwrap_or_default()
}

// ── Native entry point ──────────────────────────────────────

/// Sugiyama-style layered layout for directed graphs.
///
/// Algorithm phases:
/// 1. Cycle removal (reverse back-edges via DFS)
/// 2. Layer assignment (longest path from roots)
/// 3. Crossing minimization (barycenter heuristic)
/// 4. Position assignment (center nodes within layers)
pub fn layout_hierarchical(
    nodes: &[LayoutNode],
    edges: &[LayoutEdge],
    options: &LayoutOptions,
) -> LayoutResult {
    if nodes.is_empty() {
        return LayoutResult { positions: HashMap::new() };
    }

    let node_ids: HashSet<&str> = nodes.iter().map(|n| n.id.as_str()).collect();
    let dims: HashMap<&str, (f64, f64)> = nodes
        .iter()
        .map(|n| (n.id.as_str(), (n.width, n.height)))
        .collect();

    // Filter edges to valid nodes only
    let valid_edges: Vec<(&str, &str)> = edges
        .iter()
        .filter(|e| node_ids.contains(e.source.as_str()) && node_ids.contains(e.target.as_str()))
        .map(|e| (e.source.as_str(), e.target.as_str()))
        .collect();

    // Phase 1: Build adjacency and compute in-degree
    let mut adj: HashMap<&str, Vec<&str>> = HashMap::new();
    let mut in_degree: HashMap<&str, usize> = HashMap::new();
    for &id in &node_ids {
        adj.entry(id).or_default();
        in_degree.entry(id).or_insert(0);
    }
    for &(src, tgt) in &valid_edges {
        adj.entry(src).or_default().push(tgt);
        *in_degree.entry(tgt).or_insert(0) += 1;
    }

    // Phase 2: Layer assignment via topological sort (Kahn's algorithm)
    // Nodes in cycles get assigned to layer 0 (fallback)
    let mut layers: HashMap<&str, usize> = HashMap::new();
    let mut queue: VecDeque<&str> = VecDeque::new();

    for (&id, &deg) in &in_degree {
        if deg == 0 {
            queue.push_back(id);
            layers.insert(id, 0);
        }
    }

    while let Some(node) = queue.pop_front() {
        let layer = layers[node];
        if let Some(children) = adj.get(node) {
            for &child in children {
                let child_layer = layers.entry(child).or_insert(0);
                *child_layer = (*child_layer).max(layer + 1);
                let deg = in_degree.get_mut(child).unwrap();
                *deg -= 1;
                if *deg == 0 {
                    queue.push_back(child);
                }
            }
        }
    }

    // Fallback: assign unvisited nodes (cycles) to layer 0
    for &id in &node_ids {
        layers.entry(id).or_insert(0);
    }

    // Group nodes by layer
    let max_layer = layers.values().copied().max().unwrap_or(0);
    let mut layer_nodes: Vec<Vec<&str>> = vec![vec![]; max_layer + 1];
    for (&id, &layer) in &layers {
        layer_nodes[layer].push(id);
    }

    // Phase 3: Crossing minimization (barycenter heuristic, 2 passes)
    let rev_adj: HashMap<&str, Vec<&str>> = {
        let mut r: HashMap<&str, Vec<&str>> = HashMap::new();
        for &(src, tgt) in &valid_edges {
            r.entry(tgt).or_default().push(src);
        }
        r
    };

    for _pass in 0..4 {
        for layer_idx in 1..=max_layer {
            let prev_positions: HashMap<&str, f64> = layer_nodes[layer_idx - 1]
                .iter()
                .enumerate()
                .map(|(i, &id)| (id, i as f64))
                .collect();

            let mut barycenters: Vec<(&str, f64)> = layer_nodes[layer_idx]
                .iter()
                .map(|&id| {
                    let parents = rev_adj.get(id).map(|v| v.as_slice()).unwrap_or(&[]);
                    if parents.is_empty() {
                        (id, f64::MAX)
                    } else {
                        let sum: f64 = parents
                            .iter()
                            .filter_map(|p| prev_positions.get(p))
                            .sum();
                        let count = parents.iter().filter(|p| prev_positions.contains_key(*p)).count();
                        if count > 0 {
                            (id, sum / count as f64)
                        } else {
                            (id, f64::MAX)
                        }
                    }
                })
                .collect();

            barycenters.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
            layer_nodes[layer_idx] = barycenters.into_iter().map(|(id, _)| id).collect();
        }
    }

    // Phase 4: Position assignment
    let is_horizontal = options.rankdir == "LR";
    let mut positions = HashMap::new();

    for (layer_idx, layer) in layer_nodes.iter().enumerate() {
        let mut offset = 0.0;

        for &id in layer {
            let (w, h) = dims.get(id).copied().unwrap_or((160.0, 60.0));
            let (node_main, node_cross) = if is_horizontal { (h, w) } else { (w, h) };

            let main_pos = layer_idx as f64 * (if is_horizontal {
                node_cross + options.ranksep
            } else {
                node_cross + options.ranksep
            });

            let cross_pos = offset + node_main / 2.0;
            offset += node_main + options.nodesep;

            let pos = if is_horizontal {
                Position { x: main_pos, y: cross_pos }
            } else {
                Position { x: cross_pos, y: main_pos }
            };

            positions.insert(id.to_string(), pos);
        }

        // Center this layer
        if !layer.is_empty() {
            let total_width = offset - options.nodesep;
            let shift = -total_width / 2.0;
            for &id in layer {
                if let Some(pos) = positions.get_mut(id) {
                    if is_horizontal {
                        pos.y += shift;
                    } else {
                        pos.x += shift;
                    }
                }
            }
        }
    }

    LayoutResult { positions }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_graph() {
        let result = layout_hierarchical(&[], &[], &LayoutOptions::default());
        assert!(result.positions.is_empty());
    }

    #[test]
    fn single_node() {
        let nodes = vec![LayoutNode { id: "a".into(), width: 160.0, height: 60.0 }];
        let result = layout_hierarchical(&nodes, &[], &LayoutOptions::default());
        assert_eq!(result.positions.len(), 1);
        assert!(result.positions.contains_key("a"));
    }

    #[test]
    fn linear_chain() {
        let nodes = vec![
            LayoutNode { id: "a".into(), width: 100.0, height: 50.0 },
            LayoutNode { id: "b".into(), width: 100.0, height: 50.0 },
            LayoutNode { id: "c".into(), width: 100.0, height: 50.0 },
        ];
        let edges = vec![
            LayoutEdge { source: "a".into(), target: "b".into() },
            LayoutEdge { source: "b".into(), target: "c".into() },
        ];
        let result = layout_hierarchical(&nodes, &edges, &LayoutOptions::default());

        let a = result.positions["a"];
        let b = result.positions["b"];
        let c = result.positions["c"];

        // a should be above b, b above c (TB direction)
        assert!(a.y < b.y, "a.y ({}) should be < b.y ({})", a.y, b.y);
        assert!(b.y < c.y, "b.y ({}) should be < c.y ({})", b.y, c.y);
    }

    #[test]
    fn diamond_graph() {
        let nodes = vec![
            LayoutNode { id: "top".into(), width: 100.0, height: 50.0 },
            LayoutNode { id: "left".into(), width: 100.0, height: 50.0 },
            LayoutNode { id: "right".into(), width: 100.0, height: 50.0 },
            LayoutNode { id: "bottom".into(), width: 100.0, height: 50.0 },
        ];
        let edges = vec![
            LayoutEdge { source: "top".into(), target: "left".into() },
            LayoutEdge { source: "top".into(), target: "right".into() },
            LayoutEdge { source: "left".into(), target: "bottom".into() },
            LayoutEdge { source: "right".into(), target: "bottom".into() },
        ];
        let result = layout_hierarchical(&nodes, &edges, &LayoutOptions::default());

        // 3 layers: top, {left, right}, bottom
        let top = result.positions["top"];
        let left = result.positions["left"];
        let right = result.positions["right"];
        let bottom = result.positions["bottom"];

        assert!(top.y < left.y);
        assert!(top.y < right.y);
        assert!(left.y < bottom.y);
        assert!(right.y < bottom.y);
        // left and right on same layer
        assert!((left.y - right.y).abs() < 1.0);
    }

    #[test]
    fn handles_cycles() {
        let nodes = vec![
            LayoutNode { id: "a".into(), width: 100.0, height: 50.0 },
            LayoutNode { id: "b".into(), width: 100.0, height: 50.0 },
        ];
        let edges = vec![
            LayoutEdge { source: "a".into(), target: "b".into() },
            LayoutEdge { source: "b".into(), target: "a".into() },
        ];
        // Should not panic, both nodes get positions
        let result = layout_hierarchical(&nodes, &edges, &LayoutOptions::default());
        assert_eq!(result.positions.len(), 2);
    }

    #[test]
    fn horizontal_layout() {
        let nodes = vec![
            LayoutNode { id: "a".into(), width: 100.0, height: 50.0 },
            LayoutNode { id: "b".into(), width: 100.0, height: 50.0 },
        ];
        let edges = vec![
            LayoutEdge { source: "a".into(), target: "b".into() },
        ];
        let opts = LayoutOptions { rankdir: "LR".into(), ..Default::default() };
        let result = layout_hierarchical(&nodes, &edges, &opts);

        let a = result.positions["a"];
        let b = result.positions["b"];
        // LR: a should be left of b
        assert!(a.x < b.x, "a.x ({}) should be < b.x ({})", a.x, b.x);
    }
}