luka/algorithms/
bellman_ford.rs

1use std::marker::PhantomData;
2use crate::{Vertex, Graph};
3use crate::algorithms::definitions::Parents;
4use crate::error::{GraphError, ErrorKind};
5use std::ops::Add;
6
7pub struct Distance<'a, T> {
8    dist: Vec<Option<T>>,
9    phantom: PhantomData<&'a T>,
10}
11
12impl <'a, T> Distance<'a, T> where T: Copy {
13    pub fn get_distance(&self, target: &Vertex<T>) -> Option<T> {
14        self.dist[target.id()]
15    }
16}
17
18///
19/// The Bellman-Ford algorithm is an algorithm for finding the shortest path in a weighted graph.
20/// Unlike Dijkstra's algorithm, Bellman-Ford's algorithm allows edges with negative weight, but negative weight loops are still forbidden.
21/// Algorithmic complexity - O(|E| * |V|), where |E| is the number of edges in the graph and |V| is the number of vertexs in the graph.
22/// ```
23/// use luka::{Graph, algorithms, utils};
24///
25/// let mut graph = Graph::new(10);
26///
27/// graph.add_edge(1, 2, 2.0).unwrap();
28/// graph.add_edge(2, 3, 5.0).unwrap();
29/// graph.add_edge(3, 5, 7.0).unwrap();
30/// graph.add_edge(1, 5, 19.0).unwrap();
31///
32/// let start = graph.get_vertex(1).unwrap();
33/// let (parents, distances) = algorithms::bellman_ford(&graph, start).unwrap();
34///
35/// let target = graph.get_vertex(5).unwrap();
36/// let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
37/// assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3, 5]);
38/// assert_eq!(distances.get_distance(target).unwrap(), 14.0);
39/// ```
40
41pub fn bellman_ford<'a, T>(graph: &'a Graph<T>, from: &'a Vertex<T>) -> Result<(Parents<'a, T>, Distance<'a, T>), GraphError> where T: Default + Copy + PartialOrd + PartialEq + Add<Output = T> {
42    let mut parents = vec![None; graph.size()];
43    let mut distances = vec![None; graph.size()];
44    let from = from.id();
45    distances[from] = Some(Default::default());
46    for _ in 0..graph.size() {
47        let mut any = false;
48        for idx in 0..graph.size() {
49            if distances[idx].is_some() {
50                for edge in &graph.adj[idx].edges {
51                    if distances[edge.to].is_none() {
52                        parents[edge.to] = Some(&graph.adj[idx]);
53                        distances[edge.to] = Some(edge.weight + distances[idx].unwrap());
54                        any = true;
55                    } else if edge.weight + distances[idx].unwrap() < distances[edge.to].unwrap() {
56                        parents[edge.to] = Some(&graph.adj[idx]);
57                        distances[edge.to] = Some(edge.weight + distances[idx].unwrap());
58                        any = true
59                    }
60                }
61            }
62        }
63        if !any {
64            return Ok((parents, Distance{dist: distances, phantom: PhantomData}));
65        }
66    }
67    Err(GraphError::Regular(ErrorKind::ExistsCycleNegativeWeight))
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_bellman_ford(){
76        use crate::utils;
77
78        let mut graph = Graph::new(10);
79
80        graph.add_edge(1, 2, 2.0).unwrap();
81        graph.add_edge(2, 3, 5.0).unwrap();
82        graph.add_edge(3, 5, 7.0).unwrap();
83        graph.add_edge(1, 5, 19.0).unwrap();
84
85        let start = graph.get_vertex(1).unwrap();
86        let (parents, distances) = bellman_ford(&graph, start).unwrap();
87
88        let target = graph.get_vertex(5).unwrap();
89        let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
90        assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3, 5]);
91        assert_eq!(distances.get_distance(target).unwrap(), 14.0);
92
93        let target = graph.get_vertex(3).unwrap();
94        let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
95        assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3]);
96
97        let target = graph.get_vertex(7).unwrap();
98        assert_eq!(distances.get_distance(target), None);
99    }
100
101    #[test]
102    #[should_panic]
103    fn test_bellman_ford_exists_cycle(){
104        let mut graph = Graph::new(4);
105
106        graph.add_edge(1, 2, 2.0).unwrap();
107        graph.add_edge(2, 3, -2.0).unwrap();
108        graph.add_edge(3, 4, -2.0).unwrap();
109        graph.add_edge(4, 2, -2.0).unwrap();
110
111        let start = graph.get_vertex(1).unwrap();
112        bellman_ford(&graph, start).unwrap();
113    }
114}
luka/algorithms/bellman_ford.rs

luka/algorithms/
bellman_ford.rs
