1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
use crate::{AnyGraph, Key, Kinship, Value, Vertex};
use std::collections::{HashSet, VecDeque};
pub trait Algorithms<K, V>: AnyGraph<K, V> + Kinship<K, V>
where
K: Key,
V: Value,
{
fn bfs(&self) -> Option<Self> {
return if self.vertices().is_empty() {
None
} else {
let first = self.vertices().first().unwrap().clone();
self.bfs_with_starting_vertex(&first)
};
}
fn bfs_with_starting_vertex(&self, starting_vertex: &Vertex<K, V>) -> Option<Self> {
if !self.vertices().contains(starting_vertex) {
return None;
}
let cloned_graph = self.clone();
let mut queue: VecDeque<K> = VecDeque::new();
queue.push_back(starting_vertex.key().clone());
return if let Some((mut new_graph, _)) = cloned_graph.remove_all_edges() {
let successors = cloned_graph.successors_as_key_and_edges();
let mut flagged: HashSet<K> = HashSet::new();
flagged.insert(starting_vertex.key().clone());
while !queue.is_empty() {
let current = queue.pop_front().unwrap();
let neighbours = successors.get(¤t).unwrap();
for neighbour in neighbours {
if !flagged.contains(neighbour.to()) {
new_graph = new_graph.add_edge(*neighbour).unwrap();
flagged.insert(neighbour.to().clone());
queue.push_back(neighbour.to().clone());
}
}
}
Some(new_graph)
} else {
return None;
};
}
fn dfs(&self) -> Option<Self> {
return if self.vertices().is_empty() {
None
} else {
let first = self.vertices().first().unwrap().clone();
self.dfs_with_starting_vertex(&first)
};
}
fn dfs_with_starting_vertex(&self, starting_vertex: &Vertex<K, V>) -> Option<Self> {
if !self.vertices().contains(starting_vertex) {
return None;
}
let cloned_graph = self.clone();
let mut stack: VecDeque<K> = VecDeque::new();
stack.push_back(starting_vertex.key().clone());
return if let Some((mut new_graph, _)) = cloned_graph.remove_all_edges() {
let successors = cloned_graph.successors_as_key_and_edges();
let mut flagged: HashSet<K> = HashSet::new();
flagged.insert(starting_vertex.key().clone());
while !stack.is_empty() {
let current = stack.pop_back().unwrap();
let neighbours = successors.get(¤t).unwrap();
for neighbour in neighbours {
if !flagged.contains(neighbour.to()) {
new_graph = new_graph.add_edge(*neighbour).unwrap();
flagged.insert(neighbour.to().clone());
stack.push_back(neighbour.to().clone());
}
}
}
Some(new_graph)
} else {
return None;
};
}
}