rust_igraph/algorithms/layout/
simple.rs

1//! Simple graph layout algorithms (ALGO-LO-001).
2//!
3//! Counterparts of `igraph_layout_random`, `igraph_layout_circle`,
4//! `igraph_layout_star`, `igraph_layout_grid`, `igraph_layout_sphere`,
5//! and their 3D variants from `references/igraph/src/layout/`.
6
7use std::f64::consts::PI;
8
9use crate::core::{Graph, IgraphResult, rng::SplitMix64};
10
11/// Place vertices uniformly at random in the square `[-1, 1] × [-1, 1]`.
12///
13/// Returns a `Vec` of `(x, y)` coordinate pairs, one per vertex.
14///
15/// # Examples
16///
17/// ```
18/// use rust_igraph::{Graph, layout_random};
19///
20/// let g = Graph::with_vertices(5);
21/// let coords = layout_random(&g, 42);
22/// assert_eq!(coords.len(), 5);
23/// for &(x, y) in &coords {
24///     assert!((-1.0..=1.0).contains(&x));
25///     assert!((-1.0..=1.0).contains(&y));
26/// }
27/// ```
28pub fn layout_random(graph: &Graph, seed: u64) -> Vec<(f64, f64)> {
29    let n = graph.vcount() as usize;
30    let mut rng = SplitMix64::new(seed);
31    (0..n)
32        .map(|_| {
33            let x = 2.0 * rng.gen_unit() - 1.0;
34            let y = 2.0 * rng.gen_unit() - 1.0;
35            (x, y)
36        })
37        .collect()
38}
39
40/// Place vertices uniformly at random in the cube `[-1, 1]³`.
41///
42/// Returns a `Vec` of `(x, y, z)` coordinate triples, one per vertex.
43///
44/// # Examples
45///
46/// ```
47/// use rust_igraph::{Graph, layout_random_3d};
48///
49/// let g = Graph::with_vertices(5);
50/// let coords = layout_random_3d(&g, 42);
51/// assert_eq!(coords.len(), 5);
52/// ```
53pub fn layout_random_3d(graph: &Graph, seed: u64) -> Vec<(f64, f64, f64)> {
54    let n = graph.vcount() as usize;
55    let mut rng = SplitMix64::new(seed);
56    (0..n)
57        .map(|_| {
58            let x = 2.0 * rng.gen_unit() - 1.0;
59            let y = 2.0 * rng.gen_unit() - 1.0;
60            let z = 2.0 * rng.gen_unit() - 1.0;
61            (x, y, z)
62        })
63        .collect()
64}
65
66/// Place vertices uniformly on a unit circle.
67///
68/// Vertices are placed in the order given by `order` (if `Some`), or
69/// in vertex-ID order. Vertices not in `order` are placed at `(0, 0)`.
70///
71/// # Examples
72///
73/// ```
74/// use rust_igraph::{Graph, layout_circle};
75///
76/// let g = Graph::with_vertices(4);
77/// let coords = layout_circle(&g, None);
78/// assert_eq!(coords.len(), 4);
79/// // First vertex is at (1, 0)
80/// assert!((coords[0].0 - 1.0).abs() < 1e-9);
81/// assert!(coords[0].1.abs() < 1e-9);
82/// ```
83#[allow(clippy::cast_precision_loss)]
84pub fn layout_circle(graph: &Graph, order: Option<&[u32]>) -> Vec<(f64, f64)> {
85    let n = graph.vcount() as usize;
86    let mut coords = vec![(0.0, 0.0); n];
87
88    match order {
89        Some(ord) => {
90            let vs_size = ord.len();
91            for (i, &v) in ord.iter().enumerate() {
92                let v_us = v as usize;
93                if v_us < n {
94                    let phi = 2.0 * PI / (vs_size as f64) * (i as f64);
95                    coords[v_us] = (phi.cos(), phi.sin());
96                }
97            }
98        }
99        None => {
100            for (i, slot) in coords.iter_mut().enumerate() {
101                let phi = 2.0 * PI / (n as f64) * (i as f64);
102                *slot = (phi.cos(), phi.sin());
103            }
104        }
105    }
106
107    coords
108}
109
110/// Place vertices in a star layout: center at origin, rest on a unit
111/// circle.
112///
113/// # Parameters
114///
115/// - `center`: vertex id to place at the origin.
116/// - `order`: optional ordering of vertices. If `None`, vertices are
117///   placed in vertex-ID order.
118///
119/// # Examples
120///
121/// ```
122/// use rust_igraph::{Graph, layout_star};
123///
124/// let g = Graph::with_vertices(5);
125/// let coords = layout_star(&g, 0, None).unwrap();
126/// assert_eq!(coords.len(), 5);
127/// // Center vertex is at origin
128/// assert!((coords[0].0).abs() < 1e-9);
129/// assert!((coords[0].1).abs() < 1e-9);
130/// ```
131#[allow(clippy::cast_precision_loss)]
132pub fn layout_star(
133    graph: &Graph,
134    center: u32,
135    order: Option<&[u32]>,
136) -> IgraphResult<Vec<(f64, f64)>> {
137    let n = graph.vcount();
138    let n_us = n as usize;
139
140    if n > 0 && center >= n {
141        return Err(crate::core::IgraphError::InvalidArgument(
142            "center vertex out of range".to_string(),
143        ));
144    }
145    if let Some(ord) = order {
146        if ord.len() != n_us {
147            return Err(crate::core::IgraphError::InvalidArgument(
148                "order vector length must equal vertex count".to_string(),
149            ));
150        }
151    }
152
153    let mut coords = vec![(0.0, 0.0); n_us];
154
155    if n_us <= 1 {
156        return Ok(coords);
157    }
158
159    let ring_count = n_us - 1;
160    let mut phi = 0.0_f64;
161
162    for i in 0..n_us {
163        #[allow(clippy::cast_possible_truncation)]
164        let node = order.map_or(i as u32, |ord| ord[i]);
165        if node != center {
166            coords[node as usize] = (phi.cos(), phi.sin());
167            phi += 2.0 * PI / (ring_count as f64);
168        }
169    }
170
171    Ok(coords)
172}
173
174/// Place vertices on a regular 2D grid.
175///
176/// When `width` is 0 or negative, the grid width is
177/// `ceil(sqrt(vcount))`.
178///
179/// # Examples
180///
181/// ```
182/// use rust_igraph::{Graph, layout_grid};
183///
184/// let g = Graph::with_vertices(6);
185/// let coords = layout_grid(&g, 3);
186/// assert_eq!(coords.len(), 6);
187/// // First row: (0,0), (1,0), (2,0)
188/// assert!((coords[0].0).abs() < 1e-9);
189/// assert!((coords[1].0 - 1.0).abs() < 1e-9);
190/// assert!((coords[2].0 - 2.0).abs() < 1e-9);
191/// // Second row: (0,1), (1,1), (2,1)
192/// assert!((coords[3].1 - 1.0).abs() < 1e-9);
193/// ```
194#[allow(
195    clippy::cast_precision_loss,
196    clippy::cast_possible_truncation,
197    clippy::cast_sign_loss
198)]
199pub fn layout_grid(graph: &Graph, width: i32) -> Vec<(f64, f64)> {
200    let n = graph.vcount() as usize;
201
202    let w = if width <= 0 {
203        (n as f64).sqrt().ceil() as usize
204    } else {
205        width as usize
206    };
207
208    let mut coords = Vec::with_capacity(n);
209    let mut x = 0usize;
210    let mut y = 0usize;
211
212    for _ in 0..n {
213        coords.push((x as f64, y as f64));
214        x += 1;
215        if x == w {
216            x = 0;
217            y += 1;
218        }
219    }
220
221    coords
222}
223
224/// Place vertices on a regular 3D grid.
225///
226/// When `width` or `height` is 0 or negative, it is auto-determined.
227///
228/// # Examples
229///
230/// ```
231/// use rust_igraph::{Graph, layout_grid_3d};
232///
233/// let g = Graph::with_vertices(8);
234/// let coords = layout_grid_3d(&g, 2, 2);
235/// assert_eq!(coords.len(), 8);
236/// ```
237#[allow(
238    clippy::cast_precision_loss,
239    clippy::cast_possible_truncation,
240    clippy::cast_sign_loss,
241    clippy::many_single_char_names
242)]
243pub fn layout_grid_3d(graph: &Graph, width: i32, height: i32) -> Vec<(f64, f64, f64)> {
244    let n = graph.vcount() as usize;
245
246    let (w, h) = match (width <= 0, height <= 0) {
247        (true, true) => {
248            let side = (n as f64).cbrt().ceil() as usize;
249            (side.max(1), side.max(1))
250        }
251        (true, false) => {
252            let ht = height as usize;
253            let wd = ((n as f64) / (ht as f64)).sqrt().ceil() as usize;
254            (wd.max(1), ht)
255        }
256        (false, true) => {
257            let wd = width as usize;
258            let ht = ((n as f64) / (wd as f64)).sqrt().ceil() as usize;
259            (wd, ht.max(1))
260        }
261        (false, false) => (width as usize, height as usize),
262    };
263
264    let mut coords = Vec::with_capacity(n);
265    let mut x = 0usize;
266    let mut y = 0usize;
267    let mut z = 0usize;
268
269    for _ in 0..n {
270        coords.push((x as f64, y as f64, z as f64));
271        x += 1;
272        if x == w {
273            x = 0;
274            y += 1;
275            if y == h {
276                y = 0;
277                z += 1;
278            }
279        }
280    }
281
282    coords
283}
284
285/// Place vertices approximately uniformly on a unit sphere.
286///
287/// Uses the Saff-Kuijlaars spiral algorithm (Mathematical
288/// Intelligencer 19.1, 1997).
289///
290/// # Examples
291///
292/// ```
293/// use rust_igraph::{Graph, layout_sphere};
294///
295/// let g = Graph::with_vertices(10);
296/// let coords = layout_sphere(&g);
297/// assert_eq!(coords.len(), 10);
298/// // All points are approximately on the unit sphere
299/// for &(x, y, z) in &coords {
300///     let r = (x * x + y * y + z * z).sqrt();
301///     assert!((r - 1.0).abs() < 0.01);
302/// }
303/// ```
304#[allow(clippy::cast_precision_loss)]
305pub fn layout_sphere(graph: &Graph) -> Vec<(f64, f64, f64)> {
306    let n = graph.vcount() as usize;
307
308    if n == 0 {
309        return Vec::new();
310    }
311    if n == 1 {
312        return vec![(0.0, 0.0, -1.0)];
313    }
314
315    let sqrt_n = (n as f64).sqrt();
316    let mut coords = Vec::with_capacity(n);
317    let mut phi = 0.0_f64;
318
319    for i in 0..n {
320        let (z, r) = if i == 0 {
321            (-1.0, 0.0)
322        } else if i == n - 1 {
323            (1.0, 0.0)
324        } else {
325            let z_val = -1.0 + 2.0 * (i as f64) / ((n - 1) as f64);
326            let r_val = (1.0 - z_val * z_val).sqrt();
327            phi += 3.6 / (sqrt_n * r_val);
328            (z_val, r_val)
329        };
330
331        coords.push((r * phi.cos(), r * phi.sin(), z));
332    }
333
334    coords
335}
336
337#[cfg(test)]
338mod tests {
339    use super::*;
340    use crate::create;
341
342    fn approx_eq(a: f64, b: f64) -> bool {
343        (a - b).abs() < 1e-9
344    }
345
346    #[test]
347    fn random_empty() {
348        let g = Graph::with_vertices(0);
349        let c = layout_random(&g, 0);
350        assert!(c.is_empty());
351    }
352
353    #[test]
354    fn random_bounds() {
355        let g = Graph::with_vertices(100);
356        let c = layout_random(&g, 42);
357        assert_eq!(c.len(), 100);
358        for &(x, y) in &c {
359            assert!((-1.0..=1.0).contains(&x), "x={x} out of bounds");
360            assert!((-1.0..=1.0).contains(&y), "y={y} out of bounds");
361        }
362    }
363
364    #[test]
365    fn random_deterministic() {
366        let g = Graph::with_vertices(10);
367        let a = layout_random(&g, 123);
368        let b = layout_random(&g, 123);
369        assert_eq!(a, b);
370    }
371
372    #[test]
373    fn random_3d_bounds() {
374        let g = Graph::with_vertices(50);
375        let c = layout_random_3d(&g, 42);
376        assert_eq!(c.len(), 50);
377        for &(x, y, z) in &c {
378            assert!((-1.0..=1.0).contains(&x));
379            assert!((-1.0..=1.0).contains(&y));
380            assert!((-1.0..=1.0).contains(&z));
381        }
382    }
383
384    #[test]
385    fn circle_empty() {
386        let g = Graph::with_vertices(0);
387        let c = layout_circle(&g, None);
388        assert!(c.is_empty());
389    }
390
391    #[test]
392    fn circle_single() {
393        let g = Graph::with_vertices(1);
394        let c = layout_circle(&g, None);
395        assert_eq!(c.len(), 1);
396        assert!(approx_eq(c[0].0, 1.0));
397        assert!(approx_eq(c[0].1, 0.0));
398    }
399
400    #[test]
401    fn circle_4_vertices() {
402        let g = Graph::with_vertices(4);
403        let c = layout_circle(&g, None);
404        assert_eq!(c.len(), 4);
405        assert!(approx_eq(c[0].0, 1.0));
406        assert!(approx_eq(c[0].1, 0.0));
407        assert!(approx_eq(c[1].0, 0.0));
408        assert!(approx_eq(c[1].1, 1.0));
409        assert!(approx_eq(c[2].0, -1.0));
410        assert!(approx_eq(c[2].1, 0.0));
411        assert!(approx_eq(c[3].0, 0.0));
412        assert!(approx_eq(c[3].1, -1.0));
413    }
414
415    #[test]
416    fn circle_with_order() {
417        let g = Graph::with_vertices(3);
418        let c = layout_circle(&g, Some(&[2, 0, 1]));
419        assert!(approx_eq(c[2].0, 1.0));
420        assert!(approx_eq(c[2].1, 0.0));
421    }
422
423    #[test]
424    fn circle_unit_radius() {
425        let g = Graph::with_vertices(12);
426        let c = layout_circle(&g, None);
427        for (i, &(x, y)) in c.iter().enumerate() {
428            let r = (x * x + y * y).sqrt();
429            assert!(approx_eq(r, 1.0), "v{i}: r={r}");
430        }
431    }
432
433    #[test]
434    fn star_empty() {
435        let g = Graph::with_vertices(0);
436        let c = layout_star(&g, 0, None).expect("ok");
437        assert!(c.is_empty());
438    }
439
440    #[test]
441    fn star_single() {
442        let g = Graph::with_vertices(1);
443        let c = layout_star(&g, 0, None).expect("ok");
444        assert_eq!(c.len(), 1);
445        assert!(approx_eq(c[0].0, 0.0));
446        assert!(approx_eq(c[0].1, 0.0));
447    }
448
449    #[test]
450    fn star_center_at_origin() {
451        let g = Graph::with_vertices(5);
452        let c = layout_star(&g, 2, None).expect("ok");
453        assert!(approx_eq(c[2].0, 0.0));
454        assert!(approx_eq(c[2].1, 0.0));
455    }
456
457    #[test]
458    fn star_ring_unit_radius() {
459        let g = Graph::with_vertices(5);
460        let c = layout_star(&g, 0, None).expect("ok");
461        for (i, &(x, y)) in c.iter().enumerate().skip(1) {
462            let r = (x * x + y * y).sqrt();
463            assert!(approx_eq(r, 1.0), "v{i}: r={r}");
464        }
465    }
466
467    #[test]
468    fn star_invalid_center() {
469        let g = Graph::with_vertices(3);
470        let r = layout_star(&g, 5, None);
471        assert!(r.is_err());
472    }
473
474    #[test]
475    fn star_invalid_order_len() {
476        let g = Graph::with_vertices(3);
477        let r = layout_star(&g, 0, Some(&[0, 1]));
478        assert!(r.is_err());
479    }
480
481    #[test]
482    fn grid_empty() {
483        let g = Graph::with_vertices(0);
484        let c = layout_grid(&g, 3);
485        assert!(c.is_empty());
486    }
487
488    #[test]
489    fn grid_2x3() {
490        let g = Graph::with_vertices(6);
491        let c = layout_grid(&g, 3);
492        assert_eq!(c[0], (0.0, 0.0));
493        assert_eq!(c[1], (1.0, 0.0));
494        assert_eq!(c[2], (2.0, 0.0));
495        assert_eq!(c[3], (0.0, 1.0));
496        assert_eq!(c[4], (1.0, 1.0));
497        assert_eq!(c[5], (2.0, 1.0));
498    }
499
500    #[test]
501    fn grid_auto_width() {
502        let g = Graph::with_vertices(9);
503        let c = layout_grid(&g, 0);
504        assert_eq!(c.len(), 9);
505        assert_eq!(c[3], (0.0, 1.0));
506    }
507
508    #[test]
509    fn grid_3d_basic() {
510        let g = Graph::with_vertices(8);
511        let c = layout_grid_3d(&g, 2, 2);
512        assert_eq!(c.len(), 8);
513        assert_eq!(c[0], (0.0, 0.0, 0.0));
514        assert_eq!(c[1], (1.0, 0.0, 0.0));
515        assert_eq!(c[2], (0.0, 1.0, 0.0));
516        assert_eq!(c[3], (1.0, 1.0, 0.0));
517        assert_eq!(c[4], (0.0, 0.0, 1.0));
518    }
519
520    #[test]
521    fn grid_3d_auto() {
522        let g = Graph::with_vertices(27);
523        let c = layout_grid_3d(&g, 0, 0);
524        assert_eq!(c.len(), 27);
525    }
526
527    #[test]
528    fn sphere_empty() {
529        let g = Graph::with_vertices(0);
530        let c = layout_sphere(&g);
531        assert!(c.is_empty());
532    }
533
534    #[test]
535    fn sphere_single() {
536        let g = Graph::with_vertices(1);
537        let c = layout_sphere(&g);
538        assert_eq!(c.len(), 1);
539        assert!(approx_eq(c[0].2, -1.0));
540    }
541
542    #[test]
543    fn sphere_two() {
544        let g = Graph::with_vertices(2);
545        let c = layout_sphere(&g);
546        assert!(approx_eq(c[0].2, -1.0));
547        assert!(approx_eq(c[1].2, 1.0));
548    }
549
550    #[test]
551    fn sphere_unit_radius() {
552        let g = Graph::with_vertices(50);
553        let c = layout_sphere(&g);
554        for (i, &(x, y, z)) in c.iter().enumerate() {
555            let r = (x * x + y * y + z * z).sqrt();
556            assert!((r - 1.0).abs() < 0.01, "v{i}: r={r}");
557        }
558    }
559
560    #[test]
561    fn sphere_poles() {
562        let g = Graph::with_vertices(10);
563        let c = layout_sphere(&g);
564        assert!(approx_eq(c[0].2, -1.0));
565        assert!(approx_eq(c[9].2, 1.0));
566    }
567
568    #[test]
569    fn layout_ignores_edges() {
570        let g = create(&[(0, 1), (1, 2), (2, 0)], 3, false).expect("ok");
571        let a = layout_circle(&g, None);
572        let b = layout_circle(&Graph::with_vertices(3), None);
573        assert_eq!(a, b);
574    }
575}
576
577#[cfg(all(test, feature = "proptest-harness"))]
578mod proptests {
579    use super::*;
580    use proptest::prelude::*;
581
582    proptest! {
583        #[test]
584        fn random_all_in_bounds(n in 0u32..100, seed in 0u64..10000) {
585            let g = Graph::with_vertices(n);
586            let c = layout_random(&g, seed);
587            prop_assert_eq!(c.len(), n as usize);
588            for (i, &(x, y)) in c.iter().enumerate() {
589                prop_assert!(
590                    (-1.0..=1.0).contains(&x),
591                    "v{i}: x={x} out of [-1,1]"
592                );
593                prop_assert!(
594                    (-1.0..=1.0).contains(&y),
595                    "v{i}: y={y} out of [-1,1]"
596                );
597            }
598        }
599
600        #[test]
601        fn circle_all_on_unit_circle(n in 1u32..50) {
602            let g = Graph::with_vertices(n);
603            let c = layout_circle(&g, None);
604            for (i, &(x, y)) in c.iter().enumerate() {
605                let r = (x * x + y * y).sqrt();
606                prop_assert!(
607                    (r - 1.0).abs() < 1e-9,
608                    "v{i}: r={r} not on unit circle"
609                );
610            }
611        }
612
613        #[test]
614        fn grid_covers_expected_positions(n in 1u32..50) {
615            let g = Graph::with_vertices(n);
616            let c = layout_grid(&g, 0);
617            prop_assert_eq!(c.len(), n as usize);
618            for &(x, y) in &c {
619                prop_assert!(x >= 0.0);
620                prop_assert!(y >= 0.0);
621            }
622        }
623
624        #[test]
625        fn sphere_near_unit(n in 2u32..100) {
626            let g = Graph::with_vertices(n);
627            let c = layout_sphere(&g);
628            for (i, &(x, y, z)) in c.iter().enumerate() {
629                let r = (x * x + y * y + z * z).sqrt();
630                prop_assert!(
631                    (r - 1.0).abs() < 0.02,
632                    "v{i}: r={r} not near unit sphere"
633                );
634            }
635        }
636    }
637}
rust_igraph/algorithms/layout/simple.rs

rust_igraph/algorithms/layout/
simple.rs
