uni_algo/algo/algorithms/
all_simple_paths.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! All Simple Paths Algorithm.
5//!
6//! Finds all simple (loop-less) paths between source and target.
7//! Depth-First Search with backtracking.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use uni_common::core::id::Vid;
12
13pub struct AllSimplePaths;
14
15#[derive(Debug, Clone)]
16pub struct AllSimplePathsConfig {
17    pub source: Vid,
18    pub target: Vid,
19    pub min_depth: usize,
20    pub max_depth: usize,
21    pub limit: usize, // Max paths to return
22}
23
24impl Default for AllSimplePathsConfig {
25    fn default() -> Self {
26        Self {
27            source: Vid::from(0),
28            target: Vid::from(0),
29            min_depth: 0,
30            max_depth: 5,
31            limit: 100,
32        }
33    }
34}
35
36pub struct AllSimplePathsResult {
37    pub paths: Vec<Vec<Vid>>,
38}
39
40impl Algorithm for AllSimplePaths {
41    type Config = AllSimplePathsConfig;
42    type Result = AllSimplePathsResult;
43
44    fn name() -> &'static str {
45        "all_simple_paths"
46    }
47
48    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
49        let source_slot = match graph.to_slot(config.source) {
50            Some(s) => s,
51            None => return AllSimplePathsResult { paths: Vec::new() },
52        };
53        let target_slot = match graph.to_slot(config.target) {
54            Some(s) => s,
55            None => return AllSimplePathsResult { paths: Vec::new() },
56        };
57
58        let mut paths = Vec::new();
59        let mut current_path = Vec::with_capacity(config.max_depth + 1);
60        let mut visited = vec![false; graph.vertex_count()];
61
62        current_path.push(source_slot);
63        visited[source_slot as usize] = true;
64
65        dfs(
66            graph,
67            source_slot,
68            target_slot,
69            &config,
70            &mut current_path,
71            &mut visited,
72            &mut paths,
73        );
74
75        let mapped_paths = paths
76            .into_iter()
77            .map(|path| path.into_iter().map(|idx| graph.to_vid(idx)).collect())
78            .collect();
79
80        AllSimplePathsResult {
81            paths: mapped_paths,
82        }
83    }
84}
85
86fn dfs(
87    graph: &GraphProjection,
88    u: u32,
89    target: u32,
90    config: &AllSimplePathsConfig,
91    path: &mut Vec<u32>,
92    visited: &mut [bool],
93    paths: &mut Vec<Vec<u32>>,
94) {
95    if paths.len() >= config.limit {
96        return;
97    }
98
99    let depth = path.len() - 1; // path includes source
100    if depth > config.max_depth {
101        return;
102    }
103
104    if u == target {
105        if depth >= config.min_depth {
106            paths.push(path.clone());
107        }
108        // Continue searching? Simple path ends at target?
109        // Or can go through target? No, simple path contains nodes only once.
110        // We can't go through target and come back to target because target is visited.
111        // But we could continue from target to find longer paths if target wasn't the goal?
112        // But here target IS the goal.
113        return;
114    }
115
116    for &v in graph.out_neighbors(u) {
117        if !visited[v as usize] {
118            visited[v as usize] = true;
119            path.push(v);
120            dfs(graph, v, target, config, path, visited, paths);
121            path.pop();
122            visited[v as usize] = false;
123        }
124    }
125}
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130    use crate::algo::test_utils::build_test_graph;
131
132    #[test]
133    fn test_simple_paths_diamond() {
134        // 0->1->3, 0->2->3
135        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2), Vid::from(3)];
136        let edges = vec![
137            (Vid::from(0), Vid::from(1)),
138            (Vid::from(1), Vid::from(3)),
139            (Vid::from(0), Vid::from(2)),
140            (Vid::from(2), Vid::from(3)),
141        ];
142        let graph = build_test_graph(vids, edges);
143
144        let config = AllSimplePathsConfig {
145            source: Vid::from(0),
146            target: Vid::from(3),
147            max_depth: 5,
148            limit: 10,
149            ..Default::default()
150        };
151
152        let result = AllSimplePaths::run(&graph, config);
153        assert_eq!(result.paths.len(), 2);
154    }
155}
uni_algo/algo/algorithms/all_simple_paths.rs

uni_algo/algo/algorithms/
all_simple_paths.rs
