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
115
116

use crate::error::GraphError;
use crate::{Vertex, Graph};
use std::collections::BinaryHeap;
use std::cmp::Ordering;
use std::ops::Add;
use crate::algorithms::definitions::Parents;
use std::marker::PhantomData;

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()]
    }
}

struct Pair<T> where T: PartialOrd + PartialEq + Copy + Default {
    node: usize,
    dist: T,
}
impl <T> PartialEq for Pair<T> where T: PartialOrd + PartialEq + Copy + Default {
    fn eq(&self, other: &Pair<T>) -> bool {
        self.dist == other.dist
    }
}

impl <T> Eq for Pair<T> where T: PartialOrd + PartialEq + Copy + Default {}

impl<T> Ord for Pair<T> where T: PartialOrd + PartialEq + Copy + Default {
    fn cmp(&self, other: &Self) -> Ordering {
        other.dist.partial_cmp(&self.dist).unwrap()
    }
}

impl<T> PartialOrd for Pair<T> where T: PartialOrd + PartialEq + Copy + Default {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(other.dist.partial_cmp(&self.dist).unwrap())
    }
}

/// Deikstra's Algorithm is an algorithm on graphs. It finds shortest paths from one of the vertices of a graph to all other vertices.
/// The algorithm works only for graphs without edges of negative weight.
/// Algorithmic complexity - O(|E| log |V|), where |V| is the number of vertexs in the graph and |E| is the number of edges 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::dijkstra(&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(graph.get_vertex(5).unwrap()).unwrap(), 14.0);
/// assert_eq!(distances.get_distance(graph.get_vertex(7).unwrap()), None);
/// ```

pub fn dijkstra<'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 visited = vec![false; graph.size()];
    let mut distances = vec![None; graph.size()];
    let from = from.id();
    let mut heap = BinaryHeap::<Pair<T>>::new();
    distances[from] = Some(Default::default());
    heap.push(Pair { node: from, dist: T::default()});
    while !heap.is_empty() {
        let pair = heap.pop().unwrap();
        visited[pair.node] = true;
        for edge in &graph.adj[pair.node].edges {
            if !visited[edge.to] && (distances[edge.to].is_none() || edge.weight + pair.dist < distances[edge.to].unwrap()) {
                parents[edge.to] = Some(&graph.adj[pair.node]);
                distances[edge.to] = Some(edge.weight + pair.dist);
                heap.push(Pair {node: edge.to, dist: distances[edge.to].unwrap()});
            }
        }
    }
    Ok((parents, Distance{dist: distances, phantom: PhantomData }))
}

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

    #[test]
    fn test_dijkstra(){
        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) = dijkstra(&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]);
        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]);

        assert_eq!(distances.get_distance(graph.get_vertex(5).unwrap()).unwrap(), 14.0);
        assert_eq!(distances.get_distance(graph.get_vertex(7).unwrap()), None);
    }
}