Class ShallowRecursiveBlocking

java.lang.Object
edu.cmu.tetrad.search.ShallowRecursiveBlocking
public final class ShallowRecursiveBlocking extends Object
Shallow-commit ("near-x") variant of RecursiveBlocking.

RecursiveBlocking walks forward from x toward y and prefers to discharge each open path as deep as possible: at an intermediate node b it first tries to block all continuations without b (pushing the block toward y), and only conditions on b when nothing past b can close the path. The result is a conditioning set that clusters near y.

This class keeps the forward walk x → y identical but flips the commit preference: at each intermediate node b it prefers to condition on b itself (the shallow, near-x node) as soon as it has established that a path through b is open. Only the placement of conditioning nodes changes; the set of paths explored, and the three-valued verdict (BLOCKED / UNBLOCKABLE / INDETERMINATE), are the same disjunction over the two branches as in RecursiveBlocking.

Why the walk cannot become lazy. Openness flows backward from y: a prefix x⋯b is open iff it extends to an active path that actually reaches y, and that cannot be read off locally at b. So the scout still has to walk all the way to y to learn whether b needs blocking at all. It just commits near x once openness is established, rather than near y.

The openness probe is folded into Branch A. Running BlockAllContinuations without b both checks openness and (on the deep version) would block the path. We exploit a monotonicity fact: that call only ever adds to Z, and it adds something iff there was a genuinely open path through b that had to be blocked. Hence "Branch A returned BLOCKED and Z did not grow" is exactly "the path through b was already closed — do not condition on b". When Z did grow (or Branch A failed), the path was open; we roll back Branch A's deeper additions and prefer to add b instead. A merely-reachable continuation that never reaches y adds nothing, so it is correctly treated as "already closed" — this is why a naive "are there reachable continuations?" test would be wrong and the Z-growth test is right.

Caveats (all inherent, not artifacts of this implementation):

  • The clustering is not pure. Conditioning on a non-collider b blocks its non-collider continuations but opens its collider continuations, which must then be blocked deeper — toward y. So a near-x set still leaks a tail toward y wherever colliders sit on the open paths. (RecursiveBlocking's reverse-role trick has the same leak, mirrored.)
  • Larger sets, more work. This variant always runs Branch A (for openness) and usually Branch B as well, whereas the deep version often stops after Branch A. Worse, adding b near x activates colliders that are ancestors of b, which can spawn new active first-hops in the driver's fixed-point loop. It is structurally more exposed to combinatorial blow-up than the deep version. The returned set is not minimal.
  • Not orientation-neutral. The returned set is a sepset, and FCI orients b as a collider on a *-* b *-* c exactly when b ∉ sepset(a, c). A near-x set and a near-y set can disagree on whether a given b is included even when both genuinely m-separate, so they can yield different colliders and different PAGs. Switch deliberately, and re-check any downstream legality/maximality argument that leaned on the deep-set structure.

Implementation note. Unlike RecursiveBlocking, which uses an explicit stack to avoid StackOverflowError on deep graphs, this class is written as straightforward mutual recursion (findPathShallow ↔ blockAllContinuations) so the shallow commit rule is easy to read and validate against Procedures 1–3 of the paper. Recursion depth is bounded by recursiveDepth (≤ number of nodes), which is fine for typical FCI/FCIT use; for very deep graphs, port this to the explicit-stack machine in RecursiveBlocking (the openness/commit split has to thread across the ENTER / WITHOUT_B / WITH_B passes).

API. Mirrors RecursiveBlocking.blockPathsRecursively(Graph, Node, Node, Set, Set, int, int, int, int, boolean)'s full-parameter signature and returns the same RecursiveBlocking.BlockingResult record, so it is a drop-in alternative at call sites that already consume that type. Only the RECURSIVE-style depth-first strategy is provided; an iterative-deepening or BFS wrapper can be added exactly as in RecursiveBlocking if wanted.

  • Method Details

    • 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
      Shallow ("near-x") separating-set search between x and y, with no deadline. See blockPathsRecursively(Graph, Node, Node, Set, Set, int, int, int, int, boolean, long).
      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 - maximum recursion depth (-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
      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) throws InterruptedException
      Shallow ("near-x") separating-set search between x and y.

      Walks forward from x to y (never reversing roles) and conditions on the earliest blockable non-collider on each open path, so the returned conditioning set clusters near x. Returns a full RecursiveBlocking.BlockingResult distinguishing UNBLOCKABLE (proven no separator within the structure) from INDETERMINATE (a search limit was hit). A timeout is reported as 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 - maximum recursion depth (-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