proof_engine/graph/
layout.rs

1use glam::Vec2;
2use std::collections::{HashMap, HashSet, VecDeque};
3use super::graph_core::{Graph, GraphKind, NodeId};
4
5#[derive(Debug, Clone, Copy, PartialEq)]
6pub enum LayoutAlgorithm {
7    ForceDirected,
8    Hierarchical,
9    Circular,
10    Spectral,
11    Tree,
12    Random,
13    Grid,
14}
15
16#[derive(Debug, Clone)]
17pub struct LayoutConfig {
18    pub iterations: usize,
19    pub spacing: f32,
20    pub bounds: Vec2,
21    pub seed: u64,
22    pub temperature: f32,
23    pub cooling_factor: f32,
24}
25
26impl Default for LayoutConfig {
27    fn default() -> Self {
28        Self {
29            iterations: 300,
30            spacing: 50.0,
31            bounds: Vec2::new(800.0, 600.0),
32            seed: 42,
33            temperature: 100.0,
34            cooling_factor: 0.95,
35        }
36    }
37}
38
39pub fn compute_layout<N, E>(graph: &Graph<N, E>, algorithm: LayoutAlgorithm, config: &LayoutConfig) -> HashMap<NodeId, Vec2> {
40    match algorithm {
41        LayoutAlgorithm::ForceDirected => {
42            let mut fl = ForceDirectedLayout::new(config.clone());
43            fl.compute(graph)
44        }
45        LayoutAlgorithm::Hierarchical => {
46            let mut hl = HierarchicalLayout::new(config.clone());
47            hl.compute(graph)
48        }
49        LayoutAlgorithm::Circular => {
50            CircularLayout::new(config.clone()).compute(graph)
51        }
52        LayoutAlgorithm::Spectral => {
53            SpectralLayout::new(config.clone()).compute(graph)
54        }
55        LayoutAlgorithm::Tree => {
56            TreeLayout::new(config.clone()).compute(graph)
57        }
58        LayoutAlgorithm::Random => {
59            random_layout(graph, config)
60        }
61        LayoutAlgorithm::Grid => {
62            grid_layout(graph, config)
63        }
64    }
65}
66
67fn pseudo_random(seed: u64, i: u64) -> f64 {
68    let mut x = seed.wrapping_mul(6364136223846793005).wrapping_add(i.wrapping_mul(1442695040888963407));
69    x ^= x >> 33;
70    x = x.wrapping_mul(0xff51afd7ed558ccd);
71    x ^= x >> 33;
72    (x as f64) / (u64::MAX as f64)
73}
74
75fn random_layout<N, E>(graph: &Graph<N, E>, config: &LayoutConfig) -> HashMap<NodeId, Vec2> {
76    let mut positions = HashMap::new();
77    for (i, nid) in graph.node_ids().iter().enumerate() {
78        let x = pseudo_random(config.seed, i as u64 * 2) as f32 * config.bounds.x;
79        let y = pseudo_random(config.seed, i as u64 * 2 + 1) as f32 * config.bounds.y;
80        positions.insert(*nid, Vec2::new(x, y));
81    }
82    positions
83}
84
85fn grid_layout<N, E>(graph: &Graph<N, E>, config: &LayoutConfig) -> HashMap<NodeId, Vec2> {
86    let mut positions = HashMap::new();
87    let n = graph.node_count();
88    if n == 0 { return positions; }
89    let cols = (n as f32).sqrt().ceil() as usize;
90    let spacing = config.spacing;
91    let offset = Vec2::new(
92        config.bounds.x / 2.0 - (cols as f32 * spacing) / 2.0,
93        config.bounds.y / 2.0 - ((n / cols + 1) as f32 * spacing) / 2.0,
94    );
95    for (i, nid) in graph.node_ids().iter().enumerate() {
96        let row = i / cols;
97        let col = i % cols;
98        positions.insert(*nid, Vec2::new(
99            offset.x + col as f32 * spacing,
100            offset.y + row as f32 * spacing,
101        ));
102    }
103    positions
104}
105
106// ---- Force-Directed Layout (Fruchterman-Reingold) ----
107
108pub struct ForceDirectedLayout {
109    config: LayoutConfig,
110}
111
112impl ForceDirectedLayout {
113    pub fn new(config: LayoutConfig) -> Self {
114        Self { config }
115    }
116
117    pub fn compute<N, E>(&mut self, graph: &Graph<N, E>) -> HashMap<NodeId, Vec2> {
118        let node_ids = graph.node_ids();
119        let n = node_ids.len();
120        if n == 0 { return HashMap::new(); }
121
122        let area = self.config.bounds.x * self.config.bounds.y;
123        let k = (area / n as f32).sqrt(); // optimal distance
124
125        // Initialize positions
126        let mut positions: HashMap<NodeId, Vec2> = HashMap::new();
127        for (i, &nid) in node_ids.iter().enumerate() {
128            let x = pseudo_random(self.config.seed, i as u64 * 2) as f32 * self.config.bounds.x;
129            let y = pseudo_random(self.config.seed, i as u64 * 2 + 1) as f32 * self.config.bounds.y;
130            positions.insert(nid, Vec2::new(x, y));
131        }
132
133        let mut temperature = self.config.temperature;
134
135        for _iter in 0..self.config.iterations {
136            let mut displacements: HashMap<NodeId, Vec2> = HashMap::new();
137            for &nid in &node_ids {
138                displacements.insert(nid, Vec2::ZERO);
139            }
140
141            // Repulsive forces between all pairs
142            for i in 0..n {
143                for j in (i + 1)..n {
144                    let ni = node_ids[i];
145                    let nj = node_ids[j];
146                    let pi = positions[&ni];
147                    let pj = positions[&nj];
148                    let delta = pi - pj;
149                    let dist = delta.length().max(0.01);
150                    let repulsion = k * k / dist;
151                    let force = delta / dist * repulsion;
152                    *displacements.get_mut(&ni).unwrap() += force;
153                    *displacements.get_mut(&nj).unwrap() -= force;
154                }
155            }
156
157            // Attractive forces along edges
158            for edge in graph.edges() {
159                let pi = positions[&edge.from];
160                let pj = positions[&edge.to];
161                let delta = pi - pj;
162                let dist = delta.length().max(0.01);
163                let attraction = dist * dist / k;
164                let force = delta / dist * attraction;
165                *displacements.get_mut(&edge.from).unwrap() -= force;
166                *displacements.get_mut(&edge.to).unwrap() += force;
167            }
168
169            // Apply displacements with temperature limiting
170            for &nid in &node_ids {
171                let disp = displacements[&nid];
172                let len = disp.length().max(0.01);
173                let clamped = disp / len * len.min(temperature);
174                let mut pos = positions[&nid] + clamped;
175                // Clamp to bounds
176                pos.x = pos.x.clamp(0.0, self.config.bounds.x);
177                pos.y = pos.y.clamp(0.0, self.config.bounds.y);
178                positions.insert(nid, pos);
179            }
180
181            temperature *= self.config.cooling_factor;
182        }
183
184        positions
185    }
186}
187
188// ---- Hierarchical Layout (Sugiyama-style) ----
189
190pub struct HierarchicalLayout {
191    config: LayoutConfig,
192}
193
194impl HierarchicalLayout {
195    pub fn new(config: LayoutConfig) -> Self {
196        Self { config }
197    }
198
199    pub fn compute<N, E>(&mut self, graph: &Graph<N, E>) -> HashMap<NodeId, Vec2> {
200        let node_ids = graph.node_ids();
201        if node_ids.is_empty() { return HashMap::new(); }
202
203        // Step 1: Layer assignment via BFS from roots (nodes with in-degree 0 or lowest id)
204        let mut layers: HashMap<NodeId, usize> = HashMap::new();
205        let mut visited = HashSet::new();
206        let mut queue = VecDeque::new();
207
208        // Find roots: for directed, nodes with no incoming edges; for undirected, pick first
209        let mut has_incoming: HashSet<NodeId> = HashSet::new();
210        if graph.kind == GraphKind::Directed {
211            for edge in graph.edges() {
212                has_incoming.insert(edge.to);
213            }
214        }
215        let roots: Vec<NodeId> = if graph.kind == GraphKind::Directed {
216            node_ids.iter().filter(|n| !has_incoming.contains(n)).copied().collect()
217        } else {
218            vec![node_ids[0]]
219        };
220        let roots = if roots.is_empty() { vec![node_ids[0]] } else { roots };
221
222        for &root in &roots {
223            if visited.insert(root) {
224                queue.push_back(root);
225                layers.insert(root, 0);
226            }
227        }
228        while let Some(nid) = queue.pop_front() {
229            let layer = layers[&nid];
230            for nbr in graph.neighbors(nid) {
231                if visited.insert(nbr) {
232                    layers.insert(nbr, layer + 1);
233                    queue.push_back(nbr);
234                }
235            }
236        }
237        // Assign unvisited nodes
238        for &nid in &node_ids {
239            if !layers.contains_key(&nid) {
240                layers.insert(nid, 0);
241            }
242        }
243
244        // Step 2: Group nodes by layer
245        let max_layer = layers.values().copied().max().unwrap_or(0);
246        let mut layer_nodes: Vec<Vec<NodeId>> = vec![Vec::new(); max_layer + 1];
247        for (&nid, &layer) in &layers {
248            layer_nodes[layer].push(nid);
249        }
250        // Sort within layers for determinism
251        for layer in &mut layer_nodes {
252            layer.sort();
253        }
254
255        // Step 3: Crossing minimization (barycenter heuristic)
256        for _pass in 0..5 {
257            for l in 1..=max_layer {
258                let prev_layer = &layer_nodes[l - 1];
259                let prev_pos: HashMap<NodeId, f32> = prev_layer.iter().enumerate()
260                    .map(|(i, &nid)| (nid, i as f32))
261                    .collect();
262
263                let mut barycenters: Vec<(NodeId, f32)> = Vec::new();
264                for &nid in &layer_nodes[l] {
265                    let nbrs = graph.neighbors(nid);
266                    let parent_positions: Vec<f32> = nbrs.iter()
267                        .filter_map(|n| prev_pos.get(n).copied())
268                        .collect();
269                    let bc = if parent_positions.is_empty() {
270                        0.0
271                    } else {
272                        parent_positions.iter().sum::<f32>() / parent_positions.len() as f32
273                    };
274                    barycenters.push((nid, bc));
275                }
276                barycenters.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
277                layer_nodes[l] = barycenters.into_iter().map(|(nid, _)| nid).collect();
278            }
279        }
280
281        // Step 4: Coordinate assignment
282        let mut positions = HashMap::new();
283        let layer_spacing = self.config.bounds.y / (max_layer + 1) as f32;
284        for (l, nodes) in layer_nodes.iter().enumerate() {
285            let n = nodes.len();
286            let node_spacing = if n > 1 {
287                self.config.bounds.x / n as f32
288            } else {
289                self.config.bounds.x / 2.0
290            };
291            for (i, &nid) in nodes.iter().enumerate() {
292                let x = if n > 1 {
293                    node_spacing * (i as f32 + 0.5)
294                } else {
295                    self.config.bounds.x / 2.0
296                };
297                let y = layer_spacing * (l as f32 + 0.5);
298                positions.insert(nid, Vec2::new(x, y));
299            }
300        }
301        positions
302    }
303}
304
305// ---- Circular Layout ----
306
307pub struct CircularLayout {
308    config: LayoutConfig,
309}
310
311impl CircularLayout {
312    pub fn new(config: LayoutConfig) -> Self {
313        Self { config }
314    }
315
316    pub fn compute<N, E>(&self, graph: &Graph<N, E>) -> HashMap<NodeId, Vec2> {
317        let node_ids = graph.node_ids();
318        let n = node_ids.len();
319        if n == 0 { return HashMap::new(); }
320
321        let center = self.config.bounds * 0.5;
322        let radius = self.config.bounds.x.min(self.config.bounds.y) * 0.4;
323
324        let mut positions = HashMap::new();
325        for (i, &nid) in node_ids.iter().enumerate() {
326            let angle = 2.0 * std::f32::consts::PI * i as f32 / n as f32;
327            let x = center.x + radius * angle.cos();
328            let y = center.y + radius * angle.sin();
329            positions.insert(nid, Vec2::new(x, y));
330        }
331        positions
332    }
333}
334
335// ---- Spectral Layout (power iteration for Laplacian eigenvectors) ----
336
337pub struct SpectralLayout {
338    config: LayoutConfig,
339}
340
341impl SpectralLayout {
342    pub fn new(config: LayoutConfig) -> Self {
343        Self { config }
344    }
345
346    pub fn compute<N, E>(&self, graph: &Graph<N, E>) -> HashMap<NodeId, Vec2> {
347        let node_ids = graph.node_ids();
348        let n = node_ids.len();
349        if n == 0 { return HashMap::new(); }
350        if n == 1 {
351            let mut m = HashMap::new();
352            m.insert(node_ids[0], self.config.bounds * 0.5);
353            return m;
354        }
355
356        let idx: HashMap<NodeId, usize> = node_ids.iter().enumerate().map(|(i, &nid)| (nid, i)).collect();
357
358        // Build Laplacian matrix
359        let mut laplacian = vec![vec![0.0f64; n]; n];
360        for edge in graph.edges() {
361            if let (Some(&i), Some(&j)) = (idx.get(&edge.from), idx.get(&edge.to)) {
362                laplacian[i][j] -= 1.0;
363                laplacian[j][i] -= 1.0;
364                laplacian[i][i] += 1.0;
365                laplacian[j][j] += 1.0;
366            }
367        }
368
369        // Power iteration to find the Fiedler vector (2nd smallest eigenvector)
370        // and the 3rd smallest eigenvector for the second coordinate
371        let eigvec2 = self.fiedler_vector(&laplacian, n, 0);
372        let eigvec3 = self.fiedler_vector_orthogonal(&laplacian, n, &eigvec2);
373
374        let center = self.config.bounds * 0.5;
375        let scale = self.config.bounds.x.min(self.config.bounds.y) * 0.4;
376
377        let mut positions = HashMap::new();
378        let max2 = eigvec2.iter().map(|x| x.abs()).fold(0.0f64, f64::max).max(1e-10);
379        let max3 = eigvec3.iter().map(|x| x.abs()).fold(0.0f64, f64::max).max(1e-10);
380
381        for (i, &nid) in node_ids.iter().enumerate() {
382            let x = center.x + (eigvec2[i] / max2) as f32 * scale;
383            let y = center.y + (eigvec3[i] / max3) as f32 * scale;
384            positions.insert(nid, Vec2::new(x, y));
385        }
386        positions
387    }
388
389    fn fiedler_vector(&self, laplacian: &[Vec<f64>], n: usize, seed_offset: u64) -> Vec<f64> {
390        // Inverse power iteration with shift to find smallest non-trivial eigenvector
391        // Using simple power iteration on (max_eigenvalue * I - L) to find largest eigenvector of complement
392        // Then deflate the constant vector and repeat
393
394        let max_iter = 200;
395        // Start with a random vector orthogonal to the constant vector
396        let mut v: Vec<f64> = (0..n).map(|i| pseudo_random(self.config.seed + seed_offset, i as u64) - 0.5).collect();
397
398        // Orthogonalize against constant vector
399        let mean: f64 = v.iter().sum::<f64>() / n as f64;
400        for x in v.iter_mut() { *x -= mean; }
401        let norm: f64 = v.iter().map(|x| x * x).sum::<f64>().sqrt();
402        if norm > 1e-12 { for x in v.iter_mut() { *x /= norm; } }
403
404        for _ in 0..max_iter {
405            // Multiply: w = L * v
406            let mut w = vec![0.0f64; n];
407            for i in 0..n {
408                for j in 0..n {
409                    w[i] += laplacian[i][j] * v[j];
410                }
411            }
412            // Orthogonalize against constant vector
413            let mean: f64 = w.iter().sum::<f64>() / n as f64;
414            for x in w.iter_mut() { *x -= mean; }
415            let norm: f64 = w.iter().map(|x| x * x).sum::<f64>().sqrt();
416            if norm > 1e-12 { for x in w.iter_mut() { *x /= norm; } }
417            v = w;
418        }
419        v
420    }
421
422    fn fiedler_vector_orthogonal(&self, laplacian: &[Vec<f64>], n: usize, fiedler: &[f64]) -> Vec<f64> {
423        let max_iter = 200;
424        let mut v: Vec<f64> = (0..n).map(|i| pseudo_random(self.config.seed + 9999, i as u64) - 0.5).collect();
425
426        for _ in 0..max_iter {
427            let mut w = vec![0.0f64; n];
428            for i in 0..n {
429                for j in 0..n {
430                    w[i] += laplacian[i][j] * v[j];
431                }
432            }
433            // Orthogonalize against constant vector
434            let mean: f64 = w.iter().sum::<f64>() / n as f64;
435            for x in w.iter_mut() { *x -= mean; }
436            // Orthogonalize against Fiedler vector
437            let dot: f64 = w.iter().zip(fiedler).map(|(a, b)| a * b).sum();
438            for (x, f) in w.iter_mut().zip(fiedler) { *x -= dot * f; }
439            let norm: f64 = w.iter().map(|x| x * x).sum::<f64>().sqrt();
440            if norm > 1e-12 { for x in w.iter_mut() { *x /= norm; } }
441            v = w;
442        }
443        v
444    }
445}
446
447// ---- Tree Layout (Reingold-Tilford) ----
448
449pub struct TreeLayout {
450    config: LayoutConfig,
451}
452
453impl TreeLayout {
454    pub fn new(config: LayoutConfig) -> Self {
455        Self { config }
456    }
457
458    pub fn compute<N, E>(&self, graph: &Graph<N, E>) -> HashMap<NodeId, Vec2> {
459        let node_ids = graph.node_ids();
460        if node_ids.is_empty() { return HashMap::new(); }
461
462        // Find root: node with smallest ID or no incoming edges for directed
463        let root = if graph.kind == GraphKind::Directed {
464            let mut has_incoming: HashSet<NodeId> = HashSet::new();
465            for edge in graph.edges() { has_incoming.insert(edge.to); }
466            node_ids.iter().find(|n| !has_incoming.contains(n)).copied().unwrap_or(node_ids[0])
467        } else {
468            node_ids[0]
469        };
470
471        // BFS to build tree
472        let mut children: HashMap<NodeId, Vec<NodeId>> = HashMap::new();
473        let mut depth: HashMap<NodeId, usize> = HashMap::new();
474        let mut visited = HashSet::new();
475        let mut queue = VecDeque::new();
476        visited.insert(root);
477        depth.insert(root, 0);
478        queue.push_back(root);
479        children.insert(root, Vec::new());
480
481        while let Some(nid) = queue.pop_front() {
482            let mut kids = Vec::new();
483            for nbr in graph.neighbors(nid) {
484                if visited.insert(nbr) {
485                    depth.insert(nbr, depth[&nid] + 1);
486                    children.insert(nbr, Vec::new());
487                    queue.push_back(nbr);
488                    kids.push(nbr);
489                }
490            }
491            children.insert(nid, kids);
492        }
493
494        // Assign x positions using Reingold-Tilford approach
495        let mut x_pos: HashMap<NodeId, f32> = HashMap::new();
496        let mut next_x = 0.0f32;
497        self.assign_x(root, &children, &mut x_pos, &mut next_x);
498
499        let max_depth = depth.values().copied().max().unwrap_or(0) as f32;
500        let y_spacing = if max_depth > 0.0 {
501            self.config.bounds.y / (max_depth + 1.0)
502        } else {
503            self.config.bounds.y / 2.0
504        };
505
506        let max_x = x_pos.values().copied().fold(0.0f32, f32::max).max(1.0);
507        let x_scale = self.config.bounds.x / (max_x + 1.0);
508
509        let mut positions = HashMap::new();
510        for (&nid, &d) in &depth {
511            let x = x_pos.get(&nid).copied().unwrap_or(0.0) * x_scale + x_scale * 0.5;
512            let y = d as f32 * y_spacing + y_spacing * 0.5;
513            positions.insert(nid, Vec2::new(x, y));
514        }
515        positions
516    }
517
518    fn assign_x(&self, node: NodeId, children: &HashMap<NodeId, Vec<NodeId>>, x_pos: &mut HashMap<NodeId, f32>, next_x: &mut f32) {
519        let kids = children.get(&node).cloned().unwrap_or_default();
520        if kids.is_empty() {
521            x_pos.insert(node, *next_x);
522            *next_x += 1.0;
523        } else {
524            for &child in &kids {
525                self.assign_x(child, children, x_pos, next_x);
526            }
527            let first = x_pos[&kids[0]];
528            let last = x_pos[kids.last().unwrap()];
529            x_pos.insert(node, (first + last) / 2.0);
530        }
531    }
532}
533
534#[cfg(test)]
535mod tests {
536    use super::*;
537
538    fn make_triangle() -> Graph<(), ()> {
539        let mut g = Graph::new(GraphKind::Undirected);
540        let a = g.add_node(());
541        let b = g.add_node(());
542        let c = g.add_node(());
543        g.add_edge(a, b, ());
544        g.add_edge(b, c, ());
545        g.add_edge(a, c, ());
546        g
547    }
548
549    fn make_path(n: usize) -> Graph<(), ()> {
550        let mut g = Graph::new(GraphKind::Undirected);
551        let mut prev = g.add_node(());
552        for _ in 1..n {
553            let next = g.add_node(());
554            g.add_edge(prev, next, ());
555            prev = next;
556        }
557        g
558    }
559
560    #[test]
561    fn test_force_directed_produces_positions() {
562        let g = make_triangle();
563        let config = LayoutConfig { iterations: 50, ..Default::default() };
564        let pos = compute_layout(&g, LayoutAlgorithm::ForceDirected, &config);
565        assert_eq!(pos.len(), 3);
566        for p in pos.values() {
567            assert!(p.x >= 0.0 && p.x <= config.bounds.x);
568            assert!(p.y >= 0.0 && p.y <= config.bounds.y);
569        }
570    }
571
572    #[test]
573    fn test_circular_layout() {
574        let g = make_path(6);
575        let config = LayoutConfig::default();
576        let pos = compute_layout(&g, LayoutAlgorithm::Circular, &config);
577        assert_eq!(pos.len(), 6);
578    }
579
580    #[test]
581    fn test_hierarchical_layout() {
582        let mut g = Graph::new(GraphKind::Directed);
583        let a = g.add_node(());
584        let b = g.add_node(());
585        let c = g.add_node(());
586        let d = g.add_node(());
587        g.add_edge(a, b, ());
588        g.add_edge(a, c, ());
589        g.add_edge(b, d, ());
590        let config = LayoutConfig::default();
591        let pos = compute_layout(&g, LayoutAlgorithm::Hierarchical, &config);
592        assert_eq!(pos.len(), 4);
593        // Root should be higher (smaller y) than children
594        assert!(pos[&a].y < pos[&b].y);
595        assert!(pos[&b].y < pos[&d].y);
596    }
597
598    #[test]
599    fn test_tree_layout() {
600        let mut g = Graph::new(GraphKind::Undirected);
601        let a = g.add_node(());
602        let b = g.add_node(());
603        let c = g.add_node(());
604        let d = g.add_node(());
605        let e = g.add_node(());
606        g.add_edge(a, b, ());
607        g.add_edge(a, c, ());
608        g.add_edge(b, d, ());
609        g.add_edge(b, e, ());
610        let config = LayoutConfig::default();
611        let pos = compute_layout(&g, LayoutAlgorithm::Tree, &config);
612        assert_eq!(pos.len(), 5);
613    }
614
615    #[test]
616    fn test_spectral_layout() {
617        let g = make_path(5);
618        let config = LayoutConfig::default();
619        let pos = compute_layout(&g, LayoutAlgorithm::Spectral, &config);
620        assert_eq!(pos.len(), 5);
621    }
622
623    #[test]
624    fn test_random_layout() {
625        let g = make_triangle();
626        let config = LayoutConfig::default();
627        let pos = compute_layout(&g, LayoutAlgorithm::Random, &config);
628        assert_eq!(pos.len(), 3);
629    }
630
631    #[test]
632    fn test_grid_layout() {
633        let g = make_path(9);
634        let config = LayoutConfig::default();
635        let pos = compute_layout(&g, LayoutAlgorithm::Grid, &config);
636        assert_eq!(pos.len(), 9);
637    }
638
639    #[test]
640    fn test_empty_graph() {
641        let g: Graph<(), ()> = Graph::new(GraphKind::Undirected);
642        let config = LayoutConfig::default();
643        for alg in &[LayoutAlgorithm::ForceDirected, LayoutAlgorithm::Circular, LayoutAlgorithm::Tree] {
644            let pos = compute_layout(&g, *alg, &config);
645            assert!(pos.is_empty());
646        }
647    }
648
649    #[test]
650    fn test_single_node() {
651        let mut g: Graph<(), ()> = Graph::new(GraphKind::Undirected);
652        g.add_node(());
653        let config = LayoutConfig::default();
654        let pos = compute_layout(&g, LayoutAlgorithm::Spectral, &config);
655        assert_eq!(pos.len(), 1);
656    }
657
658    #[test]
659    fn test_force_directed_separates_components() {
660        let mut g: Graph<(), ()> = Graph::new(GraphKind::Undirected);
661        let a = g.add_node(());
662        let b = g.add_node(());
663        g.add_edge(a, b, ());
664        let c = g.add_node(());
665        let d = g.add_node(());
666        g.add_edge(c, d, ());
667        let config = LayoutConfig { iterations: 100, ..Default::default() };
668        let pos = compute_layout(&g, LayoutAlgorithm::ForceDirected, &config);
669        assert_eq!(pos.len(), 4);
670        // Connected nodes should be closer to each other than to other component
671        let dist_ab = (pos[&a] - pos[&b]).length();
672        let dist_ac = (pos[&a] - pos[&c]).length();
673        // Not guaranteed but likely with force directed
674    }
675
676    #[test]
677    fn test_circular_layout_radius() {
678        let mut g: Graph<(), ()> = Graph::new(GraphKind::Undirected);
679        let nodes: Vec<NodeId> = (0..8).map(|_| g.add_node(())).collect();
680        for i in 0..7 { g.add_edge(nodes[i], nodes[i + 1], ()); }
681        let config = LayoutConfig::default();
682        let pos = compute_layout(&g, LayoutAlgorithm::Circular, &config);
683        let center = config.bounds * 0.5;
684        let radius = config.bounds.x.min(config.bounds.y) * 0.4;
685        for p in pos.values() {
686            let dist = (*p - center).length();
687            assert!((dist - radius).abs() < 1.0);
688        }
689    }
690}
proof_engine/graph/layout.rs

proof_engine/graph/
layout.rs
