Skip to main content

sas_plus/
causal_graph.rs

1use alloc::vec;
2use alloc::vec::Vec;
3
4use crate::{Task, VarId};
5
6/// The causal graph of a task: an arc `u → v` means that changing `v` may
7/// depend on `u`, or that `u` and `v` change together.
8///
9/// As in Fast Downward, arcs run from every precondition and effect condition
10/// variable of an operator to each variable it sets, between every two
11/// variables one operator sets, and from every condition of an axiom to the
12/// variable it derives. Self-loops are left out.
13#[derive(Clone, Debug, PartialEq, Eq)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15pub struct CausalGraph {
16    successors: Vec<Vec<VarId>>,
17    predecessors: Vec<Vec<VarId>>,
18}
19
20impl CausalGraph {
21    pub fn new(task: &Task) -> Self {
22        let mut arcs = Vec::new();
23        for op in &task.operators {
24            for e in &op.eff {
25                let v = e.fact.var;
26                arcs.extend(op.pre.iter().map(|f| (f.var, v)));
27                arcs.extend(e.conditions.iter().map(|f| (f.var, v)));
28                arcs.extend(op.eff.iter().map(|other| (other.fact.var, v)));
29            }
30        }
31        for a in &task.axioms {
32            arcs.extend(a.conditions.iter().map(|f| (f.var, a.head.var)));
33        }
34        arcs.retain(|(u, v)| u != v);
35        arcs.sort_unstable();
36        arcs.dedup();
37
38        let n = task.num_variables();
39        let mut successors = vec![Vec::new(); n];
40        let mut predecessors = vec![Vec::new(); n];
41        for &(u, v) in &arcs {
42            successors[u].push(v);
43            predecessors[v].push(u);
44        }
45        Self {
46            successors,
47            predecessors,
48        }
49    }
50
51    /// Variables with an arc from `var`, sorted.
52    pub fn successors(&self, var: VarId) -> &[VarId] {
53        &self.successors[var]
54    }
55
56    /// Variables with an arc to `var`, sorted.
57    pub fn predecessors(&self, var: VarId) -> &[VarId] {
58        &self.predecessors[var]
59    }
60}