algods 0.1.0

A collection of data structures and algorithms
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

#[cfg(test)]
mod tests {
    use super::super::{EdgeWeightedDigraph, ShortestPath, ShortestPathAlgo};

    #[test]
    fn test_dijkstra() {
        let mut graph = EdgeWeightedDigraph::init(9);
        graph.add_edge(0, 1, 1);
        graph.add_edge(0, 2, 1);
        graph.add_edge(0, 6, 2);
        graph.add_edge(0, 5, 3);
        graph.add_edge(0, 7, 5);
        graph.add_edge(4, 3, 1);
        graph.add_edge(4, 5, 4);
        graph.add_edge(5, 3, 2);
        graph.add_edge(6, 7, 2);
        graph.add_edge(6, 4, 1);

        let mut dijkstra =
            ShortestPath::<usize>::init(0, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        // println!("{:?}",graph.vertex_edges(&0));
        assert_eq!(dijkstra.path_to(0), Some(vec![0]));
        assert_eq!(dijkstra.path_to(1), Some(vec![1, 0]));
        assert_eq!(dijkstra.path_to(2), Some(vec![2, 0]));
        assert_eq!(dijkstra.path_to(3), Some(vec![3, 4, 6, 0]));
        assert_eq!(dijkstra.path_to(4), Some(vec![4, 6, 0]));
        assert_eq!(dijkstra.path_to(5), Some(vec![5, 0]));
        assert_eq!(dijkstra.path_to(6), Some(vec![6, 0]));
        assert_eq!(dijkstra.path_to(7), Some(vec![7, 6, 0]));
        assert_eq!(dijkstra.path_to(8), None);

        let mut dijkstra = ShortestPath::init(1, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        assert_eq!(dijkstra.path_to(0), None);
        assert_eq!(dijkstra.path_to(1), Some(vec![1]));
        assert_eq!(dijkstra.path_to(2), None);
        assert_eq!(dijkstra.path_to(3), None);
        assert_eq!(dijkstra.path_to(4), None);
        assert_eq!(dijkstra.path_to(5), None);
        assert_eq!(dijkstra.path_to(6), None);
        assert_eq!(dijkstra.path_to(7), None);
        assert_eq!(dijkstra.path_to(8), None);

        let mut dijkstra = ShortestPath::init(2, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        assert_eq!(dijkstra.path_to(0), None);
        assert_eq!(dijkstra.path_to(1), None);
        assert_eq!(dijkstra.path_to(2), Some(vec![2]));
        assert_eq!(dijkstra.path_to(3), None);
        assert_eq!(dijkstra.path_to(4), None);
        assert_eq!(dijkstra.path_to(5), None);
        assert_eq!(dijkstra.path_to(6), None);
        assert_eq!(dijkstra.path_to(7), None);
        assert_eq!(dijkstra.path_to(8), None);

        let mut dijkstra = ShortestPath::init(3, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        assert_eq!(dijkstra.path_to(0), None);
        assert_eq!(dijkstra.path_to(1), None);
        assert_eq!(dijkstra.path_to(2), None);
        assert_eq!(dijkstra.path_to(3), Some(vec![3]));
        assert_eq!(dijkstra.path_to(4), None);
        assert_eq!(dijkstra.path_to(5), None);
        assert_eq!(dijkstra.path_to(6), None);
        assert_eq!(dijkstra.path_to(7), None);
        assert_eq!(dijkstra.path_to(8), None);

        let mut dijkstra = ShortestPath::init(4, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        assert_eq!(dijkstra.path_to(0), None);
        assert_eq!(dijkstra.path_to(1), None);
        assert_eq!(dijkstra.path_to(2), None);
        assert_eq!(dijkstra.path_to(3), Some(vec![3, 4]));
        assert_eq!(dijkstra.path_to(4), Some(vec![4]));
        assert_eq!(dijkstra.path_to(5), Some(vec![5, 4]));
        assert_eq!(dijkstra.path_to(6), None);
        assert_eq!(dijkstra.path_to(7), None);
        assert_eq!(dijkstra.path_to(8), None);

        let mut dijkstra = ShortestPath::init(5, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        assert_eq!(dijkstra.path_to(0), None);
        assert_eq!(dijkstra.path_to(1), None);
        assert_eq!(dijkstra.path_to(2), None);
        assert_eq!(dijkstra.path_to(3), Some(vec![3, 5]));
        assert_eq!(dijkstra.path_to(4), None);
        assert_eq!(dijkstra.path_to(5), Some(vec![5]));
        assert_eq!(dijkstra.path_to(6), None);
        assert_eq!(dijkstra.path_to(7), None);
        assert_eq!(dijkstra.path_to(8), None);

        let mut dijkstra = ShortestPath::init(6, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        assert_eq!(dijkstra.path_to(0), None);
        assert_eq!(dijkstra.path_to(1), None);
        assert_eq!(dijkstra.path_to(2), None);
        assert_eq!(dijkstra.path_to(3), Some(vec![3, 4, 6]));
        assert_eq!(dijkstra.path_to(4), Some(vec![4, 6]));
        assert_eq!(dijkstra.path_to(5), Some(vec![5, 4, 6]));
        assert_eq!(dijkstra.path_to(6), Some(vec![6]));
        assert_eq!(dijkstra.path_to(7), Some(vec![7, 6]));
        assert_eq!(dijkstra.path_to(8), None);

        let mut dijkstra = ShortestPath::init(7, ShortestPathAlgo::Dijkstra, graph.nb_vertices());
        dijkstra.find_paths(&graph);
        assert_eq!(dijkstra.path_to(0), None);
        assert_eq!(dijkstra.path_to(1), None);
        assert_eq!(dijkstra.path_to(2), None);
        assert_eq!(dijkstra.path_to(3), None);
        assert_eq!(dijkstra.path_to(4), None);
        assert_eq!(dijkstra.path_to(5), None);
        assert_eq!(dijkstra.path_to(6), None);
        assert_eq!(dijkstra.path_to(7), Some(vec![7]));
        assert_eq!(dijkstra.path_to(8), None);
    }

    #[test]
    fn test_shortest_path_ewdag() {
        let mut graph = EdgeWeightedDigraph::init(8);
        graph.add_edge(0, 1, 5);
        graph.add_edge(0, 4, 9);
        graph.add_edge(0, 7, 8);
        graph.add_edge(1, 2, 12);
        graph.add_edge(1, 3, 15);
        graph.add_edge(1, 7, 4);
        graph.add_edge(2, 3, 3);
        graph.add_edge(2, 6, 11);
        graph.add_edge(3, 6, 9);
        graph.add_edge(4, 5, 4);
        graph.add_edge(4, 6, 20);
        graph.add_edge(4, 7, 5);
        graph.add_edge(5, 2, 1);
        graph.add_edge(5, 6, 13);
        graph.add_edge(7, 2, 7);
        graph.add_edge(7, 5, 6);

        let mut sp_dag = ShortestPath::init(0, ShortestPathAlgo::SpDag, graph.nb_vertices());
        sp_dag.find_paths(&graph);
        assert_eq!(sp_dag.path_to(0), Some(vec![0]));
        assert_eq!(sp_dag.path_to(1), Some(vec![1, 0]));
        assert_eq!(sp_dag.path_to(2), Some(vec![2, 5, 4, 0]));
        assert_eq!(sp_dag.path_to(3), Some(vec![3, 2, 5, 4, 0]));
        assert_eq!(sp_dag.path_to(4), Some(vec![4, 0]));
        assert_eq!(sp_dag.path_to(5), Some(vec![5, 4, 0]));
        assert_eq!(sp_dag.path_to(6), Some(vec![6, 2, 5, 4, 0]));
        assert_eq!(sp_dag.path_to(7), Some(vec![7, 0]));

        let mut sp_dag = ShortestPath::init(7, ShortestPathAlgo::SpDag, graph.nb_vertices());
        sp_dag.find_paths(&graph);
        assert_eq!(sp_dag.path_to(0), None);
        assert_eq!(sp_dag.path_to(1), None);
        assert_eq!(sp_dag.path_to(2), Some(vec![2, 7]));
        assert_eq!(sp_dag.path_to(3), Some(vec![3, 2, 7]));
        assert_eq!(sp_dag.path_to(4), None);
        assert_eq!(sp_dag.path_to(5), Some(vec![5, 7]));
        assert_eq!(sp_dag.path_to(6), Some(vec![6, 2, 7]));
        assert_eq!(sp_dag.path_to(7), Some(vec![7]));
    }
}