graph_algorithms/
floyd_warshall.rs

1use crate::{GraphAlgorithm, GraphError};
2
3/// Floyd-Warshall Algorithm.
4/// Compute shortest paths between all pairs of vertices in a weighted graph.
5#[derive(Debug, Clone)]
6pub struct FloydWarshallAlgorithm {
7    /// Total number of nodes in the graph.
8    pub total_nodes: usize,
9
10    /// Edges in the graph.
11    pub edges: Vec<(usize, usize, i32)>,
12}
13
14impl Default for FloydWarshallAlgorithm {
15    /// Create a new default instance of Floyd-Warshall Algorithm.
16    ///
17    /// # Returns
18    ///
19    /// New default instance of Floyd-Warshall Algorithm.
20    fn default() -> Self {
21        Self::new()
22    }
23}
24
25impl FloydWarshallAlgorithm {
26    /// Create a new instance of Floyd-Warshall Algorithm.
27    ///
28    /// # Returns
29    ///
30    /// New instance of Floyd-Warshall Algorithm.
31    pub fn new() -> Self {
32        Self {
33            total_nodes: 0,
34            edges: Vec::new(),
35        }
36    }
37
38    /// Set a single edge to the graph.
39    ///
40    /// # Arguments
41    ///
42    /// - `source`: Source node.
43    /// - `target`: Target node.
44    /// - `weight`: Weight of the edge.
45    pub fn set_edge(&mut self, source: usize, target: usize, weight: i32) {
46        self.edges.push((source, target, weight));
47        self.total_nodes = self.total_nodes.max(source + 1).max(target + 1);
48    }
49
50    /// Set multiple nodes' edges to the graph.
51    ///
52    /// # Arguments
53    ///
54    /// - `nodes`: Vector of tuples where each tuple contains a node and its associated edges.
55    pub fn set_edges(&mut self, nodes: Vec<(usize, Vec<(usize, i32)>)>) {
56        for (source, edges) in nodes {
57            for (target, weight) in edges {
58                self.set_edge(source, target, weight);
59            }
60        }
61    }
62
63    /// Set the total number of nodes in the graph.
64    ///
65    /// # Arguments
66    ///
67    /// - `total`: Total number of nodes in the graph.
68    pub fn set_total_nodes(&mut self, total: usize) {
69        self.total_nodes = self.total_nodes.max(total);
70    }
71}
72
73impl GraphAlgorithm for FloydWarshallAlgorithm {
74    /// Type of node.
75    type Node = usize;
76
77    /// Type of weight.
78    type Weight = Vec<Vec<i32>>;
79
80    /// Run Floyd-Warshall algorithm.
81    ///
82    /// # Arguments
83    ///
84    /// - `start`: Starting node. This is not used in Floyd-Warshall algorithm.
85    ///
86    /// # Returns
87    ///
88    /// Result containing a vector of shortest paths, or an error if applicable.
89    fn run(&self, _start: Option<Self::Node>) -> Result<Self::Weight, GraphError> {
90        let mut distances = vec![vec![i32::MAX; self.total_nodes]; self.total_nodes];
91
92        for &(u, v, w) in &self.edges {
93            distances[u][v] = w;
94        }
95
96        for (v, row) in distances.iter_mut().enumerate().take(self.total_nodes) {
97            row[v] = 0;
98        }
99
100        for k in 0..self.total_nodes {
101            for i in 0..self.total_nodes {
102                for j in 0..self.total_nodes {
103                    if distances[i][k] != i32::MAX && distances[k][j] != i32::MAX {
104                        distances[i][j] = distances[i][j].min(distances[i][k] + distances[k][j]);
105                    }
106                }
107            }
108        }
109
110        Ok(distances)
111    }
112}
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117
118    #[test]
119    fn test_new() {
120        let algorithm = FloydWarshallAlgorithm::new();
121        let algorithm_default = FloydWarshallAlgorithm::default();
122
123        assert_eq!(algorithm.edges.len(), 0);
124        assert_eq!(algorithm_default.edges.len(), 0);
125    }
126
127    #[test]
128    fn test_run() {
129        let mut algorithm = FloydWarshallAlgorithm::new();
130
131        algorithm.set_edge(0, 1, 4);
132        algorithm.set_edge(1, 2, 1);
133        algorithm.set_edge(0, 2, 7);
134        algorithm.set_edge(2, 3, 3);
135        algorithm.set_edge(3, 4, 2);
136        algorithm.set_edge(4, 5, 1);
137        algorithm.set_edge(5, 6, 6);
138        algorithm.set_edge(0, 6, 15);
139        algorithm.set_edge(1, 4, 8);
140        algorithm.set_edge(2, 5, 12);
141        algorithm.set_edge(3, 6, 7);
142        algorithm.set_edge(4, 2, 5);
143        algorithm.set_edge(5, 0, 10);
144        algorithm.set_edge(6, 1, 11);
145
146        let result = algorithm.run(None).unwrap();
147
148        assert_eq!(result[0][0], 0);
149        assert_eq!(result[0][1], 4);
150        assert_eq!(result[0][2], 5);
151        assert_eq!(result[0][3], 8);
152        assert_eq!(result[0][4], 10);
153        assert_eq!(result[0][5], 11);
154        assert_eq!(result[0][6], 15);
155        assert_eq!(result[1][3], 4);
156        assert_eq!(result[1][4], 6);
157        assert_eq!(result[2][5], 6);
158        assert_eq!(result[3][5], 3);
159        assert_eq!(result[4][6], 7);
160    }
161
162    #[test]
163    fn test_run_single_node() {
164        let mut algorithm = FloydWarshallAlgorithm::new();
165        algorithm.set_edge(0, 0, 0);
166
167        let result = algorithm.run(None).unwrap();
168
169        assert_eq!(result[0][0], 0);
170    }
171
172    #[test]
173    fn test_run_two_nodes_one_edge() {
174        let mut algorithm = FloydWarshallAlgorithm::new();
175        algorithm.set_edge(0, 1, 5);
176
177        let result = algorithm.run(None).unwrap();
178
179        assert_eq!(result[0][1], 5);
180        assert_eq!(result[1][0], i32::MAX);
181    }
182
183    #[test]
184    fn test_run_negative_weights_without_cycle() {
185        let mut algorithm = FloydWarshallAlgorithm::new();
186        algorithm.set_edges(vec![
187            (0, vec![(1, -2), (2, 4)]),
188            (1, vec![(2, 1)]),
189            (0, vec![(2, 4)]),
190        ]);
191
192        let result = algorithm.run(None).unwrap();
193
194        assert_eq!(result[0][1], -2);
195        assert_eq!(result[0][2], -1);
196    }
197
198    #[test]
199    fn test_run_complete_graph() {
200        let mut algorithm = FloydWarshallAlgorithm::new();
201        algorithm.set_edge(0, 1, 1);
202        algorithm.set_edge(0, 2, 2);
203        algorithm.set_edge(1, 2, 1);
204        algorithm.set_edge(1, 0, 3);
205        algorithm.set_edge(2, 0, 4);
206        algorithm.set_edge(2, 1, 5);
207
208        let result = algorithm.run(None).unwrap();
209
210        assert_eq!(result[0][1], 1);
211        assert_eq!(result[0][2], 2);
212        assert_eq!(result[1][2], 1);
213    }
214
215    #[test]
216    fn test_run_disconnected_nodes() {
217        let mut algorithm = FloydWarshallAlgorithm::new();
218        algorithm.set_edge(0, 1, 3);
219        algorithm.set_edge(1, 2, 4);
220        algorithm.set_total_nodes(4);
221
222        let result = algorithm.run(None).unwrap();
223
224        assert_eq!(result[0][3], i32::MAX);
225        assert_eq!(result[3][3], 0);
226    }
227
228    #[test]
229    fn test_run_zero_weight_cycle() {
230        let mut algorithm = FloydWarshallAlgorithm::new();
231        algorithm.set_edge(0, 1, 2);
232        algorithm.set_edge(1, 2, -3);
233        algorithm.set_edge(2, 0, 1);
234
235        let result = algorithm.run(None).unwrap();
236
237        assert_eq!(result[0][1], 2);
238        assert_eq!(result[1][2], -3);
239        assert_eq!(result[2][0], 1);
240        assert_eq!(result[0][2], -1);
241    }
242}
graph_algorithms/floyd_warshall.rs

graph_algorithms/
floyd_warshall.rs
