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

    • 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

    • getSepsetContainingMaxP

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

    • getSepsetContainingMinP

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

    • getSepsetContainingRecursive

      public static Set<Node> getSepsetContainingRecursive(Graph graph, Node x, Node y, Set<Node> containing, IndependenceTest test)
      Retrieves the sepset (a set of nodes) between two given nodes. The sepset is the minimal set of nodes that need to be conditioned on to render two nodes conditionally independent.
      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
      test - the independence test to use
      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.

    • getSepsetParentsOfXorY

      public static Set<Node> getSepsetParentsOfXorY(Graph dag, Node x, Node y, IndependenceTest test)
      Retrieves the parents of nodes X and Y that also share in their parents based on the given DAG graph and the provided independence test.
      Parameters:
      dag - the DAG graph to analyze
      x - the first node
      y - the second node
      test - the independence test to use
      Returns:
      the set of nodes that are parents of both X and Y, excluding X and Y themselves, and excluding any latent nodes. Returns null if no common parents can be found or if the given graph is not a legal DAG.
      Throws:
      IllegalArgumentException - if the given graph is not a legal DAG

    • getSepsetPathBlockingXtoY

      public static Set<Node> getSepsetPathBlockingXtoY(Graph mpdag, Node x, Node y, IndependenceTest test, int maxLength, int depth, boolean verbose)
      Searches for sets, by following paths from x to y in the given MPDAG, that could possibly block all paths from x to y except for an edge from x to y itself. These possible sets are then tested for independence, and the first set that is found to be independent is returned as the sepset.

      This is the sepset finding method from LV-lite.

      Parameters:
      mpdag - the MPDAG graph to analyze (can be a DAG or a CPDAG)
      x - the first node
      y - the second node
      test - the independence test to use
      maxLength - the maximum blocking length for paths, or -1 for no limit
      depth - the maximum depth of the sepset, or -1 for no limit
      verbose - whether to print trace information; false by default. This can be quite verbose, so it's recommended to only use this for debugging.
      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.

    • getDsepSepset

      public static Set<Node> getDsepSepset(Graph mag, Node x, Node y, IndependenceTest test)
      Returns the sepset (separation set) between two nodes in a graph based on the given independence test.
      Parameters:
      mag - The graph containing the nodes.
      x - The first node.
      y - The second node.
      test - The independence test used to check the independence between the nodes.
      Returns:
      The sepset between the two nodes, or null if no sepset is found.

    • bfsAllPaths

      public static Set<List<Node>> bfsAllPaths(Graph graph, Set<Node> conditionSet, int maxLength, Node x, Node y)
      Performs a breadth-first search to find all paths from node x to node y in a given graph.
      Parameters:
      graph - the graph to perform the search on
      conditionSet - a set of nodes to condition the paths on
      maxLength - the maximum length of the paths, -1 for no limit
      x - the starting node
      y - the target node
      Returns:
      a set of lists of nodes, representing all found paths from x to y
      Throws:
      IllegalArgumentException - if the conditionSet is null

    • 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

    • allPathsOutOf

      public static Set<List<Node>> allPathsOutOf(Graph graph, Node node1, int maxLength, Set<Node> conditionSet, boolean allowSelectionBias)
      Finds all paths from a given starting node in a graph, with a maximum length and satisfying a set of conditions.
      Parameters:
      graph - The input graph.
      node1 - The starting node for finding paths.
      maxLength - The maximum length of paths to consider.
      conditionSet - The set of conditions that the paths must satisfy.
      allowSelectionBias - Determines whether to allow biased selection when multiple paths are available.
      Returns:
      A set of lists, where each list represents a path from the starting node that satisfies the conditions.

    • getSepsetPathBlockingOutOfX

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