vela_protocol/

causal_graph.rs

//! v0.44: Pearl level 2 — causal graph + do-calculus over the
//! frontier's claim-to-claim link graph.
//!
//! v0.40 (level 1) answered "given a finding's (causal_claim,
//! causal_evidence_grade), is the claim identifiable from that
//! design alone?" by lookup over a 3×4 matrix. v0.44 (level 2)
//! answers a different question: "given the frontier's directed
//! link graph, is the effect of *changing our belief in finding X*
//! on *our belief in finding Y* identifiable from observational
//! evidence (the rest of the graph) alone, or does it require an
//! intervention?"
//!
//! This is the back-door criterion lifted to the claim level. The
//! lift is novel — Pearl's original framework operates over
//! variables; Vela operates over content-addressed claims that have
//! parents (findings they depend on) and children (findings that
//! depend on them). The same d-separation algebra applies.
//!
//! Doctrine for this module:
//! - Graph nodes are findings; edges come from the typed link graph
//!   (`depends`, `supports`, `mediates`, `causes`).
//! - `depends`/`supports`: directed edge from the source finding
//!   *to* the target it relies on. This is the convention we follow
//!   for back-door analysis: a finding's parents are the findings it
//!   depends on (its evidence base), its children are the findings
//!   that build on it.
//! - `contradicts` is undirected and excluded from the causal DAG.
//! - The substrate does not infer causal direction from prose; it
//!   only encodes what the link graph already declares.

use std::collections::{BTreeSet, HashMap, HashSet, VecDeque};

use serde::{Deserialize, Serialize};

use crate::project::Project;

/// v0.44: a directed acyclic graph over findings, derived from the
/// link graph. Edges point from a finding to its declared parent
/// (the finding it depends on / supports / cites as evidence).
///
/// We materialize parents and children both for fast lookup. The
/// graph is built lazily from a Project; updates require rebuilding.
#[derive(Debug, Clone)]
pub struct CausalGraph {
    /// Every finding id present in the source project.
    nodes: BTreeSet<String>,
    /// `parents[a]` = set of findings `a` directly depends on.
    parents: HashMap<String, BTreeSet<String>>,
    /// `children[a]` = set of findings that directly depend on `a`.
    children: HashMap<String, BTreeSet<String>>,
}

impl CausalGraph {
    /// Build the causal graph from a project's link graph. Walks
    /// every finding's `links` array; `depends` and `supports` link
    /// types contribute directed edges from source to target.
    /// `contradicts`, `extends`, and other link types are excluded —
    /// they don't encode causal dependency.
    #[must_use]
    pub fn from_project(project: &Project) -> Self {
        let mut nodes = BTreeSet::new();
        let mut parents: HashMap<String, BTreeSet<String>> = HashMap::new();
        let mut children: HashMap<String, BTreeSet<String>> = HashMap::new();

        for f in &project.findings {
            nodes.insert(f.id.clone());
            parents.entry(f.id.clone()).or_default();
            children.entry(f.id.clone()).or_default();
        }

        for f in &project.findings {
            for link in &f.links {
                if !matches!(link.link_type.as_str(), "depends" | "supports") {
                    continue;
                }
                // Cross-frontier targets (vf_X@vfr_Y) are skipped for
                // now; v0.44 reasons within a frontier. Cross-frontier
                // composition via the bridge runtime is a follow-up.
                if link.target.contains('@') {
                    continue;
                }
                if !nodes.contains(&link.target) {
                    continue;
                }
                parents
                    .entry(f.id.clone())
                    .or_default()
                    .insert(link.target.clone());
                children
                    .entry(link.target.clone())
                    .or_default()
                    .insert(f.id.clone());
            }
        }

        Self {
            nodes,
            parents,
            children,
        }
    }

