coreason_runtime_rust/execution_plane/

blast_radius.rs

// Copyright (c) 2026 CoReason, Inc.
// All rights reserved.

//! Defeasible Cascade Blast Radius Calculator (#336).
//!
//! Replaces `coreason_runtime/execution_plane/blast_radius.py`.
//!
//! Computes the propagation blast radius when a belief node is defeated
//! in the epistemic knowledge graph. Tracks cascade depth and affected
//! nodes for rollback planning.
//!
//! Zero Waste: Delegates all graph traversal to `petgraph` (OSS).
//! We only write the domain-specific defeasibility scoring logic.

use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::visit::{Bfs, Reversed};
use serde::{Deserialize, Serialize};
use std::collections::HashMap;

/// Result of a blast radius computation.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CascadeResult {
    pub defeated_node: String,
    pub affected_nodes: Vec<String>,
    pub cascade_depth: u32,
    pub defeasibility_scores: HashMap<String, f64>,
    pub total_affected: usize,
}

/// Internal graph wrapper that builds a `petgraph::DiGraph` from an adjacency list.
///
/// We keep this thin: the graph construction is our glue code,
/// all traversal is delegated to petgraph's BFS/DFS implementations.
struct EpistemicGraph<'a> {
    graph: DiGraph<&'a str, ()>,
    node_map: HashMap<&'a str, NodeIndex>,
}

impl<'a> EpistemicGraph<'a> {
    /// Build from adjacency list. O(V + E).
    fn from_adjacency(adjacency: &'a HashMap<String, Vec<String>>) -> Self {
        let mut graph = DiGraph::<&'a str, ()>::new();
        let mut node_map: HashMap<&'a str, NodeIndex> = HashMap::new();

        // Collect all unique nodes
        for (parent, children) in adjacency {
            node_map
                .entry(parent.as_str())
                .or_insert_with(|| graph.add_node(parent.as_str()));
            for child in children {
                node_map
                    .entry(child.as_str())
                    .or_insert_with(|| graph.add_node(child.as_str()));
            }
        }

        // Add edges
        for (parent, children) in adjacency {
            let &parent_idx = node_map.get(parent.as_str()).unwrap();
            for child in children {
                let &child_idx = node_map.get(child.as_str()).unwrap();
                graph.add_edge(parent_idx, child_idx, ());
            }
        }

        Self { graph, node_map }
    }

    /// Return a reversed view of the graph (swapped edge directions).
    /// Uses petgraph's zero-cost `Reversed` wrapper — no data is copied.
    fn reversed_view(&self) -> Reversed<&DiGraph<&'a str, ()>> {
        Reversed(&self.graph)
    }
}

/// Computes belief invalidation cascades in a knowledge graph (#336).
///
/// When a belief node is defeated (e.g., new evidence contradicts it),
/// all downstream nodes that depend on it may also be invalidated.
/// This calculator delegates BFS traversal to `petgraph`.
pub struct BlastRadiusCalculator;

impl BlastRadiusCalculator {
    /// Compute the blast radius of defeating a node.
    ///
    /// Uses `petgraph::visit::Bfs` for the forward reachability traversal,
    /// then applies domain-specific defeasibility decay scoring.
    pub fn calculate_blast_radius(
        defeated_node_cid: &str,
        adjacency: &HashMap<String, Vec<String>>,
    ) -> CascadeResult {
        let eg = EpistemicGraph::from_adjacency(adjacency);

        let start_idx = match eg.node_map.get(defeated_node_cid) {
            Some(&idx) => idx,
            None => {
                return CascadeResult {
                    defeated_node: defeated_node_cid.to_string(),
                    affected_nodes: Vec::new(),
                    cascade_depth: 0,
                    defeasibility_scores: HashMap::new(),
                    total_affected: 0,
                };
            }
        };

        // Use petgraph's BFS to discover all reachable nodes
        let mut bfs = Bfs::new(&eg.graph, start_idx);
        let mut depth_map: HashMap<NodeIndex, u32> = HashMap::new();
        depth_map.insert(start_idx, 0);

        let mut affected: Vec<String> = Vec::new();
        let mut defeasibility: HashMap<String, f64> = HashMap::new();
        let mut max_depth: u32 = 0;

        while let Some(node_idx) = bfs.next(&eg.graph) {
            let node_label = eg.graph[node_idx];

            // Compute depth from parent depths (BFS guarantees shortest path)
            let depth = if node_idx == start_idx {
                0
            } else {
                // Find the minimum depth among predecessors already visited
                eg.graph
                    .neighbors_directed(node_idx, petgraph::Direction::Incoming)
                    .filter_map(|pred| depth_map.get(&pred))
                    .min()
                    .map(|d| d + 1)
                    .unwrap_or(0)
            };
            depth_map.insert(node_idx, depth);
            max_depth = max_depth.max(depth);

            if node_label != defeated_node_cid {
                affected.push(node_label.to_string());
            }

            // Domain-specific: defeasibility score decays with depth
            defeasibility.insert(node_label.to_string(), 1.0 / (1.0 + depth as f64));
        }

        CascadeResult {
            defeated_node: defeated_node_cid.to_string(),
            affected_nodes: affected.clone(),
            cascade_depth: max_depth,
            defeasibility_scores: defeasibility,
            total_affected: affected.len(),
        }
    }

