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
use crate::graph::Graph;
use crate::vertex_id::VertexId;
use std::collections::VecDeque;
use std::sync::Arc;
#[derive(Debug)]
pub struct Bfs<'a, T> {
queue: VecDeque<Arc<VertexId>>,
current_ptr: Option<Arc<VertexId>>,
visited_stack: Vec<Arc<VertexId>>,
roots_stack: Vec<Arc<VertexId>>,
iterable: &'a Graph<T>,
}
impl<'a, T> Bfs<'a, T> {
pub fn new(graph: &'a Graph<T>) -> Bfs<'_, T> {
let mut roots_stack = Vec::with_capacity(graph.roots_count());
for v in graph.roots() {
roots_stack.push(Arc::from(*v));
}
let current_ptr = roots_stack.pop();
Bfs {
queue: VecDeque::with_capacity(graph.vertex_count()),
current_ptr,
visited_stack: Vec::with_capacity(graph.vertex_count()),
roots_stack,
iterable: graph,
}
}
}
impl<'a, T> Iterator for Bfs<'a, T> {
type Item = &'a VertexId;
fn next(&mut self) -> Option<Self::Item> {
loop {
let mut next_ptr = None;
if let Some(current_ptr) = &self.current_ptr {
if !self.visited_stack.iter().any(|o| **o == **current_ptr) {
self.visited_stack.push(current_ptr.clone());
return self.iterable.fetch_id_ref(current_ptr.as_ref());
}
for n in self.iterable.out_neighbors(current_ptr.as_ref()) {
if !self.visited_stack.iter().any(|o| **o == *n) {
self.visited_stack.push(Arc::from(*n));
self.queue.push_back(Arc::from(*n));
return self.iterable.fetch_id_ref(n);
}
}
if self.queue.is_empty() {
if let Some(next_root) = self.roots_stack.pop() {
next_ptr = Some(next_root.clone());
} else {
return None;
}
} else {
next_ptr = self.queue.pop_front();
}
} else {
return None;
}
if next_ptr.is_some() {
self.current_ptr = next_ptr;
}
}
}
}