sssp_lib/
lib.rs

1pub mod graph;
2use crate::graph::SSSPGraph;
3use std::collections::HashMap;
4
5/// A library for Single Source Shortest Path (SSSP) algorithms in graphs.
6///
7/// This crate provides an implementation of SSSP using a bounded-memory shortest path algorithm.
8/// It is designed for efficiency on large graphs with constraints on memory and computation.
9pub struct SSSPAlgorithm {
10    /// The underlying graph structure.
11    pub graph: SSSPGraph,
12}
13
14impl SSSPAlgorithm {
15    /// Creates a new SSSPAlgorithm instance with an empty graph of `n` nodes.
16    ///
17    /// # Arguments
18    ///
19    /// * `n` - The number of nodes in the graph.
20    ///
21    /// # Examples
22    ///
23    /// ```
24    /// use sssp_lib::SSSPAlgorithm;
25    ///
26    /// let algo = SSSPAlgorithm::new(10);
27    /// ```
28    pub fn new(n: usize) -> Self {
29        Self {
30            graph: SSSPGraph::new(n),
31        }
32    }
33
34    /// Runs the SSSP algorithm from the given source node.
35    ///
36    /// Returns a HashMap where keys are node indices and values are the shortest distances from the source.
37    /// If the source is invalid (out of bounds), returns an empty HashMap.
38    ///
39    /// # Arguments
40    ///
41    /// * `source` - The index of the source node.
42    ///
43    /// # Examples
44    ///
45    /// ```
46    /// use sssp_lib::SSSPAlgorithm;
47    ///
48    /// let mut algo = SSSPAlgorithm::new(3);
49    /// algo.graph.add_edge(0, 1, 1.0);
50    /// algo.graph.add_edge(1, 2, 2.0);
51    ///
52    /// let dists = algo.run(0);
53    /// assert_eq!(dists.get(&2), Some(&3.0));
54    /// ```
55    pub fn run(&self, source: usize) -> HashMap<usize, f64> {
56        if source >= self.graph.n {
57            return HashMap::new();
58        }
59
60        // To avoid errors in small graphs, we adjust the work limit.
61        // For large graphs (n > 100), we apply the constraint from the paper n^(2/3).
62        // For small graphs, we allow it to complete (n * n).
63        let n_f = self.graph.n as f64;
64        let u_bound = if self.graph.n < 50 {
65            self.graph.n * self.graph.n
66        } else {
67            n_f.powf(0.66).round() as usize
68        };
69        
70        let b_bound = f64::INFINITY;
71
72        let (dists, _) = self.graph.bmssp(vec![(source, 0.0)], b_bound, u_bound);
73        
74        dists
75    }
76    /// Generates a large random graph for performance testing.
77    ///
78    /// Creates a graph with `n` nodes, where each node has approximately `edges_per_node` outgoing edges.
79    /// Edge weights are random floats between 0.0 and 10.0.
80    ///
81    /// # Arguments
82    ///
83    /// * `n` - The number of nodes.
84    /// * `edges_per_node` - The average number of outgoing edges per node.
85    ///
86    /// # Examples
87    ///
88    /// ```
89    /// use sssp_lib::SSSPAlgorithm;
90    ///
91    /// let algo = SSSPAlgorithm::generate_large_random(100, 5);
92    /// ```
93    pub fn generate_large_random(n: usize, edges_per_node: usize) -> Self {
94        use std::time::{SystemTime, UNIX_EPOCH};
95        
96        let mut algo = Self::new(n);
97        let mut seed = SystemTime::now()
98            .duration_since(UNIX_EPOCH)
99            .unwrap()
100            .as_nanos() as u64;
101
102        // Simple LCG generator to avoid adding dependencies like 'rand'
103        let mut next_rand = || {
104            seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
105            seed
106        };
107
108        for u in 0..n {
109            for _ in 0..edges_per_node {
110                let v = (next_rand() as usize) % n;
111                let weight = ((next_rand() % 100) as f64) / 10.0; // Pesos entre 0.0 y 10.0
112                if u != v {
113                    algo.graph.add_edge(u, v, weight);
114                }
115            }
116        }
117        algo
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use std::time::Instant;
124
125    use super::*;
126
127    #[test]
128    fn test_shortest_path_logic() {
129        let mut algo = SSSPAlgorithm::new(5);
130        // Grafo del fallo anterior:
131        algo.graph.add_edge(0, 1, 10.0);
132        algo.graph.add_edge(0, 3, 5.0);
133        algo.graph.add_edge(3, 1, 2.0);
134        algo.graph.add_edge(1, 2, 1.0);
135        algo.graph.add_edge(3, 2, 10.0);
136
137        let dists = algo.run(0);
138
139        // Camino: 0 -> 3 (5) -> 1 (2) -> 2 (1) = Total 8.0
140        let result = *dists.get(&2).expect("Should find node 2");
141        assert_eq!(result, 8.0, "The shortest path should be 8.0");
142    }
143
144    #[test]
145    fn test_diamond_graph() {
146        let mut algo = SSSPAlgorithm::new(4);
147        algo.graph.add_edge(0, 1, 1.0);
148        algo.graph.add_edge(0, 2, 1.0);
149        algo.graph.add_edge(1, 3, 1.0);
150        algo.graph.add_edge(2, 3, 5.0);
151
152        let dists = algo.run(0);
153        assert_eq!(*dists.get(&3).unwrap(), 2.0);
154    }
155    #[test]
156    fn test_large_graph_performance() {
157        let n = 100_000;
158        let edges_per_node = 5;
159        
160        println!("Generating graph with {} nodes...", n);
161        let algo = SSSPAlgorithm::generate_large_random(n, edges_per_node);
162        
163        println!("Running SSSP Algorithm...");
164        let start = Instant::now();
165        let results = algo.run(0);
166        let duration = start.elapsed();
167        
168        println!("Completed in: {:?}", duration);
169        println!("Nodes reached: {}", results.len());
170        
171        // Verificación básica
172        assert!(results.len() > 0);
173    }
174}
sssp_lib/lib.rs

sssp_lib/
lib.rs
