Package edu.cmu.tetrad.search

Class RecursiveBlocking

java.lang.Object

edu.cmu.tetrad.search.RecursiveBlocking

public class RecursiveBlocking
extends Object

The RecursiveBlocking class provides methods for assessing the blockability of paths in a graph based on specified conditions. It includes recursive mechanisms to determine whether specific sets of nodes can block paths and prevent certain graph traversal directions. This class is utilized in graph analysis to evaluate separation criteria, particularly in directed acyclic graphs (DAGs).

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	RecursiveBlocking.Blockable	Enum representing the blocking status for graph-path-related operations in the RecursiveBlocking class.

Method Summary

Modifier and Type	Method	Description
static Set<Node>	blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int maxPathLength)	Retrieves set that blocks all blockable paths between x and y in the given graph, where this set contains the given nodes.
static RecursiveBlocking.Blockable	findPathToTarget(Graph graph, Node a, Node b, Node y, Set<Node> path, Set<Node> z, int maxPathLength, Set<Node> notFollowed, Map<Node,Set<Node>> ancestorMap)	Finds a path from node a to node b that can be blocked by conditioning on a set of nodes z.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

blockPathsRecursively

public static Set<Node> blockPathsRecursively(Graph graph,
 Node x,
 Node y,
 Set<Node> containing,
 Set<Node> notFollowed,
 int maxPathLength)
                                       throws InterruptedException

Retrieves set that blocks all blockable paths between x and y in the given graph, where this set contains the given nodes.

Parameters:

graph - the graph to analyze

x - the first node

y - the second node

containing - the set of nodes that must be in the sepset

notFollowed - the set of nodes that should not be followed along paths

maxPathLength - the maximum length of a path to consider

Returns:

the sepset of the endpoints for the given edge in the DAG graph based on the specified conditions, or null if no sepset can be found.

Throws:

InterruptedException - if any.

findPathToTarget

public static RecursiveBlocking.Blockable findPathToTarget(Graph graph,
 Node a,
 Node b,
 Node y,
 Set<Node> path,
 Set<Node> z,
 int maxPathLength,
 Set<Node> notFollowed,
 Map<Node,Set<Node>> ancestorMap)
                                                    throws InterruptedException

Finds a path from node a to node b that can be blocked by conditioning on a set of nodes z. The method returns true if the path can be blocked, and false otherwise.

The side effects of this method are changes to z and colliders; this method is private, and the public methods that call it are responsible for handling these side effects.

Parameters:

graph - The graph containing the nodes.

a - The first node in the pair.

b - The second node in the pair.

y - The target node.

path - The current path.

z - The set of nodes that can block the path. This is a set of conditioning nodes that is being built.

maxPathLength - The maximum length of the paths to consider.

notFollowed - A set of nodes that should not be followed along paths.

ancestorMap - Map used to check to see if descendants of colliders are conditioned on.

Returns:

True if the path can be blocked.

Throws:

InterruptedException - if any.