Package edu.cmu.tetrad.search

Class Fas

java.lang.Object
edu.cmu.tetrad.search.Fas
public class Fas extends Object
Implements the Fast Adjacency Search (FAS), which is the adjacency search of the PC algorithm (see). This is a useful algorithm in many contexts, including as the first step of FCI (see).

The idea of FAS is that at a given stage of the search, an edge X*-*Y is removed from the graph if X _||_ Y | S, where S is a subset of size d either of adj(X) or of adj(Y), where d is the depth of the search. The fast adjacency search performs this procedure for each pair of adjacent edges in the graph and for each depth d = 0, 1, 2, ..., d1. Here, d1 is either the maximum depth or else the first such depth at which no edges can be removed. The interpretation of this adjacency search is different for different algorithms, depending on the assumptions of the algorithm. A mapping from {x, y} to S({x, y}) is returned for edges x *-* y that have been removed.

FAS may optionally use a heuristic from Causation, Prediction, and Search, which (like PC-Stable) renders the output invariant to the order of the input variables.

This algorithm was described in the earlier edition of this book:

Spirtes, P., Glymour, C. N., Scheines, R., & Heckerman, D. (2000). Causation, prediction, and search. MIT press.

This class is configured to respect knowledge of forbidden and required edges, including knowledge of temporal tiers.

Version:
$Id: $Id
Author:
peterspirtes, clarkglymour, josephramsey.
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    Fas(IndependenceTest test)
    Constructs a new instance of the Fas algorithm using the specified independence test.

  • Method Summary

    Modifier and Type
    Method
    Description
    List<Node>
    getNodes()
    Retrieves a list of nodes associated with the initialized independence test.
    PrintStream
    getOut()
    Retrieves the current output stream used for logging or display purposes.
    SepsetMap
    getSepsets()
    Retrieves the separation set map that is used during the search process to store information about conditional independence tests.
    Graph
    search()
    Performs a conditional independence graph search using the default set of variables from the initialized independence test.
    Graph
    search(List<Node> nodes)
    Searches for conditional independence relationships in a graph constructed from the given list of nodes.
    void
    setDepth(int depth)
    Sets the depth for the search process.
    void
    setKnowledge(Knowledge knowledge)
    Sets the knowledge object used in the conditional independence search process.
    void
    setOut(PrintStream out)
    Sets the output stream to be used for logging or other display purposes.
    void
    setStable(boolean stable)
    Sets the stability flag for the search process, which may determine the search strategy or algorithm's behavior.
    void
    setVerbose(boolean verbose)
    Sets the verbosity level for the logging or debugging output of the search process.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Fas

      public Fas(IndependenceTest test)
      Constructs a new instance of the Fas algorithm using the specified independence test.
      Parameters:
      test - The independence test to be used by the Fas algorithm for conditional independence tests during the search process.

  • Method Details

    • search

      public Graph search() throws InterruptedException
      Performs a conditional independence graph search using the default set of variables from the initialized independence test. The method delegates the search process to another method that takes a list of variables as input.
      Returns:
      A graph where edges are updated based on the results of conditional independence tests and other provided constraints.
      Throws:
      InterruptedException - if interrupted.

    • search

      public Graph search(List<Node> nodes) throws InterruptedException
      Searches for conditional independence relationships in a graph constructed from the given list of nodes. Edges are removed based on the provided set of constraints and the maximum depth for the search.
      Parameters:
      nodes - The list of nodes to construct the graph and perform the search on.
      Returns:
      A graph with edges updated based on the search process and conditional independence tests.
      Throws:
      InterruptedException - if interrupted.

    • setDepth

      public void setDepth(int depth)
      Sets the depth for the search process.
      Parameters:
      depth - The maximum depth to be considered during the search.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge object used in the conditional independence search process.
      Parameters:
      knowledge - The knowledge object that provides information about constraints or background knowledge, such as forbidden edges, required edges, or other conditional independencies.

    • getSepsets

      public SepsetMap getSepsets()
      Retrieves the separation set map that is used during the search process to store information about conditional independence tests.
      Returns:
      The separation set map represented by an instance of SepsetMap, containing conditional independence information.

    • setVerbose

      public void setVerbose(boolean verbose)
      Sets the verbosity level for the logging or debugging output of the search process.
      Parameters:
      verbose - If true, enables verbose output; if false, disables it.

    • setStable

      public void setStable(boolean stable)
      Sets the stability flag for the search process, which may determine the search strategy or algorithm's behavior.
      Parameters:
      stable - If true, enables a stable search strategy; otherwise, an unstable or alternative strategy is used.

    • getNodes

      public List<Node> getNodes()
      Retrieves a list of nodes associated with the initialized independence test.
      Returns:
      A list of nodes derived from the variables in the associated independence test.

    • getOut

      public PrintStream getOut()
      Retrieves the current output stream used for logging or display purposes.
      Returns:
      The output stream instance associated with the logging or output operations.

    • setOut

      public void setOut(PrintStream out)
      Sets the output stream to be used for logging or other display purposes.
      Parameters:
      out - The output stream to which messages or data will be printed.