weavatrix_graph/generator/
random.rs

1use crate::{EdgeEndpoints, GraphError, NodeIndex, Result, Topology, UndirectedTopology};
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4pub struct RandomGraphGenerator {
5    state: u64,
6}
7
8impl RandomGraphGenerator {
9    #[must_use]
10    pub const fn new(seed: u64) -> Self {
11        Self { state: seed }
12    }
13
14    /// Generates a directed Erdos-Renyi graph without self-loops.
15    ///
16    /// # Errors
17    ///
18    /// Returns an error for an invalid probability or compact capacity overflow.
19    pub fn directed(
20        &mut self,
21        node_count: usize,
22        numerator: u64,
23        denominator: u64,
24    ) -> Result<Topology> {
25        validate_probability(numerator, denominator)?;
26        validate_node_count(node_count)?;
27        let mut edges = Vec::new();
28        for source in 0..node_count {
29            for target in 0..node_count {
30                if source != target && self.sample(numerator, denominator) {
31                    edges.push(endpoints(source, target)?);
32                }
33            }
34        }
35        Topology::try_from_edges(node_count, edges)
36    }
37
38    /// Generates an undirected Erdos-Renyi graph without self-loops.
39    ///
40    /// # Errors
41    ///
42    /// Returns an error for an invalid probability or compact capacity overflow.
43    pub fn undirected(
44        &mut self,
45        node_count: usize,
46        numerator: u64,
47        denominator: u64,
48    ) -> Result<UndirectedTopology> {
49        validate_probability(numerator, denominator)?;
50        validate_node_count(node_count)?;
51        let mut edges = Vec::new();
52        for source in 0..node_count {
53            for target in (source + 1)..node_count {
54                if self.sample(numerator, denominator) {
55                    edges.push(endpoints(source, target)?);
56                }
57            }
58        }
59        UndirectedTopology::try_from_edges(node_count, edges)
60    }
61
62    fn sample(&mut self, numerator: u64, denominator: u64) -> bool {
63        if numerator == denominator {
64            return true;
65        }
66        if numerator == 0 {
67            return false;
68        }
69        self.next_u64() % denominator < numerator
70    }
71
72    fn next_u64(&mut self) -> u64 {
73        self.state = self.state.wrapping_add(0x9e37_79b9_7f4a_7c15);
74        let mut value = self.state;
75        value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
76        value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
77        value ^ (value >> 31)
78    }
79}
80
81fn validate_probability(numerator: u64, denominator: u64) -> Result<()> {
82    if denominator == 0 || numerator > denominator {
83        return Err(GraphError::InvalidProbability {
84            numerator,
85            denominator,
86        });
87    }
88    Ok(())
89}
90
91fn validate_node_count(node_count: usize) -> Result<()> {
92    u32::try_from(node_count)
93        .map(|_| ())
94        .map_err(|_| GraphError::IndexCapacityExceeded {
95            category: "generated nodes",
96            count: node_count,
97        })
98}
99
100fn endpoints(source: usize, target: usize) -> Result<EdgeEndpoints> {
101    let source = compact(source)?;
102    let target = compact(target)?;
103    Ok(EdgeEndpoints::new(source, target))
104}
105
106fn compact(index: usize) -> Result<NodeIndex> {
107    u32::try_from(index)
108        .map(NodeIndex::new)
109        .map_err(|_| GraphError::IndexCapacityExceeded {
110            category: "generated node index",
111            count: index,
112        })
113}
weavatrix_graph/generator/random.rs

weavatrix_graph/generator/
random.rs