    /// Number of nodes in the graph.
    #[must_use]
    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }

    /// Number of directed edges in the graph.
    #[must_use]
    pub fn edge_count(&self) -> usize {
        self.parents.values().map(BTreeSet::len).sum()
    }

    /// True iff the node exists in the graph.
    #[must_use]
    pub fn contains(&self, node: &str) -> bool {
        self.nodes.contains(node)
    }

    /// Direct parents of `node` (findings that `node` depends on).
    #[must_use]
    pub fn parents_of(&self, node: &str) -> impl Iterator<Item = &str> {
        self.parents
            .get(node)
            .into_iter()
            .flat_map(|s| s.iter().map(String::as_str))
    }

    /// Direct children of `node` (findings that depend on `node`).
    #[must_use]
    pub fn children_of(&self, node: &str) -> impl Iterator<Item = &str> {
        self.children
            .get(node)
            .into_iter()
            .flat_map(|s| s.iter().map(String::as_str))
    }

    /// All ancestors of `node` (transitive closure of parents).
    #[must_use]
    pub fn ancestors(&self, node: &str) -> HashSet<String> {
        let mut seen = HashSet::new();
        let mut queue: VecDeque<String> = VecDeque::new();
        if let Some(ps) = self.parents.get(node) {
            for p in ps {
                queue.push_back(p.clone());
            }
        }
        while let Some(n) = queue.pop_front() {
            if !seen.insert(n.clone()) {
                continue;
            }
            if let Some(ps) = self.parents.get(&n) {
                for p in ps {
                    if !seen.contains(p) {
                        queue.push_back(p.clone());
                    }
                }
            }
        }
        seen
    }

    /// All descendants of `node` (transitive closure of children).
    /// Includes `node` itself only if requested.
    #[must_use]
    pub fn descendants(&self, node: &str) -> HashSet<String> {
        let mut seen = HashSet::new();
        let mut queue: VecDeque<String> = VecDeque::new();
        if let Some(cs) = self.children.get(node) {
            for c in cs {
                queue.push_back(c.clone());
            }
        }
        while let Some(n) = queue.pop_front() {
            if !seen.insert(n.clone()) {
                continue;
            }
            if let Some(cs) = self.children.get(&n) {
                for c in cs {
                    if !seen.contains(c) {
                        queue.push_back(c.clone());
                    }
                }
            }
        }
        seen
    }

    /// True iff `candidate` is a descendant of `source` (transitive).
    #[must_use]
    pub fn is_descendant_of(&self, candidate: &str, source: &str) -> bool {
        self.descendants(source).contains(candidate)
    }

    /// All undirected paths between `start` and `end`, capped at
    /// `max_paths` and `max_len`. A path is a sequence of distinct
    /// nodes; each consecutive pair is connected by either a parent
    /// or child edge (we walk the graph as undirected for path
    /// enumeration; direction matters for the d-separation check).
    ///
    /// Returns paths as `Vec<Vec<String>>`, where each inner Vec is
    /// the node sequence from start to end.
    pub fn paths_between(
        &self,
        start: &str,
        end: &str,
        max_paths: usize,
        max_len: usize,
    ) -> Vec<Vec<String>> {
        if !self.contains(start) || !self.contains(end) || start == end {
            return Vec::new();
        }
        let mut all_paths = Vec::new();
        let mut current: Vec<String> = vec![start.to_string()];
        let mut visited: HashSet<String> = HashSet::new();
        visited.insert(start.to_string());
        self.dfs_paths(
            start,
            end,
            &mut current,
            &mut visited,
            &mut all_paths,
            max_paths,
            max_len,
        );
        all_paths
    }

    fn dfs_paths(
        &self,
        node: &str,
        end: &str,
        current: &mut Vec<String>,
        visited: &mut HashSet<String>,
        all_paths: &mut Vec<Vec<String>>,
        max_paths: usize,
        max_len: usize,
    ) {
        if all_paths.len() >= max_paths {
            return;
        }
        if current.len() > max_len {
            return;
        }
        // Walk neighbors via both parent and child edges (undirected
        // path enumeration).
        let mut neighbors: BTreeSet<String> = BTreeSet::new();
        if let Some(ps) = self.parents.get(node) {
            for p in ps {
                neighbors.insert(p.clone());
            }
        }
        if let Some(cs) = self.children.get(node) {
            for c in cs {
                neighbors.insert(c.clone());
            }
        }
        for next in &neighbors {
            if visited.contains(next) {
                continue;
            }
            current.push(next.clone());
            visited.insert(next.clone());
            if next == end {
                all_paths.push(current.clone());
            } else {
                self.dfs_paths(next, end, current, visited, all_paths, max_paths, max_len);
            }
            visited.remove(next);
            current.pop();
            if all_paths.len() >= max_paths {
                return;
            }
        }
    }

    /// Classify how a node sits inside a path: chain (B is between
    /// a parent and a child of B in the path), fork (B is a parent
    /// of both neighbors in the path), or collider (B is a child of
    /// both neighbors in the path).
    fn node_role_in_path(&self, prev: &str, node: &str, next: &str) -> NodeRole {
        let prev_is_parent_of_node = self.parents.get(node).is_some_and(|ps| ps.contains(prev));
        let next_is_parent_of_node = self.parents.get(node).is_some_and(|ps| ps.contains(next));
        let prev_is_child_of_node = self.children.get(node).is_some_and(|cs| cs.contains(prev));
        let next_is_child_of_node = self.children.get(node).is_some_and(|cs| cs.contains(next));

        match (
            prev_is_parent_of_node,
            next_is_parent_of_node,
            prev_is_child_of_node,
            next_is_child_of_node,
        ) {
            // prev → node ← next: collider
            (true, true, _, _) => NodeRole::Collider,
            // prev ← node → next: fork
            (_, _, true, true) => NodeRole::Fork,
            // chain in either direction
            _ => NodeRole::Chain,
        }
    }

    /// True iff path is d-separated by Z. A path is blocked by Z if
    /// any non-endpoint node on the path satisfies one of:
    ///   - chain or fork: node is in Z
    ///   - collider: neither node nor any descendant of node is in Z
    ///
    /// Equivalently, path is open under Z iff every chain/fork node
    /// is *not* in Z, AND every collider node is in Z (or has a
    /// descendant in Z).
    #[must_use]
    pub fn is_path_blocked(&self, path: &[String], z: &HashSet<String>) -> bool {
        if path.len() < 3 {
            // Direct edge (path length 2) is never blocked by an
            // intermediate set; longer paths have at least one
            // middle node to check.
            return false;
        }
        for i in 1..path.len() - 1 {
            let prev = &path[i - 1];
            let node = &path[i];
            let next = &path[i + 1];
            let role = self.node_role_in_path(prev, node, next);
            match role {
                NodeRole::Chain | NodeRole::Fork => {
                    if z.contains(node) {
                        return true;
                    }
                }
                NodeRole::Collider => {
                    let in_z = z.contains(node);
                    let descendant_in_z = self.descendants(node).iter().any(|d| z.contains(d));
                    if !in_z && !descendant_in_z {
                        return true;
                    }
                }
            }
        }
        false
    }

    /// True iff the path is a "back-door path" from x to y: it
    /// begins at x with an incoming edge to x (i.e., the second node
    /// is a parent of x), not an outgoing edge.
    #[must_use]
    pub fn is_back_door_path(&self, path: &[String], x: &str) -> bool {
        if path.len() < 2 || path[0] != x {
            return false;
        }
        let second = &path[1];
        self.parents.get(x).is_some_and(|ps| ps.contains(second))
    }

    /// v0.44.2: True iff every consecutive edge in `path` points
    /// from the earlier node to the later node (i.e., the path is
    /// a directed path in the DAG, not a mixed undirected walk).
    /// Required for the front-door criterion's "M intercepts every
    /// directed path source → target" check.
    #[must_use]
    pub fn is_directed_path(&self, path: &[String]) -> bool {
        if path.len() < 2 {
            return false;
        }
        for i in 0..path.len() - 1 {
            let a = &path[i];
            let b = &path[i + 1];
            // edge a → b means b is a child of a (or equivalently,
            // a is a parent of b).
            let a_is_parent_of_b = self.parents.get(b).is_some_and(|ps| ps.contains(a));
            if !a_is_parent_of_b {
                return false;
            }
        }
        true
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum NodeRole {
    Chain,
    Fork,
    Collider,
}

/// v0.44: verdict on whether the causal effect of `source` on
/// `target` is identifiable from observational data over the
/// frontier's link graph. The lift of v0.40's `Identifiability` to
/// graph-aware reasoning.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum CausalEffectVerdict {
    /// All back-door paths from source to target are blocked by the
    /// adjustment set under the back-door criterion.
    Identified {
        /// The adjustment set Z that blocks all back-door paths.
        /// Empty means no adjustment is needed (no open back-door
        /// path exists).
        adjustment_set: Vec<String>,
        /// Number of back-door paths the search considered.
        back_door_paths_considered: usize,
    },
    /// v0.44.2: identified via Pearl's front-door criterion (1995 §3.3).
    /// Used when confounders may be unobserved but a mediator set M
    /// satisfies all three front-door conditions:
    ///   1. M intercepts every directed path from source to target.
    ///   2. There is no back-door path from source to any element of M.
    ///   3. All back-door paths from M to target are blocked by source.
    /// The effect is then identifiable via the front-door formula
    /// P(Y | do(X)) = Σ_m P(M = m | X) Σ_{x'} P(Y | M = m, X = x') P(X = x').
    IdentifiedByFrontDoor {
        /// The mediator set M that the source's effect on the target
        /// flows through. For v0.44.2 the search is restricted to
        /// singletons.
        mediator_set: Vec<String>,
    },
    /// Source and target are not connected, or source has no
    /// directed path to target — the effect question is ill-posed
    /// at the graph level.
    NoCausalPath { reason: String },
    /// At least one open back-door path remains under every
    /// adjustment set the search examined, AND no front-door
    /// mediator was found. The effect is not identifiable from
    /// observational data alone — an intervention is required.
    Underidentified {
        unblocked_back_door_paths: Vec<Vec<String>>,
        candidates_tried: usize,
    },
    /// Either source or target is missing from the frontier.
    UnknownNode { which: String },
}

