ade_graph_generators/
random_graph.rs

1fn lcg_next(state: &mut u64) -> u64 {
2    *state = state.wrapping_mul(1664525).wrapping_add(1013904223);
3    *state
4}
5
6fn mix64(mut z: u64) -> u64 {
7    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
8    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
9    z ^ (z >> 31)
10}
11
12pub fn generate_random_graph_data(n: usize, m: usize, seed: u64) -> (Vec<u32>, Vec<(u32, u32)>) {
13    if n == 0 {
14        return (Vec::new(), Vec::new());
15    }
16
17    let node_keys: Vec<u32> = (0..n as u32).collect();
18    let mut rng_state = seed;
19    let mut edges = Vec::with_capacity(m);
20
21    for _ in 0..m {
22        let from = (mix64(lcg_next(&mut rng_state)) % (n as u64)) as u32;
23        let mut to = (mix64(lcg_next(&mut rng_state)) % (n as u64)) as u32;
24        if to == from {
25            to = ((to as usize + 1) % n) as u32;
26        }
27        edges.push((from, to));
28    }
29
30    (node_keys, edges)
31}
32
33#[cfg(test)]
34mod tests {
35    use super::*;
36
37    #[test]
38    fn test_generate_random_graph_data_basic() {
39        let (nodes, edges) = generate_random_graph_data(5, 8, 42);
40
41        // Check node count and values
42        assert_eq!(nodes.len(), 5);
43        assert_eq!(nodes, vec![0, 1, 2, 3, 4]);
44
45        // Check edge count
46        assert_eq!(edges.len(), 8);
47
48        // Check that all edges are valid (no self-loops, nodes within range)
49        for (source, target) in &edges {
50            assert_ne!(source, target, "Self-loop found: {} -> {}", source, target);
51            assert!(*source < 5, "Source node {} out of range", source);
52            assert!(*target < 5, "Target node {} out of range", target);
53        }
54    }
55
56    #[test]
57    fn test_generate_random_graph_data_deterministic() {
58        // Same seed should produce same result
59        let (nodes1, edges1) = generate_random_graph_data(4, 6, 123);
60        let (nodes2, edges2) = generate_random_graph_data(4, 6, 123);
61
62        assert_eq!(nodes1, nodes2);
63        assert_eq!(edges1, edges2);
64
65        // Different seed should produce different result
66        let (nodes3, edges3) = generate_random_graph_data(4, 6, 456);
67        assert_eq!(nodes1, nodes3); // Nodes should be the same
68        assert_ne!(edges1, edges3); // Edges should be different
69    }
70
71    #[test]
72    fn test_generate_random_graph_data_edge_cases() {
73        // Single node, zero edges
74        let (nodes, edges) = generate_random_graph_data(1, 0, 1);
75        assert_eq!(nodes, vec![0]);
76        assert_eq!(edges, vec![]);
77
78        // Two nodes, one edge
79        let (nodes, edges) = generate_random_graph_data(2, 1, 2);
80        assert_eq!(nodes, vec![0, 1]);
81        assert_eq!(edges.len(), 1);
82        let edge = edges[0];
83        assert!(edge == (0, 1) || edge == (1, 0));
84
85        // Zero nodes, zero edges
86        let (nodes, edges) = generate_random_graph_data(0, 0, 3);
87        assert_eq!(nodes, vec![]);
88        assert_eq!(edges, vec![]);
89    }
90
91    #[test]
92    fn test_generate_random_graph_data_distribution() {
93        // Test that different seeds produce reasonably different results
94        let n = 5;
95        let m = 10;
96        let mut all_results = Vec::new();
97
98        for seed in 0..10 {
99            let (_, edges) = generate_random_graph_data(n, m, seed);
100            all_results.push(edges);
101        }
102
103        // Check that not all results are identical
104        let first_result = &all_results[0];
105        let all_identical = all_results.iter().all(|edges| edges == first_result);
106        assert!(
107            !all_identical,
108            "All results are identical - poor randomness"
109        );
110    }
111
112    #[test]
113    fn test_generate_random_graph_data_node_coverage() {
114        let (_nodes, edges) = generate_random_graph_data(10, 30, 555);
115
116        let mut nodes_in_edges = std::collections::HashSet::new();
117        for (source, target) in &edges {
118            nodes_in_edges.insert(*source);
119            nodes_in_edges.insert(*target);
120        }
121
122        assert!(
123            nodes_in_edges.len() >= 7,
124            "Only {} out of 10 nodes appear in edges",
125            nodes_in_edges.len()
126        );
127    }
128
129    #[test]
130    fn test_generate_random_graph_data_seed_consistency_across_calls() {
131        for seed in [1, 42, 100, 999, 1234567890] {
132            let result1 = generate_random_graph_data(5, 8, seed);
133            let result2 = generate_random_graph_data(5, 8, seed);
134            assert_eq!(result1, result2, "Inconsistent results for seed {}", seed);
135        }
136    }
137}
ade_graph_generators/random_graph.rs

ade_graph_generators/
random_graph.rs
