rust_igraph/algorithms/paths/
random_walk.rs

1//! Random walk on a graph (ALGO-TR-003).
2//!
3//! Counterpart of `igraph_random_walk()` from
4//! `references/igraph/src/paths/random_walk.c:288`. Performs a
5//! discrete-time random walk starting at `start` for at most `steps`
6//! transitions. At each vertex the next neighbour is chosen
7//! - uniformly at random when `weights == None`,
8//! - with probability proportional to edge weight when `weights ==
9//!   Some(_)`.
10//!
11//! If the walk reaches a vertex with no outgoing neighbours under the
12//! chosen `mode`, the walk stops early (matches upstream's
13//! `IGRAPH_RANDOM_WALK_STUCK_RETURN` variant). The returned vertex
14//! chain always starts with `start`; the parallel edge chain has
15//! length `vertices.len() - 1`.
16//!
17//! For deterministic reproducibility the API takes a `seed: u64`
18//! parameter. We seed an inline `SplitMix64` PRNG — no external
19//! `rand` dependency. Callers wanting non-deterministic behaviour can
20//! pass `seed = std::time::SystemTime::now()`-derived bytes.
21
22use crate::algorithms::paths::dijkstra::DijkstraMode;
23use crate::core::graph::EdgeId;
24use crate::core::rng::SplitMix64;
25use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
26
27pub(super) fn validate_weights(graph: &Graph, weights: Option<&[f64]>) -> IgraphResult<()> {
28    let Some(w) = weights else {
29        return Ok(());
30    };
31    let m = graph.ecount();
32    if w.len() != m {
33        return Err(IgraphError::InvalidArgument(format!(
34            "weights vector size ({}) differs from edge count ({})",
35            w.len(),
36            m
37        )));
38    }
39    for (e, &v) in w.iter().enumerate() {
40        if v.is_nan() {
41            return Err(IgraphError::InvalidArgument(format!(
42                "weight at edge {e} is NaN"
43            )));
44        }
45        if v < 0.0 {
46            return Err(IgraphError::InvalidArgument(format!(
47                "weight at edge {e} is negative ({v}); random walk weights must be non-negative"
48            )));
49        }
50    }
51    Ok(())
52}
53
54fn incident_for_mode(graph: &Graph, v: VertexId, mode: DijkstraMode) -> IgraphResult<Vec<EdgeId>> {
55    if !graph.is_directed() {
56        return graph.incident(v);
57    }
58    match mode {
59        DijkstraMode::Out => graph.incident(v),
60        DijkstraMode::In => graph.incident_in(v),
61        DijkstraMode::All => {
62            let mut out = graph.incident(v)?;
63            out.extend(graph.incident_in(v)?);
64            Ok(out)
65        }
66    }
67}
68
69/// Random walk on `graph` starting at `start`, taking up to `steps`
70/// transitions.
71///
72/// `weights = None` selects neighbours uniformly. `weights = Some(_)`
73/// selects each candidate edge with probability proportional to its
74/// weight; a candidate edge with weight `0.0` is never chosen, but at
75/// least one outgoing edge of every visited vertex must have positive
76/// weight or the walk gets stuck. Negative or NaN weights return
77/// [`IgraphError::InvalidArgument`].
78///
79/// Returns `(vertex_chain, edge_chain)`. `vertex_chain[0] == start`;
80/// when the walk completes all `steps` transitions, the chain has
81/// length `steps + 1` and `edge_chain` has length `steps`. If the walk
82/// gets stuck early (no admissible outgoing edges), the result is
83/// truncated to the actual prefix (matches upstream's
84/// `IGRAPH_RANDOM_WALK_STUCK_RETURN`).
85///
86/// `seed` deterministically initialises the internal `SplitMix64`
87/// PRNG — same `(graph, start, mode, steps, weights, seed)` always
88/// produces the same chain.
89///
90/// Counterpart of `igraph_random_walk(_, &weights, _, _, start, mode,
91/// steps, IGRAPH_RANDOM_WALK_STUCK_RETURN)`.
92///
93/// # Examples
94///
95/// ```
96/// use rust_igraph::{Graph, random_walk, DijkstraMode};
97///
98/// // 4-cycle 0-1-2-3-0: every vertex has two neighbours so the walk
99/// // never gets stuck.
100/// let mut g = Graph::with_vertices(4);
101/// g.add_edge(0, 1).unwrap();
102/// g.add_edge(1, 2).unwrap();
103/// g.add_edge(2, 3).unwrap();
104/// g.add_edge(3, 0).unwrap();
105/// let (vs, es) = random_walk(&g, None, 0, DijkstraMode::Out, 5, 42).unwrap();
106/// assert_eq!(vs.len(), 6);
107/// assert_eq!(es.len(), 5);
108/// assert_eq!(vs[0], 0);
109/// ```
110pub fn random_walk(
111    graph: &Graph,
112    weights: Option<&[f64]>,
113    start: VertexId,
114    mode: DijkstraMode,
115    steps: u32,
116    seed: u64,
117) -> IgraphResult<(Vec<VertexId>, Vec<EdgeId>)> {
118    let n = graph.vcount();
119    if start >= n {
120        return Err(IgraphError::VertexOutOfRange { id: start, n });
121    }
122    validate_weights(graph, weights)?;
123
124    let mut rng = SplitMix64::new(seed);
125    let mut vs: Vec<VertexId> = Vec::with_capacity(steps as usize + 1);
126    let mut es: Vec<EdgeId> = Vec::with_capacity(steps as usize);
127    vs.push(start);
128
129    let mut current = start;
130    for _ in 0..steps {
131        let incidents = incident_for_mode(graph, current, mode)?;
132        if incidents.is_empty() {
133            break;
134        }
135
136        let next_eid = match weights {
137            None => {
138                let idx = rng.gen_index(incidents.len());
139                Some(incidents[idx])
140            }
141            Some(ws) => {
142                // Sum admissible weights (skip non-finite). If sum is 0,
143                // there is no admissible outgoing edge and the walk
144                // stops early.
145                let mut total = 0.0_f64;
146                for &eid in &incidents {
147                    let w = ws[eid as usize];
148                    if w.is_finite() && w > 0.0 {
149                        total += w;
150                    }
151                }
152                if total <= 0.0 {
153                    None
154                } else {
155                    let target = rng.gen_unit() * total;
156                    let mut acc = 0.0_f64;
157                    let mut chosen: Option<EdgeId> = None;
158                    for &eid in &incidents {
159                        let w = ws[eid as usize];
160                        if !(w.is_finite() && w > 0.0) {
161                            continue;
162                        }
163                        acc += w;
164                        if acc >= target {
165                            chosen = Some(eid);
166                            break;
167                        }
168                    }
169                    // Floating-point edge case: if rounding put `acc` a
170                    // hair below `target`, fall back to the last
171                    // positive-weight edge.
172                    if chosen.is_none() {
173                        for &eid in incidents.iter().rev() {
174                            let w = ws[eid as usize];
175                            if w.is_finite() && w > 0.0 {
176                                chosen = Some(eid);
177                                break;
178                            }
179                        }
180                    }
181                    chosen
182                }
183            }
184        };
185
186        let Some(eid) = next_eid else {
187            break;
188        };
189        let next_vertex = graph.edge_other(eid, current)?;
190        es.push(eid);
191        vs.push(next_vertex);
192        current = next_vertex;
193    }
194
195    Ok((vs, es))
196}
197
198#[cfg(test)]
199mod tests {
200    use super::*;
201
202    #[test]
203    fn unit_weights_4_cycle_walk_length() {
204        let mut g = Graph::with_vertices(4);
205        g.add_edge(0, 1).unwrap();
206        g.add_edge(1, 2).unwrap();
207        g.add_edge(2, 3).unwrap();
208        g.add_edge(3, 0).unwrap();
209        let (vs, es) = random_walk(&g, None, 0, DijkstraMode::Out, 5, 42).unwrap();
210        assert_eq!(vs.len(), 6);
211        assert_eq!(es.len(), 5);
212        assert_eq!(vs[0], 0);
213        // Every step is along an edge: consecutive vertices are
214        // adjacent in the input graph.
215        for w in vs.windows(2) {
216            let (a, b) = (w[0], w[1]);
217            assert!(
218                (g.find_eid(a, b).unwrap()).is_some() || (g.find_eid(b, a).unwrap()).is_some(),
219                "non-adjacent step {a}→{b}"
220            );
221        }
222    }
223
224    #[test]
225    fn stuck_returns_shorter_walk() {
226        // Sink vertex 1 has no outgoing edges in OUT mode.
227        let mut g = Graph::new(3, true).unwrap();
228        g.add_edge(0, 1).unwrap();
229        g.add_edge(2, 1).unwrap();
230        let (vs, es) = random_walk(&g, None, 0, DijkstraMode::Out, 10, 7).unwrap();
231        // 0→1 is the only step; sink 1 has no out-edges → stops.
232        assert_eq!(vs, vec![0, 1]);
233        assert_eq!(es.len(), 1);
234    }
235
236    #[test]
237    fn zero_steps_returns_singleton() {
238        let mut g = Graph::with_vertices(3);
239        g.add_edge(0, 1).unwrap();
240        let (vs, es) = random_walk(&g, None, 1, DijkstraMode::Out, 0, 0).unwrap();
241        assert_eq!(vs, vec![1]);
242        assert!(es.is_empty());
243    }
244
245    #[test]
246    fn isolated_vertex_stuck_immediately() {
247        let g = Graph::with_vertices(3);
248        let (vs, es) = random_walk(&g, None, 1, DijkstraMode::Out, 5, 0).unwrap();
249        assert_eq!(vs, vec![1]);
250        assert!(es.is_empty());
251    }
252
253    #[test]
254    fn deterministic_with_same_seed() {
255        let mut g = Graph::with_vertices(5);
256        for i in 0..5u32 {
257            g.add_edge(i, (i + 1) % 5).unwrap();
258            g.add_edge(i, (i + 2) % 5).unwrap();
259        }
260        let r1 = random_walk(&g, None, 0, DijkstraMode::Out, 20, 12345).unwrap();
261        let r2 = random_walk(&g, None, 0, DijkstraMode::Out, 20, 12345).unwrap();
262        assert_eq!(r1, r2);
263    }
264
265    #[test]
266    fn different_seeds_yield_different_walks() {
267        let mut g = Graph::with_vertices(5);
268        for i in 0..5u32 {
269            g.add_edge(i, (i + 1) % 5).unwrap();
270            g.add_edge(i, (i + 2) % 5).unwrap();
271        }
272        let r1 = random_walk(&g, None, 0, DijkstraMode::Out, 20, 1).unwrap();
273        let r2 = random_walk(&g, None, 0, DijkstraMode::Out, 20, 2).unwrap();
274        // Probabilistically these almost surely differ; deterministic
275        // because the PRNG is seeded.
276        assert_ne!(r1, r2);
277    }
278
279    #[test]
280    fn weighted_walk_picks_only_positive_weight_edges() {
281        // 0-1 weight 1, 0-2 weight 0: 0→2 must never be chosen.
282        let mut g = Graph::with_vertices(3);
283        g.add_edge(0, 1).unwrap();
284        g.add_edge(0, 2).unwrap();
285        let weights = [1.0_f64, 0.0];
286        // Need a return path from 1; add 1-0 reverse via the same edge
287        // (undirected, so 0-1 ≡ 1-0).
288        // Run a couple of one-step walks; every one must end at 1.
289        for seed in 0..16u64 {
290            let (vs, _) = random_walk(&g, Some(&weights), 0, DijkstraMode::Out, 1, seed).unwrap();
291            assert_eq!(vs, vec![0, 1], "seed {seed}");
292        }
293    }
294
295    #[test]
296    fn weighted_zero_total_weight_stops_early() {
297        // All outgoing edges have weight 0 → no admissible edge.
298        let mut g = Graph::with_vertices(3);
299        g.add_edge(0, 1).unwrap();
300        g.add_edge(0, 2).unwrap();
301        let weights = [0.0_f64, 0.0];
302        let (vs, es) = random_walk(&g, Some(&weights), 0, DijkstraMode::Out, 5, 0).unwrap();
303        assert_eq!(vs, vec![0]);
304        assert!(es.is_empty());
305    }
306
307    #[test]
308    fn negative_weight_errors() {
309        let mut g = Graph::with_vertices(2);
310        g.add_edge(0, 1).unwrap();
311        let weights = [-1.0_f64];
312        assert!(random_walk(&g, Some(&weights), 0, DijkstraMode::Out, 1, 0).is_err());
313    }
314
315    #[test]
316    fn nan_weight_errors() {
317        let mut g = Graph::with_vertices(2);
318        g.add_edge(0, 1).unwrap();
319        let weights = [f64::NAN];
320        assert!(random_walk(&g, Some(&weights), 0, DijkstraMode::Out, 1, 0).is_err());
321    }
322
323    #[test]
324    fn out_of_range_start_errors() {
325        let g = Graph::with_vertices(3);
326        assert!(random_walk(&g, None, 99, DijkstraMode::Out, 1, 0).is_err());
327    }
328
329    #[test]
330    fn weights_size_mismatch_errors() {
331        let mut g = Graph::with_vertices(2);
332        g.add_edge(0, 1).unwrap();
333        let weights = [1.0_f64, 2.0];
334        assert!(random_walk(&g, Some(&weights), 0, DijkstraMode::Out, 1, 0).is_err());
335    }
336
337    #[test]
338    fn directed_in_mode_walks_reverse_edges() {
339        let mut g = Graph::new(3, true).unwrap();
340        g.add_edge(0, 1).unwrap();
341        g.add_edge(1, 2).unwrap();
342        // From sink 2 with IN-mode: reaches 1 in step 1, 0 in step 2.
343        let (vs, _) = random_walk(&g, None, 2, DijkstraMode::In, 2, 0).unwrap();
344        assert_eq!(vs, vec![2, 1, 0]);
345    }
346}
rust_igraph/algorithms/paths/random_walk.rs

rust_igraph/algorithms/paths/
random_walk.rs