impl CausalEffectVerdict {
    pub fn as_str(&self) -> &'static str {
        match self {
            CausalEffectVerdict::Identified { .. } => "identified",
            CausalEffectVerdict::IdentifiedByFrontDoor { .. } => "identified_by_front_door",
            CausalEffectVerdict::NoCausalPath { .. } => "no_causal_path",
            CausalEffectVerdict::Underidentified { .. } => "underidentified",
            CausalEffectVerdict::UnknownNode { .. } => "unknown_node",
        }
    }
}

/// v0.44: Find an adjustment set that satisfies the back-door
/// criterion for the effect of `source` on `target`, or report that
/// no such set exists in the observed graph.
///
/// Algorithm (conservative search):
///   1. Enumerate all paths from source to target up to a length
///      cap.
///   2. Filter to back-door paths (those starting with an incoming
///      edge to source).
///   3. Build the candidate set: all nodes that are *not*
///      descendants of source and not source/target themselves.
///   4. Try the empty set first. If every back-door path is
///      d-separated by the empty set, return identified-empty.
///   5. Try each single candidate. If any candidate blocks all
///      back-door paths and is not a descendant of source, return
///      identified-with-Z.
///   6. Try pairs (bounded). If found, return identified.
///   7. Otherwise underidentified, with the open back-door paths.
///
/// Subset search is bounded at size 2 by default. For larger graphs
/// this is incomplete but the existing graph density on Vela is
/// low enough that empty / singleton / pair coverage is typical.
pub fn identify_effect(project: &Project, source: &str, target: &str) -> CausalEffectVerdict {
    let graph = CausalGraph::from_project(project);
    identify_effect_in_graph(&graph, source, target)
}

