Class ShallowRecursiveBlockingMemo

java.lang.Object
edu.cmu.tetrad.search.ShallowRecursiveBlockingMemo
public final class ShallowRecursiveBlockingMemo extends Object
ShallowRecursiveBlockingStack plus a delta-replay continuation memo.

Same algorithm, same results as the no-memo stack version (and the recursive reference); this class adds the clique optimization that RecursiveBlocking carries, adapted so it is correct for the shallow-commit variant.

Why a delta memo, not a verdict-only memo. RecursiveBlocking caches the verdict alone and, on a hit, returns it without replaying the nodes that the original frame added to Z. That is tolerable for the deep machine, whose commit decision never inspects whether Z grew, but it is unsafe here: the shallow machine's entire "already closed vs. open" decision is the Z-growth signal (Branch A blocked without growing Z ⇒ already closed ⇒ do not condition on b). A verdict-only hit on a child would report BLOCKED with no growth, the parent would read that as "already closed," and a required near-x conditioning node would silently never be added. So we cache the pair (verdict, delta = Z‑added) and, on a hit, do z.addAll(delta) before returning the verdict.

Why delta replay is correct. The key is (a, b, entry‑Z) and we cache only determined verdicts (BLOCKED with its delta, or UNBLOCKABLE with empty delta), never INDETERMINATE. A determined verdict is a depth-independent fact: "Z ∪ delta blocks every b→y continuation" (BLOCKED) or "some continuation is unblockable regardless of Z" (UNBLOCKABLE) holds no matter the arrival depth or the path taken to reach (a, b). Because the key pins entry-Z, a hit means the live Z equals the stored entry-Z, so replaying delta reproduces the original frame's final Z node-for-node — which also keeps the depth cap satisfied (same final size) and preserves the openness signal for the caller.

Taint. The one path-dependent verdict is a cycle hit (b ∈ path ⇒ BLOCKED), which is an artifact of where we came from. Such a verdict, and any ancestor verdict computed using it, must not be cached. A pathTainted flag propagates from a cycle-hit child to its parent and onward; tainted frames are never stored. Taint gates storing only — a cache hit is always safe because stored entries are untainted and therefore path-independent. The flag is single and never reset, so a Branch-A cycle hit conservatively taints a frame even when the final verdict came from Branch B; this matches RecursiveBlocking and keeps the correctness argument simple, at the cost of some cache entries.

Scope. The memo lives for one findPathToTargetVisitShallow call (one first hop, one driver iteration). It is deliberately not shared across first hops or fixed-point iterations, because Z grows between them and a per-call cache keeps every key consistent with the Z in effect when each frame was entered.

The memo must be a pure speedup: results must be identical to ShallowRecursiveBlockingStack on every instance. Any divergence is a memo bug.

  • 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