dsa/data_structures/graph.rs
1use std::collections::HashMap;
2use std::hash::Hash;
3use std::rc::Rc;
4use crate::data_structures::tree::TreeNode;
5
6/// A graph data structure represented as an adjacency list
7///
8/// This structure represents a `Graph` where each node is a `Rc` reference counted `TreeNode<T>`,
9/// and edges are stored as a vector of tuples containing `Rc` reference counted
10/// neighboring nodes and their optional weights
11pub struct Graph<T> {
12 /// The adjacency list representation of this `Graph`
13 ///
14 /// This `HashMap` stores the graph's structure
15 /// - The keys are `Rc` reference counted `TreeNode<T>` objects representing the graph's nodes
16 /// - The values are vectors of tuples, each representing an edge from the key node:
17 /// - The first element of the tuple is a `Rc` reference counted `TreeNode<T>` representing the neighboring node.
18 /// - The second element of the tuple is an optional `i32` (`Option<i32>`), representing the weight of the edge (if any).
19 ///
20 /// This design allows the graph to represent both weighted and unweighted graphs.
21 pub graph: HashMap<Rc<TreeNode<T>>, Vec<(Rc<TreeNode<T>>, Option<i32>)>>,
22}
23
24impl<T: Eq + Hash + Clone> Graph<T> {
25 /// Creates a new and empty `Graph`.
26 ///
27 /// # Returns
28 /// - A newly made `Graph` instance
29 ///
30 /// # Examples
31 /// ```
32 /// use dsa::data_structures::graph::Graph;
33 ///
34 /// let graph: Graph<i32> = Graph::new();
35 /// assert!(graph.graph.is_empty());
36 /// ```
37 pub fn new() -> Self {
38 Graph {
39 graph: HashMap::new(),
40 }
41 }
42
43 /// Adds a new `node` to this `Graph`.
44 ///
45 /// If the node already exists, this method does nothing.
46 ///
47 /// # Parameters
48 /// - `node`: The reference counted, `Rc`, `TreeNode` to be added to the graph.
49 ///
50 /// # Examples
51 /// ```
52 /// use std::rc::Rc;
53 /// use dsa::data_structures::graph::Graph;
54 /// use dsa::data_structures::tree::TreeNode;
55 ///
56 /// let node = Rc::new(TreeNode::new(1));
57 /// let mut graph = Graph::new();
58 /// graph.add_node(Rc::clone(&node));
59 ///
60 /// assert!(graph.graph.contains_key(&node));
61 /// ```
62 pub fn add_node(&mut self, node: Rc<TreeNode<T>>) {
63 self.graph.entry(node).or_insert(Vec::new());
64 }
65
66 /// Removes a node and all its edges from the `Graph`.
67 ///
68 /// This method removes the node from the graph and ensures
69 /// that any edges connected to it are also removed.
70 ///
71 /// # Parameters
72 /// - `node`: The `TreeNode` to be removed from the graph.
73 ///
74 /// # Examples
75 /// ```
76 /// use std::rc::Rc;
77 /// use dsa::data_structures::graph::Graph;
78 /// use dsa::data_structures::tree::TreeNode;
79 ///
80 /// let node1 = Rc::new(TreeNode::new(1));
81 /// let node2 = Rc::new(TreeNode::new(2));
82 /// let mut graph = Graph::new();
83 /// graph.add_node(Rc::clone(&node1));
84 /// graph.add_node(Rc::clone(&node2));
85 /// graph.add_edge(Rc::clone(&node1), Rc::clone(&node2), Some(10));
86 ///
87 /// graph.remove_node(Rc::clone(&node1));
88 /// assert!(!graph.graph.contains_key(&node1));
89 /// assert!(graph.graph.contains_key(&node2));
90 /// assert!(graph.graph[&node2].is_empty());
91 /// ```
92 pub fn remove_node(&mut self, node: Rc<TreeNode<T>>) {
93 for (_, neighbors) in &mut self.graph {
94 neighbors.retain(|(neighbor, _)| neighbor != &node);
95 }
96 self.graph.retain(|k, _| k != &node);
97 }
98
99 /// Adds an edge between two nodes in the `Graph`.
100 ///
101 /// If either node does not exist, it is added to the graph automatically.
102 /// The edge is added in both directions, making the graph undirected.
103 ///
104 /// # Parameters
105 /// - `a`: The first `TreeNode` as a reference counting `Rc` pointer
106 /// - `b`: The second `TreeNode` as a reference counting `Rc` pointer
107 /// - `weight`: An optional weight for the edge.
108 ///
109 /// # Examples
110 /// ```
111 /// use std::rc::Rc;
112 /// use dsa::data_structures::graph::Graph;
113 /// use dsa::data_structures::tree::TreeNode;
114 ///
115 /// let node1 = Rc::new(TreeNode::new(1));
116 /// let node2 = Rc::new(TreeNode::new(2));
117 /// let mut graph = Graph::new();
118 /// graph.add_edge(Rc::clone(&node1), Rc::clone(&node2), Some(10));
119 ///
120 /// assert!(graph.graph.contains_key(&node1));
121 /// assert!(graph.graph.contains_key(&node2));
122 /// assert_eq!(graph.graph[&node1].len(), 1);
123 /// assert_eq!(graph.graph[&node2].len(), 1);
124 /// ```
125 pub fn add_edge(&mut self, a: Rc<TreeNode<T>>, b: Rc<TreeNode<T>>, weight: Option<i32>) {
126 self.graph
127 .entry(Rc::clone(&a))
128 .or_insert(Vec::new())
129 .push((Rc::clone(&b), weight));
130 self.graph
131 .entry(Rc::clone(&b))
132 .or_insert(Vec::new())
133 .push((Rc::clone(&a), weight));
134 }
135
136 /// Removes an edge between two nodes in the `Graph`.
137 ///
138 /// If either node does not exist or the edge does not exist,
139 /// this method does nothing.
140 ///
141 /// # Parameters
142 /// - `a`: The first `TreeNode` as a reference counting `Rc` pointer.
143 /// - `b`: The second `TreeNode` as a reference counting `Rc` pointer.
144 ///
145 /// # Examples
146 /// ```
147 /// use std::rc::Rc;
148 /// use dsa::data_structures::graph::Graph;
149 /// use dsa::data_structures::tree::TreeNode;
150 ///
151 /// let node1 = Rc::new(TreeNode::new(1));
152 /// let node2 = Rc::new(TreeNode::new(2));
153 /// let mut graph = Graph::new();
154 /// graph.add_edge(Rc::clone(&node1), Rc::clone(&node2), Some(10));
155 /// graph.remove_edge(Rc::clone(&node1), Rc::clone(&node2));
156 ///
157 /// assert!(graph.graph[&node1].is_empty());
158 /// assert!(graph.graph[&node2].is_empty());
159 /// ```
160 pub fn remove_edge(&mut self, a: Rc<TreeNode<T>>, b: Rc<TreeNode<T>>) {
161 if let Some(neighbors) = self.graph.get_mut(&a) {
162 neighbors.retain(|(neighbor, _)| neighbor != &b);
163 }
164 if let Some(neighbors) = self.graph.get_mut(&b) {
165 neighbors.retain(|(neighbor, _)| neighbor != &a);
166 }
167 }
168}