Consolidated d-separation utilities (DAG-centric). More...

#include <separation.h>

Static Public Member Functions
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).
static bool	isBackdoorSeparated (const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
	Backdoor-style restriction: only paths whose first edge points into X.
static bool	isForwardSeparated (const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
	Forward-style restriction: only paths whose first edge leaves X.
static DAG	reduceForDSeparation (const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
	Barren-node pruning relative to the interest set (X \cup Y \cup Z).
static NodeSet	findBarrenNodes (const DAG &dag, const NodeSet &evidenceZ, const NodeSet &targetsXY)
	Compute barren nodes given evidence and targets.
static bool	isAncestorOf (const DAG &dag, NodeId x, NodeId y)
	Is x an ancestor of y?
static bool	isDescendantOf (const DAG &dag, NodeId x, NodeId y)
	Is x a descendant of y?

Static Private Member Functions
static bool	anyUndirectedConnection (const UndiGraph &ug, const NodeSet &A, const NodeSet &B)
	Check if any node in A is undirected-connected to any node in B.

Detailed Description

Consolidated d-separation utilities (DAG-centric).

High-level helpers to test (conditional) independence in directed acyclic graphs (DAGs) using the d-separation criterion. Wherever possible, this class delegates to aGrUM-provided primitives and mirrors pyAgrum semantics.

C++ ↔ pyAgrum correspondence

isDSeparated ⇨ isDSep / isDSep_tech2
isBackdoorSeparated ⇨ isDSep_parents / _isDSep_tech2_parents
isForwardSeparated ⇨ _isDSep_tech2_children
reduceForDSeparation ⇨ dSep_reduce (uses _barren_nodes)
findBarrenNodes ⇨ _barren_nodes
isAncestorOf ⇨ _is_ascendant
isDescendantOf ⇨ _is_descendant
anyUndirectedConnection ⇨ _is_path_x_y (internal helper)

Definition at line 75 of file separation.h.

Member Function Documentation

◆ anyUndirectedConnection()

bool gum::Separation::anyUndirectedConnection	(	const UndiGraph &	ug,
		const NodeSet &	A,
		const NodeSet &	B )

staticprivate

Check if any node in A is undirected-connected to any node in B.

Pyagrum counterpart: _is_path_x_y.

Parameters

ug	An undirected graph (usually a moralized ancestral graph).
A	First node set.
B	Second node set.

Returns: true iff there exists an undirected path between some a ∈ A and some b ∈ B in ug.

Definition at line 217 of file separation.cpp.

                                                                                                 {
    return graph::areConnected(ug, A, B);
  }

References gum::graph::areConnected().

Referenced by isForwardSeparated().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findBarrenNodes()

NodeSet gum::Separation::findBarrenNodes	(	const DAG &	dag,
		const NodeSet &	evidenceZ,
		const NodeSet &	targetsXY )

static

Compute barren nodes given evidence and targets.

Pyagrum counterpart: _barren_nodes.

Thin wrapper over BarrenNodesFinder::barrenNodes().

Parameters

dag	The causal DAG.
evidenceZ	Evidence/conditioning set Z.
targetsXY	Union of target nodes (typically (X \cup Y)).

Returns: Set of barren nodes that can be pruned without affecting d-sep.

Implementation note: Conservative stand-in: nodes outside Anc(X∪Y∪Z) are "barren" for our purpose. If BarrenNodesFinder::barrenNodes() is available, you can implement this as a thin wrapper around it.

Definition at line 182 of file separation.cpp.

                                                                {
    gum::BarrenNodesFinder finder(&dag);
    finder.setTargets(&targetsXY);
    finder.setEvidence(&evidenceZ);
    return finder.barrenNodes();
  }

References gum::BarrenNodesFinder::barrenNodes(), gum::BarrenNodesFinder::setEvidence(), and gum::BarrenNodesFinder::setTargets().

Here is the call graph for this function:

◆ isAncestorOf()

bool gum::Separation::isAncestorOf	(	const DAG &	dag,
		NodeId	x,
		NodeId	y )

static

Is x an ancestor of y?

Pyagrum counterpart: _is_ascendant.

Parameters

dag	The causal DAG.
x	Candidate ancestor.
y	Candidate descendant.

Returns: true iff (x \in \mathrm{Anc}(y)).

Definition at line 198 of file separation.cpp.

                                                                  {
    return dag.ancestors(y).contains(x);
  }

References gum::DiGraph::ancestors(), and gum::Set< Key >::contains().

Here is the call graph for this function:

◆ isBackdoorSeparated()

bool gum::Separation::isBackdoorSeparated	(	const DAG &	dag,
		const NodeSet &	X,
		const NodeSet &	Y,
		const NodeSet &	Z )

static

Backdoor-style restriction: only paths whose first edge points into X.

Pyagrum counterpart: isDSep_parents / _isDSep_tech2_parents.

Semantics: tests whether Z blocks all paths from Y to X that enter X via an incoming edge (the “backdoor graph” (G_{\underline{X}})).

Implementation:

Copy dag to g.
For each (x \in X), erase every outgoing arc (x \to c) in g.
Return g.dSeparation(X, Y, Z).

Parameters

dag	The causal DAG.
X	Set of “treatment” nodes (incoming-edge focus).
Y	Set of outcome nodes.
Z	Conditioning set.

Returns: true iff Z d-separates X and Y in the backdoor graph (G_{\underline{X}}).

Definition at line 91 of file separation.cpp.

                                                         {
    // Build G_{\underline X}: remove all outgoing arcs from X
    DAG g = dag;
 
    for (auto x: X) {
      // collect children first, then erase (avoid iterator invalidation)
      std::vector< NodeId > ch;
      ch.reserve(g.children(x).size());
      for (auto c: g.children(x))
        ch.push_back(c);
 
      for (auto c: ch) {
        if (g.existsArc(x, c)) g.eraseArc(gum::Arc(x, c));
      }
    }
 
    // Now test standard d-separation in G_{\underline X}
    return g.dSeparation(X, Y, Z);
  }

References gum::ArcGraphPart::children(), gum::DAG::dSeparation(), gum::ArcGraphPart::eraseArc(), gum::ArcGraphPart::existsArc(), and gum::Set< Key >::size().

Referenced by gum::CausalImpact< GUM_ELEMENT >::_namesToIds_(), gum::DoorCriteria::enumerateBackdoorSets(), gum::DoorCriteria::enumerateFrontdoorSets(), gum::DoorCriteria::hasBackdoorPath(), gum::DoorCriteria::satisfiesBackdoorCriterion(), and gum::DoorCriteria::satisfiesFrontdoorCriterion().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isDescendantOf()

bool gum::Separation::isDescendantOf	(	const DAG &	dag,
		NodeId	x,
		NodeId	y )

static

Is x a descendant of y?

Pyagrum counterpart: _is_descendant.

Parameters

dag	The causal DAG.
x	Candidate descendant.
y	Candidate ancestor.

Returns: true iff (x \in \mathrm{Desc}(y)).

Definition at line 205 of file separation.cpp.

                                                                    {
    return dag.descendants(y).contains(x);
  }

References gum::Set< Key >::contains(), and gum::DiGraph::descendants().

Here is the call graph for this function:

◆ isDSeparated()

bool gum::Separation::isDSeparated	(	const DAG &	dag,
		const NodeSet &	X,
		const NodeSet &	Y,
		const NodeSet &	Z )

static

Test ( X \perp!!!\perp Y \mid Z ) (general d-separation).

Pyagrum counterpart: isDSep (delegates to isDSep_tech2).

Delegates to DAG::dSeparation, which:

Builds the moralized ancestral graph of (X \cup Y \cup Z).
Removes nodes in (Z).
Checks undirected connectivity between (X) and (Y).

Parameters

dag	The causal DAG.
X	Set of source nodes.
Y	Set of target nodes.
Z	Conditioning set.

Returns: true iff (X) is d-separated from (Y) given (Z) in dag.

Definition at line 80 of file separation.cpp.

                                                  {
    // delegate directly to aGrUM's built-in d-separation
    return dag.dSeparation(X, Y, Z);
  }

References gum::DAG::dSeparation().

Referenced by gum::DoCalculus< GUM_SCALAR >::doCalculusWithObservation().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isForwardSeparated()

bool gum::Separation::isForwardSeparated	(	const DAG &	dag,
		const NodeSet &	X,
		const NodeSet &	Y,
		const NodeSet &	Z )

static

Forward-style restriction: only paths whose first edge leaves X.

Pyagrum counterpart: _isDSep_tech2_children.

Semantics: tests whether Z blocks all paths starting from X via an outgoing edge (children-first restriction used in frontdoor checks).

Outline:

Let interest = Anc(Y ∪ Z). Build the moralized ancestral graph: UndiGraph ug = dag.moralizedAncestralGraph(interest).
Ensure each (x \in X) exists in ug (add isolated node if missing), but do not add (x)–parent links.
For each (x \in X), add an undirected edge (x)—(c) for every child (c) of (x) present in ug.
Remove all nodes in (Z) from ug.
Return true iff there is no undirected path between any node in X and any node in Y.

Parameters

dag	The causal DAG.
X	Set of start nodes (outgoing-edge focus).
Y	Set of target nodes.
Z	Conditioning set.

Returns: true iff Z blocks all forward/children paths from X to Y.

Definition at line 117 of file separation.cpp.

                                                        {
    // 1) Moralize only on Anc(Y ∪ Z)
    NodeSet interest = Y;
    for (auto z: Z)
      interest.insert(z);
    UndiGraph ug = dag.moralizedAncestralGraph(interest);
 
    // Ensure nodes in X exist in ug (without adding X—parent edges)
    for (auto x: X)
      if (!ug.existsNode(x)) ug.addNodeWithId(x);
 
    // 2) Add edges X—c for children c of X that are already in ug
    for (auto x: X) {
      for (auto c: dag.children(x)) {
        if (ug.existsNode(c) && !ug.existsEdge(x, c)) ug.addEdge(x, c);
      }
    }
 
    // 3) Remove conditioning nodes Z
    removeConditioningNodes(ug, Z);
 
    // 4) Return true iff there is no undirected path between X and Y
    return !anyUndirectedConnection(ug, X, Y);
  }

References gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), anyUndirectedConnection(), gum::ArcGraphPart::children(), gum::EdgeGraphPart::existsEdge(), gum::NodeGraphPart::existsNode(), gum::Set< Key >::insert(), and gum::DAG::moralizedAncestralGraph().

Here is the call graph for this function:

◆ reduceForDSeparation()

DAG gum::Separation::reduceForDSeparation	(	const DAG &	dag,
		const NodeSet &	X,
		const NodeSet &	Y,
		const NodeSet &	Z )

static

Barren-node pruning relative to the interest set (X \cup Y \cup Z).

Pyagrum counterpart: dSep_reduce (uses _barren_nodes).

Uses BarrenNodesFinder with evidence = Z and targets = X ∪ Y to compute barren nodes, then removes them from a copy of dag.

Parameters

dag	The causal DAG to prune.
X	Source nodes of interest.
Y	Target nodes of interest.
Z	Evidence/conditioning set.

Returns: A reduced DAG with barren nodes removed (safe for d-sep queries).

Definition at line 153 of file separation.cpp.

                                                         {
    // Targets = X ∪ Y
    const NodeSet targets{X + Y};
 
    // Configure finder
    gum::BarrenNodesFinder finder(&dag);
    finder.setTargets(&targets);   // nodes we care about reaching
    finder.setEvidence(&Z);        // observed nodes
 
    // Compute barren nodes and remove them from a copy
    const NodeSet barren = finder.barrenNodes();
    DAG           reduced{dag};
    for (auto n: barren)
      if (reduced.existsNode(n)) reduced.eraseNode(n);
 
    return reduced;
  }

References gum::BarrenNodesFinder::barrenNodes(), gum::DiGraph::eraseNode(), gum::NodeGraphPart::existsNode(), gum::BarrenNodesFinder::setEvidence(), and gum::BarrenNodesFinder::setTargets().

Referenced by gum::DoorCriteria::enumerateBackdoorSets(), gum::DoorCriteria::enumerateFrontdoorSets(), and gum::DoorCriteria::satisfiesFrontdoorCriterion().

Here is the call graph for this function:

Here is the caller graph for this function:

The documentation for this class was generated from the following files:

agrum/CM/tools/separation.h
agrum/CM/tools/separation.cpp

Static Public Member Functions

Static Private Member Functions

Detailed Description

Member Function Documentation

◆ anyUndirectedConnection()

◆ findBarrenNodes()

◆ isAncestorOf()

◆ isBackdoorSeparated()

◆ isDescendantOf()

◆ isDSeparated()

◆ isForwardSeparated()

◆ reduceForDSeparation()