Class ShallowRecursiveBlockingStack
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 Summary
Modifier and TypeMethodDescriptionblockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int recursiveDepth, int depth, int maxRadius, int nearWhichEndpoint, boolean ignoreDirectEdge) Shallow ("near-x") separating-set search, no deadline.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) Shallow ("near-x") separating-set search.
-
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 graphx- first endpointy- second endpointcontaining- nodes forced into Z (the seed set)notFollowed- nodes not to be traversedrecursiveDepth- 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 bothignoreDirectEdge- whether to ignore the direct x–y edge- Returns:
- a
RecursiveBlocking.BlockingResultdescribing 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 graphx- first endpointy- second endpointcontaining- nodes forced into Z (the seed set)notFollowed- nodes not to be traversedrecursiveDepth- 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 bothignoreDirectEdge- whether to ignore the direct x–y edgedeadlineMs- deadline for the operation (in ms)- Returns:
- a
RecursiveBlocking.BlockingResultdescribing the outcome - Throws:
InterruptedException- if the thread is interrupted
-