geometric-traits 0.2.3

Trait-based algebraic and graph algorithms for Rust, supporting no_std environments
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//! Generator for wheel graphs (W_n).
#![cfg(feature = "alloc")]

use alloc::vec::Vec;

use super::builder_utils::build_symmetric;
use crate::impls::{CSR2D, SymmetricCSR2D};

/// Returns the wheel graph W_n: a hub vertex 0 connected to a rim cycle of n
/// vertices.
///
/// Total vertices: n+1, total edges: 2n.
#[must_use]
pub fn wheel_graph(n: usize) -> SymmetricCSR2D<CSR2D<usize, usize, usize>> {
    assert!(n >= 3, "wheel_graph requires n >= 3");
    let total = n + 1;
    let mut edges = Vec::with_capacity(2 * n);
    // Hub edges: (0, i) for 1 <= i <= n
    for i in 1..=n {
        edges.push((0, i));
    }
    // Rim edges: (i, i+1) for 1 <= i < n, plus wrap (1, n)
    edges.push((1, n));
    for i in 1..n {
        edges.push((i, i + 1));
    }
    edges.sort_unstable();
    build_symmetric(total, edges)
}