weavatrix_graph/generator/
random.rs

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

weavatrix_graph/generator/
random.rs
