Class ShallowRecursiveBlockingStack

java.lang.Object
edu.cmu.tetrad.search.ShallowRecursiveBlockingStack

public final class ShallowRecursiveBlockingStack extends Object
Explicit-stack (no JVM recursion) port of ShallowRecursiveBlocking (the recursive "near-x" shallow-commit reference).

This is the production form: it walks forward from x to y and conditions on the earliest blockable non-collider on each open path, so the returned conditioning set clusters near x. See ShallowRecursiveBlocking for the full rationale (openness flows back from y, so the scout must still trace to y to establish openness; conditioning on a non-collider opens its collider continuations, which leak toward y; the returned set is not minimal and is not orientation-neutral).

Nothing semantic changes vs. ShallowRecursiveBlocking. The verdict (BLOCKED / UNBLOCKABLE / INDETERMINATE) and the conditioning set are identical; this class exists only so a deep graph cannot raise StackOverflowError. Run both on the same instances and diff the results as a correctness check; pick one for production. The mutual recursion findPath ↔ blockAllContinuations is replaced by an explicit Deque of ShallowRecursiveBlockingStack.Frames. Each frame runs three passes: ENTER (guards, snapshot Z), BRANCH_A (block continuations without b; doubles as the openness probe), BRANCH_B (block continuations with b). The shallow commit rule is the post-BRANCH_A block: if Branch A blocked without growing Z, the path was already closed and b is not added; otherwise the path was open and we prefer to add b (Branch B), falling back to Branch A's deeper solution only if adding b fails.

One difference from RecursiveBlocking's deep stack machine. There, an INDETERMINATE Branch A short-circuits the whole frame. Here it must not: an inconclusive deep result can still be resolved by conditioning on b shallowly, so Branch B is still attempted.

Memoization is intentionally omitted so this stays a 1:1 transcription of the recursive reference (diffable for identical output). The clique-optimization memo is a separate layer; a cache hit returns a verdict without replaying the subtree's Z additions, which needs care to keep the final Z complete — more so here, since the near-x bias grows Z more aggressively.

API. Identical to RecursiveBlocking.blockPathsRecursively(Graph, Node, Node, Set, Set, int, int, int, int, boolean)'s full-parameter signature; returns RecursiveBlocking.BlockingResult.

  • 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, no deadline.
      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.
      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