aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
doCalculus_tpl.h
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2026 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2026 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40
41
50#pragma once
51
52#include <algorithm>
53#include <queue>
54#include <utility>
55
59
60#include <unordered_map>
61#include <unordered_set>
62
63namespace gum {
64
65
66 namespace {
67 // format a vector of strings as "{a, b, c}"
68 inline std::string _fmtBraceList_(std::vector< std::string > v) {
69 std::sort(v.begin(), v.end());
70 std::string os = "{";
71 for (size_t i = 0; i < v.size(); ++i) {
72 if (i) os += ", ";
73 os += v[i];
74 }
75 os += "}";
76 return os;
77 }
78
79 } // anonymous namespace
80
81 template < GUM_Numeric GUM_SCALAR >
83 return _cm;
84 }
85
86 /* ========================================================================== */
87 /* Backdoor / Frontdoor */
88 /* ========================================================================== */
89
90 template < GUM_Numeric GUM_SCALAR >
93 NodeId effect,
94 const NodeSet& zset) const {
95 // Preconditions: cause/effect must be observed (non-latent), Z must not contain latents.
96 const NodeSet lat = _cm.latentVariablesIds();
97 if (lat.contains(cause) || lat.contains(effect)) {
99 "getBackDoorTree: 'cause' and 'effect' must be observed (non-latent).");
100 }
101 for (auto z: zset) {
102 if (lat.contains(z)) {
103 GUM_ERROR(InvalidArgument, "getBackDoorTree: zset contains a latent variable.");
104 }
105 }
106
107 // ids -> names
108 const auto& dag = _cm.causalDAG();
109 auto mapO = _cm.id2name(/*includeLatentVariables=*/false);
110 const std::string xName = _cm.nameFromId(cause);
111 const std::string yName = _cm.nameFromId(effect);
112
113 Set< std::string > zNames;
114 std::vector< std::string > zOrder;
115 zOrder.reserve(zset.size());
116 for (auto z: zset) {
117 const std::string zn = _cm.nameFromId(z);
118 zNames.insert(zn);
119 zOrder.push_back(zn);
120 }
121 std::sort(zOrder.begin(), zOrder.end());
122
123 // P(y | x, z)
125 lhsY.insert(yName);
127 knw.insert(xName);
128 for (const auto& zn: zNames)
129 knw.insert(zn);
130 auto Pyxz = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, mapO, lhsY, knw);
131
132 if (zNames.empty()) {
133 // returns P(y | x)
134 return Pyxz;
135 }
136
137 // P(z)
138 auto Pz = std::make_unique< ASTjointProba< GUM_SCALAR > >(zNames);
139
140 // P(y|x,z) * P(z), then sum over Z
141 std::vector< std::unique_ptr< ASTtree< GUM_SCALAR > > > terms;
142 terms.emplace_back(std::move(Pyxz));
143 terms.emplace_back(std::move(Pz));
144 auto prod = productOfTrees< GUM_SCALAR >(std::move(terms));
145
146 return std::make_unique< ASTsum< GUM_SCALAR > >(zOrder, std::move(prod));
147 }
148
149 template < GUM_Numeric GUM_SCALAR >
152 std::string_view effectName,
153 const NameList& zNames) const {
154 const NodeId x = _cm.idFromName(causeName);
155 const NodeId y = _cm.idFromName(effectName);
156
157 NodeSet Z;
158 for (const auto& zn: zNames)
159 Z.insert(_cm.idFromName(zn));
160
161 return getBackDoorTree(x, y, Z);
162 }
163
164 template < GUM_Numeric GUM_SCALAR >
167 NodeId effect,
168 const NodeSet& zset) const {
169 // --- Preconditions ---
170 const NodeSet lat = _cm.latentVariablesIds();
171 if (lat.contains(cause) || lat.contains(effect)) {
173 "getFrontDoorTree: 'cause' and 'effect' must be observed (non-latent).");
174 }
175 if (zset.empty()) {
176 GUM_ERROR(InvalidArgument, "getFrontDoorTree: zset must be non-empty for frontdoor.");
177 }
178 if (zset.contains(cause) || zset.contains(effect)) {
179 GUM_ERROR(InvalidArgument, "getFrontDoorTree: zset must be disjoint from {cause,effect}.");
180 }
181 for (auto z: zset) {
182 if (lat.contains(z)) {
183 GUM_ERROR(InvalidArgument, "getFrontDoorTree: zset contains a latent variable.");
184 }
185 }
186
187 // --- ids → names ---
188 const std::string xName = _cm.nameFromId(cause);
189 const std::string yName = _cm.nameFromId(effect);
190
191 Set< std::string > zNames;
192 std::vector< std::string > zOrder;
193 zOrder.reserve(zset.size());
194 for (auto z: zset) {
195 const auto zn = _cm.nameFromId(z);
196 zNames.insert(zn);
197 zOrder.push_back(zn);
198 }
199 std::sort(zOrder.begin(), zOrder.end()); // deterministic
200
201 // --- Build P(Z | X) using DAG ctor (observed-only mapping inferred from model) ---
202 const auto& dag = _cm.causalDAG();
203 auto mapO = _cm.id2name(/*includeLatentVariables=*/false);
204
205 Set< std::string > condX;
206 condX.insert(xName);
207 auto Pz_given_x = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, mapO, zNames, condX);
208
209 // --- Build sum_x P(Y | X, Z) * P(X) ---
211 ySet.insert(yName);
212
213 Set< std::string > condXZ = zNames; // copy
214 condXZ.insert(xName);
215 auto Py_given_xz = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, mapO, ySet, condXZ);
216
218 xSet.insert(xName);
219 auto Px = std::make_unique< ASTjointProba< GUM_SCALAR > >(xSet);
220
221 auto inner_prod
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));
225
226 // --- P(Z|X) * (sum_x ...) then sum over Z ---
227 auto outer_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));
230 }
231
232 template < GUM_Numeric GUM_SCALAR >
235 std::string_view effectName,
236 const NameList& zNames) const {
237 const NodeId x = _cm.idFromName(causeName);
238 const NodeId y = _cm.idFromName(effectName);
239
240 NodeSet Z;
241 for (const auto& zn: zNames)
242 Z.insert(_cm.idFromName(zn));
243
244 return getFrontDoorTree(x, y, Z);
245 }
246
247 /* ========================================================================== */
248 /* Helper utilities */
249 /* ========================================================================== */
250
251 template < GUM_Numeric GUM_SCALAR >
253 const NodeSet& Y,
254 const NodeSet& X,
255 const NodeSet& V,
256 const NodeSet& S) {
257 // turn NodeSets into sorted name lists
258 auto namesOf = [&](const NodeSet& Ns) {
259 std::vector< std::string > out;
260 out.reserve(Ns.size());
261 for (auto id: Ns)
262 out.push_back(cm.nameFromId(id));
263 std::sort(out.begin(), out.end());
264 return out;
265 };
266
267 const auto yN = namesOf(Y);
268 const auto xN = namesOf(X);
269 const auto vN = namesOf(V);
270 const auto sN = namesOf(S);
271
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.",
278 _fmtBraceList_(yN),
279 _fmtBraceList_(xN),
280 _fmtBraceList_(vN),
281 _fmtBraceList_(sN));
282 }
283
284 template < GUM_Numeric GUM_SCALAR >
285 std::vector< NodeSet >
287 // c-components: undirected connectivity among observed children of the same latent.
288 const NodeSet lat = cm.latentVariablesIds();
289 const NodeSet V = cm.causalDAG().nodes().asNodeSet() - lat;
290
291 // adjacency among observed nodes, via latent co-children
292 std::unordered_map< NodeId, std::vector< NodeId > > adj;
293 for (auto v: V)
294 adj[v]; // ensure key exists
295
296 for (auto h: lat) {
297 const auto& ch = cm.children(h);
298 // connect all observed pairs of children with an undirected edge
299 for (auto it1 = ch.begin(); it1 != ch.end(); ++it1) {
300 if (lat.contains(*it1)) continue;
301 auto it2 = it1;
302 ++it2;
303 for (; it2 != ch.end(); ++it2) {
304 if (lat.contains(*it2)) continue;
305 adj[*it1].push_back(*it2);
306 adj[*it2].push_back(*it1);
307 }
308 }
309 }
310
311 // BFS/DFS over observed nodes
312 std::vector< NodeSet > comps;
313 std::unordered_set< NodeId > seen;
314 for (auto v: V) {
315 if (seen.count(v)) continue;
316 NodeSet comp;
317 std::queue< NodeId > q;
318 q.push(v);
319 seen.insert(v);
320 comp.insert(v);
321 while (!q.empty()) {
322 auto u = q.front();
323 q.pop();
324 for (auto w: adj[u]) {
325 if (!seen.count(w)) {
326 seen.insert(w);
327 comp.insert(w);
328 q.push(w);
329 }
330 }
331 }
332 comps.push_back(std::move(comp));
333 }
334 return comps;
335 }
336
337 template < GUM_Numeric GUM_SCALAR >
338 std::vector< NodeSet >
342
343 template < GUM_Numeric GUM_SCALAR >
344 std::vector< NodeId >
346 const NodeSet lat = cm.latentVariablesIds();
347 const NodeSet V = cm.causalDAG().nodes().asNodeSet() - lat;
348 const DAG dag = cm.causalDAG();
349
350 // indegree in the observed DAG (ignore latent-induced parent arcs)
351 std::unordered_map< NodeId, Size > indeg;
352 for (auto v: V)
353 indeg[v] = (dag.parents(v) - lat).size();
354
355 std::vector< NodeId > order;
356 order.reserve(V.size());
357
358 // Kahn on observed DAG only
359 std::queue< NodeId > q;
360 for (const auto& kv: indeg)
361 if (kv.second == 0) q.push(kv.first);
362
363 while (!q.empty()) {
364 const NodeId u = q.front();
365 q.pop();
366 order.push_back(u);
367
368 for (auto c: dag.children(u)) {
369 if (indeg.contains(c) && indeg[c] > 0) {
370 --indeg[c];
371 if (indeg[c] == 0) q.push(c);
372 }
373 }
374 }
375 return order;
376 }
377
378 template < GUM_Numeric GUM_SCALAR >
380 NodeSet res = T * g.nodes().asNodeSet(); // keep only nodes that actually exist in g
381
382 std::queue< NodeId > q;
383 for (auto t: res)
384 q.push(t);
385
386 while (!q.empty()) {
387 NodeId u = q.front();
388 q.pop();
389 for (auto p: g.parents(u)) {
390 if (!res.contains(p)) {
391 res.insert(p);
392 q.push(p);
393 }
394 }
395 }
396 return res;
397 }
398
399 template < GUM_Numeric GUM_SCALAR >
401 DAG g = dag; // copy
402 for (auto x: X) {
403 auto ps = g.parents(x); // snapshot
404 for (auto p: ps)
405 g.eraseArc(Arc(p, x));
406 }
407 return g;
408 }
409
410 template < GUM_Numeric GUM_SCALAR >
412 const NodeSet& doing,
413 const NodeSet& knowing) {
414 DAG g = dag; // copy
415 for (auto x: doing) {
416 auto ps = g.parents(x);
417 for (auto p: ps)
418 g.eraseArc(Arc(p, x));
419 }
420 for (auto z: knowing) {
421 auto ch = g.children(z);
422 for (auto c: ch)
423 g.eraseArc(Arc(z, c));
424 }
425 return g;
426 }
427
428 /* ========================================================================== */
429 /* General identification */
430 /* ========================================================================== */
431
432 template < GUM_Numeric GUM_SCALAR >
435 return _ID_(_cm, Y, X, nullptr);
436 }
437
438 template < GUM_Numeric GUM_SCALAR >
441 const NameList& X) const {
442 NodeSet YY, XX;
443 for (const auto& s: Y)
444 YY.insert(_cm.idFromName(s));
445 for (const auto& s: X)
446 XX.insert(_cm.idFromName(s));
447 return identifyingIntervention(YY, XX);
448 }
449
450 template < GUM_Numeric GUM_SCALAR >
452 DoCalculus< GUM_SCALAR >::doCalculus(const NodeSet& on, const NodeSet& doing) const {
453 return identifyingIntervention(on, doing);
454 }
455
456 template < GUM_Numeric GUM_SCALAR >
459 return identifyingIntervention(on, doing);
460 }
461
462 template < GUM_Numeric GUM_SCALAR >
465 const NodeSet& doing,
466 const NodeSet& knowing) const {
467 // IDC reduction: try to promote any Z∈knowing to doing if Z ⟂ on | doing ∪ (knowing\{Z})
468 // in the graph where incoming into doing and outgoing from knowing are removed.
469 if (!knowing.empty()) {
470 DAG gmod = _removeInIntoDoing_outOfKnowing_(_cm.causalDAG(), doing, knowing);
471
472 for (auto z: knowing) {
473 NodeSet Zi;
474 Zi.insert(z);
475 NodeSet Kminus = knowing - Zi;
476 if (Separation::isDSeparated(gmod, Zi, on, doing + Kminus)) {
477 // recurse with z moved to doing
478 NodeSet doing2 = doing + Zi;
479 NodeSet knowing2 = Kminus;
480 return doCalculusWithObservation(on, doing2, knowing2);
481 }
482 }
483 }
484
485 // Fallback: ratio P(on ∪ knowing | do(doing)) / P(knowing | do(doing))
486 NameList Yw, W;
487 for (auto y: on)
488 Yw.push_back(_cm.nameFromId(y));
489 for (auto w: knowing)
490 W.push_back(_cm.nameFromId(w));
491
492 NameList Xn;
493 for (auto x: doing)
494 Xn.push_back(_cm.nameFromId(x));
495
496 // numerator: ID on Y ∪ W ; denominator: ID on W (if W empty, denominator is 1)
497 NodeSet onUkn = on + knowing;
498
499 auto num = identifyingIntervention(onUkn, doing);
500 if (knowing.empty()) {
501 // P(Y|do(X)) when knowing is empty: just return numerator
502 return num;
503 }
504 auto den = identifyingIntervention(knowing, doing);
505 return std::make_unique< ASTdiv< GUM_SCALAR > >(std::move(num), std::move(den));
506 }
507
508 template < GUM_Numeric GUM_SCALAR >
511 const NameList& doing,
512 const NameList& knowing) const {
513 NodeSet ON, DO, KN;
514 for (const auto& s: on)
515 ON.insert(_cm.idFromName(s));
516 for (const auto& s: doing)
517 DO.insert(_cm.idFromName(s));
518 for (const auto& s: knowing)
519 KN.insert(_cm.idFromName(s));
520 return doCalculusWithObservation(ON, DO, KN);
521 }
522
523 /* ========================================================================== */
524 /* ID core */
525 /* ========================================================================== */
526
527 template < GUM_Numeric GUM_SCALAR >
530 const NodeSet& Y,
531 const NodeSet& X,
532 std::unique_ptr< ASTtree< GUM_SCALAR > > P) const {
533 const NodeSet lat = cm.latentVariablesIds();
534 const NodeSet V = cm.causalDAG().nodes().asNodeSet() - lat;
535
536 // --- 1) if X is empty ---
537 if (X.empty()) {
538 if (!P) {
539 // return P(Y)
541 for (auto y: Y)
542 Yn.insert(cm.nameFromId(y));
543 return std::make_unique< ASTjointProba< GUM_SCALAR > >(Yn);
544 }
545 // return sum_{V\Y} P
546 NodeSet Vy = V - Y;
547 if (Vy.empty()) return std::move(P);
548 std::vector< std::string > tosum;
549 tosum.reserve(Vy.size());
550 for (auto v: Vy)
551 tosum.push_back(cm.nameFromId(v));
552 return std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(P));
553 }
554
555 // --- 2) restrict to ancestors of Y in G ---
556 {
557 DAG g = cm.causalDAG();
558 NodeSet A = _ancestorsIn_(g, Y);
559 A += Y;
560 // Only observed ancestors (V is observed-only)
561 NodeSet Aobs = A - lat;
562 if (Aobs.size() != V.size()) {
563 // sum out V \ Aobs from P if present, recurse on induced submodel G[Aobs]
564 if (P) {
565 NodeSet VminusA = V - Aobs;
566 if (!VminusA.empty()) {
567 std::vector< std::string > tosum;
568 tosum.reserve(VminusA.size());
569 for (auto v: VminusA)
570 tosum.push_back(cm.nameFromId(v));
571 P = std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(P));
572 }
573 }
574 auto sub = cm.inducedCausalSubModel(cm, Aobs);
575 NodeSet XA = X * Aobs;
576 return _ID_(sub, Y, XA, std::move(P));
577 }
578 }
579
580
581 // --- 3) W := (V\X) \ An_{G_{\overline X}}(Y); if non-empty, move W to X and recurse ---
582 {
583 DAG gXbar = _removeIncomingInto_(cm.causalDAG(), X);
584 NodeSet AnY = _ancestorsIn_(gXbar, Y);
585 AnY += Y;
586 NodeSet W = (V - X) - AnY;
587 if (!W.empty()) { return _ID_(cm, Y, X + W, std::move(P)); }
588 }
589
590 // --- 4) c-decompose G[V\X]; if >1 component, multiply and sum ---
591 {
592 auto gvx = cm.inducedCausalSubModel(cm, V - X);
593 auto icomp = _cDecompositionOn_(gvx);
594
595 if (icomp.size() > 1) {
596 // t = Π_i ID(S_i, V \ S_i)
597 std::unique_ptr< ASTtree< GUM_SCALAR > > t;
598 for (size_t i = 0; i < icomp.size(); ++i) {
599 NodeSet Si = icomp[i];
600 NameList Sn;
601 for (auto s: Si)
602 Sn.push_back(cm.nameFromId(s));
603
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));
609 }
610 NodeSet Vyx = V - (X + Y);
611 if (Vyx.empty()) return t;
612 std::vector< std::string > tosum;
613 tosum.reserve(Vyx.size());
614 for (auto v: Vyx)
615 tosum.push_back(cm.nameFromId(v));
616 return std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(t));
617 }
618
619 // Only one component:
620 NodeSet S = icomp.front();
621 auto cdg = _cDecomposition_(cm);
622
623 // --- 5) Hedge check: if full graph is one c-component, not identifiable
624 if (cdg.size() == 1) {
625 NodeSet all = cdg.front();
626 if (all.size() == V.size()) {
627 // build names for message
628 Set< std::string > Vn, Sn;
629 for (auto v: V)
630 Vn.insert(cm.nameFromId(v));
631 for (auto s: S)
632 Sn.insert(cm.nameFromId(s));
633 auto msg = _hedgeExceptionMsg(cm, Y, X, V, S);
635 }
636 }
637
638 // --- 6) If S is also a c-component in G: product of local conditionals over S
639 {
640 // test membership: S ∈ cdg ?
641 bool sInCdg = false;
642 for (const auto& comp: cdg) {
643 if (comp == S) {
644 sInCdg = true;
645 break;
646 }
647 }
648
649 if (sInCdg) {
650 // P_new := Π_{v∈S in topo order} P(v | v_π) under current P (if provided),
651 // otherwise P from the BN (chain rule)
652 auto order = _topoObserved_(cm);
653 const DAG dag = cm.causalDAG();
654 const auto id2n = cm.id2name(/*includeLatentVariables=*/false);
655
656 std::unique_ptr< ASTtree< GUM_SCALAR > > prod;
657
658 // Make a name lookup for quick topo prefix
659 std::unordered_map< NodeId, Size > pos;
660 for (Size i = 0; i < order.size(); ++i)
661 pos[order[i]] = i;
662
663 // build in topo order filtered to S
664 std::vector< NodeId > ordering;
665 ordering.reserve(S.size());
666 for (auto v: order)
667 if (S.contains(v)) ordering.push_back(v);
668
669 for (Size j = 0; j < ordering.size(); ++j) {
670 auto v = ordering[j];
671 std::unique_ptr< ASTtree< GUM_SCALAR > > term;
672 if (!P) {
673 // from BN: P(v | predecessors) using chain rule prefix
674 Size k = pos[v];
675 Set< std::string > condNames;
676 for (Size i = 0; i < k; ++i)
677 condNames.insert(cm.nameFromId(order[i]));
679 lhs.insert(cm.nameFromId(v));
680 if (condNames.empty()) term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
681 else
682 term = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag,
683 id2n,
684 lhs,
685 condNames);
686 } else {
687 // from accumulated P: factorize Q[S] by full-order prefix marginals
688 Size k = pos[v];
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]));
693
694 // numerator = marginal of P on current prefix
695 std::unique_ptr< ASTtree< GUM_SCALAR > > num(P->copy());
696 std::vector< std::string > sumNum;
697 for (auto u: V) {
698 const auto& un = cm.nameFromId(u);
699 if (std::find(prefixNames.begin(), prefixNames.end(), un) == prefixNames.end()) {
700 sumNum.push_back(un);
701 }
702 }
703 if (!sumNum.empty()) {
704 num = std::make_unique< ASTsum< GUM_SCALAR > >(sumNum, std::move(num));
705 }
706
707 if (k == 0) {
709 lhs.insert(cm.nameFromId(v));
710 term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
711
712 } else {
713 // denominator = marginal of P on previous prefix
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;
720 for (auto u: V) {
721 const auto& un = cm.nameFromId(u);
722 if (std::find(prevPrefix.begin(), prevPrefix.end(), un) == prevPrefix.end()) {
723 sumDen.push_back(un);
724 }
725 }
726 if (!sumDen.empty()) {
727 den = std::make_unique< ASTsum< GUM_SCALAR > >(sumDen, std::move(den));
728 }
729 term = std::make_unique< ASTdiv< GUM_SCALAR > >(std::move(num), std::move(den));
730 }
731 }
732
733 if (!prod) prod = std::move(term);
734 else prod = std::make_unique< ASTmult< GUM_SCALAR > >(std::move(term), std::move(prod));
735 }
736
737 NodeSet Sy = S - Y;
738 if (Sy.empty()) return prod;
739 std::vector< std::string > tosum;
740 tosum.reserve(Sy.size());
741 for (auto v: Sy)
742 tosum.push_back(cm.nameFromId(v));
743 return std::make_unique< ASTsum< GUM_SCALAR > >(tosum, std::move(prod));
744 }
745 }
746
747 // --- 7) Else: pick a c-component S' of G, build Q[S'] then recurse on G[S']
748 {
749 // choose the c-component of G that contains S (SP Step 7: S ⊆ S')
750 NodeSet Spr;
751 bool found = false;
752 for (const auto& comp: cdg) {
753 if ((S - comp).empty()) {
754 Spr = comp;
755 found = true;
756 break;
757 }
758 }
759 if (!found) {
760 // Fallback should not happen; be conservative
761 Spr = S;
762 }
763
764 auto order = _topoObserved_(cm);
765 const DAG dag = cm.causalDAG();
766 const auto id2n = cm.id2name(/*includeLatentVariables=*/false);
767
768 std::unique_ptr< ASTtree< GUM_SCALAR > > prod;
769
770 std::unordered_map< NodeId, Size > pos;
771 for (Size i = 0; i < order.size(); ++i)
772 pos[order[i]] = i;
773
774 std::vector< NodeId > ordering;
775 ordering.reserve(Spr.size());
776 for (auto v: order)
777 if (Spr.contains(v)) ordering.push_back(v);
778
779 for (Size j = 0; j < ordering.size(); ++j) {
780 auto v = ordering[j];
781 std::unique_ptr< ASTtree< GUM_SCALAR > > term;
782 if (!P) {
783 Size k = pos[v];
784 Set< std::string > condNames;
785 for (Size i = 0; i < k; ++i)
786 condNames.insert(cm.nameFromId(order[i]));
788 lhs.insert(cm.nameFromId(v));
789 if (condNames.empty()) term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
790 else
791 term = std::make_unique< ASTposteriorProba< GUM_SCALAR > >(dag, id2n, lhs, condNames);
792 } else {
793 // from accumulated P: factorize Q[Spr] by full-order prefix marginals
794 Size k = pos[v];
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]));
799
800 // numerator = marginal of P on current prefix
801 std::unique_ptr< ASTtree< GUM_SCALAR > > num(P->copy());
802 std::vector< std::string > sumNum;
803 for (auto u: V) {
804 const auto& un = cm.nameFromId(u);
805 if (std::find(prefixNames.begin(), prefixNames.end(), un) == prefixNames.end()) {
806 sumNum.push_back(un);
807 }
808 }
809 if (!sumNum.empty()) {
810 num = std::make_unique< ASTsum< GUM_SCALAR > >(sumNum, std::move(num));
811 }
812
813 if (k == 0) {
815 lhs.insert(cm.nameFromId(v));
816 term = std::make_unique< ASTjointProba< GUM_SCALAR > >(lhs);
817
818 } else {
819 // denominator = marginal of P on previous prefix
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;
826 for (auto u: V) {
827 const auto& un = cm.nameFromId(u);
828 if (std::find(prevPrefix.begin(), prevPrefix.end(), un) == prevPrefix.end()) {
829 sumDen.push_back(un);
830 }
831 }
832 if (!sumDen.empty()) {
833 den = std::make_unique< ASTsum< GUM_SCALAR > >(sumDen, std::move(den));
834 }
835 term = std::make_unique< ASTdiv< GUM_SCALAR > >(std::move(num), std::move(den));
836 }
837 }
838
839 if (!prod) prod = std::move(term);
840 else prod = std::make_unique< ASTmult< GUM_SCALAR > >(std::move(term), std::move(prod));
841 }
842
843 auto sub = cm.inducedCausalSubModel(cm, Spr);
844 NodeSet Yspr = Y * Spr; // <— important
845 NodeSet Xspr = X * Spr;
846
847 if (Yspr.empty()) {
849 "Internal error in ID step 7: chosen C-component is disjoint from Y.");
850 }
851
852 return _ID_(sub, Yspr, Xspr, std::move(prod));
853 }
854 }
855 }
856
857} // namespace gum
d-separation utilities
Represents an identified causal formula and its query context.
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.
Definition causalModel.h:96
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).
Base class for dag.
Definition DAG.h:121
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
Definition doCalculus.h:127
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.
Definition doCalculus.h:84
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.
Definition doCalculus.h:81
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.
Definition set_tpl.h:468
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition set_tpl.h:613
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
Size size() const noexcept
Returns the number of elements in the set.
Definition set_tpl.h:607
Do-calculus utilities and AST builders bound to a single CausalModel.
#define GUM_ERROR(type, msg)
Definition exceptions.h:76
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74
Size NodeId
Type for node ids.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
std::unique_ptr< ASTtree< GUM_SCALAR > > productOfTrees(std::vector< std::unique_ptr< ASTtree< GUM_SCALAR > > > &&lterms)
Build a product AST from a list of terms.
Definition doAST_tpl.h:633