ifc_model/traverse/
bfs.rs1use std::collections::VecDeque;
8
9use ahash::AHashSet;
10
11use super::budget::{Budget, Stop, Walk};
12use crate::value::EntityId;
13
14pub fn breadth_first(
19 start: EntityId,
20 budget: Budget,
21 mut successors: impl FnMut(EntityId) -> Vec<EntityId>,
22) -> Walk {
23 let mut visited = Vec::new();
24 let mut seen = AHashSet::new();
25 let mut revisited = Vec::new();
26 let mut queue = VecDeque::from([(start, 0usize)]);
27 let mut stop = Stop::Exhausted;
28
29 while let Some((node, depth)) = queue.pop_front() {
30 if !seen.insert(node) {
31 revisited.push(node);
32 continue;
33 }
34 if visited.len() >= budget.max_nodes {
35 stop = Stop::NodeLimit;
36 break;
37 }
38 visited.push(node);
39
40 if depth >= budget.max_depth {
41 stop = Stop::DepthLimit;
42 continue;
43 }
44 for successor in successors(node) {
45 queue.push_back((successor, depth + 1));
46 }
47 }
48
49 revisited.sort_unstable();
50 revisited.dedup();
51 Walk {
52 visited,
53 stop,
54 revisited,
55 }
56}