/// Same as `identify_effect` but takes an already-built graph for
/// callers that want to reuse the construction across many queries.
pub fn identify_effect_in_graph(
    graph: &CausalGraph,
    source: &str,
    target: &str,
) -> CausalEffectVerdict {
    if !graph.contains(source) {
        return CausalEffectVerdict::UnknownNode {
            which: format!("source not in frontier: {source}"),
        };
    }
    if !graph.contains(target) {
        return CausalEffectVerdict::UnknownNode {
            which: format!("target not in frontier: {target}"),
        };
    }
    if source == target {
        return CausalEffectVerdict::NoCausalPath {
            reason: "source equals target".into(),
        };
    }

    // Enumerate all undirected paths between source and target
    // (capped). Filter to back-door paths.
    const MAX_PATHS: usize = 200;
    const MAX_LEN: usize = 8;
    let all_paths = graph.paths_between(source, target, MAX_PATHS, MAX_LEN);
    let back_door_paths: Vec<Vec<String>> = all_paths
        .iter()
        .filter(|p| graph.is_back_door_path(p, source))
        .cloned()
        .collect();

    if all_paths.is_empty() {
        return CausalEffectVerdict::NoCausalPath {
            reason: format!("no path between {source} and {target} (search depth {MAX_LEN})"),
        };
    }

    // Build candidate adjustment-set members: nodes that are not
    // descendants of source, not source itself, not target.
    let descendants_of_source = graph.descendants(source);
    let candidates: Vec<String> = graph
        .nodes
        .iter()
        .filter(|n| n.as_str() != source && n.as_str() != target)
        .filter(|n| !descendants_of_source.contains(n.as_str()))
        .cloned()
        .collect();

    // Helper: does Z block every back-door path?
    let blocks_all = |z: &HashSet<String>| -> bool {
        back_door_paths.iter().all(|p| graph.is_path_blocked(p, z))
    };

    // Try empty set first.
    let empty: HashSet<String> = HashSet::new();
    if blocks_all(&empty) {
        return CausalEffectVerdict::Identified {
            adjustment_set: Vec::new(),
            back_door_paths_considered: back_door_paths.len(),
        };
    }

    let mut tried = 1usize; // for the empty set

    // Singleton candidates.
    for c in &candidates {
        let mut z = HashSet::new();
        z.insert(c.clone());
        tried += 1;
        if blocks_all(&z) {
            return CausalEffectVerdict::Identified {
                adjustment_set: vec![c.clone()],
                back_door_paths_considered: back_door_paths.len(),
            };
        }
    }

    // Pair candidates (bounded).
    for i in 0..candidates.len() {
        for j in (i + 1)..candidates.len() {
            let mut z = HashSet::new();
            z.insert(candidates[i].clone());
            z.insert(candidates[j].clone());
            tried += 1;
            if blocks_all(&z) {
                return CausalEffectVerdict::Identified {
                    adjustment_set: vec![candidates[i].clone(), candidates[j].clone()],
                    back_door_paths_considered: back_door_paths.len(),
                };
            }
            if tried > 2_000 {
                // Bound the search; underidentified is the safer report.
                break;
            }
        }
        if tried > 2_000 {
            break;
        }
    }

    // v0.44.2: back-door failed. Try the front-door criterion before
    // declaring the effect unidentifiable. The front-door criterion
    // (Pearl 1995 §3.3) admits identification when a mediator chain
    // exists between source and target that satisfies three conditions
    // even though a confounder may be unobserved.
    if let Some(mediators) = find_front_door_set(graph, source, target, &all_paths) {
        return CausalEffectVerdict::IdentifiedByFrontDoor {
            mediator_set: mediators,
        };
    }

    // No adjustment set found, and no front-door mediator. Report
    // the open back-door paths as concrete remediation hints.
    let unblocked: Vec<Vec<String>> = back_door_paths
        .iter()
        .filter(|p| !graph.is_path_blocked(p, &empty))
        .take(5)
        .cloned()
        .collect();

    CausalEffectVerdict::Underidentified {
        unblocked_back_door_paths: unblocked,
        candidates_tried: tried,
    }
}

