capability_skeleton/
build_node_level_map.rs

1// ---------------- [ File: capability-skeleton/src/build_node_level_map.rs ]
2crate::ix!();
3
4/// A local BFS returning node_id => level, skipping unconnected nodes.
5#[instrument(level = "trace", skip(skel))]
6pub fn build_node_level_map(skel: &Skeleton) -> HashMap<u16, u8> {
7    trace!("Building node->level map with BFS for Skeleton.");
8
9    let mut visited = HashSet::new();
10    let mut map = HashMap::<u16, u8>::new();
11    let mut queue = VecDeque::new();
12
13    if let Some(rid) = skel.root_id() {
14        // rid is a u16, so we can push it directly with level=0
15        queue.push_back((*rid, 0u8));
16    } else {
17        debug!("No root => empty map");
18        return map;
19    }
20
21    while let Some((nid, lvl)) = queue.pop_front() {
22        // If we’ve visited nid before, skip
23        if !visited.insert(nid) {
24            continue;
25        }
26        // Insert into the map
27        map.insert(nid, lvl);
28
29        // Find the node with ID == nid
30        if let Some(node) = skel.nodes().iter().find(|n| n.id() == nid) {
31            // For each child, push => BFS
32            for &child_id in node.child_ids() {
33                let next_lvl = lvl.saturating_add(1);
34                queue.push_back((child_id, next_lvl));
35            }
36        }
37    }
38
39    trace!("Finished BFS => discovered {} connected nodes", map.len());
40    map
41}
42
43#[cfg(test)]
44mod build_node_level_map_assessment {
45    use super::*;
46
47    fn make_node(id: u16, child_ids: &[u16]) -> SkeletonNode {
48        let k = if child_ids.is_empty() {
49            NodeKind::LeafHolder
50        } else {
51            NodeKind::Dispatch
52        };
53        SkeletonNodeBuilder::default()
54            .id(id)
55            .child_ids(child_ids.to_vec())
56            .name(format!("Node_{id}"))
57            .original_key(format!("Node_{id}"))
58            .build(k)
59            .unwrap()
60    }
61
62    #[traced_test]
63    fn check_empty_skeleton() {
64        let skel = SkeletonBuilder::default().build().unwrap();
65        let map = build_node_level_map(&skel);
66        assert!(map.is_empty());
67    }
68
69    #[traced_test]
70    fn check_single_node() {
71        let node0 = make_node(0, &[]);
72        let skel = SkeletonBuilder::default()
73            .nodes(vec![node0])
74            .root_id(Some(0))
75            .build()
76            .unwrap();
77        let map = build_node_level_map(&skel);
78        assert_eq!(map.len(), 1);
79        assert_eq!(map.get(&0), Some(&0u8));
80    }
81
82    #[traced_test]
83    fn check_linear_chain() {
84        let n0 = make_node(0, &[1]);
85        let n1 = make_node(1, &[2]);
86        let n2 = make_node(2, &[]);
87        let skel = SkeletonBuilder::default()
88            .nodes(vec![n0, n1, n2])
89            .root_id(Some(0))
90            .build()
91            .unwrap();
92        let map = build_node_level_map(&skel);
93        assert_eq!(map.get(&0), Some(&0u8));
94        assert_eq!(map.get(&1), Some(&1u8));
95        assert_eq!(map.get(&2), Some(&2u8));
96        assert_eq!(map.len(), 3);
97    }
98
99    #[traced_test]
100    fn check_branching() {
101        let n0 = make_node(0, &[1,2]);
102        let n1 = make_node(1, &[3]);
103        let n2 = make_node(2, &[]);
104        let n3 = make_node(3, &[]);
105        let skel = SkeletonBuilder::default()
106            .nodes(vec![n0,n1,n2,n3])
107            .root_id(Some(0))
108            .build()
109            .unwrap();
110        let map = build_node_level_map(&skel);
111        assert_eq!(map.get(&0), Some(&0u8));
112        assert_eq!(map.get(&1), Some(&1u8));
113        assert_eq!(map.get(&2), Some(&1u8));
114        assert_eq!(map.get(&3), Some(&2u8));
115    }
116
117    #[traced_test]
118    fn check_unconnected_nodes() {
119        // root=0 => BFS sees 0,1 => doesn't see 2,3
120        let n0 = make_node(0, &[1]);
121        let n1 = make_node(1, &[]);
122        let n2 = make_node(2, &[3]);
123        let n3 = make_node(3, &[]);
124        let skel = SkeletonBuilder::default()
125            .nodes(vec![n0,n1,n2,n3])
126            .root_id(Some(0))
127            .build()
128            .unwrap();
129
130        let map = build_node_level_map(&skel);
131        assert_eq!(map.len(), 2);
132        assert_eq!(map.get(&0), Some(&0u8));
133        assert_eq!(map.get(&1), Some(&1u8));
134    }
135
136    #[traced_test]
137    fn check_cycle_doesnt_loop() {
138        // 0->1, 1->0
139        let n0 = make_node(0, &[1]);
140        let n1 = make_node(1, &[0]);
141        let skel = SkeletonBuilder::default()
142            .nodes(vec![n0,n1])
143            .root_id(Some(0))
144            .build()
145            .unwrap();
146
147        let map = build_node_level_map(&skel);
148        assert_eq!(map.len(), 2);
149        assert_eq!(map.get(&0), Some(&0u8));
150        assert_eq!(map.get(&1), Some(&1u8));
151    }
152}
capability_skeleton/build_node_level_map.rs

capability_skeleton/
build_node_level_map.rs
