graphalgos/algos.rs
1use crate::graphs::*;
2use crate::util::DisjointSet;
3
4use std::cmp::Reverse;
5use std::collections::BinaryHeap;
6use std::collections::HashMap;
7use std::collections::HashSet;
8use std::collections::VecDeque;
9use std::fmt::Debug;
10
11use std::sync::{Arc, Mutex};
12use std::thread;
13
14type VLT = String; // vertex label type
15
16const INF: f64 = f64::INFINITY;
17
18//type TMPV = f64; // Should be V, but I'm being specific so I can debug.
19/// Dijkstra Algorithm - Find the single source shortest path given a graph and a starting vertex
20///
21/// # Parameters:
22///
23/// 1. g - the graph that needs to be traversed. This will be of type `Graph`
24/// 2. start_vertex - the source vertex from which you want to find the shortest distance of all other vertex
25///
26/// # Return Value:
27///
28/// Void
29///
30///
31/// # Example Usage:
32///
33/// ```
34///
35/// use graphalgos::algos;
36/// use graphalgos::graphs;
37///
38/// let mut g: graphs::Graph = graphs::Graph::new(false); // creates an undirected graph
39///
40/// // Add vertices
41///
42/// g.add_vertex(String::from("A")); // add vertex A
43/// g.add_vertex(String::from("B")); // add vertex B
44/// ...
45/// ...
46/// g.add_vertex(String::from("I")); // add vertex I
47///
48/// // Add edges
49///
50/// // Add multiple edges
51/// g.add_edge(
52/// (String::from("A"), String::from('B')),
53/// graphs::GNumber::I32(4),
54/// );
55/// ...
56/// ...
57/// algos::dijkstra(g);
58///
59/// ```
60///
61fn _dijkstra<E>(mut g: Graph, start_vertex: VLT) {
62 //FIXME: Finish implementation.
63 println!("Beginning Dikstra's algorithm.");
64
65 // let prev: HashMap<Vertex<TMPV>, Option<Vertex<TMPV>>> = HashMap::new();
66 let mut prev: HashMap<VLT, Option<VLT>> = HashMap::new();
67
68 for (lbl, vertex) in g.get_vertices().iter_mut() {
69 //Initialize all vertex values to Inf.
70 //We will interpret this value as the distance to the vertex.
71 (*vertex).set_value(INF);
72
73 //Initialize previous to none.
74 prev.insert(lbl.clone(), None);
75 }
76
77 //Initialize distance to start as 0.
78 g.get_vertex(&start_vertex).unwrap().set_value(0.0);
79
80 //Can maybe convert to binary heap so we have ordering.
81 //let heap: BinaryHeap<_> = g.get_vertices().values().collect();
82}
83
84fn dfs(g: &mut Graph, start_vertex: VLT) -> HashMap<VLT, bool> {
85 //Stack will hold all vertices. Algorithm will end when all vertices have been popped.
86 let stack: Arc<Mutex<VecDeque<Vertex>>> = Arc::new(Mutex::new(VecDeque::new()));
87 //Hashmap letting us know which vertices have been visited by dfs.
88 let visited: Arc<Mutex<HashMap<VLT, bool>>> = Arc::new(Mutex::new(HashMap::new()));
89 //Initialize visited.
90 for (lbl, _) in g.get_vertices().iter() {
91 (*visited).lock().unwrap().insert((*lbl).clone(), false);
92 }
93 //Populate stack.
94 (*stack)
95 .lock()
96 .unwrap()
97 .push_front(g.get_vertex(&start_vertex).unwrap().clone());
98
99 //Because of interactions between lifetimes and Arc's, we have to clone the graph.
100 //It could greatly speed up our algorithm if we found a way to avoid this.
101 let h = Arc::new(Mutex::new(g.clone()));
102
103 let mut handles: Vec<thread::JoinHandle<_>> = vec![]; //Vector of thread handles.
104 let max_num_threads = 10; //Maximum number of theads allowed at a time.
105 let num_threads = Arc::new(Mutex::new(0)); //Counter to keep track of number of threads.
106 while !(*(*stack).lock().unwrap()).is_empty() {
107 //While stack is not empty
108 let stack_clone = Arc::clone(&stack);
109 let visited_clone = Arc::clone(&visited);
110 let g_clone = Arc::clone(&h);
111
112 let num_threads = Arc::clone(&num_threads);
113 if *num_threads.lock().unwrap() < max_num_threads {
114 //Limit the number of threads.
115 {
116 *num_threads.lock().unwrap() += 1;
117 }
118 let handler = thread::spawn(move || {
119 let mut sc = stack_clone.lock().unwrap();
120 if let Some(v) = sc.pop_front() {
121 //Pop vertex off of stack.
122 let mut vis = visited_clone.lock().unwrap();
123 if !vis.get(&v.label).unwrap() {
124 //If vertex has not already been visited:
125 vis.insert(v.label.clone(), true); //Label vertex as visited.
126 let mut int_g = g_clone.lock().unwrap();
127 for neighbor in int_g.get_neighbors(&v.label).iter() {
128 //Push all unvisited neighbors onto the stack.
129 if !vis.get(neighbor).unwrap() {
130 sc.push_front((int_g.get_vertex(neighbor).unwrap()).clone());
131 }
132 }
133 }
134 } else {
135 //This means the algorithm has finished, and we can begin wrapping up threads.
136 }
137 *num_threads.lock().unwrap() -= 1;
138 });
139 handles.push(handler);
140 }
141 }
142
143 //Make sure all threads have finished.
144 for handle in handles {
145 let _ = handle.join();
146 }
147
148 //Return the visited hashmap.
149 let x = (*visited.lock().unwrap()).clone();
150 x
151}
152
153// pub fn bellman_ford<E>(mut _g: Graph, _start_vertex: VLT)
154// where
155// E: Clone,
156// {
157// println!("Beginning the Bellman-Ford algorithm.");
158// }
159
160/// Kruskals Algorithm - Generate MST for any graph using the Kruskal's Algorithm
161///
162/// # Parameters:
163///
164/// 1. g - the graph that needs to be converted to MST. This will be of type `Graph`
165///
166/// # Return Value:
167///
168/// This function returns a result, which will be either a Graph - the MST that was generated using the algo or a `Error<String>` in case of any error.
169///
170/// The common errors would be - if graph is directed or if MST cannot be generated for the given graph
171///
172///
173/// # Example Usage:
174///
175/// ```
176///
177/// use graphalgos::algos;
178/// use graphalgos::graphs;
179///
180/// let mut g: graphs::Graph = graphs::Graph::new(false); // creates an undirected graph
181///
182/// // Add vertices
183///
184/// g.add_vertex(String::from("A")); // add vertex A
185/// g.add_vertex(String::from("B")); // add vertex B
186/// ...
187/// ...
188/// g.add_vertex(String::from("I")); // add vertex I
189///
190/// // Add edges
191///
192/// // Add multiple edges
193/// g.add_edge(
194/// (String::from("A"), String::from('B')),
195/// graphs::GNumber::I32(4),
196/// );
197/// ...
198/// ...
199/// let mst = algos::kruskals(g); // get the mst using kruskals algorithm
200///
201/// // kruskals returns results, so use match statement to process it
202/// match mst{
203/// Ok(g) => g.print(), // print the MST if generated successfully
204/// Err(e) => println!("{}", e), // print the error if any
205/// }
206///
207/// ```
208///
209pub fn kruskals(mut g: Graph) -> Result<Graph, String> {
210 // check if graph has directed edges - Kruskals work on undirected graph and not directed
211 let is_directed = match g.edge_type {
212 EdgeType::Directed => true,
213 EdgeType::Undirected => false,
214 };
215
216 // return error if the graph has directed edges
217 if is_directed {
218 return Err(String::from(
219 "Kruskals only work properly on undirected graphs!",
220 ));
221 }
222
223 // Check for empty or trivial graph
224 if g.get_vertices().len() <= 1 {
225 return Ok(g);
226 }
227
228 // println!("{}", g.edges.len());
229
230 // vector to collect all edge values
231 let mut edges: Vec<Edge> = Vec::new();
232
233 // fill the vector with edges in graph
234 for (_, edge) in &g.edges {
235 edges.push(edge.clone());
236 }
237
238 edges.sort_by(|a, b| a.weight.partial_cmp(&b.weight).unwrap());
239
240 // The graph that we are going to return
241 let mut mst = Graph::new(false);
242
243 // Use Disjoint set for union find algorithm
244 let mut set = DisjointSet::new();
245
246 // Add all the vertices to the disjoint set
247 for (node, _) in &g.vertices {
248 set.set_insert(node.clone());
249 }
250
251 // iterate over edges - smallest weight to largest weight
252 for edge in edges {
253 let u = edge.endpoints.0.clone(); // get the first vertex of the edge
254 let v = edge.endpoints.1.clone(); // get the second vertex of the edge
255 set.find(&u); // Find parent of u
256
257 // check if they are in different sets
258 if set.find(&u) != set.find(&v) {
259 // If they are in different sets then we join them using union and also use the edge in MST
260 mst.add_vertex(u.clone()); // add vertex u to mst
261 mst.add_vertex(v.clone()); // add vertex v to mst
262 mst.add_edge((u.clone(), v.clone()), edge.weight.clone());
263 set.union(&u, &v);
264 }
265 }
266
267 // check if MST is successfull
268 if mst.edges.len() != mst.vertices.len() - 1 {
269 return Err(String::from(
270 "MST doesn't exist for this graph since it is not connected",
271 ));
272 }
273
274 println!("\nMST generated using Kruskal's algorithm: \n");
275
276 for (_, edge) in &mst.edges {
277 println!(
278 "({}) -------[{}]------- ({})",
279 edge.endpoints.0.clone(),
280 edge.weight,
281 edge.endpoints.1.clone()
282 );
283 }
284
285 println!("");
286
287 Ok(mst)
288}
289
290/// Boruvka's Algorithm - Generate MST for any graph using the Boruvka's Algorithm
291///
292/// # Parameters:
293///
294/// 1. g - the graph that needs to be converted to MST. This will be of type `Graph`
295///
296/// # Return Value:
297///
298/// This function returns a result, which will be either a Graph - the MST that was generated using the algo or a `Error<String>` in case of any error.
299///
300/// The common errors would be - if graph is directed or if MST cannot be generated for the given graph
301///
302///
303/// # Example Usage:
304///
305/// ```
306/// use graphalgos::algos;
307/// use graphalgos::graphs;
308
309/// let mut g: graphs::Graph = graphs::Graph::new(false); /// creates an undirected graph
310
311/// // Add vertices
312
313/// g.add_vertex(String::from("A")); // add vertex A
314/// g.add_vertex(String::from("B")); // add vertex B
315
316/// g.add_vertex(String::from("I")); // add vertex I
317
318/// // Add edges
319
320/// // Add multiple edges
321/// g.add_edge(
322/// (String::from("A"), String::from('B')),
323/// graphs::GNumber::I32(4),
324/// );
325
326/// let mst = algos::boruvka(g); // get the mst using boruvkas algorithm
327
328/// // boruvkas returns results, so use match statement to process it
329/// match mst {
330/// Ok(g) => g.print(), // print the MST if generated successfully
331/// Err(e) => println!("{}", e), // print the error if any
332/// }
333/// ```
334///
335pub fn boruvka(mut g: Graph) -> Result<Graph, String> {
336 // check if graph has directed edges - boruvkas work on undirected graph and not directed
337 let is_directed = match g.edge_type {
338 EdgeType::Directed => true,
339 EdgeType::Undirected => false,
340 };
341
342 // return error if the graph has directed edges
343
344 if is_directed {
345 return Err(String::from(
346 "Boruvka's only work properly on undirected graphs!",
347 ));
348 }
349
350 // Check for empty or trivial graph
351 if g.get_vertices().len() <= 1 {
352 return Ok(g);
353 }
354
355 println!("{}", g.edges.len());
356
357 // vector to collect all edge values
358 let mut edges: Vec<Edge> = Vec::new();
359
360 //
361 let mut added_edges: Vec<Edge> = Vec::new();
362
363 // fill the vector with edges in graph
364 for (_, edge) in &g.edges {
365 edges.push(edge.clone());
366 }
367
368 edges.sort_by(|a, b| a.weight.partial_cmp(&b.weight).unwrap());
369
370 // set to keep track of visited nodes
371 let mut visited = HashSet::new();
372
373 // Use Disjoint set for union find algorithm
374 let mut set = DisjointSet::new();
375
376 // Add all the vertices to the disjoint set
377 for (node, _) in &g.vertices {
378 set.set_insert(node.clone());
379 }
380
381 //Minimum spanning graph initialization
382 let mut mst = Graph::new(true);
383
384 // Add the first vertex to the visited set
385 let first_vertex = g.vertices.keys().next().unwrap().clone();
386 visited.insert(first_vertex.clone());
387
388 let edges1 = edges.clone();
389 for (vertex, _) in &g.vertices {
390 //
391 for (endpoint, edge) in &g.edges {
392 if endpoint.0 == vertex.clone() {
393 added_edges.push(edge.clone());
394 }
395 }
396 for edge in &edges1 {
397 let u = edge.endpoints.0.clone(); // get the first vertex of the edge
398 let v = edge.endpoints.1.clone();
399
400 // Skip this edge if both endpoints are already visited
401 if visited.contains(&u) && visited.contains(&v) {
402 continue;
403 }
404
405 // get the second vertex of the edge
406 set.find(&u); // Find parent of u
407 // check if they are in different sets
408 if set.find(&u) != set.find(&v) {
409 // If they are in different sets then we join them using union and also use the edge in MST
410 mst.add_vertex(u.clone()); // add vertex u to mst
411 mst.add_vertex(v.clone()); // add vertex v to mst
412 mst.add_edge((u.clone(), v.clone()), edge.weight.clone());
413 added_edges.push(edge.clone());
414 set.union(&u, &v);
415 }
416 }
417 }
418
419 let mut remaining_edges: Vec<Edge> = Vec::new();
420 for iter in added_edges {
421 if edges.contains(&iter) {
422 continue;
423 } else {
424 remaining_edges.push(iter);
425 }
426 }
427
428 remaining_edges.sort_by(|a, b| a.weight.partial_cmp(&b.weight).unwrap());
429
430 for in_between in remaining_edges {
431 let u = in_between.endpoints.0.clone(); // get the first vertex of the edge
432 let v = in_between.endpoints.1.clone();
433 if set.find(&u) != set.find(&v) {
434 // If they are in different sets then we join them using union and also use the edge in MST
435 mst.add_vertex(u.clone()); // add vertex u to mst
436 mst.add_vertex(v.clone()); // add vertex v to mst
437 mst.add_edge((u.clone(), v.clone()), in_between.weight.clone());
438 set.union(&u, &v);
439 }
440 }
441
442 // check if MST is successfull
443 if mst.edges.len() != mst.vertices.len() - 1 {
444 return Err(String::from(
445 "MST doesn't exist for this graph since it is not connected",
446 ));
447 }
448
449 println!("\nMST generated using Boruvka's algorithm: \n");
450
451 for (_, edge) in &mst.edges {
452 println!(
453 "({}) -------[{}]------- ({})",
454 edge.endpoints.0.clone(),
455 edge.weight,
456 edge.endpoints.1.clone()
457 );
458 }
459
460 println!("");
461
462 Ok(mst)
463}
464
465/// Reverse Delete Algorithm - Generate MST for any graph using the Reverse Delete Algorithm
466///
467/// # Parameters:
468///
469/// 1. g - the graph that needs to be converted to MST. This will be of type `Graph`
470///
471/// # Return Value:
472///
473/// This function returns a result, which will be either a Graph - the MST that was generated using the algo or a `Error<String>` in case of any error.
474///
475/// The common errors would be - if graph is directed or if MST cannot be generated for the given graph
476///
477/// # Example Usage:
478///
479/// ```
480/// use graphalgos::algos;
481/// use graphalgos::graphs;
482
483/// let mut g: graphs::Graph = graphs::Graph::new(false); /// creates an undirected graph
484
485/// // Add vertices
486
487/// g.add_vertex(String::from("A")); // add vertex A
488/// g.add_vertex(String::from("B")); // add vertex B
489
490/// g.add_vertex(String::from("I")); // add vertex I
491
492/// // Add edges
493
494/// // Add multiple edges
495/// g.add_edge(
496/// (String::from("A"), String::from('B')),
497/// graphs::GNumber::I32(4),
498/// );
499
500/// let mst = algos::reverse_delete(g); // get the mst using reverse delete algorithm
501
502/// // reverse delete returns results, so use match statement to process it
503/// match mst {
504/// Ok(g) => g.print(), // print the MST if generated successfully
505/// Err(e) => println!("{}", e), // print the error if any
506/// }
507/// ```
508///
509pub fn reverse_delete(mut g: Graph) -> Result<Graph, String> {
510 // Reverse delete only works for undirected graphs.
511 let _is_directed = match g.edge_type {
512 EdgeType::Directed => {
513 return Err(String::from(
514 "Reverse delete only work on undirected graphs!",
515 ))
516 }
517 EdgeType::Undirected => {}
518 };
519
520 // Check for empty or trivial graph
521 if g.get_vertices().len() <= 1 {
522 return Ok(g);
523 }
524
525 // Check for connected graph
526 //TODO: Consider removing this check for speed and instead check that resulting MST is connected.
527 let start_vertex_lbl = g.get_vertices().keys().next().unwrap().clone(); //Get an arbitrary start vertex.
528 if !dfs(&mut g, start_vertex_lbl).values().all(|&x| x) {
529 return Err(String::from("Graph is not connected."));
530 }
531
532 // vector to collect all edge values
533 let mut edges: Vec<Edge> = Vec::new();
534
535 // fill the vector with edges in graph
536 for (_, edge) in g.get_edges().iter() {
537 edges.push(edge.clone());
538 }
539
540 edges.sort_by(|a, b| a.weight.partial_cmp(&b.weight).unwrap());
541 edges.reverse(); //Instead of reversing here, could use a reverse iterator. Not sure which is faster.
542
543 // iterate over edges - largest to smallest weight
544 for edge in edges.iter() {
545 let w = g.get_edges().get(&edge.endpoints).unwrap().weight.clone(); //TODO: This isn't pretty. Better is to have remove_edge return the edge that was removed.
546 g.remove_edge(edge.endpoints.clone());
547 let start_vertex_lbl = g.get_vertices().keys().next().unwrap().clone();
548 if !dfs(&mut g, start_vertex_lbl).values().all(|&x| x) {
549 g.add_edge(edge.endpoints.clone(), w);
550 }
551 }
552
553 println!("\nMST: \n");
554 for (_, edge) in &g.edges {
555 println!(
556 "({}) -------[{}]------- ({})",
557 edge.endpoints.0.clone(),
558 edge.weight,
559 edge.endpoints.1.clone()
560 );
561 }
562
563 Ok(g)
564}
565
566/// Prim's Algorithm - Generate MST for any graph using the Prim's Algorithm
567///
568/// # Parameters:
569///
570/// 1. g - the graph that needs to be converted to MST. This will be of type `Graph`
571///
572/// # Return Value:
573///
574/// This function returns a result, which will be either a Graph - the MST that was generated using the algo or a `Error<String>` in case of any error.
575///
576/// The common errors would be - if graph is directed or if MST cannot be generated for the given graph
577///
578/// # Example Usage:
579///
580/// ```
581/// use graphalgos::algos;
582/// use graphalgos::graphs;
583
584/// let mut g: graphs::Graph = graphs::Graph::new(false); /// creates an undirected graph
585
586/// // Add vertices
587
588/// g.add_vertex(String::from("A")); // add vertex A
589/// g.add_vertex(String::from("B")); // add vertex B
590
591/// g.add_vertex(String::from("I")); // add vertex I
592
593/// // Add edges
594
595/// // Add multiple edges
596/// g.add_edge(
597/// (String::from("A"), String::from('B')),
598/// graphs::GNumber::I32(4),
599/// );
600
601/// let mst = algos::boruvka(g); // get the mst using prims algorithm
602
603/// // prims returns results, so use match statement to process it
604/// match mst {
605/// Ok(g) => g.print(), // print the MST if generated successfully
606/// Err(e) => println!("{}", e), // print the error if any
607/// }
608/// ```
609///
610pub fn prims(mut g: Graph) -> Result<Graph, String> {
611 // check if graph has directed edges - Prims works on undirected graph and not directed
612 let is_directed = match g.edge_type {
613 EdgeType::Directed => true,
614 EdgeType::Undirected => false,
615 };
616
617 // return error if the graph has directed edges
618 if is_directed {
619 return Err(String::from(
620 "Prims only works properly on undirected graphs!",
621 ));
622 }
623 // Check for empty or trivial graph
624 if g.get_vertices().len() <= 1 {
625 return Ok(g);
626 }
627
628 // Check for connected graph
629 //TODO: Consider removing this check for speed and instead check that resulting MST is connected.
630 let start_vertex_lbl = g.get_vertices().keys().next().unwrap().clone(); //Get an arbitrary start vertex.
631 if !dfs(&mut g, start_vertex_lbl).values().all(|&x| x) {
632 return Err(String::from("Graph is not connected."));
633 }
634
635 // vector to collect all edge values
636 let mut edges: Vec<Edge> = Vec::new();
637
638 // fill the vector with edges in graph
639 for (_, edge) in &g.edges {
640 edges.push(edge.clone());
641 }
642
643 // The graph that we are going to return
644 let mut mst = Graph::new(false);
645
646 // set to keep track of visited nodes
647 let mut visited = HashSet::new();
648
649 // Use a priority queue to keep track of the minimum edge at each step
650 let mut pq = BinaryHeap::new();
651
652 // Add the first vertex to the visited set
653 let first_vertex = g.vertices.keys().next().unwrap().clone();
654 visited.insert(first_vertex.clone());
655
656 // Add all edges from the first vertex to the priority queue
657 for (endpoint, edge) in &g.edges {
658 if endpoint.0 == first_vertex || endpoint.1 == first_vertex {
659 pq.push(Reverse(edge.clone()));
660 }
661 }
662
663 // Iterate until we have visited all vertices
664 while visited.len() != g.vertices.len() {
665 // Get the minimum edge from the priority queue
666 let Reverse(edge) = pq.pop().unwrap();
667
668 // Get the two endpoints of the edge
669 let u = edge.endpoints.0.clone();
670 let v = edge.endpoints.1.clone();
671
672 // Skip this edge if both endpoints are already visited
673 if visited.contains(&u) && visited.contains(&v) {
674 continue;
675 }
676
677 // Add the vertices and edge to the MST
678 mst.add_vertex(u.clone());
679 mst.add_vertex(v.clone());
680 mst.add_edge(
681 (u.clone(), v.clone()),
682 edge.weight.clone(),
683 //graphs::EdgeType::Undirected,
684 );
685
686 // Add the endpoint that is not visited to the visited set
687 if visited.contains(&u) {
688 visited.insert(v.clone());
689 } else {
690 visited.insert(u.clone());
691 }
692
693 // Add all edges from the new visited vertex to the priority queue
694 for (endpoint, edge) in &g.edges {
695 if visited.contains(&endpoint.0) && !visited.contains(&endpoint.1)
696 || visited.contains(&endpoint.1) && !visited.contains(&endpoint.0)
697 {
698 pq.push(Reverse(edge.clone()));
699 }
700 }
701 }
702
703 println!("\nMST: \n");
704
705 for (_, edge) in &mst.edges {
706 println!(
707 "({}) -------{}------- ({})",
708 edge.endpoints.0.clone(),
709 edge.weight,
710 edge.endpoints.1.clone()
711 );
712 }
713
714 println!("");
715
716 Ok(mst)
717}
718
719/// Tests
720#[cfg(test)]
721mod algos_tests {
722 use super::*;
723 fn get_test_graph_1(directed: bool) -> Graph {
724 // Generate a connected undirected graph.
725 let mut g: Graph = Graph::new(directed);
726 g.add_vertex(String::from("A"));
727 g.add_vertex(String::from("B"));
728 g.add_vertex(String::from("C"));
729 g.add_vertex(String::from("D"));
730 g.add_vertex(String::from("E"));
731 g.add_vertex(String::from("F"));
732 g.add_vertex(String::from("G"));
733 g.add_vertex(String::from("H"));
734 g.add_vertex(String::from("I"));
735
736 // Integers - i32
737 g.add_edge((String::from("A"), String::from('B')), GNumber::I32(4));
738 g.add_edge((String::from("B"), String::from('C')), GNumber::I32(8));
739 g.add_edge((String::from("C"), String::from('D')), GNumber::I32(7));
740 g.add_edge((String::from("D"), String::from('E')), GNumber::I32(10));
741 g.add_edge((String::from("E"), String::from('F')), GNumber::I32(11));
742 g.add_edge((String::from("F"), String::from('G')), GNumber::I32(2));
743 g.add_edge((String::from("G"), String::from('H')), GNumber::I32(1));
744 g.add_edge((String::from("H"), String::from('I')), GNumber::I32(7));
745 g.add_edge((String::from("H"), String::from('A')), GNumber::I32(9));
746 g.add_edge((String::from("B"), String::from('H')), GNumber::I32(12));
747 g.add_edge((String::from("C"), String::from('I')), GNumber::I32(2));
748 g.add_edge((String::from("C"), String::from('F')), GNumber::I32(4));
749 g.add_edge((String::from("D"), String::from('F')), GNumber::I32(14));
750 g.add_edge((String::from("G"), String::from('I')), GNumber::I32(6));
751 g
752 }
753
754 fn get_test_graph_2(directed: bool) -> Graph {
755 //Generates a graph with 2 connected components.
756 let mut g = get_test_graph_1(directed);
757 g.remove_vertex(String::from("I"));
758 g.remove_edge((String::from("B"), String::from('C')));
759 g.remove_edge((String::from("F"), String::from('G')));
760 g
761 }
762
763 fn get_mst_of_graph_1() -> Graph {
764 //Generate solution to test graph 1.
765 let mut g: Graph = Graph::new(false);
766 g.add_vertex(String::from("A"));
767 g.add_vertex(String::from("B"));
768 g.add_vertex(String::from("C"));
769 g.add_vertex(String::from("D"));
770 g.add_vertex(String::from("E"));
771 g.add_vertex(String::from("F"));
772 g.add_vertex(String::from("G"));
773 g.add_vertex(String::from("H"));
774 g.add_vertex(String::from("I"));
775 g.add_edge((String::from("A"), String::from('B')), GNumber::I32(4));
776 g.add_edge((String::from("B"), String::from('C')), GNumber::I32(8));
777 g.add_edge((String::from("C"), String::from('D')), GNumber::I32(7));
778 g.add_edge((String::from("D"), String::from('E')), GNumber::I32(10));
779 g.add_edge((String::from("F"), String::from('G')), GNumber::I32(2));
780 g.add_edge((String::from("G"), String::from('H')), GNumber::I32(1));
781 g.add_edge((String::from("C"), String::from('I')), GNumber::I32(2));
782 g.add_edge((String::from("C"), String::from('F')), GNumber::I32(4));
783 g
784 }
785
786 //Test depth-first search.
787 #[test]
788 fn test_dfs_on_connected() {
789 let mut g = get_test_graph_1(false);
790 let res = dfs(&mut g, String::from("A"));
791 assert!(res.values().all(|&x| x));
792 println!("dfs result: {:?}", res);
793 }
794
795 #[test]
796 fn test_dfs_on_disconnected() {
797 let mut g = get_test_graph_2(false);
798 let res = dfs(&mut g, String::from("A"));
799 assert!(res.get(&String::from("G")).unwrap());
800 assert!(!res.get(&String::from("E")).unwrap());
801 }
802
803 //Test reverse delete algorithm.
804 #[test]
805 fn test_reverse_delete_on_directed() {
806 let g = get_test_graph_1(true);
807 //TODO: Figure out how to check assertion error.
808 assert!(reverse_delete(g).is_err());
809 //assert_eq!(reverse_delete(G).unwrap_err(), "Reverse delete only work on undirected graphs!");
810 }
811
812 #[test]
813 fn test_reverse_delete_on_empty() {
814 let g: Graph = Graph::new(false);
815 //TODO: Come up with a better check.
816 assert_eq!(reverse_delete(g).unwrap().get_vertices().len(), 0);
817 }
818
819 #[test]
820 fn test_reverse_delete_on_trivial() {
821 let mut g: Graph = Graph::new(false);
822 g.add_vertex(String::from("Banana"));
823 //TODO: Come up with a better check.
824 assert_eq!(reverse_delete(g).unwrap().get_vertices().len(), 1);
825 }
826
827 #[test]
828 fn test_reverse_delete_disconnected() {
829 let g = get_test_graph_2(false);
830 assert!(reverse_delete(g).is_err());
831 }
832
833 #[test]
834 fn test_reverse_delete_on_non_trivial() {
835 let g = get_test_graph_1(false);
836 let mut mst = reverse_delete(g).unwrap();
837 let mut solution = get_mst_of_graph_1();
838 println!("{:?}", mst.get_edges().keys());
839 println!("{:?}", solution.get_edges().keys());
840 assert!(mst
841 .get_edges()
842 .keys()
843 .all(|x| solution.get_edges().contains_key(x)));
844 }
845
846 //Test boruvka's algorithm.
847 #[test]
848 fn test_boruvka_on_directed() {
849 let g = get_test_graph_1(true);
850 //TODO: Figure out how to check assertion error.
851 assert!(boruvka(g).is_err());
852 //assert_eq!(reverse_delete(G).unwrap_err(), "Boruvka only work on undirected graphs!");
853 }
854
855 #[test]
856 fn test_boruvka_on_empty() {
857 let g: Graph = Graph::new(false);
858 //TODO: Come up with a better check.
859 assert_eq!(boruvka(g).unwrap().get_vertices().len(), 0);
860 }
861
862 #[test]
863 fn test_boruvka_on_trivial() {
864 let mut g: Graph = Graph::new(false);
865 g.add_vertex(String::from("Banana"));
866 //TODO: Come up with a better check.
867 assert_eq!(boruvka(g).unwrap().get_vertices().len(), 1);
868 }
869
870 #[test]
871 fn test_boruvka_disconnected() {
872 let g = get_test_graph_2(false);
873 assert!(boruvka(g).is_err());
874 }
875
876 #[test]
877 fn test_boruvka_on_non_trivial() {
878 let g = get_test_graph_1(false);
879 let mut mst = boruvka(g).unwrap();
880 let mut solution = get_mst_of_graph_1();
881 println!("{:?}", mst.get_edges().keys());
882 println!("{:?}", solution.get_edges().keys());
883 assert!(mst
884 .get_edges()
885 .keys()
886 .all(|y| solution.get_edges().contains_key(y)));
887 }
888
889 //Test Kruskal's algorithm.
890 #[test]
891 fn test_kruskals_on_directed() {
892 let g = get_test_graph_1(true);
893 //TODO: Figure out how to check assertion error.
894 assert!(kruskals(g).is_err());
895 //assert_eq!(reverse_delete(G).unwrap_err(), "Boruvka only work on undirected graphs!");
896 }
897
898 #[test]
899 fn test_kruskals_on_empty() {
900 let g: Graph = Graph::new(false);
901 //TODO: Come up with a better check.
902 assert_eq!(kruskals(g).unwrap().get_vertices().len(), 0);
903 }
904
905 #[test]
906 fn test_kruskals_on_trivial() {
907 let mut g: Graph = Graph::new(false);
908 g.add_vertex(String::from("Banana"));
909 //TODO: Come up with a better check.
910 assert_eq!(kruskals(g).unwrap().get_vertices().len(), 1);
911 }
912
913 #[test]
914 fn test_kruskals_disconnected() {
915 let g = get_test_graph_2(false);
916 assert!(kruskals(g).is_err());
917 }
918
919 #[test]
920 fn test_kruskals_on_non_trivial() {
921 let g = get_test_graph_1(false);
922 let mut mst = kruskals(g).unwrap();
923 let mut solution = get_mst_of_graph_1();
924 println!("{:?}", mst.get_edges().keys());
925 println!("{:?}", solution.get_edges().keys());
926 assert!(mst
927 .get_edges()
928 .keys()
929 .all(|y| solution.get_edges().contains_key(y)));
930 }
931 // Test Prim's algorithm on an empty graph
932 #[test]
933 fn test_prims_on_empty() {
934 let g: Graph = Graph::new(false);
935 assert_eq!(prims(g).unwrap().get_vertices().len(), 0);
936 }
937
938 // Test Prim's algorithm on a trivial graph
939 #[test]
940 fn test_prims_on_trivial() {
941 let mut g: Graph = Graph::new(false);
942 g.add_vertex(String::from("Apple"));
943 assert_eq!(prims(g).unwrap().get_vertices().len(), 1);
944 }
945
946 // Test Prim's algorithm on a disconnected graph
947 #[test]
948 fn test_prims_disconnected() {
949 let g = get_test_graph_2(false);
950 assert!(prims(g).is_err());
951 }
952
953 // Test Prim's algorithm on a non-trivial graph
954 #[test]
955 fn test_prims_on_non_trivial() {
956 let g = get_test_graph_1(false);
957 let mut mst = prims(g).unwrap();
958 let mut solution = get_mst_of_graph_1();
959 assert!(mst
960 .get_edges()
961 .keys()
962 .all(|y| solution.get_edges().contains_key(y)));
963 }
964}