graphalgos/util.rs
1use std::collections::HashMap;
2use std::hash::Hash;
3
4/// Disjoint Set Definition
5pub struct DisjointSet<T>
6where
7 T: Clone + Eq + Hash,
8{
9 sets: HashMap<T, Vec<T>>,
10 representatives: HashMap<T, T>,
11}
12
13impl<T> DisjointSet<T>
14where
15 T: Clone + Eq + Hash, // Got error coz hashmap value needs these traits
16{
17 /// Associate Function
18 /// Creates a new Disjoint Set
19 ///
20 /// # Example
21 ///
22 /// ```
23 /// let mut set = DisjointSet::new(); // creates a new Disjoint set
24 /// ```
25 pub fn new() -> Self {
26 Self {
27 sets: HashMap::new(),
28 representatives: HashMap::new(),
29 }
30 }
31
32 /// Insert a value to the set
33 ///
34 /// # Example
35 ///
36 /// ```
37 /// // Add all the vertices of graph g to the disjoint set
38 /// for (node, _) in &g.vertices {
39 /// set.set_insert(node.clone());
40 /// }
41 /// ```
42 pub fn set_insert(&mut self, val: T) {
43 self.sets.insert(val.clone(), vec![val.clone()]);
44 self.representatives.insert(val.clone(), val.clone());
45 }
46
47 /// Find parent of the value
48 ///
49 /// # Example
50 ///
51 /// ```
52 /// set.find(&vertex)
53 /// ```
54 ///
55 pub fn find(&self, val: &T) -> T {
56 self.representatives.get(val).unwrap().clone()
57 }
58
59 /// Union function for two nodes (vertices)
60 ///
61 /// # Example
62 ///
63 /// ```
64 /// set.union(&vertex1, &vertex2)
65 /// ```
66 ///
67 pub fn union(&mut self, a: &T, b: &T) {
68 let repa = self.representatives.get(a).unwrap().clone();
69 let repb = self.representatives.get(b).unwrap().clone();
70 let setb = self.sets.remove(&repb).unwrap(); // get all from set of the second value
71
72 for i in setb.iter() {
73 self.representatives.remove(i); // remove them from their group
74 self.representatives.insert(i.clone(), repa.clone()); // and add them to the first group
75 }
76
77 let seta = self.sets.get_mut(&repa).unwrap();
78
79 // Now all elements from the second set will be added to first and thus union is complete
80 for i in &setb {
81 seta.push(i.clone());
82 }
83 }
84}