Package edu.cmu.tetrad.search

Class RecursiveBlocking

java.lang.Object

edu.cmu.tetrad.search.RecursiveBlocking

public class RecursiveBlocking
extends Object

The RecursiveBlocking class implements a recursive procedure for constructing candidate separating sets between two nodes under PAG semantics.

Given distinct nodes x and y, the algorithm attempts to build a set Z that blocks all blockable paths between x and y, starting from an optional seed set of nodes to include. If such a set is found, it is returned and may later be tested against the distribution for conditional independence. If any path is provably un-blockable (or the analysis is interrupted or inconclusive), the routine returns null, indicating that no valid graphical separating set exists.

Key features:

• Respects PAG semantics for colliders, non-colliders, and latent nodes.
• Supports path length limits and "do not follow" constraints.
• Can be run with or without background knowledge (currently unused, but supported for extension).
• Returns a candidate blocking set agnostic to adjacency: the presence of a direct edge x–y does not preempt construction, but such an edge may prevent a valid separator from existing.

In the context of FCIT and related algorithms, the returned set is always subject to a statistical independence test to confirm whether it functions as an actual separating set in the distribution.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	RecursiveBlocking.Blockable	The Blockable enum represents the state of an entity in relation to its ability to be blocked.

Method Summary

Modifier and Type	Method	Description
static Set<Node>	blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int maxPathLength)	Attempts to construct a candidate blocking set Z between nodes x and y under PAG semantics.
static Set<Node>	blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int maxPathLength, Knowledge knowledge)	Variant of blockPathsRecursively(Graph, Node, Node, Set, Set, int) that additionally accepts an optional Knowledge object.
static RecursiveBlocking.Blockable	findPathToTarget(Graph graph, Node a, Node b, Node y, Set<Node> path, Set<Node> z, int maxPathLength, Set<Node> notFollowed, Map<Node,Set<Node>> descendantsMap)	Evaluates whether all paths from a→b onward to y can be blocked by the current candidate set Z, possibly augmented with b.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

blockPathsRecursively

public static Set<Node> blockPathsRecursively(Graph graph,
 Node x,
 Node y,
 Set<Node> containing,
 Set<Node> notFollowed,
 int maxPathLength)
                                       throws InterruptedException

Attempts to construct a candidate blocking set Z between nodes x and y under PAG semantics. The returned set Z contains the nodes in containing and is augmented as needed to block all blockable paths from x to y, ignoring any direct edge x–y on the first step.

Semantics:

• If x and y are adjacent, this method does not produce a separating set (returns null).
• If x and y are not adjacent, the routine returns a candidate blocking set Z if all blockable paths can be blocked. This set is only a graphical sepset and must be validated with an independence test.
• If some path is un-blockable or the recursion is indeterminate (e.g., interrupted or exceeds maxPathLength), the method returns null.

Parameters:

graph - the PAG structure

x - first endpoint

y - second endpoint

containing - nodes that must be included in the blocking set

notFollowed - nodes that should not be traversed into

maxPathLength - maximum allowed path length (-1 for unlimited)

Returns:

a candidate blocking set Z if all blockable paths can be blocked, or null if no valid graphical separating set exists

Throws:

InterruptedException - if the search is interrupted

blockPathsRecursively

public static Set<Node> blockPathsRecursively(Graph graph,
 Node x,
 Node y,
 Set<Node> containing,
 Set<Node> notFollowed,
 int maxPathLength,
 Knowledge knowledge)
                                       throws InterruptedException

Variant of blockPathsRecursively(Graph, Node, Node, Set, Set, int) that additionally accepts an optional Knowledge object.

Currently, the knowledge argument is reserved for future extensions and is not applied in this routine, but it is passed along to maintain compatibility with knowledge-aware search strategies.

Parameters:

graph - the PAG structure

x - first endpoint

y - second endpoint

containing - nodes that must be included in the blocking set

notFollowed - nodes that should not be traversed into

maxPathLength - maximum allowed path length (-1 for unlimited)

knowledge - optional background knowledge (currently unused here)

Returns:

a candidate blocking set Z if all blockable paths can be blocked, or null if no valid graphical separating set exists

Throws:

InterruptedException - if the search is interrupted

findPathToTarget

public static RecursiveBlocking.Blockable findPathToTarget(Graph graph,
 Node a,
 Node b,
 Node y,
 Set<Node> path,
 Set<Node> z,
 int maxPathLength,
 Set<Node> notFollowed,
 Map<Node,Set<Node>> descendantsMap)
                                                    throws InterruptedException

Evaluates whether all paths from a→b onward to y can be blocked by the current candidate set Z, possibly augmented with b.

The method explores continuations from the triple (a, b, c) under PAG semantics and returns one of three outcomes:

• BLOCKED — all continuations through b are blocked given the current Z (with or without conditioning on b).
• UNBLOCKABLE — some continuation cannot be blocked even after adding b to Z.
• INDETERMINATE — traversal was aborted (interrupted or path length exceeded) or could not be decided safely.

Special cases:

• If b == y, the path immediately certifies as UNBLOCKABLE.
• If b has already been visited in the current path, it is treated as UNBLOCKABLE (cycle guard).
• If b is in notFollowed, the branch is aborted as INDETERMINATE.
• If y is in notFollowed, that branch is treated as BLOCKED (refusing to follow into y cannot make paths less blockable).

Traversal policy:

1. If b is latent or already in Z, traversal continues without conditioning on b.
2. Otherwise, the method first tries to block without conditioning on b. If that fails, it retries with b added to Z, rolling back if this does not succeed.

Path bookkeeping: after adding b to the current path, this method guarantees that b is removed again before returning.

Parameters:

graph - the PAG structure

a - predecessor node in the path

b - current node under consideration

y - target node to be separated from x

path - nodes visited so far (cycle guard)

z - current candidate blocking set

maxPathLength - maximum allowed path length (-1 for unlimited)

notFollowed - nodes not to be traversed into

descendantsMap - precomputed node→descendants map (for collider checks)

Returns:

one of BLOCKED, UNBLOCKABLE, or INDETERMINATE

Throws:

InterruptedException - if the traversal is interrupted