Package edu.cmu.tetrad.search

Class SepsetFinder

java.lang.Object

edu.cmu.tetrad.search.SepsetFinder

public class SepsetFinder
extends Object

This class provides methods for finding sepsets in a given graph.

Constructor Summary

Constructors

Constructor	Description
SepsetFinder()	Private constructor to prevent instantiation.

Method Summary

Modifier and Type	Method	Description
static Set<List<Node>>	bfsAllPathsOutOfX(Graph graph, Set<Node> conditionSet, Set<Node> couldBeColliders, Set<Node> blacklist, int maxLength, Node x, Node y, boolean allowSelectionBias)	Performs a breadth-first search to find all paths out of a specific node in a graph, considering certain conditions and constraints.
static Set<Node>	blockPathsLocalMarkov(Graph graph, Node x)	Returns a set of nodes that are the parents of the given node in the graph.
static Set<Node>	blockPathsNoncollidersOnly(Graph graph, Node x, Node y, int maxLength, boolean isPag)	Returns a set that blocks all paths that can be blocked by conditioning on noncolliders only, searching outward from x.
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 Set<Node>	blockPathsWithMarkovBlanket(Node x, Graph G)	Identifies the set of nodes that form the Markov Blanket for a given node in a graph.
static Set<Node>	getPathBlockingSetRecursive(Graph graph, Node x, Node y, Set<Node> containing, int maxPathLength, Set<Node> notFollowing)	Finds a set of nodes that blocks all paths from node x to node y in a graph, considering a maximum path length and a set of nodes that must be included in the blocking set.
static Set<Node>	getSepsetContainingGreedy(Graph graph, Node x, Node y, Set<Node> containing, IndependenceTest test, int depth)	Returns the sepset that contains the greedy test for variables x and y in the given graph.
static Set<Node>	getSepsetContainingMaxPHybrid(Graph graph, Node x, Node y, Set<Node> containing, IndependenceTest test, int depth)	Returns the set of nodes that act as a separating set between two given nodes (x and y) in a graph.
static Set<Node>	getSepsetContainingMinPHybrid(Graph graph, Node x, Node y, Set<Node> containing, IndependenceTest test, int depth)	Returns the sepset containing the minimum p-value for the given variables x and y.
static Set<Node>	getSepsetPathBlockingOutOfX(Graph mpdag, Node x, Node y, IndependenceTest test, int maxLength, int depth, boolean allowSelectionBias, Set<Node> blacklist)	Calculates the sepset path blocking out-of operation for a given pair of nodes in a graph.
static Set<Node>	getSmallestSubset(Node x, Node y, Set<Node> blocking, Set<Node> containing, Graph graph, boolean isPag)	Finds a smallest subset S of blocking that renders two nodes x and y conditionally d-separated conditional on S in the given graph.

Methods inherited from class java.lang.Object

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

Constructor Details

SepsetFinder

public SepsetFinder()

Private constructor to prevent instantiation.

Method Details

getSepsetContainingGreedy

public static Set<Node> getSepsetContainingGreedy(Graph graph,
 Node x,
 Node y,
 Set<Node> containing,
 IndependenceTest test,
 int depth)

Returns the sepset that contains the greedy test for variables x and y in the given graph.

Parameters:

graph - the graph containing the variables

x - the first variable

y - the second variable

containing - the set of nodes that must be contained in the sepset (optional)

test - the independence test to use

depth - the depth of the search

Returns:

the sepset containing the greedy test for variables x and y, or null if no sepset is found

getSepsetContainingMaxPHybrid

public static Set<Node> getSepsetContainingMaxPHybrid(Graph graph,
 Node x,
 Node y,
 Set<Node> containing,
 IndependenceTest test,
 int depth)
                                               throws InterruptedException

Returns the set of nodes that act as a separating set between two given nodes (x and y) in a graph. The method calculates the p-value for each possible separating set and returns the set that has the maximum p-value above the specified alpha threshold.

Parameters:

graph - the graph containing the nodes

x - the first node

y - the second node

containing - the set of nodes that must be included in the separating set (optional, can be null)

test - the independence test used to calculate the p-values

depth - the maximum depth to explore for each separating set

Returns:

the set of nodes that act as a separating set, or null if such set is not found

Throws:

InterruptedException

getSepsetContainingMinPHybrid

public static Set<Node> getSepsetContainingMinPHybrid(Graph graph,
 Node x,
 Node y,
 Set<Node> containing,
 IndependenceTest test,
 int depth)
                                               throws InterruptedException

Returns the sepset containing the minimum p-value for the given variables x and y.

Parameters:

graph - the graph representing the network

x - the first node

y - the second node

containing - the set of nodes to be excluded from the sepset

test - the independence test to use for calculating the p-value

depth - the depth of the search for the sepset

Returns:

the sepset containing the minimum p-value, or null if no sepset is found

Throws:

InterruptedException

blockPathsLocalMarkov

public static Set<Node> blockPathsLocalMarkov(Graph graph,
 Node x)

Returns a set of nodes that are the parents of the given node in the graph.

Parameters:

