generic_graph/adjacency_list/mod.rs
1//!This module provide an implementation of a growable directed graph.
2//! The graph is implemented as a set of adjacency list (list of vertex adjacent to one vertex).
3//!
4//!These lists consists of HashMaps, allowing the graph to grow to a considerable size while still
5//! maintaining a certain speed. Though it is not indicated for small or not growing graphs
6use super::{DirectedGraph, VariableEdges, VariableVertexes, SimpleVertex, Edge};
7use std::collections::HashMap;
8use std::hash::Hash;
9use std::ops::{Add, Sub};
10
11pub mod elements;
12use elements::*;
13use crate::{Vertex, EdgeSide};
14
15//The type AdjacencyList is a private type meant to associate a vertex
16// to its adjacency list
17struct AdjacencyList<K, V, W>
18 where K: Hash + Eq + Clone,
19 W: Add + Sub + Eq + Ord + Copy,
20{
21 vertex: DirectedVertex<K, V>,
22 list: HashMap<CompoundKey<K>, DirectedEdge<K, W>>,
23}
24
25///`AdjacencyGraph` implements a DirectedGraph using a set (one for every vertex) of lists containing
26/// edges leading from the vertex to another. This lists are stored as HashMaps, allowing fast access
27/// to vertexes and edges even with a large number of them or when they change quickly in number
28///
29///for small graphs this might not be the ideal implementation
30pub struct AdjacencyGraph<K, V, W>
31 where K: Hash + Eq + Clone,
32 W: Add + Sub + Eq + Ord + Copy,
33{
34 vertexes: HashMap<K, AdjacencyList<K, V, W>>,
35}
36
37impl<K: Hash + Eq + Clone, V, W: Add + Sub + Eq + Ord + Copy> AdjacencyGraph<K, V, W> {
38
39 ///Returns a new empty graph
40 pub fn new() -> AdjacencyGraph<K, V, W>{
41 AdjacencyGraph {
42 vertexes: HashMap::new()
43 }
44 }
45}
46
47///`AdjacencyGraph` implement the DirectedGraph trait Specifying the vertex type (DirectedVertex),
48/// the edge type (Directed Edge), and the edge key type (CompoundKey). But the vertex key type,
49/// the vertex value type and the edge weight type remain generics.
50impl<K: Hash + Eq + Clone, V, W: Add + Sub + Eq + Ord + Copy> DirectedGraph<
51 DirectedVertex<K, V>,
52 DirectedEdge<K, W>,
53 K, V, W,
54 CompoundKey<K>
55> for AdjacencyGraph<K, V, W> {
56
57 ///Check if an edge going from the first to the second vertex exists
58 ///
59 /// # Examples
60 ///
61 /// ```rust
62 /// use generic_graph::adjacency_list::AdjacencyGraph;
63 /// use generic_graph::{SimpleVertex, VariableVertexes, VariableEdges, DirectedGraph};
64 /// use generic_graph::adjacency_list::elements::DirectedEdge;
65 /// let mut graph = AdjacencyGraph::new();
66 /// graph.add_vertex(SimpleVertex::new(1, "a"));
67 /// graph.add_vertex(SimpleVertex::new(2, "b"));
68 /// graph.add_vertex(SimpleVertex::new(3, "c"));
69 /// graph.add_edge(DirectedEdge::new(2, 3, 3)).expect("Won't fail");
70 /// graph.add_edge(DirectedEdge::new(1, 3, 3)).expect("Won't fail");
71 /// assert_eq!(true, graph.adjacent(&1, &3));
72 /// assert_eq!(false, graph.adjacent(&3, &1));
73 /// assert_eq!(false, graph.adjacent(&2, &1));
74 /// ```
75 fn adjacent(&self, from: &K, to: &K) -> bool {
76 if let Some(adjacency) = self.vertexes.get(from) {
77 if let Some(_) = adjacency.list.get(&DirectedEdge::<K, W>::generate_key((from, to))) {
78 true
79 } else {
80 false
81 }
82 } else {
83 false
84 }
85 }
86
87 ///Returns a Vector containing the keys of the vertexes reached by edges leaving from the vertex
88 /// identified by the passed key
89 ///
90 /// # Examples
91 ///
92 /// ```rust
93 /// use generic_graph::adjacency_list::AdjacencyGraph;
94 /// use generic_graph::{SimpleVertex, VariableVertexes, VariableEdges, DirectedGraph};
95 /// use generic_graph::adjacency_list::elements::DirectedEdge;
96 /// let mut graph = AdjacencyGraph::new();
97 /// graph.add_vertex(SimpleVertex::new(1, "a"));
98 /// graph.add_vertex(SimpleVertex::new(2, "b"));
99 /// graph.add_vertex(SimpleVertex::new(3, "c"));
100 /// graph.add_edge(DirectedEdge::new(2, 3, 3)).expect("Won't fail");
101 /// graph.add_edge(DirectedEdge::new(2, 1, 3)).expect("Won't fail");
102 /// graph.add_edge(DirectedEdge::new(1, 3, 3)).expect("Won't fail");
103 ///
104 /// let mut neighbors = graph.neighbors(&2);
105 /// neighbors.sort();
106 /// assert_eq!(neighbors, vec![&1,&3]);
107 /// ```
108 fn neighbors(&self, from: &K) -> Vec<&K> {
109 let mut neighbors = Vec::new();
110
111 if let Some(adjacency) = self.vertexes.get(from) {
112 for (_, edge) in &adjacency.list {
113 neighbors.push(edge.right());
114 }
115 }
116
117 neighbors
118 }
119
120 ///Returns a vector containing the keys of the Vertexes from which an edge leave to reach the
121 /// vertex identified by the passed key
122 ///
123 /// # Examples
124 ///
125 /// ```rust
126 /// use generic_graph::adjacency_list::AdjacencyGraph;
127 /// use generic_graph::{SimpleVertex, VariableVertexes, VariableEdges, DirectedGraph};
128 /// use generic_graph::adjacency_list::elements::DirectedEdge;
129 /// let mut graph = AdjacencyGraph::new();
130 /// graph.add_vertex(SimpleVertex::new(1, "a"));
131 /// graph.add_vertex(SimpleVertex::new(2, "b"));
132 /// graph.add_vertex(SimpleVertex::new(3, "c"));
133 /// graph.add_edge(DirectedEdge::new(2, 3, 3)).expect("Won't fail");
134 /// graph.add_edge(DirectedEdge::new(1, 3, 3)).expect("Won't fail");
135 ///
136 /// let mut leading_to = graph.leading_to(&3);
137 /// leading_to.sort();
138 /// assert_eq!(leading_to, vec![&1,&2]);
139 /// ```
140 fn leading_to(&self, to: &K) -> Vec<&K> {
141 let mut leading = Vec::new();
142
143 for (from, adjacency) in &self.vertexes {
144 if let Some(_) = adjacency.list.get(&DirectedEdge::<K, W>::generate_key((from, &to))){
145 leading.push(from);
146 }
147 }
148
149 leading
150 }
151
152 ///Returns a vector containing the references to keys of all vertexes in the graph
153 ///
154 /// # Examples
155 ///
156 /// ```rust
157 /// use generic_graph::adjacency_list::AdjacencyGraph;
158 /// use generic_graph::{SimpleVertex, VariableVertexes, VariableEdges, DirectedGraph};
159 /// use generic_graph::adjacency_list::elements::DirectedEdge;
160 /// let mut graph = AdjacencyGraph::new();
161 /// graph.add_vertex(SimpleVertex::new(1, "a"));
162 /// graph.add_vertex(SimpleVertex::new(2, "b"));
163 /// graph.add_vertex(SimpleVertex::new(3, "c"));
164 /// graph.add_edge(DirectedEdge::new(2, 3, 3)).expect("Won't fail");
165 /// graph.add_edge(DirectedEdge::new(1, 3, 3)).expect("Won't fail");
166 ///
167 /// let mut keys = graph.get_all_keys();
168 /// keys.sort();
169 /// assert_eq!(keys, vec![&1, &2, &3]);
170 /// ```
171 fn get_all_keys(&self) -> Vec<&K> {
172 let mut vertexes = Vec::new();
173
174 for (key, _) in &self.vertexes {
175 vertexes.push(key);
176 }
177
178 vertexes
179 }
180
181 ///Returns a vector containing the pairs of all edges in the graph
182 ///
183 /// # Examples
184 ///
185 /// ```rust
186 /// use generic_graph::adjacency_list::AdjacencyGraph;
187 /// use generic_graph::{SimpleVertex, VariableVertexes, VariableEdges, DirectedGraph};
188 /// use generic_graph::adjacency_list::elements::DirectedEdge;
189 /// let mut graph = AdjacencyGraph::new();
190 /// graph.add_vertex(SimpleVertex::new(1, "a"));
191 /// graph.add_vertex(SimpleVertex::new(2, "b"));
192 /// graph.add_vertex(SimpleVertex::new(3, "c"));
193 /// graph.add_edge(DirectedEdge::new(2, 3, 3)).expect("Won't fail");
194 /// graph.add_edge(DirectedEdge::new(1, 3, 3)).expect("Won't fail");
195 ///
196 /// let mut pairs = graph.get_all_pairs();
197 /// pairs.sort();
198 /// assert_eq!(pairs, vec![(&1, &3), (&2, &3)]);
199 /// ```
200 fn get_all_pairs(&self) -> Vec<(&K, &K)> {
201 let mut pairs = Vec::new();
202
203 for (_, adjacency) in &self.vertexes {
204 for (_, edge) in &adjacency.list {
205 pairs.push(edge.get_pair());
206 }
207 }
208
209 pairs
210 }
211
212 ///Returns a reference to the vertex identified by the passed key
213 fn get_vertex(&self, key: &K) -> Option<&SimpleVertex<K, V>> {
214 if let Some(adjacency) = self.vertexes.get(&key) {
215 Some(&adjacency.vertex)
216 } else {
217 None
218 }
219 }
220
221 ///Returns a mutable reference to the vertex identified by the passed key
222 fn get_mut_vertex(&mut self, key: &K) -> Option<&mut SimpleVertex<K, V>> {
223 if let Some(adjacency) = self.vertexes.get_mut(&key) {
224 Some(&mut adjacency.vertex)
225 } else {
226 None
227 }
228 }
229
230 ///Returns a reference to the edge identified by the passed pair of keys
231 fn get_edge(&self, pair: (&K, &K)) -> Option<&DirectedEdge<K, W>> {
232 if let Some(adjacency) = self.vertexes.get(pair.0) {
233 adjacency.list.get(&DirectedEdge::<K, W>::generate_key(pair))
234 } else {
235 None
236 }
237 }
238
239 ///Returns a mutable reference to the edge identified by the passed pair of keys
240 fn get_mut_edge(&mut self, pair: (&K, &K)) -> Option<&mut DirectedEdge<K, W>> {
241 if let Some(adjacency) = self.vertexes.get_mut(pair.0) {
242 adjacency.list.get_mut(&DirectedEdge::<K, W>::generate_key(pair))
243 } else {
244 None
245 }
246 }
247}
248
249///`AdjacencyGraph` uses HashMaps to store vertexes, allowing fast insertion and removal of the latter
250impl<K: Hash + Eq + Clone, V, W: Add + Sub + Eq + Ord + Copy> VariableVertexes<
251 DirectedVertex<K, V>,
252 DirectedEdge<K, W>,
253 K, V, W,
254 CompoundKey<K>
255> for AdjacencyGraph<K, V, W>
256{
257
258 ///This method adds (or, if present, updates maintaining its edges) a vertex and returns None ore Some(old_vertex)
259 ///
260 /// # Examples
261 /// ```rust
262 /// use generic_graph::adjacency_list::AdjacencyGraph;
263 /// use generic_graph::{SimpleVertex, VariableVertexes};
264 /// let mut graph = AdjacencyGraph::<i32, &str, i32>::new();
265 ///
266 /// assert_eq!(None, graph.add_vertex(SimpleVertex::new(1, "a")));
267 /// assert_eq!(None, graph.add_vertex(SimpleVertex::new(2, "b")));
268 /// assert_eq!(Some(SimpleVertex::new(1, "a")), graph.add_vertex(SimpleVertex::new(1, "c")))
269 /// ```
270 fn add_vertex(&mut self, vertex: SimpleVertex<K, V>) -> Option<SimpleVertex<K, V>> {
271 if let Some(
272 AdjacencyList{
273 vertex: old_vertex,
274 list
275 }) = self.vertexes.remove(&vertex.key()) {
276
277 self.vertexes.insert(
278 vertex.key(),
279 AdjacencyList {
280 vertex,
281 list
282 });
283
284 Some(old_vertex)
285 } else {
286
287 self.vertexes.insert(
288 vertex.key(),
289 AdjacencyList {
290 vertex,
291 list: HashMap::new()
292 });
293
294 None
295 }
296 }
297
298 ///This method removes a vertex and its edges from the graph and returns None ore Some(old_vertex)
299 ///
300 /// # Examples
301 /// ```rust
302 /// use generic_graph::adjacency_list::AdjacencyGraph;
303 /// use generic_graph::{SimpleVertex, VariableVertexes};
304 /// let mut graph = AdjacencyGraph::<i32, &str, i32>::new();
305 /// graph.add_vertex(SimpleVertex::new(1, "a"));
306 /// graph.add_vertex(SimpleVertex::new(2, "b"));
307 ///
308 /// assert_eq!(None, graph.remove_vertex(0));
309 /// assert_eq!(Some(SimpleVertex::new(1, "a")), graph.remove_vertex(1));
310 /// assert_eq!(Some(SimpleVertex::new(2, "b")), graph.remove_vertex(2));
311 /// assert_eq!(None, graph.remove_vertex(1));
312 /// ```
313 fn remove_vertex(&mut self, key: K) -> Option<SimpleVertex<K, V>> {
314 for (from, adjacency) in &mut self.vertexes {
315 adjacency.list.remove(&DirectedEdge::<K, W>::generate_key((from, &key)));
316 }
317
318 if let Some(
319 AdjacencyList{
320 vertex: old_vertex,
321 list: _
322 }) = self.vertexes.remove(&key) {
323 Some(old_vertex)
324 } else {
325 None
326 }
327 }
328}
329
330///`AdjacencyGraph` uses HashMaps to store edges, allowing fast insertion and removal of the latter
331impl<K: Hash + Eq + Clone, V, W: Add + Sub + Eq + Ord + Copy> VariableEdges<
332 DirectedVertex<K, V>,
333 DirectedEdge<K, W>,
334 K, V, W,
335 CompoundKey<K>
336> for AdjacencyGraph<K, V, W>
337{
338
339 ///The `add_edge()` method shall return `Ok(None)` if the element was not previously set. Otherwise the element shall be updated (but no the key)
340 /// and the old element shall be returned as `Ok(Some(old_element))`. If one or both of the concerned vertexes are missing an error
341 /// containing an enum specifying which side is missing (`Err(EdgeSide)`)
342 ///
343 /// # Examples
344 /// ```rust
345 /// use generic_graph::adjacency_list::AdjacencyGraph;
346 /// use generic_graph::{SimpleVertex, VariableVertexes, VariableEdges};
347 /// use generic_graph::adjacency_list::elements::DirectedEdge;
348 /// use generic_graph::EdgeSide::Right;
349 /// let mut graph = AdjacencyGraph::new();
350 /// graph.add_vertex(SimpleVertex::new(1, "a"));
351 /// graph.add_vertex(SimpleVertex::new(2, "b"));
352 /// graph.add_vertex(SimpleVertex::new(3, "c"));
353 ///
354 /// assert_eq!(Ok(None), graph.add_edge(DirectedEdge::new(1, 2, 0)));
355 /// assert_eq!(Ok(None), graph.add_edge(DirectedEdge::new(2, 1, 0)));
356 /// assert_eq!(Ok(None), graph.add_edge(DirectedEdge::new(3, 2, 0)));
357 /// assert_eq!(
358 /// Ok(Some(DirectedEdge::new(1, 2, 0))),
359 /// graph.add_edge(DirectedEdge::new(1, 2, 3))
360 /// );
361 /// assert_eq!(Err(Right), graph.add_edge(DirectedEdge::new(1, 4, 0)));
362 /// ```
363 fn add_edge(&mut self, edge: DirectedEdge<K, W>) -> Result<Option<DirectedEdge<K, W>>, EdgeSide> {
364 if let Some(_) = self.vertexes.get(&edge.right()) {
365 if let Some(AdjacencyList {
366 vertex: _,
367 list
368 }) = self.vertexes.get_mut(&edge.left()) {
369
370 Ok(if let Some(old_edge) = list.remove(&edge.key()) {
371 list.insert(edge.key(), edge);
372 Some(old_edge)
373 } else {
374 list.insert(edge.key(), edge);
375 None
376 })
377
378 } else {
379 Err(EdgeSide::Left)
380 }
381 } else {
382
383 if let Some(_) = self.vertexes.get(&edge.left()){
384 Err(EdgeSide::Right)
385 } else {
386 Err(EdgeSide::Both)
387 }
388
389 }
390 }
391
392 ///The `remove_edge()` method shall return `None` if the element was not found, or `Some(element)` if it was found and removed.
393 ///
394 /// # Examples
395 /// ```rust
396 /// use generic_graph::adjacency_list::AdjacencyGraph;
397 /// use generic_graph::{SimpleVertex, VariableVertexes, VariableEdges};
398 /// use generic_graph::adjacency_list::elements::DirectedEdge;
399 /// use generic_graph::EdgeSide::Right;
400 /// let mut graph = AdjacencyGraph::new();
401 /// graph.add_vertex(SimpleVertex::new(1, "a"));
402 /// graph.add_vertex(SimpleVertex::new(2, "b"));
403 ///
404 /// graph.add_edge(DirectedEdge::new(1, 2, 3));
405 ///
406 /// assert_eq!(
407 /// Some(DirectedEdge::new(1, 2, 3)),
408 /// graph.remove_edge((&1, &2))
409 /// );
410 /// assert_eq!(None, graph.remove_edge((&1, &2)));
411 /// ```
412 fn remove_edge(&mut self, pair: (&K, &K)) -> Option<DirectedEdge<K, W>> {
413 if let Some(adjacency) = self.vertexes.get_mut(pair.0) {
414 adjacency.list.remove(&DirectedEdge::<K, W>::generate_key(pair))
415 } else {
416 None
417 }
418 }
419}
420
421#[cfg(test)]
422mod tests {
423 use super::*;
424 use crate::EdgeSide::*;
425
426 #[test]
427 fn add_remove_edge_all_cases() {
428 let mut graph = AdjacencyGraph::new();
429 graph.add_vertex(SimpleVertex::new(1, "a"));
430 graph.add_vertex(SimpleVertex::new(2, "b"));
431 graph.add_vertex(SimpleVertex::new(3, "c"));
432 graph.add_vertex(SimpleVertex::new(4, "d"));
433
434 assert_eq!(Ok(None), graph.add_edge(DirectedEdge::new(1, 2, 3)));
435 assert_eq!(Ok(None), graph.add_edge(DirectedEdge::new(2, 1, 3)));
436 assert_eq!(
437 Ok(Some(DirectedEdge::new(2,1, 3))),
438 graph.add_edge(DirectedEdge::new(2,1, 4))
439 );
440 assert_eq!(Err(Left), graph.add_edge(DirectedEdge::new(150, 2, 1)));
441 assert_eq!(Err(Right), graph.add_edge(DirectedEdge::new(3, 2000, 1)));
442 assert_eq!(Err(Both), graph.add_edge(DirectedEdge::new(48, 56, 1)));
443 }
444
445 #[test]
446 fn adjacency_neighboring() {
447 let mut graph = AdjacencyGraph::new();
448 graph.add_vertex(SimpleVertex::new(1, "a"));
449 graph.add_vertex(SimpleVertex::new(2, "b"));
450 graph.add_vertex(SimpleVertex::new(3, "c"));
451 graph.add_vertex(SimpleVertex::new(4, "d"));
452 graph.add_vertex(SimpleVertex::new(5, "e"));
453 graph.add_edge(DirectedEdge::new(1, 2, 3)).expect("Won't fail");
454 graph.add_edge(DirectedEdge::new(2, 1, 3)).expect("Won't fail");
455 graph.add_edge(DirectedEdge::new(2, 3, 3)).expect("Won't fail");
456 graph.add_edge(DirectedEdge::new(1, 3, 3)).expect("Won't fail");
457 graph.add_edge(DirectedEdge::new(4, 2, 3)).expect("Won't fail");
458
459 assert_eq!(true, graph.adjacent(&1, &3));
460 assert_eq!(false, graph.adjacent(&3, &1));
461 assert_eq!(false, graph.adjacent(&200, &300));
462 assert_eq!(Vec::<&i32>::new(), graph.neighbors(&5));
463 assert_eq!(Vec::<&i32>::new(), graph.leading_to(&5));
464 assert_eq!(Vec::<&i32>::new(), graph.neighbors(&6));
465 assert_eq!(Vec::<&i32>::new(), graph.leading_to(&6));
466
467 let mut neighbors = graph.neighbors(&2);
468 let mut leading_to = graph.leading_to(&2);
469 neighbors.sort();
470 leading_to.sort();
471 assert_eq!(neighbors, vec![&1,&3]);
472 assert_eq!(leading_to, vec![&1,&4]);
473
474 graph.add_vertex(SimpleVertex::new(2, "f"));
475 let mut neighbors = graph.neighbors(&2);
476 let mut leading_to = graph.leading_to(&2);
477 neighbors.sort();
478 leading_to.sort();
479 assert_eq!(neighbors, vec![&1,&3]);
480 assert_eq!(leading_to, vec![&1,&4]);
481 assert_eq!(Some(&SimpleVertex::new(2, "f")), graph.get_vertex(&2));
482 }
483
484 #[test]
485 fn mutable_getters() {
486 let mut graph = AdjacencyGraph::new();
487 graph.add_vertex(SimpleVertex::new(1, 4));
488 graph.add_vertex(SimpleVertex::new(2, 5));
489 graph.add_vertex(SimpleVertex::new(3, 6));
490 graph.add_edge(DirectedEdge::new(1, 2, 3)).expect("Won't fail");
491 graph.add_edge(DirectedEdge::new(2, 1, 3)).expect("Won't fail");
492
493 assert_eq!(None, graph.get_mut_vertex(&4));
494 assert_eq!(None, graph.get_mut_edge((&4, &4)));
495 assert_eq!(None, graph.get_mut_edge((&2, &3)));
496
497 let vertex = graph.get_mut_vertex(&2);
498 assert_eq!(Some(&mut SimpleVertex::new(2, 5)), vertex);
499 let vertex = vertex.unwrap();
500 *vertex.get_mut_value() += 1;
501 assert_eq!(Some(&SimpleVertex::new(2, 6)), graph.get_vertex(&2));
502
503 let edge = graph.get_mut_edge((&1, &2));
504 assert_eq!(Some(&mut DirectedEdge::new(1,2, 3)), edge);
505 let edge = edge.unwrap();
506 edge.set_weight(12);
507 assert_eq!(Some(&DirectedEdge::new(1,2, 12)), graph.get_edge((&1, &2)));
508 }
509}