data_structures_lib/
graphs.rs1use std::collections::HashMap;
2
3use crate::Error;
4
5#[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 pub fn new(directed: bool) -> Self {
15 Self {
16 adj: HashMap::new(),
17 directed,
18 }
19 }
20
21 pub fn vertex_count(&self) -> usize {
23 self.adj.len()
24 }
25
26 pub fn is_empty(&self) -> bool {
28 self.adj.is_empty()
29 }
30
31 pub fn add_vertex(&mut self, vertex: T) {
33 self.adj.entry(vertex).or_insert_with(Vec::new);
34 }
35
36 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 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 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 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 pub fn neighbors(&self, vertex: &T) -> Vec<T> {
88 self.adj.get(vertex).cloned().unwrap_or_default()
89 }
90
91 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[¤t] {
103 if visited.insert(neighbor.clone()) {
104 queue.insert(0, neighbor.clone());
105 }
106 }
107 }
108 result
109 }
110
111 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#[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 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 pub fn vertex_count(&self) -> usize {
155 self.vertices.len()
156 }
157
158 pub fn is_empty(&self) -> bool {
160 self.vertices.is_empty()
161 }
162
163 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 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 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 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 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 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 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 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(¤t) {
255 if visited.insert(neighbor.clone()) {
256 queue.insert(0, neighbor);
257 }
258 }
259 }
260 result
261 }
262
263 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}