capability_skeleton/
tree_configuration_complexity_measurer.rs

1// ---------------- [ File: capability-skeleton/src/tree_configuration_complexity_measurer.rs ]
2crate::ix!();
3
4impl TreeConfigurationComplexityMeasurer for Skeleton {
5    #[instrument(level = "trace", skip(self))]
6    fn measure_tree_configuration_complexity(&self) -> Option<DetectedTreeConfigurationComplexity> {
7        let nodes = self.nodes();
8        let n = nodes.len();
9        if n < 2 {
10            return None;
11        }
12
13        let branching: Vec<&SkeletonNode> = nodes
14            .iter()
15            .filter(|n| n.child_ids().len() >= 2)
16            .collect();
17
18        if branching.is_empty() {
19            return Some(DetectedTreeConfigurationComplexity::Linear);
20        }
21
22        if branching.len() == 1 {
23            let b = branching[0];
24            let c = b.child_ids().len();
25            if c == n - 1 {
26                return Some(DetectedTreeConfigurationComplexity::Star);
27            }
28        }
29
30        if let Some(sym) = self.measure_tree_balance_symmetry() {
31            if (sym - 1.0).abs() < f32::EPSILON {
32                return Some(DetectedTreeConfigurationComplexity::Balanced);
33            }
34        }
35        Some(DetectedTreeConfigurationComplexity::Complex)
36    }
37}
38
39#[cfg(test)]
40mod skeleton_configuration_complexity_measurer_assessment {
41    use super::*;
42
43    #[traced_test]
44    fn empty_skeleton_returns_none() {
45        let skel = SkeletonBuilder::default().build().unwrap();
46        assert_eq!(skel.measure_tree_configuration_complexity(), None);
47    }
48
49    #[traced_test]
50    fn single_node_returns_none() {
51        let node = SkeletonNodeBuilder::default()
52            .id(0_u16)
53            .name("solo")
54            .original_key("solo")
55            .build(NodeKind::LeafHolder)
56            .unwrap();
57
58        let skel = SkeletonBuilder::default()
59            .nodes(vec![node]).root_id(Some(0)).build().unwrap();
60        assert_eq!(skel.measure_tree_configuration_complexity(), None);
61    }
62
63    #[traced_test]
64    fn linear_chain_returns_linear() {
65        // 0->1->2
66        // We do `.build(NodeKind::Dispatch)` if child_ids is not empty, otherwise LeafHolder
67        let n0 = SkeletonNodeBuilder::default()
68            .id(0).child_ids(vec![1])
69            .name("n0").original_key("n0")
70            .build(NodeKind::Dispatch)
71            .unwrap();
72        let n1 = SkeletonNodeBuilder::default()
73            .id(1).child_ids(vec![2])
74            .name("n1").original_key("n1")
75            .build(NodeKind::Dispatch)
76            .unwrap();
77        let n2 = SkeletonNodeBuilder::default()
78            .id(2).name("n2").original_key("n2")
79            .build(NodeKind::LeafHolder)
80            .unwrap();
81
82        let skel = SkeletonBuilder::default()
83            .nodes(vec![n0,n1,n2])
84            .root_id(Some(0)).build().unwrap();
85
86        assert_eq!(
87            skel.measure_tree_configuration_complexity(),
88            Some(DetectedTreeConfigurationComplexity::Linear)
89        );
90    }
91
92    #[traced_test]
93    fn star_tree_returns_star() {
94        // 0->(1,2,3)
95        let children = vec![1,2,3];
96        let n0 = SkeletonNodeBuilder::default()
97            .id(0_u16).child_ids(children.clone())
98            .name("root").original_key("root")
99            .build(NodeKind::Dispatch)
100            .unwrap();
101
102        let mut nodes = vec![n0];
103        for i in children {
104            let leaf = SkeletonNodeBuilder::default()
105                .id(i)
106                .name(format!("n{}", i))
107                .original_key(format!("n{}", i))
108                .build(NodeKind::LeafHolder)
109                .unwrap();
110            nodes.push(leaf);
111        }
112        let skel = SkeletonBuilder::default().nodes(nodes).root_id(Some(0)).build().unwrap();
113        assert_eq!(
114            skel.measure_tree_configuration_complexity(),
115            Some(DetectedTreeConfigurationComplexity::Star)
116        );
117    }
118
119    #[traced_test]
120    fn perfect_binary_is_balanced() {
121        // 0->(1,2), 1->(3,4), 2->(5,6), 3->[],4->[],5->[],6->[]
122        fn make(id: u16, kids: Vec<u16>) -> SkeletonNode {
123            let k = if kids.is_empty() {
124                NodeKind::LeafHolder
125            } else {
126                NodeKind::Dispatch
127            };
128            SkeletonNodeBuilder::default()
129                .id(id).child_ids(kids)
130                .name(format!("n{}", id))
131                .original_key(format!("n{}", id))
132                .build(k)
133                .unwrap()
134        }
135
136        let mut nodes = Vec::new();
137        let n1 = make(1, vec![3,4]);
138        let n2 = make(2, vec![5,6]);
139        let n0 = make(0, vec![1,2]);
140        nodes.push(n0); nodes.push(n1); nodes.push(n2);
141        for i in 3..=6 {
142            nodes.push(make(i, vec![]));
143        }
144        let skel = SkeletonBuilder::default().nodes(nodes).root_id(Some(0)).build().unwrap();
145
146        assert_eq!(
147            skel.measure_tree_configuration_complexity(),
148            Some(DetectedTreeConfigurationComplexity::Balanced)
149        );
150    }
151
152    #[traced_test]
153    fn irregular_tree_is_complex() {
154        // 0->(1,2,3), 1->(4), 2->(), 3->(5,6), 5->(7), 4->(),6->(),7->()
155        fn mk(id: u16, kids: Vec<u16>) -> SkeletonNode {
156            let k = if kids.is_empty() {
157                NodeKind::LeafHolder
158            } else {
159                NodeKind::Dispatch
160            };
161            SkeletonNodeBuilder::default()
162                .id(id).child_ids(kids)
163                .name(format!("n{}",id))
164                .original_key(format!("n{}",id))
165                .build(k)
166                .unwrap()
167        }
168        let n0 = mk(0, vec![1,2,3]);
169        let n1 = mk(1, vec![4]);
170        let n2 = mk(2, vec![]);
171        let n3 = mk(3, vec![5,6]);
172        let n4 = mk(4, vec![]);
173        let n5 = mk(5, vec![7]);
174        let n6 = mk(6, vec![]);
175        let n7 = mk(7, vec![]);
176        let skel = SkeletonBuilder::default()
177            .nodes(vec![n0,n1,n2,n3,n4,n5,n6,n7])
178            .root_id(Some(0))
179            .build()
180            .unwrap();
181
182        assert_eq!(
183            skel.measure_tree_configuration_complexity(),
184            Some(DetectedTreeConfigurationComplexity::Complex)
185        );
186    }
187}
capability_skeleton/tree_configuration_complexity_measurer.rs

capability_skeleton/
tree_configuration_complexity_measurer.rs