graph - the graph containing the nodes and edges

x - the node whose parent nodes are to be found

Returns:

a set of nodes that are the parents of the given node

blockPathsRecursively

public 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.

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.

getPathBlockingSetRecursive

public static Set<Node> getPathBlockingSetRecursive(Graph graph,
 Node x,
 Node y,
 Set<Node> containing,
 int maxPathLength,
 Set<Node> notFollowing)

Finds a set of nodes that blocks all paths from node x to node y in a graph, considering a maximum path length and a set of nodes that must be included in the blocking set.

Parameters:

graph - The graph containing the nodes.

x - The starting node of the path.

y - The ending node of the path.

containing - The set of nodes that must be included in the blocking set.

maxPathLength - The maximum length of the paths to consider.

notFollowing - A set of notes that should not be followed along paths.

Returns:

A set of nodes that blocks all paths from node x to node y, or null if no such set exists.

blockPathsNoncollidersOnly

public static Set<Node> blockPathsNoncollidersOnly(Graph graph,
 Node x,
 Node y,
 int maxLength,
 boolean isPag)

Returns a set that blocks all paths that can be blocked by conditioning on noncolliders only, searching outward from x.

Parameters:

graph - The graph representing the Markov equivalence class that contains the nodes.

x - The first node in the pair.

y - The second node in the pair.

maxLength - The maximum length of the paths to consider. If set to a negative value or a value greater than the number of nodes minus one, it is adjusted accordingly.

isPag - A flag indicating whether the graph is a PAG or a CPDAG, true = PAG, false = MPDAG. This is needed to make sure the proper version of the separation algorithm is used.

Returns:

A set of nodes that can block all blockable paths from x to y that can be blocked with noncolliders only, or null if no such set exists.

getSmallestSubset

public static Set<Node> getSmallestSubset(Node x,
 Node y,
 Set<Node> blocking,
 Set<Node> containing,
 Graph graph,
 boolean isPag)

Finds a smallest subset S of blocking that renders two nodes x and y conditionally d-separated conditional on S in the given graph. (There may be more than one smallest subset; only one is returned.)

Parameters:

x - the first node.

y - the second node.

blocking - the initial set of blocking nodes; this may not be a sepset.

containing - a set of nodes that must be contained in the sepset.

graph - the graph containing the nodes.

isPag - true if the graph is a PAG (Partial Ancestral Graph), false otherwise.

Returns:

the smallest set of nodes that renders x and y conditionally independent.

blockPathsWithMarkovBlanket

public static Set<Node> blockPathsWithMarkovBlanket(Node x,
 Graph G)

Identifies the set of nodes that form the Markov Blanket for a given node in a graph.

Parameters:

x - The node for which the Markov Blanket is to be identified.

G - The graph containing the node and its relationships.

Returns:

A set of nodes that form the Markov Blanket of the specified node.

getSepsetPathBlockingOutOfX

public static Set<Node> getSepsetPathBlockingOutOfX(Graph mpdag,
 Node x,
 Node y,
 IndependenceTest test,
 int maxLength,
 int depth,
 boolean allowSelectionBias,
 Set<Node> blacklist)
                                             throws InterruptedException

Calculates the sepset path blocking out-of operation for a given pair of nodes in a graph. This method searches for m-connecting paths out of x and y, and then tries to block these paths by conditioning on definite noncollider nodes. If all paths are blocked, the method returns the sepset; otherwise, it returns null. The length of the paths to consider can be limited by the maxLength parameter, and the depth of the final sepset can be limited by the depth parameter. When increasing the considered path length does not yield any new paths, the search is terminated early.

Parameters:

mpdag - The graph representing the Markov equivalence class that contains the nodes.

x - The first node in the pair.

y - The second node in the pair.

test - The independence test object to use for checking independence.

maxLength - The maximum length of the paths to consider. If set to a negative value or a value greater than the number of nodes minus one, it is adjusted accordingly.

depth - The maximum depth of the final sepset. If set to a negative value, no limit is applied.

allowSelectionBias - A boolean flag indicating whether to allow selection bias.

blacklist - The set of nodes to blacklist.

Returns:

The sepset if independence holds, otherwise null.

Throws:

InterruptedException

bfsAllPathsOutOfX

public static Set<List<Node>> bfsAllPathsOutOfX(Graph graph,
 Set<Node> conditionSet,
 Set<Node> couldBeColliders,
 Set<Node> blacklist,
 int maxLength,
 Node x,
 Node y,
 boolean allowSelectionBias)

Performs a breadth-first search to find all paths out of a specific node in a graph, considering certain conditions and constraints.

Parameters:

graph - the graph to search

conditionSet - the set of nodes that need to be conditioned on

couldBeColliders - the set of nodes that could potentially be colliders

blacklist - the set of nodes to exclude from the search

maxLength - the maximum length of the paths (-1 for unlimited)

x - the starting node

y - the destination node

allowSelectionBias - flag to indicate whether to allow selection bias in path selection

Returns:

a set of all paths that satisfy the conditions and constraints

Throws:

IllegalArgumentException - if the conditioning set is null