    /// Compute how vulnerable a node is to cascade invalidation.
    ///
    /// Uses `petgraph::visit::Bfs` on the reversed graph to count ancestors.
    /// A node with many ancestors that could be defeated has a high
    /// defeasibility score (0 = safe, 1 = highly vulnerable).
    pub fn compute_defeasibility_score(
        node_cid: &str,
        adjacency: &HashMap<String, Vec<String>>,
    ) -> f64 {
        let eg = EpistemicGraph::from_adjacency(adjacency);

        let start_idx = match eg.node_map.get(node_cid) {
            Some(&idx) => idx,
            None => return 0.0,
        };

        // Use Reversed view and BFS to count ancestors (zero-cost graph reversal)
        let rev = eg.reversed_view();
        let mut bfs = Bfs::new(&rev, start_idx);
        let mut ancestor_count: usize = 0;

        while let Some(node_idx) = bfs.next(&rev) {
            if node_idx != start_idx {
                ancestor_count += 1;
            }
        }

        let total_nodes = adjacency.len().max(1);
        (ancestor_count as f64 / total_nodes as f64).min(1.0)
    }
}

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

    fn sample_graph() -> HashMap<String, Vec<String>> {
        let mut g = HashMap::new();
        g.insert("root".to_string(), vec!["a".to_string(), "b".to_string()]);
        g.insert("a".to_string(), vec!["c".to_string(), "d".to_string()]);
        g.insert("b".to_string(), vec!["d".to_string(), "e".to_string()]);
        g.insert("c".to_string(), vec![]);
        g.insert("d".to_string(), vec!["f".to_string()]);
        g.insert("e".to_string(), vec![]);
        g.insert("f".to_string(), vec![]);
        g
    }

    #[test]
    fn test_blast_radius_from_root() {
        let graph = sample_graph();
        let result = BlastRadiusCalculator::calculate_blast_radius("root", &graph);

        assert_eq!(result.defeated_node, "root");
        // root → a, b → c, d, e → f = 6 total nodes, 5 affected (excluding root)
        assert!(result.total_affected >= 5);
        assert!(result.cascade_depth >= 2);
        assert_eq!(result.defeasibility_scores["root"], 1.0);
    }

    #[test]
    fn test_blast_radius_leaf_node() {
        let graph = sample_graph();
        let result = BlastRadiusCalculator::calculate_blast_radius("f", &graph);

        assert_eq!(result.total_affected, 0);
        assert_eq!(result.cascade_depth, 0);
    }

    #[test]
    fn test_blast_radius_missing_node() {
        let graph = sample_graph();
        let result = BlastRadiusCalculator::calculate_blast_radius("nonexistent", &graph);

        assert_eq!(result.total_affected, 0);
        assert_eq!(result.cascade_depth, 0);
    }

    #[test]
    fn test_defeasibility_score_root_has_no_ancestors() {
        let graph = sample_graph();
        let score = BlastRadiusCalculator::compute_defeasibility_score("root", &graph);
        assert_eq!(score, 0.0);
    }

    #[test]
    fn test_defeasibility_score_deep_node_has_ancestors() {
        let graph = sample_graph();
        let score = BlastRadiusCalculator::compute_defeasibility_score("f", &graph);
        assert!(score > 0.0);
    }
}