rust_igraph/algorithms/paths/
simple_paths.rs

1//! All simple paths enumeration (ALGO-SP-031).
2//!
3//! Counterpart of `igraph_get_all_simple_paths` from
4//! `references/igraph/src/paths/simple_paths.c` (189 lines).
5
6use crate::core::{Graph, IgraphResult};
7
8/// Mode for traversing neighbors in directed graphs.
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum SimplePathMode {
11    /// Follow outgoing edges only.
12    Out,
13    /// Follow incoming edges only.
14    In,
15    /// Treat directed edges as undirected.
16    All,
17}
18
19/// Enumerate all simple paths from `from` to vertices in `to`.
20///
21/// A path is *simple* if no vertex appears more than once. Returns
22/// paths as vertex sequences (including `from` and the final vertex).
23///
24/// Multi-edges and self-loops in the graph are ignored — the neighbor
25/// list is deduplicated before traversal.
26///
27/// # Parameters
28///
29/// - `to`: target vertices. If `None`, all vertices are targets.
30/// - `mode`: direction of traversal for directed graphs. Ignored for
31///   undirected graphs.
32/// - `min_len`: minimum path length (number of edges). Paths shorter
33///   than this are not returned. Use 0 or negative for no lower bound.
34/// - `max_len`: maximum path length. Use a negative value for no
35///   upper bound.
36/// - `max_results`: maximum number of paths to return. Use a negative
37///   value for no limit.
38///
39/// # Examples
40///
41/// ```
42/// use rust_igraph::{Graph, create, all_simple_paths, SimplePathMode};
43///
44/// // Path graph: 0-1-2-3
45/// let g = create(&[(0,1),(1,2),(2,3)], 4, false).unwrap();
46/// let paths = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).unwrap();
47/// // From 0: paths to 1 (len 1), to 2 (len 2), to 3 (len 3)
48/// assert_eq!(paths.len(), 3);
49/// ```
50pub fn all_simple_paths(
51    graph: &Graph,
52    from: u32,
53    to: Option<&[u32]>,
54    mode: SimplePathMode,
55    min_len: i32,
56    max_len: i32,
57    max_results: i64,
58) -> IgraphResult<Vec<Vec<u32>>> {
59    let vcount = graph.vcount();
60    if from >= vcount {
61        return Err(crate::core::IgraphError::InvalidArgument(
62            "source vertex out of range".to_string(),
63        ));
64    }
65
66    let mut result: Vec<Vec<u32>> = Vec::new();
67
68    if max_results == 0 {
69        return Ok(result);
70    }
71
72    let target_set: Option<Vec<bool>> = to.map(|targets| {
73        let mut set = vec![false; vcount as usize];
74        for &t in targets {
75            if (t as usize) < set.len() {
76                set[t as usize] = true;
77            }
78        }
79        set
80    });
81
82    let adj = build_adjlist(graph, mode)?;
83
84    let mut stack: Vec<u32> = vec![from];
85    let mut dist: Vec<i32> = vec![0];
86    let mut added = vec![false; vcount as usize];
87    let mut nptr = vec![0usize; vcount as usize];
88    added[from as usize] = true;
89
90    while let Some(&act) = stack.last() {
91        let cur_dist = *dist.last().unwrap_or(&0);
92        let neis = &adj[act as usize];
93        let n = neis.len();
94        let ptr = &mut nptr[act as usize];
95
96        let within_dist = max_len < 0 || cur_dist < max_len;
97        let mut found_nei = false;
98        let mut nei = 0u32;
99
100        if within_dist {
101            while !found_nei && *ptr < n {
102                nei = neis[*ptr];
103                found_nei = !added[nei as usize];
104                *ptr += 1;
105            }
106        }
107
108        if within_dist && found_nei {
109            stack.push(nei);
110            dist.push(cur_dist + 1);
111            added[nei as usize] = true;
112
113            let is_target = match &target_set {
114                None => true,
115                Some(set) => set[nei as usize],
116            };
117            if is_target && (min_len <= 0 || cur_dist + 1 >= min_len) {
118                result.push(stack.clone());
119                if max_results >= 0
120                    && i64::try_from(result.len()).unwrap_or(i64::MAX) >= max_results
121                {
122                    break;
123                }
124            }
125        } else {
126            let up = stack.pop().unwrap_or(0);
127            dist.pop();
128            added[up as usize] = false;
129            nptr[up as usize] = 0;
130        }
131    }
132
133    Ok(result)
134}
135
136fn build_adjlist(graph: &Graph, mode: SimplePathMode) -> IgraphResult<Vec<Vec<u32>>> {
137    let n = graph.vcount();
138    let mut adj = Vec::with_capacity(n as usize);
139
140    for v in 0..n {
141        let raw = match mode {
142            SimplePathMode::Out => {
143                if graph.is_directed() {
144                    graph.out_neighbors_vec(v)?
145                } else {
146                    graph.neighbors(v)?
147                }
148            }
149            SimplePathMode::In => {
150                if graph.is_directed() {
151                    graph.in_neighbors_vec(v)?
152                } else {
153                    graph.neighbors(v)?
154                }
155            }
156            SimplePathMode::All => {
157                if graph.is_directed() {
158                    let mut all = graph.out_neighbors_vec(v)?;
159                    all.extend(graph.in_neighbors_vec(v)?);
160                    all
161                } else {
162                    graph.neighbors(v)?
163                }
164            }
165        };
166
167        let mut deduped: Vec<u32> = Vec::with_capacity(raw.len());
168        for &nei in &raw {
169            if nei != v && !deduped.contains(&nei) {
170                deduped.push(nei);
171            }
172        }
173        adj.push(deduped);
174    }
175
176    Ok(adj)
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182    use crate::create;
183
184    #[test]
185    fn empty_graph() {
186        let g = Graph::with_vertices(0);
187        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1);
188        assert!(r.is_err());
189    }
190
191    #[test]
192    fn single_vertex() {
193        let g = Graph::with_vertices(1);
194        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
195        assert!(r.is_empty());
196    }
197
198    #[test]
199    fn single_edge() {
200        let g = create(&[(0, 1)], 2, false).expect("ok");
201        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
202        assert_eq!(r.len(), 1);
203        assert_eq!(r[0], vec![0, 1]);
204    }
205
206    #[test]
207    fn path_3() {
208        let g = create(&[(0, 1), (1, 2)], 3, false).expect("ok");
209        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
210        assert_eq!(r.len(), 2);
211        assert_eq!(r[0], vec![0, 1]);
212        assert_eq!(r[1], vec![0, 1, 2]);
213    }
214
215    #[test]
216    fn triangle_from_0() {
217        let g = create(&[(0, 1), (1, 2), (0, 2)], 3, false).expect("ok");
218        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
219        // 0->1, 0->1->2, 0->2, 0->2->1
220        assert_eq!(r.len(), 4);
221    }
222
223    #[test]
224    fn target_filter() {
225        let g = create(&[(0, 1), (1, 2), (2, 3)], 4, false).expect("ok");
226        let r = all_simple_paths(&g, 0, Some(&[3]), SimplePathMode::Out, 0, -1, -1).expect("ok");
227        assert_eq!(r.len(), 1);
228        assert_eq!(r[0], vec![0, 1, 2, 3]);
229    }
230
231    #[test]
232    fn max_len_filter() {
233        let g = create(&[(0, 1), (1, 2), (2, 3)], 4, false).expect("ok");
234        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, 2, -1).expect("ok");
235        // Only paths of length <= 2: [0,1] and [0,1,2]
236        assert_eq!(r.len(), 2);
237    }
238
239    #[test]
240    fn min_len_filter() {
241        let g = create(&[(0, 1), (1, 2), (2, 3)], 4, false).expect("ok");
242        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 2, -1, -1).expect("ok");
243        // Only paths of length >= 2: [0,1,2] and [0,1,2,3]
244        assert_eq!(r.len(), 2);
245    }
246
247    #[test]
248    fn max_results() {
249        let g = create(&[(0, 1), (1, 2), (2, 3)], 4, false).expect("ok");
250        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, 2).expect("ok");
251        assert_eq!(r.len(), 2);
252    }
253
254    #[test]
255    fn directed_out() {
256        let g = create(&[(0, 1), (1, 2), (2, 0)], 3, true).expect("ok");
257        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
258        // 0->1, 0->1->2
259        assert_eq!(r.len(), 2);
260        assert_eq!(r[0], vec![0, 1]);
261        assert_eq!(r[1], vec![0, 1, 2]);
262    }
263
264    #[test]
265    fn directed_in() {
266        let g = create(&[(0, 1), (1, 2), (2, 0)], 3, true).expect("ok");
267        let r = all_simple_paths(&g, 0, None, SimplePathMode::In, 0, -1, -1).expect("ok");
268        // In mode from 0: follow incoming edges → 2->0, then 1->2, so: [0,2], [0,2,1]
269        assert_eq!(r.len(), 2);
270        assert_eq!(r[0], vec![0, 2]);
271        assert_eq!(r[1], vec![0, 2, 1]);
272    }
273
274    #[test]
275    fn directed_all() {
276        let g = create(&[(0, 1), (1, 2)], 3, true).expect("ok");
277        let r = all_simple_paths(&g, 1, None, SimplePathMode::All, 0, -1, -1).expect("ok");
278        // From 1 in ALL mode: can go to 0 (reverse 0->1) and to 2 (forward 1->2)
279        // So: [1,0], [1,2]
280        assert_eq!(r.len(), 2);
281    }
282
283    #[test]
284    fn self_loop_ignored() {
285        let g = create(&[(0, 0), (0, 1)], 2, false).expect("ok");
286        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
287        assert_eq!(r.len(), 1);
288        assert_eq!(r[0], vec![0, 1]);
289    }
290
291    #[test]
292    fn multi_edge_ignored() {
293        let g = create(&[(0, 1), (0, 1), (1, 2)], 3, false).expect("ok");
294        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
295        assert_eq!(r.len(), 2);
296        assert_eq!(r[0], vec![0, 1]);
297        assert_eq!(r[1], vec![0, 1, 2]);
298    }
299
300    #[test]
301    fn disconnected() {
302        let g = create(&[(0, 1), (2, 3)], 4, false).expect("ok");
303        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
304        assert_eq!(r.len(), 1);
305        assert_eq!(r[0], vec![0, 1]);
306    }
307
308    #[test]
309    fn source_out_of_range() {
310        let g = Graph::with_vertices(3);
311        let r = all_simple_paths(&g, 5, None, SimplePathMode::Out, 0, -1, -1);
312        assert!(r.is_err());
313    }
314
315    #[test]
316    fn max_results_zero() {
317        let g = create(&[(0, 1)], 2, false).expect("ok");
318        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, 0).expect("ok");
319        assert!(r.is_empty());
320    }
321
322    #[test]
323    fn k4_complete() {
324        let g = create(&[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)], 4, false).expect("ok");
325        let r = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, -1).expect("ok");
326        // K4 from 0: 3 paths of len 1, 4 paths of len 2, 2 paths of len 3 = 9 total
327        // len 1: [0,1], [0,2], [0,3]
328        // len 2: [0,1,2], [0,1,3], [0,2,3], [0,3,2] — wait, also [0,2,1], [0,3,1] etc.
329        // Actually K4: from 0, neighbors are {1,2,3}
330        // DFS explores: 0->1->2->3, 0->1->3->2, 0->2->1->3, 0->2->3->1, 0->3->1->2, 0->3->2->1
331        // Paths found along the way include all intermediate prefixes
332        // Let me just check the count is correct
333        assert!(r.len() >= 9, "got {} paths", r.len());
334    }
335}
336
337#[cfg(all(test, feature = "proptest-harness"))]
338mod proptests {
339    use super::*;
340    use crate::create;
341    use proptest::prelude::*;
342
343    fn arb_graph(max_v: u32) -> impl Strategy<Value = Graph> {
344        (2..=max_v).prop_flat_map(|n| {
345            let max_e = (n as usize)
346                .saturating_mul(n.saturating_sub(1) as usize)
347                .min(20);
348            proptest::collection::vec((0..n, 0..n), 0..=max_e).prop_map(move |edges| {
349                let edge_tuples: Vec<(u32, u32)> = edges.into_iter().collect();
350                create(&edge_tuples, n, false).expect("arb graph")
351            })
352        })
353    }
354
355    proptest! {
356        #[test]
357        fn all_paths_are_simple(g in arb_graph(6)) {
358            let n = g.vcount();
359            if n > 0 {
360                let paths = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, 100)
361                    .expect("ok");
362                for path in &paths {
363                    let mut seen = vec![false; n as usize];
364                    for &v in path {
365                        prop_assert!(
366                            !seen[v as usize],
367                            "vertex {v} repeated in path {:?}",
368                            path
369                        );
370                        seen[v as usize] = true;
371                    }
372                }
373            }
374        }
375
376        #[test]
377        fn all_paths_start_with_source(g in arb_graph(6)) {
378            let n = g.vcount();
379            if n > 0 {
380                let paths = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, 100)
381                    .expect("ok");
382                for path in &paths {
383                    prop_assert_eq!(
384                        path[0], 0,
385                        "path {:?} does not start with source 0",
386                        path
387                    );
388                }
389            }
390        }
391
392        #[test]
393        fn path_edges_exist(g in arb_graph(6)) {
394            let n = g.vcount();
395            if n > 0 {
396                let paths = all_simple_paths(&g, 0, None, SimplePathMode::Out, 0, -1, 100)
397                    .expect("ok");
398                for path in &paths {
399                    for w in path.windows(2) {
400                        let neis = g.neighbors(w[0]).expect("ok");
401                        prop_assert!(
402                            neis.contains(&w[1]),
403                            "edge {}->{} not in graph but in path {:?}",
404                            w[0], w[1], path
405                        );
406                    }
407                }
408            }
409        }
410    }
411}
rust_igraph/algorithms/paths/simple_paths.rs

rust_igraph/algorithms/paths/
simple_paths.rs
