capability_skeleton/

tree_balance_symmetry_measurer.rs

// ---------------- [ File: capability-skeleton/src/tree_balance_symmetry_measurer.rs ]
crate::ix!();

impl TreeBalanceSymmetryMeasurer for Skeleton {

    #[instrument(level = "trace", skip(self))]
    fn measure_tree_balance_symmetry(&self) -> Option<f32> {
        use std::collections::HashSet;

        /// Count the number of *structural* leaves under `start_id`, but:
        /// - if we ever revisit a node → we’ve detected a cycle and return 0
        /// - if a child_id isn’t found in `self.nodes()` → we treat it as one leaf
        fn count_leaves(skel: &Skeleton, start_id: u16) -> usize {
            let mut visited = HashSet::new();
            let mut stack = vec![start_id];
            let mut leaf_count = 0;
            let mut cycle_seen = false;

            while let Some(nid) = stack.pop() {
                // cycle detection
                if !visited.insert(nid) {
                    cycle_seen = true;
                    continue;
                }
                // try find the node
                if let Some(node) = skel.nodes().iter().find(|n| n.id() == nid) {
                    let kids = node.child_ids();
                    if kids.is_empty() {
                        // a real structural leaf
                        leaf_count += 1;
                    } else {
                        // traverse its children
                        for &cid in kids {
                            stack.push(cid);
                        }
                    }
                } else {
                    // invalid child reference = treat as one leaf
                    leaf_count += 1;
                }
            }

            if cycle_seen { 0 } else { leaf_count }
        }

        let mut ratios = Vec::new();
        for node in self.nodes() {
            let kids = node.child_ids();
            if kids.len() < 2 { continue; }
            // collect leaf‐counts per child‐subtree
            let mut counts = Vec::with_capacity(kids.len());
            for &cid in kids {
                counts.push(count_leaves(self, cid) as f32);
            }
            let max = counts.iter().cloned().fold(f32::NEG_INFINITY, f32::max);
            if max == 0.0 { continue; }
            let min = counts.iter().cloned().fold(f32::INFINITY, f32::min);
            ratios.push(min / max);
        }

        if ratios.is_empty() {
            None
        } else {
            Some(ratios.iter().sum::<f32>() / (ratios.len() as f32))
        }
    }
}

#[cfg(test)]
mod skeleton_balance_symmetry_measurer_assessment {
    use super::*;

    #[traced_test]
    fn empty_skeleton_returns_none() {
        let skel = SkeletonBuilder::default().build().unwrap();
        assert!(skel.measure_tree_balance_symmetry().is_none());
    }

    #[traced_test]
    fn single_node_returns_none() {
        let node = SkeletonNodeBuilder::default()
            .id(0_u16)
            .name("solo")
            .original_key("solo")
            .build(NodeKind::LeafHolder)
            .unwrap();
        let skel = SkeletonBuilder::default()
            .nodes(vec![node])
            .root_id(Some(0))
            .build()
            .unwrap();
        assert!(skel.measure_tree_balance_symmetry().is_none());
    }

