problemreductions/
random.rs

1//! Shared deterministic building blocks for model-owned random generators.
2
3use crate::registry::ConstructionError;
4use crate::topology::SimpleGraph;
5use serde::Deserialize;
6
7/// Inputs shared by models generated from an Erdős–Rényi simple graph.
8#[derive(Debug, Deserialize, crate::CreateSpec)]
9pub struct SimpleGraphRandomSpec {
10    /// Number of graph vertices.
11    pub num_vertices: usize,
12    /// Independent probability of including each possible edge (default: 0.5).
13    pub edge_prob: Option<f64>,
14    /// Seed for reproducible generation.
15    pub seed: Option<i64>,
16}
17
18/// Inputs shared by integer-lattice graph generators.
19#[derive(Debug, Deserialize, crate::CreateSpec)]
20pub struct IntegerGeometryRandomSpec {
21    /// Number of graph vertices.
22    pub num_vertices: usize,
23    /// Seed for reproducible generation.
24    pub seed: Option<i64>,
25}
26
27/// Inputs shared by unit-disk graph generators.
28#[derive(Debug, Deserialize, crate::CreateSpec)]
29pub struct UnitDiskRandomSpec {
30    /// Number of graph vertices.
31    pub num_vertices: usize,
32    /// Disk radius used to derive edges (default: 1.0).
33    pub radius: Option<f64>,
34    /// Seed for reproducible generation.
35    pub seed: Option<i64>,
36}
37
38/// Random simple-graph inputs with a required clique size.
39#[derive(Debug, Deserialize, crate::CreateSpec)]
40pub struct CliqueRandomSpec {
41    /// Number of graph vertices.
42    pub num_vertices: usize,
43    /// Independent edge probability (default: 0.5).
44    pub edge_prob: Option<f64>,
45    /// Seed for reproducible generation.
46    pub seed: Option<i64>,
47    /// Required clique size.
48    pub k: usize,
49}
50
51impl CliqueRandomSpec {
52    /// Generate the graph using the common graph inputs.
53    pub fn graph(&self) -> Result<SimpleGraph, ConstructionError> {
54        SimpleGraphRandomSpec {
55            num_vertices: self.num_vertices,
56            edge_prob: self.edge_prob,
57            seed: self.seed,
58        }
59        .graph()
60    }
61}
62
63/// Random simple-graph inputs with optional source and sink vertices.
64#[derive(Debug, Deserialize, crate::CreateSpec)]
65pub struct EndpointRandomSpec {
66    /// Number of graph vertices.
67    pub num_vertices: usize,
68    /// Independent edge probability (default: 0.5).
69    pub edge_prob: Option<f64>,
70    /// Seed for reproducible generation.
71    pub seed: Option<i64>,
72    /// Source vertex (default: 0).
73    pub source: Option<usize>,
74    /// Sink vertex (default: the final vertex).
75    pub sink: Option<usize>,
76}
77
78/// Random simple-graph inputs with an optional runtime color count.
79#[derive(Debug, Deserialize, crate::CreateSpec)]
80pub struct ColoringRandomSpec {
81    /// Number of graph vertices.
82    pub num_vertices: usize,
83    /// Independent edge probability (default: 0.5).
84    pub edge_prob: Option<f64>,
85    /// Seed for reproducible generation.
86    pub seed: Option<i64>,
87    /// Runtime color count (default: 3).
88    pub k: Option<usize>,
89}
90
91impl ColoringRandomSpec {
92    /// Generate the graph using the common graph inputs.
93    pub fn graph(&self) -> Result<SimpleGraph, ConstructionError> {
94        SimpleGraphRandomSpec {
95            num_vertices: self.num_vertices,
96            edge_prob: self.edge_prob,
97            seed: self.seed,
98        }
99        .graph()
100    }
101}
102
103impl EndpointRandomSpec {
104    /// Generate the graph using the common graph inputs.
105    pub fn graph(&self) -> Result<SimpleGraph, ConstructionError> {
106        SimpleGraphRandomSpec {
107            num_vertices: self.num_vertices,
108            edge_prob: self.edge_prob,
109            seed: self.seed,
110        }
111        .graph()
112    }
113
114    /// Validate and return distinct source and sink vertices.
115    pub fn endpoints(&self) -> Result<(usize, usize), ConstructionError> {
116        if self.num_vertices < 2 {
117            return Err("num_vertices must be at least 2".into());
118        }
119        let source = self.source.unwrap_or(0);
120        let sink = self.sink.unwrap_or(self.num_vertices - 1);
121        if source >= self.num_vertices || sink >= self.num_vertices {
122            return Err(format!(
123                "source and sink must be below num_vertices ({})",
124                self.num_vertices
125            )
126            .into());
127        }
128        if source == sink {
129            return Err("source and sink must be distinct".into());
130        }
131        Ok((source, sink))
132    }
133}
134
135impl SimpleGraphRandomSpec {
136    /// Generate the requested graph after validating its probability.
137    pub fn graph(&self) -> Result<SimpleGraph, ConstructionError> {
138        let edge_prob = self.edge_prob.unwrap_or(0.5);
139        if !(0.0..=1.0).contains(&edge_prob) {
140            return Err(format!("edge_prob must be between 0 and 1, got {edge_prob}").into());
141        }
142        Ok(create_random_graph(
143            self.num_vertices,
144            edge_prob,
145            seed_to_u64(self.seed)?,
146        ))
147    }
148}
149
150/// Implement a typed, model-owned random generator using a typed input spec.
151#[macro_export]
152macro_rules! impl_random_generate {
153    ($target:ty, $spec:ty, |$input:ident| $body:block) => {
154        impl $crate::registry::RandomGenerate for $target {
155            fn inputs() -> Vec<$crate::registry::CreateInputInfo> {
156                <$spec as $crate::registry::CreateSpec>::inputs()
157            }
158
159            fn generate(
160                data: serde_json::Value,
161            ) -> Result<Self, $crate::registry::ConstructionError> {
162                $crate::registry::validate_create_inputs(&Self::inputs(), &data)?;
163                let $input: $spec = <$spec as $crate::registry::CreateSpec>::deserialize_inputs(
164                    data,
165                )
166                .map_err(|error| {
167                    $crate::registry::ConstructionError::InvalidInput(error.to_string())
168                })?;
169                let generate = || -> Result<Self, $crate::registry::ConstructionError> { $body };
170                generate()
171            }
172        }
173    };
174}
175
176/// LCG PRNG step returning a uniform value in `[0, 1)`.
177pub(crate) fn lcg_step(state: &mut u64) -> f64 {
178    *state = state
179        .wrapping_mul(6364136223846793005)
180        .wrapping_add(1442695040888963407);
181    (*state >> 33) as f64 / (1u64 << 31) as f64
182}
183
184/// Initialize LCG state from a seed or the current time.
185pub(crate) fn lcg_init(seed: Option<u64>) -> u64 {
186    seed.unwrap_or_else(|| {
187        let duration = std::time::SystemTime::now()
188            .duration_since(std::time::UNIX_EPOCH)
189            .expect("system clock must be after the Unix epoch");
190        duration.as_secs() ^ u64::from(duration.subsec_nanos())
191    })
192}
193
194/// Generate an Erdős–Rényi simple graph.
195pub(crate) fn create_random_graph(
196    num_vertices: usize,
197    edge_prob: f64,
198    seed: Option<u64>,
199) -> SimpleGraph {
200    let mut state = lcg_init(seed);
201    let edges = (0..num_vertices)
202        .flat_map(|u| ((u + 1)..num_vertices).map(move |v| (u, v)))
203        .filter(|_| lcg_step(&mut state) < edge_prob)
204        .collect();
205    SimpleGraph::new(num_vertices, edges)
206}
207
208/// Generate unique integer positions on a square grid.
209pub(crate) fn create_random_int_positions(
210    num_vertices: usize,
211    seed: Option<u64>,
212) -> Vec<(i64, i64)> {
213    let mut state = lcg_init(seed);
214    let grid_size = (num_vertices as f64).sqrt().ceil() as i64 + 1;
215    let capacity = (grid_size * grid_size) as usize;
216    lcg_choose(&mut state, capacity, num_vertices)
217        .expect("grid capacity exceeds the requested position count")
218        .into_iter()
219        .map(|index| {
220            let index = i64::try_from(index).expect("random position index exceeds i64");
221            (index / grid_size, index % grid_size)
222        })
223        .collect()
224}
225
226/// Generate float positions in `[0, sqrt(N)]²`.
227pub(crate) fn create_random_float_positions(
228    num_vertices: usize,
229    seed: Option<u64>,
230) -> Vec<(f64, f64)> {
231    let mut state = lcg_init(seed);
232    let side = (num_vertices as f64).sqrt();
233    (0..num_vertices)
234        .map(|_| (lcg_step(&mut state) * side, lcg_step(&mut state) * side))
235        .collect()
236}
237
238/// Choose `k` distinct sorted indices from `0..n`.
239pub(crate) fn lcg_choose(
240    state: &mut u64,
241    n: usize,
242    k: usize,
243) -> Result<Vec<usize>, ConstructionError> {
244    if k > n {
245        return Err(ConstructionError::Conversion(format!(
246            "cannot choose {k} elements from {n}"
247        )));
248    }
249    let mut indices = (0..n).collect::<Vec<_>>();
250    for i in 0..k {
251        let j = i + (lcg_step(state) * (n - i) as f64) as usize % (n - i);
252        indices.swap(i, j);
253    }
254    let mut chosen = indices[..k].to_vec();
255    chosen.sort_unstable();
256    Ok(chosen)
257}
258
259pub(crate) fn seed_to_u64(seed: Option<i64>) -> Result<Option<u64>, ConstructionError> {
260    seed.map(|value| u64::try_from(value).map_err(|_| "seed must be a nonnegative i64".into()))
261        .transpose()
262}
problemreductions/random.rs

problemreductions/
random.rs
