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
use crate::graph::Graph;
use crate::vertex_id::VertexId;
use hashbrown::HashSet;
#[cfg(not(feature = "no_std"))]
use std::collections::VecDeque;
#[cfg(feature = "no_std")]
extern crate alloc;
#[cfg(feature = "no_std")]
use alloc::{collections::vec_deque::VecDeque};
#[cfg(feature = "no_std")]
use alloc::vec::Vec;
#[derive(Debug)]
pub struct Bfs<'a, T> {
queue: VecDeque<VertexId>,
current_ptr: Option<VertexId>,
visited_set: HashSet<VertexId>,
roots_stack: Vec<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(v.clone());
}
let current_ptr = roots_stack.pop();
Bfs {
queue: VecDeque::with_capacity(graph.vertex_count()),
current_ptr,
visited_set: HashSet::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_set.contains(current_ptr) {
self.visited_set.insert(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_set.contains(n) {
self.visited_set.insert(n.clone());
self.queue.push_back(n.clone());
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;
}
}
}
}