simple_graph/graph.rs
1use std::collections::{hash_map::DefaultHasher, HashMap, HashSet, VecDeque};
2use std::hash::Hasher;
3
4use linked_hash_map::LinkedHashMap;
5use linked_hash_set::LinkedHashSet;
6
7use super::{GraphOperationError, Label, Result};
8
9/// Represents hash of vertex and is used to access the HashMap
10#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
11pub struct VertexId(u64);
12
13/// Directed graph data-structure with generic parameters
14///
15/// It is assumed that the user can specify the data types stored at each vertex and edge.
16///
17/// For example, if you want to make a structure like this:
18/// `(town1) <----- 100 km -----> (town2)`
19/// you can use [`Graph<String, u32>`] data type
20///
21/// ### Serialization to [`String`] in Trivial Graph Format
22/// See [`impl<V, E> Display for Graph<V, E>`](#impl-Display-for-Graph<V%2C%20E>)
23///
24/// ### Deserialization from [`&str`] in Trivial Graph Format
25/// See [`impl<V, E> FromStr for Graph<V, E>`](#impl-FromStr-for-Graph<V%2C%20E>)
26///
27/// ### Example
28/// In this example, we will make several cities and link them together with specified distance in km
29///
30/// ```
31/// use simple_graph::Graph;
32/// use std::str::FromStr;
33///
34/// let mut graph = Graph::<String, u32>::new();
35///
36/// let moscow = graph.add_vertex("Moscow".into()).unwrap();
37/// let vladimir = graph.add_vertex("Vladimir".into()).unwrap();
38/// let yaroslavl = graph.add_vertex("Yaroslavl".into()).unwrap();
39/// let novgorod = graph.add_vertex("Novgorod".into()).unwrap();
40/// let vologda = graph.add_vertex("Vologda".into()).unwrap();
41///
42/// graph.add_edge(moscow, vladimir, 180).unwrap();
43/// graph.add_edge(moscow, yaroslavl, 250).unwrap();
44/// graph.add_edge(vladimir, novgorod, 225).unwrap();
45/// graph.add_edge(yaroslavl, vologda, 175).unwrap();
46///
47/// let serialized = graph.to_string();
48/// let expected = concat!(
49/// "1 Moscow\n",
50/// "2 Vladimir\n",
51/// "3 Yaroslavl\n",
52/// "4 Novgorod\n",
53/// "5 Vologda\n",
54/// "#\n",
55/// "1 2 180\n",
56/// "1 3 250\n",
57/// "2 4 225\n",
58/// "3 5 175\n",
59/// );
60/// assert_eq!(serialized, expected);
61///
62/// let mut graph_deserialized = Graph::from_str(&serialized).unwrap();
63/// assert_eq!(graph, graph_deserialized);
64/// ```
65#[derive(Debug, Default, Eq, PartialEq)]
66pub struct Graph<V: Label, E: Label> {
67 pub(crate) vertices: LinkedHashMap<VertexId, LinkedHashSet<([VertexId; 2], E)>>,
68 pub(crate) vertices_data: HashMap<VertexId, V>,
69}
70
71impl<V: Label, E: Label> Graph<V, E> {
72 /// Creates new graph
73 ///
74 /// ```
75 /// use simple_graph::Graph;
76 ///
77 /// let _: Graph<String, u32> = Graph::new();
78 /// ```
79 pub fn new() -> Self {
80 Self::default()
81 }
82
83 /// Gets [`VertexId`] by it's value. It just creates hash of the `&V`, doesn't panics
84 ///
85 /// ```
86 /// use simple_graph::Graph;
87 /// use std::str::FromStr;
88 ///
89 /// let graph: Graph<String, u32> = Graph::new();
90 /// assert_ne!(graph.get_vertex_id(&"Moscow".into()), graph.get_vertex_id(&"Vladimir".into()));
91 ///
92 /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
93 ///
94 /// let moscow = graph.get_vertex_id(&"Moscow".into());
95 /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
96 ///
97 /// assert_eq!(graph.get_edge_value(moscow, vladimir), Ok(&180));
98 /// ```
99 pub fn get_vertex_id(&self, vertex: &V) -> VertexId {
100 let mut hasher = DefaultHasher::new();
101 vertex.hash(&mut hasher);
102 VertexId(hasher.finish())
103 }
104
105 /// Trying to add vertex to the graph, returns [`GraphOperationError::VertexAlreadyExists`]
106 /// if can't do this
107 ///
108 ///
109 /// ```
110 /// use simple_graph::{Graph, GraphOperationError};
111 ///
112 /// let mut graph: Graph<String, u32> = Graph::new();
113 ///
114 /// assert!(graph.add_vertex("Moscow".into()).is_ok());
115 /// assert_eq!(graph.add_vertex("Moscow".into()), Err(GraphOperationError::VertexAlreadyExists));
116 /// ```
117 pub fn add_vertex(&mut self, vertex: V) -> Result<VertexId> {
118 let vertex_id = self.get_vertex_id(&vertex);
119 if self
120 .vertices
121 .insert(vertex_id, LinkedHashSet::new())
122 .is_some()
123 {
124 return Err(GraphOperationError::VertexAlreadyExists);
125 }
126 self.vertices_data.insert(vertex_id, vertex);
127 Ok(vertex_id)
128 }
129
130 /// Trying to get vertex by id, returns [`GraphOperationError::VertexDoesNotExist`]
131 /// if can't do this
132 ///
133 /// ```
134 /// use simple_graph::{Graph, GraphOperationError};
135 /// use std::str::FromStr;
136 ///
137 /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
138 ///
139 /// assert!(graph.get_vertex(graph.get_vertex_id(&"Moscow".into())).is_ok());
140 /// assert_eq!(graph.get_vertex(graph.get_vertex_id(&"New York".into())), Err(GraphOperationError::VertexDoesNotExist));
141 /// ```
142 pub fn get_vertex(&self, vertex: VertexId) -> Result<&V> {
143 self.vertices_data
144 .get(&vertex)
145 .ok_or(GraphOperationError::VertexDoesNotExist)
146 }
147
148 /// Trying to remove vertex by id, returns [`GraphOperationError::VertexDoesNotExist`]
149 /// if can't do this
150 ///
151 /// ```
152 /// use simple_graph::{Graph, GraphOperationError};
153 /// use std::str::FromStr;
154 ///
155 /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
156 ///
157 /// assert!(graph.remove_vertex(graph.get_vertex_id(&"Moscow".into())).is_ok());
158 /// assert_eq!(graph.remove_vertex(graph.get_vertex_id(&"New York".into())), Err(GraphOperationError::VertexDoesNotExist));
159 ///
160 /// assert_eq!(graph.vertices_count(), 4);
161 /// ```
162 pub fn remove_vertex(&mut self, target_vertex: VertexId) -> Result<()> {
163 self.get_vertex(target_vertex)?;
164
165 let mut pairs = Vec::new();
166 for &other_vertex in self.vertices.keys() {
167 if let Ok(edge) = self.get_edge(other_vertex, target_vertex).cloned() {
168 pairs.push((other_vertex, edge));
169 }
170 }
171
172 for (other_vertex, edge) in &pairs {
173 if let Some(neighbours) = self.vertices.get_mut(other_vertex) {
174 neighbours.remove(edge);
175 }
176 }
177
178 self.vertices.remove(&target_vertex);
179 self.vertices_data.remove(&target_vertex);
180
181 Ok(())
182 }
183
184 /// Trying to add edge between two vertices, returns [`GraphOperationError::VertexDoesNotExist`]
185 /// if can't do this
186 ///
187 /// ```
188 /// use simple_graph::{Graph, GraphOperationError};
189 /// use std::str::FromStr;
190 ///
191 /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
192 ///
193 /// let novgorod = graph.get_vertex_id(&"Novgorod".into());
194 /// let kazan = graph.add_vertex("Kazan".into()).unwrap();
195 /// let new_york = graph.get_vertex_id(&"New York".into());
196 ///
197 /// assert!(graph.add_edge(novgorod, kazan, 325).is_ok());
198 /// assert_eq!(graph.add_edge(new_york, kazan, 9000), Err(GraphOperationError::VertexDoesNotExist));
199 /// ```
200 pub fn add_edge(&mut self, from: VertexId, to: VertexId, edge: E) -> Result<()> {
201 if self.vertices.get(&to).is_some() {
202 if let Some(neighbours) = self.vertices.get_mut(&from) {
203 neighbours.insert(([from, to], edge));
204 return Ok(());
205 }
206 }
207 Err(GraphOperationError::VertexDoesNotExist)
208 }
209
210 /// Trying to get edge between two vertices, returns [`GraphOperationError::EdgeDoesNotExist`]
211 /// if can't do this
212 ///
213 /// ```
214 /// use simple_graph::{Graph, GraphOperationError};
215 /// use std::str::FromStr;
216 ///
217 /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
218 ///
219 /// let moscow = graph.get_vertex_id(&"Moscow".into());
220 /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
221 ///
222 /// // Moscow -> Vladimir (ok)
223 /// let ([_from, _to], value) = graph.get_edge(moscow, vladimir).unwrap();
224 /// assert_eq!(value, &180);
225 /// // Vladimir -> Moscow (err)
226 /// assert_eq!(graph.get_edge(vladimir, moscow), Err(GraphOperationError::EdgeDoesNotExist));
227 /// ```
228 pub fn get_edge(&self, from: VertexId, to: VertexId) -> Result<&([VertexId; 2], E)> {
229 if let Some(neighbours) = self.vertices.get(&from) {
230 for edge in neighbours {
231 let [_, destination_vertex] = edge.0;
232 if destination_vertex == to {
233 return Ok(edge);
234 }
235 }
236 }
237 Err(GraphOperationError::EdgeDoesNotExist)
238 }
239
240 /// Trying to get edge **value** between two vertices, returns [`GraphOperationError::EdgeDoesNotExist`]
241 /// if can't do this
242 ///
243 /// ```
244 /// use simple_graph::Graph;
245 /// use std::str::FromStr;
246 ///
247 /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
248 ///
249 /// let moscow = graph.get_vertex_id(&"Moscow".into());
250 /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
251 ///
252 /// assert_eq!(graph.get_edge_value(moscow, vladimir), Ok(&180));
253 /// ```
254 pub fn get_edge_value(&self, from: VertexId, to: VertexId) -> Result<&E> {
255 let (_, value) = self.get_edge(from, to)?;
256 Ok(value)
257 }
258
259 /// Trying to remove edge between two vertices, returns [`GraphOperationError::EdgeDoesNotExist`]
260 /// if can't do this
261 ///
262 /// ```
263 /// use simple_graph::{Graph, GraphOperationError};
264 /// use std::str::FromStr;
265 ///
266 /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
267 ///
268 /// let moscow = graph.get_vertex_id(&"Moscow".into());
269 /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
270 ///
271 /// assert!(graph.remove_edge(moscow, vladimir).is_ok());
272 /// assert_eq!(graph.remove_edge(moscow, vladimir), Err(GraphOperationError::EdgeDoesNotExist));
273 /// ```
274 pub fn remove_edge(&mut self, from: VertexId, to: VertexId) -> Result<()> {
275 if let Ok(edge) = self.get_edge(from, to).cloned() {
276 if let Some(neighbours) = self.vertices.get_mut(&from) {
277 neighbours.remove(&edge);
278 return Ok(());
279 }
280 }
281 Err(GraphOperationError::EdgeDoesNotExist)
282 }
283
284 /// Returns count of vertices in the graph
285 ///
286 /// ```
287 /// use simple_graph::Graph;
288 /// use std::str::FromStr;
289 ///
290 /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
291 /// assert_eq!(graph.vertices_count(), 5);
292 /// ```
293 pub fn vertices_count(&self) -> usize {
294 self.vertices.len()
295 }
296
297 /// Returns count of edges in the graph
298 ///
299 /// ```
300 /// use simple_graph::Graph;
301 /// use std::str::FromStr;
302 ///
303 /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
304 /// assert_eq!(graph.edges_count(), 4);
305 /// ```
306 pub fn edges_count(&self) -> usize {
307 let mut count = 0;
308 for (_, neighbours) in self.vertices.iter() {
309 count += neighbours.len();
310 }
311 count
312 }
313
314 /// Returns [`Result<Vec<(&V, Vec<(&V, &E)>)>>`] which is vertices representation
315 ///
316 /// where
317 /// - `&V` - vertex
318 /// - `Vec<(&V, &E)>` - adjacent vertices
319 ///
320 /// ```
321 /// use simple_graph::Graph;
322 /// use std::str::FromStr;
323 ///
324 /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
325 ///
326 /// for (vertex, adjacent_vertices) in graph.vertices().unwrap() {
327 /// println!("{vertex}: {adjacent_vertices:?}");
328 /// }
329 ///
330 /// //output looks like
331 ///
332 /// //Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]
333 /// //Vladimir: [("Novgorod", 225)]
334 /// //Yaroslavl: [("Vologda", 175)]
335 /// //Novgorod: []
336 /// //Vologda: []
337 /// ```
338 #[allow(clippy::type_complexity)]
339 pub fn vertices(&self) -> Result<Vec<(&V, Vec<(&V, &E)>)>> {
340 self.vertices
341 .keys()
342 .map(|&id| self.get_vertex_info(id))
343 .collect::<Result<Vec<_>>>()
344 }
345
346 /// Returns [`Result<Vec<([&V; 2], &E)>>`] which is edges representation
347 ///
348 /// where
349 /// - `[&V; 2]` - `[from, to]`
350 /// - `&E` - edge data
351 ///
352 /// ```
353 /// use simple_graph::Graph;
354 /// use std::str::FromStr;
355 ///
356 /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
357 ///
358 /// for ([from, to], data) in graph.edges().unwrap() {
359 /// println!("{from} ---- [{data}] ----> {to}");
360 /// }
361 ///
362 /// //output looks like
363 ///
364 /// //Moscow ---- [180] ----> Vladimir
365 /// //Moscow ---- [250] ----> Yaroslavl
366 /// //Vladimir ---- [225] ----> Novgorod
367 /// //Yaroslavl ---- [175] ----> Vologda
368 /// ```
369 pub fn edges(&self) -> Result<Vec<([&V; 2], &E)>> {
370 let mut edges = Vec::new();
371 for (_, neighbours) in self.vertices.iter() {
372 for ([from, to], edge) in neighbours {
373 edges.push(([self.get_vertex(*from)?, self.get_vertex(*to)?], edge));
374 }
375 }
376 Ok(edges)
377 }
378
379 /// Trying to get detailed information about the vertex
380 ///
381 /// ```
382 /// use simple_graph::Graph;
383 /// use std::str::FromStr;
384 ///
385 /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
386 ///
387 /// let moscow = graph.get_vertex_id(&"Moscow".into());
388 ///
389 /// let (vertex_data, adjacent_vertices) = graph.get_vertex_info(moscow).unwrap();
390 /// assert_eq!(vertex_data, &String::from("Moscow"));
391 /// assert_eq!(adjacent_vertices, vec![(&"Vladimir".into(), &180), (&"Yaroslavl".into(), &250)]);
392 /// ```
393 pub fn get_vertex_info(&self, vertex_id: VertexId) -> Result<(&V, Vec<(&V, &E)>)> {
394 let vertex = self.get_vertex(vertex_id)?;
395
396 let mut adjacent_vertices = Vec::new();
397 if let Some(neighbours) = self.vertices.get(&vertex_id) {
398 for ([_, vertex], edge) in neighbours {
399 adjacent_vertices.push((self.get_vertex(*vertex)?, edge));
400 }
401 }
402
403 Ok((vertex, adjacent_vertices))
404 }
405
406 /// Generic search algorithm for implementation BFS and DFS.
407 /// It uses generic queue type and queue operations to prevent code duplication
408 fn generic_search<
409 QueueTy,
410 QueueInitFn: Fn() -> QueueTy,
411 QueueInsertFn: Fn(&mut QueueTy, VertexId),
412 QueueRemoveFn: Fn(&mut QueueTy) -> Option<VertexId>,
413 AccessFn: FnMut(&V, Vec<(&V, &E)>),
414 >(
415 &self,
416 queue_init: QueueInitFn,
417 queue_insert: QueueInsertFn,
418 queue_remove: QueueRemoveFn,
419 source: VertexId,
420 mut access: AccessFn,
421 ) -> Result<()> {
422 let mut queue = queue_init();
423 let mut visited = HashSet::new();
424
425 queue_insert(&mut queue, source);
426 visited.insert(source);
427
428 while let Some(vertex) = queue_remove(&mut queue) {
429 let (vertex, adjacent_vertices) = self.get_vertex_info(vertex)?;
430 for (adjacent_vertex, _) in adjacent_vertices.iter() {
431 let id = self.get_vertex_id(adjacent_vertex);
432 if !visited.contains(&id) {
433 queue_insert(&mut queue, id);
434 visited.insert(id);
435 }
436 }
437 access(vertex, adjacent_vertices);
438 }
439
440 Ok(())
441 }
442
443 /// Breadth-first search algorithm uses [`VecDeque`] for queue
444 ///
445 /// ```
446 /// use simple_graph::Graph;
447 /// use std::str::FromStr;
448 ///
449 /// let graph: Graph<String, u32> =
450 /// Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
451 ///
452 /// let moscow = graph.get_vertex_id(&"Moscow".into());
453 ///
454 /// let mut visited = Vec::new();
455 /// graph
456 /// .bfs(moscow, |vertex, adjacent_vertices| {
457 /// visited.push(format!("{vertex}: {adjacent_vertices:?}"));
458 /// })
459 /// .expect("failed to perform BFS");
460 ///
461 /// //(1) Moscow ->
462 /// // (2) Vladimir -> (4) Novgorod
463 /// // (3) Yaroslavl -> (5) Vologda
464 /// let expected = vec![
465 /// r#"Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]"#, //1
466 /// r#"Vladimir: [("Novgorod", 225)]"#, //2
467 /// r#"Yaroslavl: [("Vologda", 175)]"#, //3
468 /// r#"Novgorod: []"#, //4
469 /// r#"Vologda: []"#, //5
470 /// ];
471 /// assert_eq!(visited, expected);
472 /// ```
473 pub fn bfs<F: FnMut(&V, Vec<(&V, &E)>)>(&self, source: VertexId, access: F) -> Result<()> {
474 self.generic_search(
475 VecDeque::new,
476 |queue, vertex| queue.push_back(vertex),
477 |queue| queue.pop_front(),
478 source,
479 access,
480 )
481 }
482
483 /// Depth-first search algorithm uses [`Vec`] for stack
484 ///
485 /// ```
486 /// use simple_graph::Graph;
487 /// use std::str::FromStr;
488 ///
489 /// let graph: Graph<String, u32> =
490 /// Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
491 ///
492 /// let moscow = graph.get_vertex_id(&"Moscow".into());
493 ///
494 /// let mut visited = Vec::new();
495 /// graph
496 /// .dfs(moscow, |vertex, adjacent_vertices| {
497 /// visited.push(format!("{vertex}: {adjacent_vertices:?}"));
498 /// })
499 /// .expect("failed to perform DFS");
500 ///
501 /// //(1) Moscow ->
502 /// // (2) Yaroslavl -> (3) Vologda
503 /// // (4) Vladimir -> (5) Novgorod
504 /// let expected = vec![
505 /// r#"Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]"#,
506 /// r#"Yaroslavl: [("Vologda", 175)]"#,
507 /// r#"Vologda: []"#,
508 /// r#"Vladimir: [("Novgorod", 225)]"#,
509 /// r#"Novgorod: []"#,
510 /// ];
511 /// assert_eq!(visited, expected);
512 /// ```
513 pub fn dfs<F: FnMut(&V, Vec<(&V, &E)>)>(&self, source: VertexId, access: F) -> Result<()> {
514 self.generic_search(
515 Vec::new,
516 |stack, vertex| stack.push(vertex),
517 |stack| stack.pop(),
518 source,
519 access,
520 )
521 }
522}