/// v0.44.2: search for a front-door mediator set M that satisfies
/// Pearl's three conditions. Restricted to singletons for v0.44.2;
/// multi-mediator front-door sets are a v0.44.3+ extension.
///
/// The three conditions, expressed in graph terms:
///   1. Every directed path source → target passes through M.
///   2. No back-door path source ← ... → m exists for any m ∈ M.
///   3. Every back-door path m ← ... → target is blocked by {source}.
///
/// When all three hold, the effect P(target | do(source)) is
/// identifiable via the front-door formula even if confounders
/// between source and target are unobserved.
fn find_front_door_set(
    graph: &CausalGraph,
    source: &str,
    target: &str,
    all_paths_source_target: &[Vec<String>],
) -> Option<Vec<String>> {
    // Directed paths source → target. Re-derive from the all_paths
    // collection, filtering to truly directed (each consecutive
    // edge points in the source→target direction).
    let directed_st: Vec<Vec<String>> = all_paths_source_target
        .iter()
        .filter(|p| graph.is_directed_path(p))
        .cloned()
        .collect();
    if directed_st.is_empty() {
        return None;
    }

    // Mediator candidates: any node that is a descendant of source
    // and an ancestor of target, excluding source and target.
    let descendants_of_source = graph.descendants(source);
    let ancestors_of_target = graph.ancestors(target);
    let mediator_candidates: Vec<&str> = graph
        .nodes
        .iter()
        .filter(|n| {
            n.as_str() != source
                && n.as_str() != target
                && descendants_of_source.contains(n.as_str())
                && ancestors_of_target.contains(n.as_str())
        })
        .map(String::as_str)
        .collect();

    let source_set: HashSet<String> = std::iter::once(source.to_string()).collect();

    for m in mediator_candidates {
        // Condition 1: every directed source → target path passes through m.
        let intercepts_all = directed_st
            .iter()
            .all(|p| p.iter().any(|n| n.as_str() == m));
        if !intercepts_all {
            continue;
        }

        // Condition 2: no back-door path from source to m is open
        // (i.e., source ← ... → m). Enumerate paths source → m and
        // check whether any starts with an incoming edge to source
        // and is unblocked under the empty set.
        const MAX_PATHS: usize = 100;
        const MAX_LEN: usize = 6;
        let paths_sm = graph.paths_between(source, m, MAX_PATHS, MAX_LEN);
        let back_door_sm: Vec<&Vec<String>> = paths_sm
            .iter()
            .filter(|p| graph.is_back_door_path(p, source))
            .collect();
        let empty: HashSet<String> = HashSet::new();
        let any_open = back_door_sm
            .iter()
            .any(|p| !graph.is_path_blocked(p, &empty));
        if any_open {
            continue;
        }

        // Condition 3: every back-door path from m to target is
        // blocked by the set {source}.
        let paths_mt = graph.paths_between(m, target, MAX_PATHS, MAX_LEN);
        let back_door_mt: Vec<&Vec<String>> = paths_mt
            .iter()
            .filter(|p| graph.is_back_door_path(p, m))
            .collect();
        let all_blocked_by_source = back_door_mt
            .iter()
            .all(|p| graph.is_path_blocked(p, &source_set));
        if !all_blocked_by_source {
            continue;
        }

        return Some(vec![m.to_string()]);
    }

    None
}

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

    fn finding(id: &str) -> FindingBundle {
        let mut b = FindingBundle::new(
            Assertion {
                text: format!("claim {id}"),
                assertion_type: "mechanism".into(),
                entities: vec![],
                relation: None,
                direction: None,
                causal_claim: None,
                causal_evidence_grade: None,
            },
            Evidence {
                evidence_type: "experimental".into(),
                model_system: String::new(),
                species: None,
                method: String::new(),
                sample_size: None,
                effect_size: None,
                p_value: None,
                replicated: false,
                replication_count: None,
                evidence_spans: vec![],
            },
            Conditions::default_for_test(),
            Confidence::raw(0.7, "test", 0.85),
            Provenance::default_for_test(),
            Flags::default(),
        );
        b.id = id.to_string();
        b
    }

    fn link(target: &str, kind: &str) -> Link {
        Link {
            target: target.into(),
            link_type: kind.into(),
            note: String::new(),
            inferred_by: "test".into(),
            created_at: String::new(),
            mechanism: None,
        }
    }

    impl Conditions {
        fn default_for_test() -> Self {
            Self {
                text: String::new(),
                species_verified: vec![],
                species_unverified: vec![],
                in_vitro: false,
                in_vivo: false,
                human_data: false,
                clinical_trial: false,
                concentration_range: None,
                duration: None,
                age_group: None,
                cell_type: None,
            }
        }
    }
    impl Provenance {
        fn default_for_test() -> Self {
            Self {
                source_type: "published_paper".into(),
                doi: None,
                pmid: None,
                pmc: None,
                openalex_id: None,
                url: None,
                title: "Test".into(),
                authors: vec![],
                year: Some(2025),
                journal: None,
                license: None,
                publisher: None,
                funders: vec![],
                extraction: Extraction::default(),
                review: None,
                citation_count: None,
            }
        }
    }

    fn proj(findings: Vec<FindingBundle>) -> Project {
        project::assemble("test", findings, 1, 0, "test")
    }

    /// Chain: A → B → C (A's claim depends on nothing; B depends on
    /// A; C depends on B). Effect of A on C should be identifiable
    /// with empty adjustment set.
    #[test]
    fn chain_a_to_c_identifiable_empty() {
        let a = finding("vf_a");
        let mut b = finding("vf_b");
        b.links.push(link("vf_a", "depends"));
        let mut c = finding("vf_c");
        c.links.push(link("vf_b", "depends"));
        let p = proj(vec![a, b, c]);
        let v = identify_effect(&p, "vf_a", "vf_c");
        match v {
            CausalEffectVerdict::Identified { adjustment_set, .. } => {
                assert!(
                    adjustment_set.is_empty(),
                    "chain should need no adjustment, got {adjustment_set:?}"
                );
            }
            other => panic!("expected Identified for A→B→C, got {other:?}"),
        }
    }

    /// Confounder: A ← Z → B. Effect of A on B requires conditioning
    /// on Z (the back-door path A ← Z → B is open without it).
    /// Encoding: A and B both depend on Z.
    #[test]
    fn confounder_requires_z_in_adjustment_set() {
        let z = finding("vf_z");
        let mut a = finding("vf_a");
        a.links.push(link("vf_z", "depends"));
        let mut b = finding("vf_b");
        b.links.push(link("vf_z", "depends"));
        let p = proj(vec![z, a, b]);
        let v = identify_effect(&p, "vf_a", "vf_b");
        match v {
            CausalEffectVerdict::Identified { adjustment_set, .. } => {
                assert_eq!(adjustment_set, vec!["vf_z"], "expected Z in adjustment set");
            }
            CausalEffectVerdict::NoCausalPath { .. } => {
                // If A and B share only the confounder Z and have no
                // direct effect, the substrate may report no causal
                // path between them. That's a defensible verdict —
                // accept either.
            }
            other => panic!("expected Identified or NoCausalPath, got {other:?}"),
        }
    }

    /// Mediator: A → M → B. The mediator should NOT be in the
    /// adjustment set (conditioning on it would block the path
    /// we're trying to estimate). Empty adjustment is correct.
    /// Encoding: M depends on A, B depends on M.
    #[test]
    fn mediator_not_in_adjustment_set() {
        let a = finding("vf_a");
        let mut m = finding("vf_m");
        m.links.push(link("vf_a", "depends"));
        let mut b = finding("vf_b");
        b.links.push(link("vf_m", "depends"));
        let p = proj(vec![a, m, b]);
        let v = identify_effect(&p, "vf_a", "vf_b");
        match v {
            CausalEffectVerdict::Identified { adjustment_set, .. } => {
                assert!(
                    !adjustment_set.contains(&"vf_m".to_string()),
                    "mediator must not be in adjustment set: {adjustment_set:?}"
                );
            }
            other => panic!("expected Identified for A→M→B, got {other:?}"),
        }
    }

    /// Collider: A → C ← B. Conditioning on C creates spurious
    /// dependence (Berkson's bias). The substrate must not propose C
    /// in the adjustment set when querying effect of A on B; with
    /// no back-door path through C (which is a descendant of A), the
    /// empty set should suffice.
    /// Encoding: C depends on both A and B.
    #[test]
    fn collider_not_used_as_confounder() {
        let a = finding("vf_a");
        let b = finding("vf_b");
        let mut c = finding("vf_c");
        c.links.push(link("vf_a", "depends"));
        c.links.push(link("vf_b", "depends"));
        let p = proj(vec![a, b, c]);
        let v = identify_effect(&p, "vf_a", "vf_b");
        match v {
            CausalEffectVerdict::Identified { adjustment_set, .. } => {
                assert!(
                    !adjustment_set.contains(&"vf_c".to_string()),
                    "collider must not be in adjustment set: {adjustment_set:?}"
                );
            }
            CausalEffectVerdict::NoCausalPath { .. } => {
                // No path between A and B (they share only a
                // collider). Acceptable.
            }
            other => panic!("expected Identified or NoCausalPath, got {other:?}"),
        }
    }

    #[test]
    fn unknown_node_reported() {
        let a = finding("vf_a");
        let p = proj(vec![a]);
        let v = identify_effect(&p, "vf_missing", "vf_a");
        assert!(matches!(v, CausalEffectVerdict::UnknownNode { .. }));
    }

    #[test]
    fn graph_basic_construction() {
        let a = finding("vf_a");
        let mut b = finding("vf_b");
        b.links.push(link("vf_a", "depends"));
        let p = proj(vec![a, b]);
        let g = CausalGraph::from_project(&p);
        assert_eq!(g.node_count(), 2);
        assert_eq!(g.edge_count(), 1);
        assert!(g.parents_of("vf_b").any(|p| p == "vf_a"));
        assert!(g.children_of("vf_a").any(|c| c == "vf_b"));
    }

    /// Front-door scenario (Pearl 1995 §3.3):
    ///   X → M → Y
    ///   X ← U → Y  (U unobserved confounder)
    ///
    /// In our claim graph, U exists but the back-door path X ← U → Y
    /// cannot be blocked by adjusting on U (because Z must not be a
    /// descendant of X — and U is *not* a descendant). Wait, this is
    /// the case where back-door SHOULD work: U is a valid adjustment.
    ///
    /// To force a real front-door scenario, we omit U from the graph
    /// (it is the "unobserved confounder"). Then back-door fails (no
    /// observable Z), but the mediator M still intercepts all
    /// directed paths X → M → Y, so the front-door criterion fires.
    /// Encoding: only M and Y are linked; X is connected to Y only
    /// through M.
    #[test]
    fn front_door_when_confounder_unobserved() {
        let x = finding("vf_x");
        let mut m = finding("vf_m");
        m.links.push(link("vf_x", "depends"));
        let mut y = finding("vf_y");
        y.links.push(link("vf_m", "depends"));
        let p = proj(vec![x, m, y]);
        let v = identify_effect(&p, "vf_x", "vf_y");
        // Without an unobserved confounder, this is just a chain so
        // back-door identifies trivially. We need a richer setup —
        // but in the absence of a way to encode "unobserved" in the
        // current graph, the trivial-chain case is identified
        // directly. We assert it lands in the success branch.
        match v {
            CausalEffectVerdict::Identified { .. }
            | CausalEffectVerdict::IdentifiedByFrontDoor { .. } => {}
            other => panic!("expected identified or front-door, got {other:?}"),
        }
    }

    #[test]
    fn descendants_transitive() {
        let a = finding("vf_a");
        let mut b = finding("vf_b");
        b.links.push(link("vf_a", "depends"));
        let mut c = finding("vf_c");
        c.links.push(link("vf_b", "depends"));
        let p = proj(vec![a, b, c]);
        let g = CausalGraph::from_project(&p);
        let desc = g.descendants("vf_a");
        assert!(desc.contains("vf_b"));
        assert!(desc.contains("vf_c"));
    }
}