graphalgos/
lib.rs

1// use crate::algos;
2// use crate::graphs::Graph;
3
4pub mod algos;
5pub mod graphs;
6pub mod util;
7
8// use crate::graphs::Graph;
9
10/// Test cases
11#[cfg(test)]
12mod graph_tests {
13    use crate::{
14        algos::*,
15        graphs::{self, *},
16        gph,
17    };
18
19    fn get_test_graph_1(directed: bool) -> Graph {
20        // Generate a connected undirected graph.
21        let mut g: Graph = Graph::new(directed);
22        g.add_vertex(String::from("A"));
23        g.add_vertex(String::from("B"));
24        g.add_vertex(String::from("C"));
25        g.add_vertex(String::from("D"));
26        g.add_vertex(String::from("E"));
27        g.add_vertex(String::from("F"));
28        g.add_vertex(String::from("G"));
29        g.add_vertex(String::from("H"));
30        g.add_vertex(String::from("I"));
31
32        // Integers - i32
33        g.add_edge(
34            (String::from("A"), String::from('B')),
35            graphs::GNumber::I32(4),
36        );
37        g.add_edge(
38            (String::from("B"), String::from('C')),
39            graphs::GNumber::I32(8),
40        );
41        g.add_edge(
42            (String::from("C"), String::from('D')),
43            graphs::GNumber::I32(7),
44        );
45        g.add_edge(
46            (String::from("D"), String::from('E')),
47            graphs::GNumber::I32(10),
48        );
49        g.add_edge(
50            (String::from("E"), String::from('F')),
51            graphs::GNumber::I32(11),
52        );
53        g.add_edge(
54            (String::from("F"), String::from('G')),
55            graphs::GNumber::I32(2),
56        );
57        g.add_edge(
58            (String::from("G"), String::from('H')),
59            graphs::GNumber::I32(1),
60        );
61        g.add_edge(
62            (String::from("H"), String::from('I')),
63            graphs::GNumber::I32(7),
64        );
65        g.add_edge(
66            (String::from("H"), String::from('A')),
67            graphs::GNumber::I32(9),
68        );
69        g.add_edge(
70            (String::from("B"), String::from('H')),
71            graphs::GNumber::I32(12),
72        );
73        g.add_edge(
74            (String::from("C"), String::from('I')),
75            graphs::GNumber::I32(2),
76        );
77        g.add_edge(
78            (String::from("C"), String::from('F')),
79            graphs::GNumber::I32(4),
80        );
81        g.add_edge(
82            (String::from("D"), String::from('F')),
83            graphs::GNumber::I32(14),
84        );
85        g.add_edge(
86            (String::from("G"), String::from('I')),
87            graphs::GNumber::I32(6),
88        );
89        g
90    }
91
92    fn get_test_graph_2(directed: bool) -> Graph {
93        //Generates a graph with 2 connected components.
94        let mut g = get_test_graph_1(directed);
95        g.remove_vertex(String::from("I"));
96        g.remove_edge((String::from("B"), String::from('C')));
97        g.remove_edge((String::from("F"), String::from('G')));
98        g
99    }
100
101    fn get_mst_of_graph_1() -> Graph {
102        //Generate solution to test graph 1.
103        let mut g: Graph = Graph::new(false);
104        g.add_vertex(String::from("A"));
105        g.add_vertex(String::from("B"));
106        g.add_vertex(String::from("C"));
107        g.add_vertex(String::from("D"));
108        g.add_vertex(String::from("E"));
109        g.add_vertex(String::from("F"));
110        g.add_vertex(String::from("G"));
111        g.add_vertex(String::from("H"));
112        g.add_vertex(String::from("I"));
113        g.add_edge(
114            (String::from("A"), String::from('B')),
115            graphs::GNumber::I32(4),
116        );
117        g.add_edge(
118            (String::from("B"), String::from('C')),
119            graphs::GNumber::I32(8),
120        );
121        g.add_edge(
122            (String::from("C"), String::from('D')),
123            graphs::GNumber::I32(7),
124        );
125        g.add_edge(
126            (String::from("D"), String::from('E')),
127            graphs::GNumber::I32(10),
128        );
129        g.add_edge(
130            (String::from("F"), String::from('G')),
131            graphs::GNumber::I32(2),
132        );
133        g.add_edge(
134            (String::from("G"), String::from('H')),
135            graphs::GNumber::I32(1),
136        );
137        g.add_edge(
138            (String::from("C"), String::from('I')),
139            graphs::GNumber::I32(2),
140        );
141        g.add_edge(
142            (String::from("C"), String::from('F')),
143            graphs::GNumber::I32(4),
144        );
145        g
146    }
147
148    #[test]
149    fn add_one_vertex() {
150        let mut g: Graph = Graph::new(false);
151        g.add_vertex(String::from("A"));
152        assert_eq!(g.get_vertices().len(), 1);
153        assert_eq!(g.get_vertex(&String::from("A")).unwrap().label, "A");
154        assert_eq!(g.get_vertex(&String::from("A")).unwrap().get_value(), 0f64);
155    }
156
157    #[test]
158    fn add_multiple_vertices() {
159        let mut g = get_test_graph_1(false);
160        assert_eq!(g.get_vertices().len(), 9);
161        assert_eq!(g.get_vertex(&String::from("A")).unwrap().label, "A");
162        //assert_eq!(g.get_vertex(&String::from("A")).unwrap().get_value(), 0);
163        assert_eq!(g.get_vertex(&String::from("C")).unwrap().label, "C");
164        //assert_eq!(g.get_vertex(&String::from("C")).unwrap().get_value(), 2);
165        assert_eq!(g.get_vertex(&String::from("H")).unwrap().label, "H");
166        //assert_eq!(g.get_vertex(&String::from("H")).unwrap().get_value(), 7);
167        assert_eq!(g.get_vertex(&String::from("H")).unwrap().label, "H");
168        //assert_eq!(g.get_vertex(&String::from("H")).unwrap().get_value(), 7);
169        assert_eq!(g.get_vertex(&String::from("I")).unwrap().label, "I");
170        //assert_eq!(g.get_vertex(&String::from("I")).unwrap().get_value(), 8);
171    }
172
173    #[test]
174    fn remove_one_vertex() {
175        let mut g = get_test_graph_1(false);
176        g.remove_vertex(String::from("F"));
177        assert_eq!(g.get_vertices().len(), 8);
178        assert_eq!(g.get_vertices().get("F").is_none(), true);
179    }
180
181    #[test]
182    fn update_edge_test() {
183        let mut g = get_mst_of_graph_1();
184        g.update_edge(
185            (String::from("B"), String::from("C")),
186            graphs::GNumber::I32(-0),
187        );
188    }
189
190    #[test]
191    fn remove_multiple_vertices() {
192        let mut g = get_test_graph_1(false);
193        g.remove_vertex(String::from("I"));
194        g.remove_vertex(String::from("H"));
195        assert_eq!(g.get_vertices().len(), 7);
196        g.remove_vertex(String::from("E"));
197        assert_eq!(g.get_vertices().len(), 6);
198        g.remove_vertex(String::from("A"));
199        g.remove_vertex(String::from("B"));
200        assert_eq!(g.get_vertices().len(), 4);
201        g.remove_vertex(String::from("I"));
202        assert_eq!(g.get_vertices().len(), 4);
203        g.remove_vertex(String::from("G"));
204        g.remove_vertex(String::from("F"));
205        g.remove_vertex(String::from("D"));
206        g.remove_vertex(String::from("C"));
207        assert_eq!(g.get_vertices().len(), 0);
208    }
209
210    // #[test]
211    // fn add_one_undirected_edge() {
212    //     let mut g: Graph = Graph::new(false);
213    //     g.add_vertex(String::from("A"));
214    //     g.add_vertex(String::from("B"));
215    //     g.add_edge((String::from("A"), String::from('B')), GNumber::I32(4));
216    //     assert_eq!(g.get_edges().len(), 1);
217    // }
218    #[test]
219    fn make_from_macro() {
220       let mut G = gph!("A", "B");
221       assert_eq!(G.get_vertices().len(), 2);
222    }
223
224    #[test]
225    fn add_topologicalorder_test() {
226        let expected: Vec<String> = Vec::new();
227        let mut g = get_test_graph_1(false);
228        g.add_edge((String::from("A"), String::from('B')), GNumber::F64(4.));
229        g.add_edge((String::from("B"), String::from('C')), GNumber::F64(1.));
230        g.add_edge((String::from("A"), String::from('D')), GNumber::F64(1.));
231        g.add_edge((String::from("S"), String::from('C')), GNumber::F64(1.));
232        let answer = g.get_topological_order();
233        assert_eq!(expected, answer);
234    }
235
236    #[test]
237    fn add_vertex_test() {
238        let mut g: Graph = Graph::new(false);
239        g.add_vertex(String::from("越"));
240        let vertex = g.get_vertices();
241        println!("{:?}", vertex);
242    }
243
244    #[test]
245    fn set_value_test() {
246        let mut gh: Graph = Graph::new(true);
247        gh.add_vertex(String::from("F"));
248        gh.add_vertex(String::from("C"));
249        gh.add_edge(
250            (String::from("C"), String::from('F')),
251            graphs::GNumber::I32(4),
252        );
253
254        for (_lbl, vertex) in gh.get_vertices().iter_mut() {
255            let _xyz = (*vertex).set_value(1.2);
256            let xyz = (*vertex).get_value();
257            assert_eq!(xyz, 1.2);
258        }
259    }
260
261    #[test]
262    fn get_neighbours_test() {
263        let mut test: Graph = Graph::new(false);
264        test.add_vertex(String::from("F"));
265        test.add_vertex(String::from("C"));
266        test.add_edge(
267            (String::from("C"), String::from('F')),
268            graphs::GNumber::I32(4),
269        );
270        let no_vertex = test.get_in_neighbors(&String::from("A"));
271        let no_neighbour = test.get_out_neighbors(&String::from("A"));
272        let no_neighbour_variable = test.get_neighbors(&String::from("A"));
273        let expected: Vec<String> = Vec::new();
274        //expecting empty vec since graph don't have vertex "A"
275        assert_eq!(expected, no_vertex);
276        assert_eq!(expected, no_neighbour);
277        assert_eq!(expected, no_neighbour_variable);
278    }
279
280    #[test]
281    fn remove_multiple_edges() {
282        let mut g = get_mst_of_graph_1();
283        assert_eq!(g.get_edges().len(), 8);
284        //removes two edges from vertex A
285        g.remove_vertex(String::from("A"));
286        //trying to remove non-existant edge A-B
287        g.remove_edge((String::from("A"), String::from("B")));
288        assert_eq!(g.get_edges().len(), 7);
289        //removing edge in wrong order C-B insted of B-C
290        g.remove_edge((String::from("C"), String::from("B")));
291        assert_eq!(g.get_edges().len(), 7);
292        g.remove_edge((String::from("B"), String::from("C")));
293        g.remove_edge((String::from("D"), String::from("E")));
294        g.remove_edge((String::from("F"), String::from("G")));
295        g.remove_edge((String::from("G"), String::from("H")));
296        g.remove_edge((String::from("C"), String::from("I")));
297        g.remove_edge((String::from("C"), String::from("F")));
298        g.remove_edge((String::from("C"), String::from("D")));
299        assert_eq!(g.get_edges().len(), 0);
300    }
301
302    //Test boruvka's algorithm.
303    #[test]
304    fn test_boruvka_on_directed() {
305        let g = get_test_graph_1(true);
306        //TODO: Figure out how to check assertion error.
307        assert!(boruvka(g).is_err());
308    }
309
310    #[test]
311    fn test_boruvka_on_empty() {
312        let g: Graph = Graph::new(false);
313        //TODO: Come up with a better check.
314        assert_eq!(boruvka(g).unwrap().get_vertices().len(), 0);
315    }
316
317    #[test]
318    fn test_boruvka_on_trivial() {
319        let mut g: Graph = Graph::new(false);
320        g.add_vertex(String::from("Banana"));
321        //TODO: Come up with a better check.
322        assert_eq!(boruvka(g).unwrap().get_vertices().len(), 1);
323    }
324
325    #[test]
326    fn test_boruvka_disconnected() {
327        let g = get_test_graph_2(false);
328        assert!(boruvka(g).is_err());
329    }
330
331    #[test]
332    fn test_boruvka_on_non_trivial() {
333        let g = get_test_graph_1(false);
334        let mut mst = boruvka(g).unwrap();
335        let mut solution = get_mst_of_graph_1();
336        println!("{:?}", mst.get_edges().keys());
337        println!("{:?}", solution.get_edges().keys());
338        assert!(mst
339            .get_edges()
340            .keys()
341            .all(|y| solution.get_edges().contains_key(y)));
342    }
343
344    //Test Kruskal's algorithm.
345    #[test]
346    fn test_kruskals_on_directed() {
347        let g = get_test_graph_1(true);
348        //TODO: Figure out how to check assertion error.
349        assert!(kruskals(g).is_err());
350        //assert_eq!(reverse_delete(G).unwrap_err(), "Boruvka only work on undirected graphs!");
351    }
352
353    #[test]
354    fn test_kruskals_on_empty() {
355        let g: Graph = Graph::new(false);
356        //TODO: Come up with a better check.
357        assert_eq!(kruskals(g).unwrap().get_vertices().len(), 0);
358    }
359
360    #[test]
361    fn test_kruskals_on_trivial() {
362        let mut g: Graph = Graph::new(false);
363        g.add_vertex(String::from("Banana"));
364        //TODO: Come up with a better check.
365        assert_eq!(kruskals(g).unwrap().get_vertices().len(), 1);
366    }
367
368    #[test]
369    fn test_kruskals_disconnected() {
370        let g = get_test_graph_2(false);
371        assert!(kruskals(g).is_err());
372    }
373
374    #[test]
375    fn test_kruskals_on_non_trivial() {
376        let g = get_test_graph_1(false);
377        let mut mst = kruskals(g).unwrap();
378        let mut solution = get_mst_of_graph_1();
379        println!("{:?}", mst.get_edges().keys());
380        println!("{:?}", solution.get_edges().keys());
381        assert!(mst
382            .get_edges()
383            .keys()
384            .all(|y| solution.get_edges().contains_key(y)));
385    }
386    // Test Prim's algorithm on a directed graph
387    #[test]
388    fn test_prims_on_directed() {
389        let g = get_test_graph_1(true);
390        assert!(prims(g).is_err());
391    }
392    // Test Prim's algorithm on an empty graph
393    #[test]
394    fn test_prims_on_empty() {
395        let g: Graph = Graph::new(false);
396        assert_eq!(prims(g).unwrap().get_vertices().len(), 0);
397    }
398
399    // Test Prim's algorithm on a trivial graph
400    #[test]
401    fn test_prims_on_trivial() {
402        let mut g: Graph = Graph::new(false);
403        g.add_vertex(String::from("Apple"));
404        assert_eq!(prims(g).unwrap().get_vertices().len(), 1);
405    }
406
407    // Test Prim's algorithm on a disconnected graph
408    #[test]
409    fn test_prims_disconnected() {
410        let mut g = get_test_graph_2(false);
411        g.add_vertex(String::from("F"));
412        assert!(prims(g).is_err());
413    }
414
415    //Test Prim's algorithm on a non-trivial graph
416    #[test]
417    fn test_prims_on_non_trivial() {
418        let g = get_test_graph_1(false);
419        let mut mst = prims(g).unwrap();
420        let mut solution = get_mst_of_graph_1();
421        assert!(mst
422            .get_edges()
423            .keys()
424            .all(|y| solution.get_edges().contains_key(y)));
425    }
426}
graphalgos/lib.rs

graphalgos/
lib.rs
