sssp_lib/
graph.rs

1use std::collections::{BinaryHeap, HashMap};
2use std::cmp::Ordering;
3
4/// Represents an edge in the graph.
5///
6/// An edge has a target node and a weight.
7#[derive(Debug, Clone, PartialEq)]
8pub struct Edge {
9    /// The target node index.
10    pub to: usize,
11    /// The weight of the edge.
12    pub weight: f64,
13}
14
15#[derive(Copy, Clone, PartialEq)]
16struct State {
17    node: usize,
18    dist: f64,
19}
20
21impl Eq for State {}
22impl Ord for State {
23    fn cmp(&self, other: &Self) -> Ordering {
24        // Min-heap: sort by increasing distance
25        other.dist.partial_cmp(&self.dist).unwrap_or(Ordering::Equal)
26    }
27}
28impl PartialOrd for State {
29    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
30        Some(self.cmp(other))
31    }
32}
33
34/// Represents a graph for SSSP algorithms.
35///
36/// The graph is stored as an adjacency list.
37pub struct SSSPGraph {
38    /// Adjacency list: adj\[u\] contains edges from node u.
39    pub adj: Vec<Vec<Edge>>,
40    /// Number of nodes in the graph.
41    pub n: usize,
42}
43
44impl SSSPGraph {
45    /// Creates a new empty graph with `n` nodes.
46    ///
47    /// # Arguments
48    ///
49    /// * `n` - The number of nodes.
50    ///
51    /// # Examples
52    ///
53    /// ```
54    /// use sssp_lib::graph::SSSPGraph;
55    ///
56    /// let graph = SSSPGraph::new(5);
57    /// ```
58    pub fn new(n: usize) -> Self {
59        Self {
60            adj: vec![vec![]; n],
61            n,
62        }
63    }
64
65    /// Adds a directed edge from node `u` to node `v` with weight `w`.
66    ///
67    /// If `u` or `v` is out of bounds, the edge is ignored.
68    ///
69    /// # Arguments
70    ///
71    /// * `u` - The source node index.
72    /// * `v` - The target node index.
73    /// * `w` - The edge weight.
74    ///
75    /// # Examples
76    ///
77    /// ```
78    /// use sssp_lib::graph::SSSPGraph;
79    ///
80    /// let mut graph = SSSPGraph::new(3);
81    /// graph.add_edge(0, 1, 1.0);
82    /// ```
83    pub fn add_edge(&mut self, u: usize, v: usize, w: f64) {
84        if u < self.n && v < self.n {
85            self.adj[u].push(Edge { to: v, weight: w });
86        }
87    }
88
89    /// Runs the Bounded Memory Shortest Path (BMSSP) algorithm.
90    ///
91    /// This is an internal method used by the SSSP algorithm with bounds on distance and work.
92    ///
93    /// # Arguments
94    ///
95    /// * `sources` - A vector of (node, initial_distance) pairs.
96    /// * `b_bound` - The maximum distance bound.
97    /// * `u_bound` - The maximum work bound (number of relaxations).
98    ///
99    /// # Returns
100    ///
101    /// A tuple of (distances, parents) HashMaps.
102    pub fn bmssp(
103        &self,
104        sources: Vec<(usize, f64)>,
105        b_bound: f64,
106        u_bound: usize,
107    ) -> (HashMap<usize, f64>, HashMap<usize, usize>) {
108    let mut dists = HashMap::new();
109    let mut parents = HashMap::new(); // Store who relaxed whom
110    let mut heap = BinaryHeap::new();
111    let mut work_done = 0;
112
113    for (node, d) in sources {
114        dists.insert(node, d);
115        heap.push(State { node, dist: d });
116    }
117
118    while let Some(State { node, dist }) = heap.pop() {
119        if dist > *dists.get(&node).unwrap_or(&f64::INFINITY) { continue; }
120        if work_done >= u_bound { break; }
121
122        for edge in &self.adj[node] {
123            let new_dist = dist + edge.weight;
124            if new_dist <= b_bound {
125                let current_dist = dists.get(&edge.to).cloned().unwrap_or(f64::INFINITY);
126                if new_dist < current_dist {
127                    dists.insert(edge.to, new_dist);
128                    parents.insert(edge.to, node); // <--- Store the parent
129                    heap.push(State { node: edge.to, dist: new_dist });
130                    work_done += 1;
131                }
132            }
133        }
134    }
135    (dists, parents)
136}}
sssp_lib/graph.rs

sssp_lib/
graph.rs
