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 Details

    • SepsetFinder

      public SepsetFinder()
      Private constructor to prevent instantiation.

  • Method Details

    • findSepsetSubsetOfAdjxOrAdjy

      public static Set<Node> findSepsetSubsetOfAdjxOrAdjy(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

    • getSepsetContainingGreedySubsetMb

      public static Set<Node> getSepsetContainingGreedySubsetMb(Graph graph, Graph cpdag, Node x, Node y, Set<Node> containing, IndependenceTest test, int depth)
      Identifies a separating set (sepset) containing a given subset of nodes between two nodes x and y in a graph using a greedy approach and subsets of (adj(x) U adu(y)) \ {x, y}. The method applies constraints such as independence testing, specified node ordering, and optional filtering of certain node types.

      This method mainly focuses on finding a feasible separating set under the given constraints by iterating through node combinations from the union of adjacent nodes of x and y in the graph.

      Parameters:
      graph - The graph in which the nodes and their adjacency relationships are defined.
      cpdag - The CDPDAG.
      x - The first node for which the sepset is being determined.
      y - The second node for which the sepset is being determined.
      containing - A specified subset of nodes that the resulting sepset must contain.
      test - The independence test to verify conditional independence between nodes.
      depth - The maximum allowable size for subsets to consider during the search for the sepset.
      Returns:
      A set of nodes representing the sepset containing the given subset, or null if no such set 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 - if any

    • getSepsetContainingMinPHybrid

      public static Set<Node> getSepsetContainingMinPHybrid(Graph graph, Node x, Node y, 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
      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 - if any

    • 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

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