luka 0.4.0

Library for working with graphs
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

use std::marker::PhantomData;
use crate::{Vertex, Graph};
use crate::algorithms::definitions::Parents;
use crate::error::{GraphError, ErrorKind};
use std::ops::Add;

pub struct Distance<'a, T> {
    dist: Vec<Option<T>>,
    phantom: PhantomData<&'a T>,
}

impl <'a, T> Distance<'a, T> where T: Copy {
    pub fn get_distance(&self, target: &Vertex<T>) -> Option<T> {
        self.dist[target.id()]
    }
}

///
/// The Bellman-Ford algorithm is an algorithm for finding the shortest path in a weighted graph.
/// Unlike Dijkstra's algorithm, Bellman-Ford's algorithm allows edges with negative weight, but negative weight loops are still forbidden.
/// 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.
/// ```
/// use luka::{Graph, algorithms, utils};
///
/// let mut graph = Graph::new(10);
///
/// graph.add_edge(1, 2, 2.0).unwrap();
/// graph.add_edge(2, 3, 5.0).unwrap();
/// graph.add_edge(3, 5, 7.0).unwrap();
/// graph.add_edge(1, 5, 19.0).unwrap();
///
/// let start = graph.get_vertex(1).unwrap();
/// let (parents, distances) = algorithms::bellman_ford(&graph, start).unwrap();
///
/// let target = graph.get_vertex(5).unwrap();
/// let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
/// assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3, 5]);
/// assert_eq!(distances.get_distance(target).unwrap(), 14.0);
/// ```

pub 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> {
    let mut parents = vec![None; graph.size()];
    let mut distances = vec![None; graph.size()];
    let from = from.id();
    distances[from] = Some(Default::default());
    for _ in 0..graph.size() {
        let mut any = false;
        for idx in 0..graph.size() {
            if distances[idx].is_some() {
                for edge in &graph.adj[idx].edges {
                    if distances[edge.to].is_none() {
                        parents[edge.to] = Some(&graph.adj[idx]);
                        distances[edge.to] = Some(edge.weight + distances[idx].unwrap());
                        any = true;
                    } else if edge.weight + distances[idx].unwrap() < distances[edge.to].unwrap() {
                        parents[edge.to] = Some(&graph.adj[idx]);
                        distances[edge.to] = Some(edge.weight + distances[idx].unwrap());
                        any = true
                    }
                }
            }
        }
        if !any {
            return Ok((parents, Distance{dist: distances, phantom: PhantomData}));
        }
    }
    Err(GraphError::Regular(ErrorKind::ExistsCycleNegativeWeight))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bellman_ford(){
        use crate::utils;

        let mut graph = Graph::new(10);

        graph.add_edge(1, 2, 2.0).unwrap();
        graph.add_edge(2, 3, 5.0).unwrap();
        graph.add_edge(3, 5, 7.0).unwrap();
        graph.add_edge(1, 5, 19.0).unwrap();

        let start = graph.get_vertex(1).unwrap();
        let (parents, distances) = bellman_ford(&graph, start).unwrap();

        let target = graph.get_vertex(5).unwrap();
        let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
        assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3, 5]);
        assert_eq!(distances.get_distance(target).unwrap(), 14.0);

        let target = graph.get_vertex(3).unwrap();
        let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
        assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3]);

        let target = graph.get_vertex(7).unwrap();
        assert_eq!(distances.get_distance(target), None);
    }

    #[test]
    #[should_panic]
    fn test_bellman_ford_exists_cycle(){
        let mut graph = Graph::new(4);

        graph.add_edge(1, 2, 2.0).unwrap();
        graph.add_edge(2, 3, -2.0).unwrap();
        graph.add_edge(3, 4, -2.0).unwrap();
        graph.add_edge(4, 2, -2.0).unwrap();

        let start = graph.get_vertex(1).unwrap();
        bellman_ford(&graph, start).unwrap();
    }
}