clm-kernel 0.0.24

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Layer 2: Shared Content-Graph Reachability Traversal (Sprint 630, INV-630)
//! Canonical Path: kernel/clm_rust_core/src/layer2/traversal.rs

use std::collections::{HashSet, VecDeque};
use std::hash::Hash;

/// Deterministic BFS reachability from `roots`, returning visited nodes in discovery order.
pub fn reachable_from<N, I, S, Out>(roots: I, mut successors: S) -> Vec<N>
where
    N: Clone + Eq + Hash,
    I: IntoIterator<Item = N>,
    S: FnMut(&N) -> Out,
    Out: IntoIterator<Item = N>,
{
    reachable_from_with_edges(roots, |node| successors(node).into_iter().map(|next| (next, ()))).0
}

/// Deterministic BFS reachability collecting both visited nodes and every incident edge
/// emitted when each reachable node is expanded once (preserving diamond and parallel edges).
pub fn reachable_from_with_edges<N, E, I, S, Out>(roots: I, mut incident: S) -> (Vec<N>, Vec<E>)
where
    N: Clone + Eq + Hash,
    I: IntoIterator<Item = N>,
    S: FnMut(&N) -> Out,
    Out: IntoIterator<Item = (N, E)>,
{
    let mut visited = HashSet::new();
    let mut order = Vec::new();
    let mut edges = Vec::new();
    let mut queue: VecDeque<N> = roots.into_iter().collect();

    while let Some(curr) = queue.pop_front() {
        if !visited.insert(curr.clone()) {
            continue;
        }
        order.push(curr.clone());
        for (next, edge) in incident(&curr) {
            edges.push(edge);
            if !visited.contains(&next) {
                queue.push_back(next);
            }
        }
    }

    (order, edges)
}

#[cfg(test)]
mod tests {
    use super::{reachable_from, reachable_from_with_edges};

    #[test]
    fn traversal_multi_root_and_cycles_are_deterministic() {
        let edges: &[(&str, &str)] = &[("r1", "a"), ("a", "r1"), ("r2", "b"), ("a", "b")];
        let got = reachable_from(["r1", "r2"], |n| {
            edges.iter().filter(|(s, _)| s == n).map(|(_, t)| *t).collect::<Vec<_>>()
        });
        assert_eq!(got, vec!["r1", "r2", "a", "b"]);
    }

    #[test]
    fn traversal_collects_diamond_and_parallel_edges_once_per_node() {
        let graph: &[(&str, &str, &str)] = &[
            ("out", "mid1", "left"),
            ("out", "mid2", "right"),
            ("mid1", "root", "e1"),
            ("mid2", "root", "e2"),
            ("mid2", "root", "e2_alt"),
        ];
        let (nodes, collected) = reachable_from_with_edges(["out"], |n| {
            graph
                .iter()
                .filter(|(src, _, _)| src == n)
                .map(|(_, dst, lbl)| (*dst, *lbl))
                .collect::<Vec<_>>()
        });
        assert_eq!(nodes, vec!["out", "mid1", "mid2", "root"]);
        assert_eq!(collected, vec!["left", "right", "e1", "e2", "e2_alt"]);
    }
}