Class RecursiveBlocking

java.lang.Object
edu.cmu.tetrad.search.RecursiveBlocking
public class RecursiveBlocking extends Object
Implements a procedure for constructing candidate separating sets between two nodes under PAG semantics.

This version replaces the mutual recursion between findPathToTargetVisit and tryBlockAllContinuations with an explicit stack, eliminating the risk of StackOverflowError on deep graphs. All semantics are identical to the original recursive version.

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 unblockable, or the analysis is interrupted or inconclusive, the routine returns null, indicating that no valid graphical separating set was found within the given constraints.

The eligible conditioning nodes are drawn from BFS shells of radius maxRadius around x and/or y, controlled by nearWhichEndpoint:

  • 1 — pool drawn from shells around x only
  • 2 — pool drawn from shells around y only
  • 3 — pool drawn from shells around both x and y (union)

A node outside the pool that would otherwise be required to block a path causes that branch to return INDETERMINATE rather than UNBLOCKABLE, so the overall call returns null without asserting that no separator exists at all — a wider radius might succeed. When maxRadius is -1 the pool is unrestricted and all graph nodes are eligible. A depth parameter additionally caps the total size of Z; attempts to exceed it are likewise treated as INDETERMINATE.

Continuation memoization (clique optimization). Within a single findPathToTargetVisit call, the verdict for a frame is, in the common case, a pure function of the incoming pair (a, b) and the conditioning set z in effect at frame entry: reachable inspects only the triple (a, b, c) and z, so two frames that arrive at the same b from the same a under the same entry z explore identical continuations and reach the same verdict. This recurs heavily inside cliques, where many distinct path prefixes converge on the same node. We cache such verdicts keyed on (a, b, z) and reuse them on later arrivals.

The cache is not a pure function of (a, b, z) in one situation: a frame can return BLOCKED early because its node already lies on the current path (a cycle hit). That verdict is an artifact of where we came from, not an intrinsic property of (a, b, z), so it must never be cached, and any ancestor frame whose verdict was computed using such a child verdict must also not be cached. We track this with a pathTainted flag that propagates from child to parent. Only untainted, non-INDETERMINATE verdicts are stored. INDETERMINATE verdicts are never cached because they reflect a search-limit (recursion depth, frame cap) rather than a graph fact, and could resolve differently in another context.

The cache lives for the duration of one findPathToTargetVisit call. It is deliberately not shared across the outer fixed-point iterations in blockPathsRecursivelyAdj, nor across first hops, because z grows between those calls and a per-call cache keeps every key consistent with the z actually in effect when the frame was entered. The clique redundancy Bryan identified occurs entirely within a single DFS call, so this scoping captures the win while keeping the correctness argument simple.

