60#include <unordered_map>
61#include <unordered_set>
68 inline std::string _fmtBraceList_(std::vector< std::string > v) {
69 std::sort(v.begin(), v.end());
71 for (
size_t i = 0; i < v.size(); ++i) {
81 template < GUM_Numeric GUM_SCALAR >
90 template < GUM_Numeric GUM_SCALAR >
99 "getBackDoorTree: 'cause' and 'effect' must be observed (non-latent).");
108 const auto& dag =
_cm.causalDAG();
109 auto mapO =
_cm.id2name(
false);
110 const std::string xName =
_cm.nameFromId(cause);
111 const std::string yName =
_cm.nameFromId(effect);
114 std::vector< std::string > zOrder;
115 zOrder.reserve(zset.
size());
117 const std::string zn =
_cm.nameFromId(z);
119 zOrder.push_back(zn);
121 std::sort(zOrder.begin(), zOrder.end());
128 for (
const auto& zn: zNames)
130 auto Pyxz = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, mapO, lhsY, knw);
132 if (zNames.
empty()) {
138 auto Pz = std::make_unique< ASTjointProba< GUM_SCALAR > >(zNames);
141 std::vector< std::unique_ptr< ASTtree< GUM_SCALAR > > > terms;
142 terms.emplace_back(std::move(Pyxz));
143 terms.emplace_back(std::move(Pz));
146 return std::make_unique< ASTsum< GUM_SCALAR > >(zOrder, std::move(prod));
149 template < GUM_Numeric GUM_SCALAR >
152 std::string_view effectName,
154 const NodeId x =
_cm.idFromName(causeName);
155 const NodeId y =
_cm.idFromName(effectName);
158 for (
const auto& zn: zNames)
164 template < GUM_Numeric GUM_SCALAR >
173 "getFrontDoorTree: 'cause' and 'effect' must be observed (non-latent).");
188 const std::string xName =
_cm.nameFromId(cause);
189 const std::string yName =
_cm.nameFromId(effect);
192 std::vector< std::string > zOrder;
193 zOrder.reserve(zset.
size());
195 const auto zn =
_cm.nameFromId(z);
197 zOrder.push_back(zn);
199 std::sort(zOrder.begin(), zOrder.end());
202 const auto& dag =
_cm.causalDAG();
203 auto mapO =
_cm.id2name(
false);
207 auto Pz_given_x = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, mapO, zNames, condX);
215 auto Py_given_xz = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, mapO, ySet, condXZ);
219 auto Px = std::make_unique< ASTjointProba< GUM_SCALAR > >(xSet);
222 = std::make_unique< ASTmult< GUM_SCALAR > >(std::move(Py_given_xz), std::move(Px));
223 auto inner_sum = std::make_unique< ASTsum< GUM_SCALAR > >(std::vector< std::string >{xName},
224 std::move(inner_prod));
228 = std::make_unique< ASTmult< GUM_SCALAR > >(std::move(Pz_given_x), std::move(inner_sum));
229 return std::make_unique< ASTsum< GUM_SCALAR > >(zOrder, std::move(outer_prod));
232 template < GUM_Numeric GUM_SCALAR >
235 std::string_view effectName,
237 const NodeId x =
_cm.idFromName(causeName);
238 const NodeId y =
_cm.idFromName(effectName);
241 for (
const auto& zn: zNames)
251 template < GUM_Numeric GUM_SCALAR >
258 auto namesOf = [&](
const NodeSet& Ns) {
259 std::vector< std::string > out;
260 out.reserve(Ns.size());
263 std::sort(out.begin(), out.end());
267 const auto yN = namesOf(Y);
268 const auto xN = namesOf(X);
269 const auto vN = namesOf(V);
270 const auto sN = namesOf(S);
272 return std::format(
"Not identifiable: hedge detected. "
273 "Target P{} | do{}. Witness: V = {} is a single c-component and S = {} "
274 "is a c-component in both G and G\\X (forms a hedge). "
275 "Interpretation: unblocked confounding remains under intervention; "
276 "the effect cannot be expressed from the observational distribution "
277 "using current graph structure.",
284 template < GUM_Numeric GUM_SCALAR >
285 std::vector< NodeSet >
292 std::unordered_map< NodeId, std::vector< NodeId > > adj;
299 for (
auto it1 = ch.begin(); it1 != ch.end(); ++it1) {
303 for (; it2 != ch.end(); ++it2) {
305 adj[*it1].push_back(*it2);
306 adj[*it2].push_back(*it1);
312 std::vector< NodeSet > comps;
313 std::unordered_set< NodeId > seen;
315 if (seen.count(v))
continue;
317 std::queue< NodeId > q;
324 for (
auto w: adj[u]) {
325 if (!seen.count(w)) {
332 comps.push_back(std::move(comp));
337 template < GUM_Numeric GUM_SCALAR >
338 std::vector< NodeSet >
343 template < GUM_Numeric GUM_SCALAR >
344 std::vector< NodeId >
351 std::unordered_map< NodeId, Size > indeg;
353 indeg[v] = (dag.
parents(v) - lat).size();
355 std::vector< NodeId > order;
356 order.reserve(V.
size());
359 std::queue< NodeId > q;
360 for (
const auto& kv: indeg)
361 if (kv.second == 0) q.push(kv.first);
364 const NodeId u = q.front();
369 if (indeg.contains(c) && indeg[c] > 0) {
371 if (indeg[c] == 0) q.push(c);
378 template < GUM_Numeric GUM_SCALAR >
382 std::queue< NodeId > q;
399 template < GUM_Numeric GUM_SCALAR >
410 template < GUM_Numeric GUM_SCALAR >
415 for (
auto x: doing) {
420 for (
auto z: knowing) {
432 template < GUM_Numeric GUM_SCALAR >
435 return _ID_(
_cm, Y, X,
nullptr);
438 template < GUM_Numeric GUM_SCALAR >
443 for (
const auto& s: Y)
445 for (
const auto& s: X)
450 template < GUM_Numeric GUM_SCALAR >
456 template < GUM_Numeric GUM_SCALAR >
462 template < GUM_Numeric GUM_SCALAR >
466 const NodeSet& knowing)
const {
469 if (!knowing.
empty()) {
472 for (
auto z: knowing) {
488 Yw.push_back(
_cm.nameFromId(y));
489 for (
auto w: knowing)
490 W.push_back(
_cm.nameFromId(w));
494 Xn.push_back(
_cm.nameFromId(x));
500 if (knowing.
empty()) {
505 return std::make_unique< ASTdiv< GUM_SCALAR > >(std::move(num), std::move(den));
508 template < GUM_Numeric GUM_SCALAR >
514 for (
const auto& s: on)
516 for (
const auto& s: doing)
518 for (
const auto& s: knowing)
527 template < GUM_Numeric GUM_SCALAR >
532 std::unique_ptr< ASTtree< GUM_SCALAR > > P)
const {
543 return std::make_unique< ASTjointProba< GUM_SCALAR > >(Yn);
547 if (Vy.
empty())
return std::move(P);
548 std::vector< std::string > tosum;
549 tosum.reserve(Vy.
size());
552 return std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(P));
566 if (!VminusA.
empty()) {
567 std::vector< std::string > tosum;
568 tosum.reserve(VminusA.
size());
569 for (
auto v: VminusA)
571 P = std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(P));
576 return _ID_(sub, Y, XA, std::move(P));
587 if (!W.
empty()) {
return _ID_(cm, Y, X + W, std::move(P)); }
595 if (icomp.size() > 1) {
597 std::unique_ptr< ASTtree< GUM_SCALAR > > t;
598 for (
size_t i = 0; i < icomp.size(); ++i) {
604 std::unique_ptr< ASTtree< GUM_SCALAR > > Pcopy
605 = P ? std::unique_ptr< ASTtree< GUM_SCALAR > >(P->copy()) :
nullptr;
606 auto term =
_ID_(cm, Si, V - Si, std::move(Pcopy));
607 if (!t) t = std::move(term);
608 else t = std::make_unique< ASTmult< GUM_SCALAR > >(std::move(term), std::move(t));
611 if (Vyx.
empty())
return t;
612 std::vector< std::string > tosum;
613 tosum.reserve(Vyx.
size());
616 return std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(t));
624 if (cdg.size() == 1) {
642 for (
const auto& comp: cdg) {
654 const auto id2n = cm.
id2name(
false);
656 std::unique_ptr< ASTtree< GUM_SCALAR > > prod;
659 std::unordered_map< NodeId, Size > pos;
660 for (
Size i = 0; i < order.size(); ++i)
664 std::vector< NodeId > ordering;
665 ordering.reserve(S.
size());
667 if (S.
contains(v)) ordering.push_back(v);
669 for (
Size j = 0; j < ordering.size(); ++j) {
670 auto v = ordering[j];
671 std::unique_ptr< ASTtree< GUM_SCALAR > > term;
676 for (
Size i = 0; i < k; ++i)
680 if (condNames.
empty()) term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
682 term = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag,
689 std::vector< std::string > prefixNames;
690 prefixNames.reserve(k + 1);
691 for (
Size i = 0; i <= k; ++i)
692 prefixNames.push_back(cm.
nameFromId(order[i]));
695 std::unique_ptr< ASTtree< GUM_SCALAR > > num(P->copy());
696 std::vector< std::string > sumNum;
699 if (std::find(prefixNames.begin(), prefixNames.end(), un) == prefixNames.end()) {
700 sumNum.push_back(un);
703 if (!sumNum.empty()) {
704 num = std::make_unique< ASTsum< GUM_SCALAR > >(sumNum, std::move(num));
710 term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
714 std::unique_ptr< ASTtree< GUM_SCALAR > > den(P->copy());
715 std::vector< std::string > prevPrefix;
716 prevPrefix.reserve(k);
717 for (
Size i = 0; i < k; ++i)
718 prevPrefix.push_back(cm.
nameFromId(order[i]));
719 std::vector< std::string > sumDen;
722 if (std::find(prevPrefix.begin(), prevPrefix.end(), un) == prevPrefix.end()) {
723 sumDen.push_back(un);
726 if (!sumDen.empty()) {
727 den = std::make_unique< ASTsum< GUM_SCALAR > >(sumDen, std::move(den));
729 term = std::make_unique< ASTdiv< GUM_SCALAR > >(std::move(num), std::move(den));
733 if (!prod) prod = std::move(term);
734 else prod = std::make_unique< ASTmult< GUM_SCALAR > >(std::move(term), std::move(prod));
738 if (Sy.
empty())
return prod;
739 std::vector< std::string > tosum;
740 tosum.reserve(Sy.
size());
743 return std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(prod));
752 for (
const auto& comp: cdg) {
753 if ((S - comp).empty()) {
766 const auto id2n = cm.
id2name(
false);
768 std::unique_ptr< ASTtree< GUM_SCALAR > > prod;
770 std::unordered_map< NodeId, Size > pos;
771 for (
Size i = 0; i < order.size(); ++i)
774 std::vector< NodeId > ordering;
775 ordering.reserve(Spr.
size());
777 if (Spr.
contains(v)) ordering.push_back(v);
779 for (
Size j = 0; j < ordering.size(); ++j) {
780 auto v = ordering[j];
781 std::unique_ptr< ASTtree< GUM_SCALAR > > term;
785 for (
Size i = 0; i < k; ++i)
789 if (condNames.
empty()) term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
791 term = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, id2n, lhs, condNames);
795 std::vector< std::string > prefixNames;
796 prefixNames.reserve(k + 1);
797 for (
Size i = 0; i <= k; ++i)
798 prefixNames.push_back(cm.
nameFromId(order[i]));
801 std::unique_ptr< ASTtree< GUM_SCALAR > > num(P->copy());
802 std::vector< std::string > sumNum;
805 if (std::find(prefixNames.begin(), prefixNames.end(), un) == prefixNames.end()) {
806 sumNum.push_back(un);
809 if (!sumNum.empty()) {
810 num = std::make_unique< ASTsum< GUM_SCALAR > >(sumNum, std::move(num));
816 term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
820 std::unique_ptr< ASTtree< GUM_SCALAR > > den(P->copy());
821 std::vector< std::string > prevPrefix;
822 prevPrefix.reserve(k);
823 for (
Size i = 0; i < k; ++i)
824 prevPrefix.push_back(cm.
nameFromId(order[i]));
825 std::vector< std::string > sumDen;
828 if (std::find(prevPrefix.begin(), prevPrefix.end(), un) == prevPrefix.end()) {
829 sumDen.push_back(un);
832 if (!sumDen.empty()) {
833 den = std::make_unique< ASTsum< GUM_SCALAR > >(sumDen, std::move(den));
835 term = std::make_unique< ASTdiv< GUM_SCALAR > >(std::move(num), std::move(den));
839 if (!prod) prod = std::move(term);
840 else prod = std::make_unique< ASTmult< GUM_SCALAR > >(std::move(term), std::move(prod));
849 "Internal error in ID step 7: chosen C-component is disjoint from Y.");
852 return _ID_(sub, Yspr, Xspr, std::move(prod));
const NodeSet & parents(NodeId id) const
returns the set of nodes with arc ingoing to a given node
NodeSet children(const NodeSet &ids) const
returns the set of nodes which consists in the node and its parents returns the set of children of a ...
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
Arc(NodeId tail, NodeId head)
basic constructor. Creates tail -> head.
A causal model pairing a causal DAG with an optional observational BayesNet.
DAG causalDAG() const
Causal DAG (observed + latent variables), with node names set.
CausalModel< GUM_SCALAR > inducedCausalSubModel(const CausalModel< GUM_SCALAR > &cm, NodeSet subset) const
Induced causal submodel on a subset of nodes.
NodeSet latentVariablesIds() const
Node ids of all latent variables.
Bijection< NodeId, std::string > id2name(bool includeLatentVariable=false) const
Bidirectional mapping between node ids and variable names.
std::string nameFromId(NodeId id) const
Variable name from node id (observed or latent).
NodeSet children(NodeId x) const
Children of a node (by id) in the causal DAG (including latents).
static DAG _removeInIntoDoing_outOfKnowing_(const DAG &dag, const NodeSet &doing, const NodeSet &knowing)
IDC helper: DAG copy with incoming into doing removed AND outgoing from knowing removed.
FormulaPtr doCalculusWithObservation(const NodeSet &on, const NodeSet &doing, const NodeSet &knowing) const
IDC: identify P(on | do(doing), knowing).
FormulaPtr _ID_(const CausalModel< GUM_SCALAR > &cm, const NodeSet &Y, const NodeSet &X, std::unique_ptr< ASTtree< GUM_SCALAR > > P) const
ID core (recursive), with optional accumulated distribution P (AST) to carry in decompositions.
static DAG _removeIncomingInto_(const DAG &dag, const NodeSet &X)
DAG copy with all incoming arcs into X removed (G_{\overline X}).
const CausalModel< GUM_SCALAR > & _cm
std::vector< NodeId > _topoObserved_(const CausalModel< GUM_SCALAR > &cm) const
Topological order over observed nodes (ignoring latent parents).
std::vector< std::string > NameList
Convenience container for name-based overloads.
FormulaPtr getFrontDoorTree(NodeId cause, NodeId effect, const NodeSet &zset) const
std::vector< NodeSet > _cDecompositionOn_(const CausalModel< GUM_SCALAR > &sub) const
c-decomposition on an induced submodel (observed nodes only).
std::unique_ptr< ASTtree< GUM_SCALAR > > FormulaPtr
Owned pointer to an AST representing a probability expression.
static NodeSet _ancestorsIn_(const DAG &g, const NodeSet &T)
Ancestors (in DAG g) of a set T (including T).
FormulaPtr doCalculus(const NodeSet &on, const NodeSet &doing) const
Thin wrapper around ID: doCalculus(on, doing).
std::vector< NodeSet > _cDecomposition_(const CausalModel< GUM_SCALAR > &cm) const
c-decomposition (confounding components) among observed nodes.
static std::string _hedgeExceptionMsg(const CausalModel< GUM_SCALAR > &cm, const NodeSet &Y, const NodeSet &X, const NodeSet &V, const NodeSet &S)
Format a hedge exception message.
FormulaPtr identifyingIntervention(const NodeSet &Y, const NodeSet &X) const
ID: identify P(Y | do(X)) (NodeId-based).
FormulaPtr getBackDoorTree(NodeId cause, NodeId effect, const NodeSet &zset) const
const CausalModel< GUM_SCALAR > & model() const noexcept
Exception : "hedge" (witness of non-identifiability) is detected in do-calculus / ID computations.
Exception: at least one argument passed to a function is not what was expected.
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
NodeSet asNodeSet() const
returns a copy of the set of nodes represented by the NodeGraphPart
Exception : operation not allowed.
static bool isDSeparated(const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
Test ( X \perp!!!\perp Y \mid Z ) (general d-separation).
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
bool empty() const noexcept
Indicates whether the set is the empty set.
void insert(const Key &k)
Inserts a new element into the set.
Size size() const noexcept
Returns the number of elements in the set.
Do-calculus utilities and AST builders bound to a single CausalModel.
#define GUM_ERROR(type, msg)
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Size NodeId
Type for node ids.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
gum is the global namespace for all aGrUM entities
std::unique_ptr< ASTtree< GUM_SCALAR > > productOfTrees(std::vector< std::unique_ptr< ASTtree< GUM_SCALAR > > > &<erms)
Build a product AST from a list of terms.