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}