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}