Key features:

  • Respects PAG semantics for colliders, non-colliders, and latent nodes.
  • Uses an outer fixed-point loop to handle colliders activated by Z growth across branches.
  • Supports recursion depth limits, depth limits, radius limits, and "do not follow" constraints.
  • Background knowledge parameter is reserved for future extension.
  • The presence of a direct edge x–y does not preempt construction, but such an edge may prevent a valid separator from existing.
  • The returned set is always subject to a statistical independence test to confirm it functions as an actual separating set in the distribution.

  • Field Details

    • DEFAULT_STRATEGY

      public static RecursiveBlocking.Strategy DEFAULT_STRATEGY
      The default strategy used for processing or executing tasks in the system. This is a globally accessible constant that indicates the predefined approach, which is set to a recursive strategy. It can be utilized wherever a default execution policy is required.

  • Method Details

    • beginConflictCollection

      public static void beginConflictCollection()
      Begins collecting load-bearing blocked-collider marks on this thread. Every blocking call on this thread records into the same set until endConflictCollection() is called.

    • endConflictCollection

      public static Set<RecursiveBlocking.Mark> endConflictCollection()
      Ends collection on this thread and returns the marks recorded since beginConflictCollection().
      Returns:
      the recorded marks, in first-encountered order; empty if none.

    • blockPathsRecursively

      public static RecursiveBlocking.BlockingResult blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int recursiveDepth, int depth, int maxRadius, int nearWhichEndpoint, boolean ignoreDirectEdge) throws InterruptedException
      Recursively blocks paths in a graph between two nodes based on specified parameters and constraints.
      Parameters:
      graph - The graph in which the paths are to be blocked.
      x - The starting node of the path.
      y - The ending node of the path.
      containing - A set of nodes that must be included in the path.
      notFollowed - A set of nodes that must not be followed in the path.
      recursiveDepth - The maximum depth for recursion during the path blocking process.
      depth - The current depth of the recursive call.
      maxRadius - The maximum radius from the starting node to consider for path blocking.
      nearWhichEndpoint - Determines near which endpoint of the path the restriction is to be enforced.
      ignoreDirectEdge - A flag indicating whether to ignore direct edges between the starting node and ending node.
      Returns:
      A BlockingResult object containing the results of the path blocking operation.
      Throws:
      InterruptedException - If the operation is interrupted during execution.

    • blockPathsRecursively

      public static RecursiveBlocking.BlockingResult blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int recursiveDepth, int depth, int maxRadius, int nearWhichEndpoint, boolean ignoreDirectEdge, long deadlineMs) throws InterruptedException
      Single canonical entry point for separating-set search.

      Dispatches to blockPathsRecursivelyFull(Graph, Node, Node, Set, Set, int, int, int, int, boolean) (depth-first with backtracking) or blockPathsIterativeDeepening(Graph, Node, Node, Set, Set, int, int, int, int, boolean) (iterative deepening on recursion depth) based on strategy, and returns a full RecursiveBlocking.BlockingResult distinguishing UNBLOCKABLE from INDETERMINATE.

      Parameters:
      graph - the graph
      x - first endpoint
      y - second endpoint
      containing - nodes forced into Z (the seed set)
      notFollowed - nodes not to be traversed
      recursiveDepth - max recursion depth for RECURSIVE; ceiling for ITERATIVE_DEEPENING (-1 = graph.getNumNodes())
      depth - maximum size of Z (-1 = unlimited)
      maxRadius - BFS radius for the node pool (-1 = unlimited)
      nearWhichEndpoint - 1 = near x, 2 = near y, 3 = near both
      ignoreDirectEdge - whether to ignore the direct x–y edge
      deadlineMs - deadline for the operation (in ms)
      Returns:
      a RecursiveBlocking.BlockingResult describing the outcome
      Throws:
      InterruptedException - if the thread is interrupted

    • blockPathsRecursively

      public static RecursiveBlocking.BlockingResult blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int recursiveDepth, int depth, int maxRadius, int nearWhichEndpoint, boolean ignoreDirectEdge, long deadlineMs, RecursiveBlocking.Strategy strategy) throws InterruptedException
      Blocks paths in a graph recursively based on the given parameters and strategy.
      Parameters:
      graph - the graph in which paths are to be blocked
      x - the starting node for path blocking
      y - the ending node for path blocking
      containing - the set of nodes that paths must contain
      notFollowed - the set of nodes that paths must not include
      recursiveDepth - the current recursive depth of the process
      depth - the depth of the search
      maxRadius - the maximum radius for path blocking consideration
      nearWhichEndpoint - specifies which endpoint (x or y) the operation is near, influencing behavior
      ignoreDirectEdge - whether to ignore the direct edge between x and y
      deadlineMs - the time limit in milliseconds for the operation
      strategy - the strategy to use for blocking paths (e.g., ITERATIVE_DEEPENING, SHALLOW_RECURSIVE, RECURSIVE)
      Returns:
      a BlockingResult object containing the result of the blocking operation and associated metadata
      Throws:
      InterruptedException - if the blocking operation is interrupted