Skip to main content

ifc_model/traverse/
bfs.rs

1//! Bounded breadth-first walk.
2//!
3//! Breadth-first is the right default for a containment tree: it yields a
4//! storey's own elements before descending into nested spaces, which is the
5//! order a consumer building a level-by-level view wants.
6
7use std::collections::VecDeque;
8
9use ahash::AHashSet;
10
11use super::budget::{Budget, Stop, Walk};
12use crate::value::EntityId;
13
14/// Walk breadth-first from `start`, following `successors`.
15///
16/// See [`super::dfs::depth_first`] for why successors are supplied by the
17/// caller rather than derived here.
18pub 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}