geometric-traits 0.1.0

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

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

use alloc::vec::Vec;

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

/// Returns the hypercube graph Q_d with 2^d vertices.
#[must_use]
pub fn hypercube_graph(d: usize) -> SymmetricCSR2D<CSR2D<usize, usize, usize>> {
    let n = 1usize << d;
    let mut edges = Vec::with_capacity(d * n / 2);
    for v in 0..n {
        for b in 0..d {
            let w = v ^ (1 << b);
            if v < w {
                edges.push((v, w));
            }
        }
    }
    edges.sort_unstable();
    build_symmetric(n, edges)
}