    #[traced_test]
    fn linear_chain_returns_none() {
        // 0->1->2 : no node has >=2 children
        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16).child_ids(vec![1])
            .name("n0").original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();
        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16).child_ids(vec![2])
            .name("n1").original_key("n1")
            .build(NodeKind::Dispatch)
            .unwrap();
        let n2 = SkeletonNodeBuilder::default()
            .id(2_u16)
            .name("n2").original_key("n2")
            .build(NodeKind::LeafHolder)
            .unwrap();
        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2])
            .root_id(Some(0))
            .build().unwrap();
        assert!(skel.measure_tree_balance_symmetry().is_none());
    }

    #[traced_test]
    fn perfectly_balanced_binary_tree_returns_one() {
        //      0
        //     / \
        //    1   2
        //   /\   /\
        //  3 4  5 6

        // We'll define a helper that picks Dispatch if child_ids non-empty, else LeafHolder:
        fn children(id: u16, kids: Vec<u16>, use_aggregate: bool) -> SkeletonNode {
            // If `use_aggregate` is true, we do NodeKind::Aggregate, else NodeKind::Dispatch
            let kind = if kids.is_empty() {
                NodeKind::LeafHolder
            } else if use_aggregate {
                NodeKind::Aggregate
            } else {
                NodeKind::Dispatch
            };
            SkeletonNodeBuilder::default()
                .id(id)
                .child_ids(kids)
                .name(format!("n{}", id))
                .original_key(format!("n{}", id))
                .build(kind)
                .unwrap()
        }

        let n3 = children(3, vec![], false);
        let n4 = children(4, vec![], false);
        let n5 = children(5, vec![], false);
        let n6 = children(6, vec![], false);
        let n1 = children(1, vec![3,4], false);   // dispatch
        let n2 = children(2, vec![5,6], true);    // let's pick aggregator for variety
        let n0 = children(0, vec![1,2], false);   // dispatch

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2,n3,n4,n5,n6])
            .root_id(Some(0))
            .build().unwrap();

        let sym = skel.measure_tree_balance_symmetry().unwrap();
        assert!((sym - 1.0).abs() < f32::EPSILON);
    }

    #[traced_test]
    fn unbalanced_tree_returns_fraction() {
        //  0
        // / \
        //1   2
        //|   /|\
        //3  4,5,6
        //
        // Branching nodes:
        //  • Node 0 → leaves-under-1 = 1, leaves-under-2 = 3 ⇒ ratio = 1/3
        //  • Node 2 → children 4,5,6 are all true leaves ⇒ min/max = 1/1 ⇒ 1.0
        // average = (1/3 + 1.0)/2 ≈ 0.6666667

        fn make(id: u16, kids: Vec<u16>, use_agg: bool) -> SkeletonNode {
            let k = if kids.is_empty() {
                NodeKind::LeafHolder
            } else if use_agg {
                NodeKind::Aggregate
            } else {
                NodeKind::Dispatch
            };
            SkeletonNodeBuilder::default()
                .id(id)
                .child_ids(kids)
                .name(format!("n{}", id))
                .original_key(format!("n{}", id))
                .build(k)
                .unwrap()
        }

        let n3 = make(3, vec![], false);
        let n1 = make(1, vec![3], false);
        let n4 = make(4, vec![], false);
        let n5 = make(5, vec![], false);
        let n6 = make(6, vec![], false);
        let n2 = make(2, vec![4,5,6], true); // aggregator
        let n0 = make(0, vec![1,2], false);  // dispatch

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2,n3,n4,n5,n6])
            .root_id(Some(0))
            .build().unwrap();

        let sym = skel.measure_tree_balance_symmetry().unwrap();
        let expected = (1.0/3.0 + 1.0) / 2.0;
        assert!((sym - expected).abs() < 1e-6);
    }

    #[traced_test]
    fn multiple_branching_nodes_average_correctly() {
        // Now *all* branching nodes count:
        //  • Node 0 → children 1 (2 leaves) & 2 (4 leaves) ⇒ 2/4 = 0.5
        //  • Node 1 → children 3,4 both leaves ⇒ 1/1 = 1.0
        //  • Node 2 → children 5,6,7,8 all leaves ⇒ 1/1 = 1.0
        // average = (0.5 + 1.0 + 1.0) / 3 = 0.8333333…

        fn mk(id: u16, kids: Vec<u16>, agg: bool) -> SkeletonNode {
            let k = if kids.is_empty() {
                NodeKind::LeafHolder
            } else if agg {
                NodeKind::Aggregate
            } else {
                NodeKind::Dispatch
            };
            SkeletonNodeBuilder::default()
                .id(id)
                .child_ids(kids)
                .name(format!("n{}", id))
                .original_key(format!("n{}", id))
                .build(k)
                .unwrap()
        }
        let leaves = |id: u16| mk(id, vec![], false);

        let n5 = leaves(5);
        let n6 = leaves(6);
        let n7 = leaves(7);
        let n8 = leaves(8);

        let n2 = mk(2, vec![5,6,7,8], true);  // aggregator
        let n3 = leaves(3);
        let n4 = leaves(4);
        let n1 = mk(1, vec![3,4], false);     // dispatch
        let n0 = mk(0, vec![1,2], false);

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2,n3,n4,n5,n6,n7,n8])
            .root_id(Some(0))
            .build().unwrap();

        let sym = skel.measure_tree_balance_symmetry().unwrap();
        let expected = (0.5 + 1.0 + 1.0) / 3.0;
        assert!((sym - expected).abs() < 1e-6);
    }

    #[traced_test]
    fn cycles_do_not_infinite_loop_and_are_ignored() {
        // 0→1, 1→0, 0→2, 2→()
        // Node 0 has children [1,2].  Subtrees:
        //   via 1: cycle -> 0 leaves
        //   via 2: 1 leaf => ratio=0

        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16).child_ids(vec![1,2])
            .name("n0").original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();
        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16).child_ids(vec![0])
            .name("n1").original_key("n1")
            .build(NodeKind::Dispatch)
            .unwrap();
        let n2 = SkeletonNodeBuilder::default()
            .id(2_u16).child_ids(vec![])
            .name("n2").original_key("n2")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2])
            .root_id(Some(0))
            .build().unwrap();

        let sym = skel.measure_tree_balance_symmetry().unwrap();
        assert!((sym - 0.0).abs() < 1e-6);
    }

    #[traced_test]
    fn invalid_children_are_skipped() {
        // 0→[1,99], 1→() => child=99 is invalid => ratio=1

        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16).child_ids(vec![1,99])
            .name("n0").original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();
        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16).child_ids(vec![])
            .name("n1").original_key("n1")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1])
            .root_id(Some(0))
            .build().unwrap();

        let sym = skel.measure_tree_balance_symmetry().unwrap();
        assert!((sym - 1.0).abs() < 1e-6);
    }
}