Skip to main content

data_structures_lib/
graphs.rs

1use std::collections::HashMap;
2
3use crate::Error;
4
5/// A graph represented as an adjacency list.
6#[derive(Debug, Clone)]
7pub struct AdjacencyListGraph<T: Clone + Eq + std::hash::Hash> {
8    adj: HashMap<T, Vec<T>>,
9    directed: bool,
10}
11
12impl<T: Clone + Eq + std::hash::Hash> AdjacencyListGraph<T> {
13    /// Creates a new AdjacencyListGraph.
14    pub fn new(directed: bool) -> Self {
15        Self {
16            adj: HashMap::new(),
17            directed,
18        }
19    }
20
21    /// Returns the number of vertices.
22    pub fn vertex_count(&self) -> usize {
23        self.adj.len()
24    }
25
26    /// Returns true if the graph is empty.
27    pub fn is_empty(&self) -> bool {
28        self.adj.is_empty()
29    }
30
31    /// Adds a vertex.
32    pub fn add_vertex(&mut self, vertex: T) {
33        self.adj.entry(vertex).or_insert_with(Vec::new);
34    }
35
36    /// Removes a vertex.
37    pub fn remove_vertex(&mut self, vertex: &T) -> Result<(), Error> {
38        if !self.adj.contains_key(vertex) {
39            return Err(Error::NotFound);
40        }
41        for neighbors in self.adj.values_mut() {
42            if let Some(pos) = neighbors.iter().position(|v| v == vertex) {
43                neighbors.remove(pos);
44            }
45        }
46        self.adj.remove(vertex);
47        Ok(())
48    }
49
50    /// Adds an edge.
51    pub fn add_edge(&mut self, u: T, v: T) {
52        self.add_vertex(u.clone());
53        self.add_vertex(v.clone());
54        if !self.adj[&u].contains(&v) {
55            self.adj.get_mut(&u).unwrap().push(v.clone());
56        }
57        if !self.directed && !self.adj[&v].contains(&u) {
58            self.adj.get_mut(&v).unwrap().push(u);
59        }
60    }
61
62    /// Removes an edge.
63    pub fn remove_edge(&mut self, u: &T, v: &T) {
64        if let Some(neighbors) = self.adj.get_mut(u) {
65            if let Some(pos) = neighbors.iter().position(|x| x == v) {
66                neighbors.remove(pos);
67            }
68        }
69        if !self.directed {
70            if let Some(neighbors) = self.adj.get_mut(v) {
71                if let Some(pos) = neighbors.iter().position(|x| x == u) {
72                    neighbors.remove(pos);
73                }
74            }
75        }
76    }
77
78    /// Returns true if there is an edge from u to v.
79    pub fn has_edge(&self, u: &T, v: &T) -> bool {
80        self.adj
81            .get(u)
82            .map(|neighbors| neighbors.contains(v))
83            .unwrap_or(false)
84    }
85
86    /// Returns the neighbors of a vertex.
87    pub fn neighbors(&self, vertex: &T) -> Vec<T> {
88        self.adj.get(vertex).cloned().unwrap_or_default()
89    }
90
91    /// Returns vertices in breadth-first order.
92    pub fn bfs(&self, start: &T) -> Vec<T> {
93        if !self.adj.contains_key(start) {
94            return Vec::new();
95        }
96        let mut visited = std::collections::HashSet::new();
97        visited.insert(start.clone());
98        let mut queue = vec![start.clone()];
99        let mut result = Vec::new();
100        while let Some(current) = queue.pop() {
101            result.push(current.clone());
102            for neighbor in &self.adj[&current] {
103                if visited.insert(neighbor.clone()) {
104                    queue.insert(0, neighbor.clone());
105                }
106            }
107        }
108        result
109    }
110
111    /// Returns vertices in depth-first order.
112    pub fn dfs(&self, start: &T) -> Vec<T> {
113        if !self.adj.contains_key(start) {
114            return Vec::new();
115        }
116        let mut visited = std::collections::HashSet::new();
117        let mut result = Vec::new();
118        self.dfs_visit(start, &mut visited, &mut result);
119        result
120    }
121
122    fn dfs_visit(&self, vertex: &T, visited: &mut std::collections::HashSet<T>, result: &mut Vec<T>) {
123        if !visited.insert(vertex.clone()) {
124            return;
125        }
126        result.push(vertex.clone());
127        for neighbor in &self.adj[vertex] {
128            self.dfs_visit(neighbor, visited, result);
129        }
130    }
131}
132
133/// A graph represented as an adjacency matrix.
134#[derive(Debug, Clone)]
135pub struct AdjacencyMatrixGraph<T: Clone + Eq + std::hash::Hash> {
136    vertices: Vec<T>,
137    index: HashMap<T, usize>,
138    matrix: Vec<Vec<i32>>,
139    directed: bool,
140}
141
142impl<T: Clone + Eq + std::hash::Hash> AdjacencyMatrixGraph<T> {
143    /// Creates a new AdjacencyMatrixGraph.
144    pub fn new(directed: bool) -> Self {
145        Self {
146            vertices: Vec::new(),
147            index: HashMap::new(),
148            matrix: Vec::new(),
149            directed,
150        }
151    }
152
153    /// Returns the number of vertices.
154    pub fn vertex_count(&self) -> usize {
155        self.vertices.len()
156    }
157
158    /// Returns true if the graph is empty.
159    pub fn is_empty(&self) -> bool {
160        self.vertices.is_empty()
161    }
162
163    /// Adds a vertex.
164    pub fn add_vertex(&mut self, vertex: T) {
165        if self.index.contains_key(&vertex) {
166            return;
167        }
168        self.index.insert(vertex.clone(), self.vertices.len());
169        self.vertices.push(vertex);
170        for row in &mut self.matrix {
171            row.push(0);
172        }
173        self.matrix.push(vec![0; self.vertices.len()]);
174    }
175
176    /// Removes a vertex.
177    pub fn remove_vertex(&mut self, vertex: &T) -> Result<(), Error> {
178        let idx = *self.index.get(vertex).ok_or(Error::NotFound)?;
179        self.vertices.remove(idx);
180        self.index.remove(vertex);
181        self.matrix.remove(idx);
182        for row in &mut self.matrix {
183            row.remove(idx);
184        }
185        for (i, v) in self.vertices.iter().enumerate() {
186            self.index.insert(v.clone(), i);
187        }
188        Ok(())
189    }
190
191    /// Adds an edge with weight.
192    pub fn add_edge(&mut self, u: T, v: T, weight: i32) {
193        self.add_vertex(u.clone());
194        self.add_vertex(v.clone());
195        let ui = self.index[&u];
196        let vi = self.index[&v];
197        self.matrix[ui][vi] = weight;
198        if !self.directed {
199            self.matrix[vi][ui] = weight;
200        }
201    }
202
203    /// Removes an edge.
204    pub fn remove_edge(&mut self, u: &T, v: &T) {
205        if let (Some(&ui), Some(&vi)) = (self.index.get(u), self.index.get(v)) {
206            self.matrix[ui][vi] = 0;
207            if !self.directed {
208                self.matrix[vi][ui] = 0;
209            }
210        }
211    }
212
213    /// Returns true if there is an edge from u to v.
214    pub fn has_edge(&self, u: &T, v: &T) -> bool {
215        if let (Some(&ui), Some(&vi)) = (self.index.get(u), self.index.get(v)) {
216            return self.matrix[ui][vi] != 0;
217        }
218        false
219    }
220
221    /// Returns the weight of an edge.
222    pub fn weight(&self, u: &T, v: &T) -> Result<i32, Error> {
223        let ui = *self.index.get(u).ok_or(Error::NotFound)?;
224        let vi = *self.index.get(v).ok_or(Error::NotFound)?;
225        Ok(self.matrix[ui][vi])
226    }
227
228    /// Returns the neighbors of a vertex.
229    pub fn neighbors(&self, vertex: &T) -> Vec<T> {
230        let idx = match self.index.get(vertex) {
231            Some(&i) => i,
232            None => return Vec::new(),
233        };
234        let mut result = Vec::new();
235        for (i, w) in self.matrix[idx].iter().enumerate() {
236            if *w != 0 {
237                result.push(self.vertices[i].clone());
238            }
239        }
240        result
241    }
242
243    /// Returns vertices in breadth-first order.
244    pub fn bfs(&self, start: &T) -> Vec<T> {
245        if !self.index.contains_key(start) {
246            return Vec::new();
247        }
248        let mut visited = std::collections::HashSet::new();
249        visited.insert(start.clone());
250        let mut queue = vec![start.clone()];
251        let mut result = Vec::new();
252        while let Some(current) = queue.pop() {
253            result.push(current.clone());
254            for neighbor in self.neighbors(&current) {
255                if visited.insert(neighbor.clone()) {
256                    queue.insert(0, neighbor);
257                }
258            }
259        }
260        result
261    }
262
263    /// Returns vertices in depth-first order.
264    pub fn dfs(&self, start: &T) -> Vec<T> {
265        if !self.index.contains_key(start) {
266            return Vec::new();
267        }
268        let mut visited = std::collections::HashSet::new();
269        let mut result = Vec::new();
270        self.dfs_visit(start, &mut visited, &mut result);
271        result
272    }
273
274    fn dfs_visit(&self, vertex: &T, visited: &mut std::collections::HashSet<T>, result: &mut Vec<T>) {
275        if !visited.insert(vertex.clone()) {
276            return;
277        }
278        result.push(vertex.clone());
279        for neighbor in self.neighbors(vertex) {
280            self.dfs_visit(&neighbor, visited, result);
281        }
282    }
283}