Struct Dag 

pub struct Dag { /* private fields */ }

Static directed acyclic graph over variables.

Implementations

impl Dag

pub fn ancestors_of( &self, nodes: &[DenseNodeId], out: &mut BitSet, ws: &mut GraphWorkspace, )

Collect all ancestors of nodes (including nodes themselves) into out.

pub fn descendants_of( &self, nodes: &[DenseNodeId], out: &mut BitSet, ws: &mut GraphWorkspace, )

Collect all descendants of nodes (including nodes) into out.

pub fn is_ancestor(&self, anc: DenseNodeId, desc: DenseNodeId) -> bool

Whether anc is an ancestor of desc (or equal).

pub fn markov_blanket( &self, node: DenseNodeId, out: &mut BitSet, ) -> Result<(), GraphError>

Markov blanket of node: parents ∪ children ∪ spouses (co-parents of children). Does not include node itself.

Errors

Unknown node id.

pub fn markov_blanket_nodes( &self, node: DenseNodeId, ) -> Result<Vec<DenseNodeId>, GraphError>

Sorted Markov blanket of node (excluding node).

Errors

Unknown node id.

pub fn mutilate(&self, intervened: &[DenseNodeId]) -> Result<Dag, GraphError>

Mutilate the graph under intervention: remove all edges into each intervened node. Returns a new DAG (nodes preserved).

Prefer Dag::view with GraphOverlay::do_intervention on hot paths to avoid cloning adjacency.

Errors

Unknown node ids.

impl Dag

pub fn empty() -> Self

Empty DAG.

pub fn with_variables(n: u32) -> Self

Build a DAG with one static node per variable 0..n.

pub fn from_named_edges( schema: &CausalSchema, edges: &[(&str, &str)], ) -> Result<Self, GraphError>

Build a DAG with one static node per schema variable (VariableId raw == dense id), then insert directed edges named by schema variable names.

Errors

Unknown names, duplicate edges, or cycles.

pub fn node_count(&self) -> usize

Number of nodes.

pub fn is_empty(&self) -> bool

Whether empty.

pub fn nodes(&self) -> &[NodeRef]

Node refs in dense order.

pub fn add_node(&mut self, node: NodeRef) -> Result<DenseNodeId, GraphError>

Add a static node; returns its dense id.

Errors

GraphError::TooManyNodes on overflow.

pub fn insert_directed( &mut self, from: DenseNodeId, to: DenseNodeId, ) -> Result<(), GraphError>

Insert a directed edge from -> to if it preserves acyclicity.

Errors

Unknown nodes, duplicates, or cycles.

pub fn remove_directed(&mut self, from: DenseNodeId, to: DenseNodeId)

Remove a directed edge if present.

pub fn children(&self, id: DenseNodeId) -> &[DenseNodeId]

Children of id.

pub fn parents(&self, id: DenseNodeId) -> &[DenseNodeId]

Parents of id.

pub fn reaches(&self, from: DenseNodeId, to: DenseNodeId) -> bool

Whether from can reach to via directed edges.

pub fn reaches_with( &self, from: DenseNodeId, to: DenseNodeId, ws: &mut GraphWorkspace, ) -> bool

Reachability using a reusable workspace.

pub fn topological_order(&self) -> Option<Vec<DenseNodeId>>

Topological order (Kahn). Returns None if a cycle slipped in.

pub fn validate(&self) -> Result<(), GraphError>

Validate graph invariants.

Errors

Cycle detected.

pub fn edges(&self) -> impl Iterator<Item = MarkedEdge> + '_

Iterate directed edges as marked edges.

pub fn directed_paths( &self, from: DenseNodeId, to: DenseNodeId, max_paths: usize, max_len: usize, ) -> Result<Vec<Vec<DenseNodeId>>, GraphError>

Enumerate simple directed paths from from to to (inclusive endpoints).

Bounded by max_paths and max_len (number of nodes on the path).

The returned set is silently truncated when either bound binds. Callers whose correctness depends on seeing every path — e.g. a recanting-witness test, which concludes “no witness exists” from the absence of one — must use Self::directed_paths_with_budget and fail closed on truncation instead.

Errors

Unknown nodes.

pub fn directed_paths_with_budget( &self, from: DenseNodeId, to: DenseNodeId, max_paths: usize, max_len: usize, ) -> Result<(Vec<Vec<DenseNodeId>>, bool), GraphError>

Self::directed_paths plus a flag reporting whether enumeration was cut short.

The flag is true when max_paths stopped the search with candidates still pending, or when max_len pruned a partial path that had not yet reached to. It is deliberately conservative: true means “the path set may be incomplete”, never “it is definitely incomplete”.

Errors

Unknown nodes.

impl Dag

pub fn is_d_separated( &self, x: DenseNodeId, y: DenseNodeId, z: &[DenseNodeId], ws: &mut DSeparationWorkspace, ) -> Result<bool, GraphError>

Whether x is d-separated from y given z (boolean; no path alloc).

If Z ∩ {x,y} ≠ ∅ the query is ill-posed and this returns false (not separated), matching PAG m-separation / definite-status activity.

Errors

Unknown node ids.

pub fn is_d_separated_batch( &self, queries: &[(DenseNodeId, DenseNodeId, &[DenseNodeId])], out: &mut [bool], ws: &mut DSeparationWorkspace, ) -> Result<(), GraphError>

Batch boolean d-separation. out[i] corresponds to queries[i] = (x,y,z).

Errors

Unknown nodes; or out.len() != queries.len().

pub fn d_separation( &self, x: DenseNodeId, y: DenseNodeId, z: &[DenseNodeId], ws: &mut DSeparationWorkspace, ) -> Result<SeparationResult, GraphError>

d-separation with witness (active path or separation certificate).

Errors

Unknown nodes.

impl Dag

pub fn view<'a>(&'a self, overlay: &'a GraphOverlay) -> DagView<'a>

Borrow self under an intervention / mutilation overlay.

Trait Implementations

impl Clone for Dag

fn clone(&self) -> Dag

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Dag

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.