Package edu.cmu.tetrad.search

Class Fas

java.lang.Object
edu.cmu.tetrad.search.Fas
All Implemented Interfaces:
IFas, IGraphSearch
public class Fas extends Object implements IFas
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.
    SepsetMap
    getSepsets()
    Retrieves the separation set map that is used during the search process to store information about conditional independence tests.
    IndependenceTest
    getTest()
    Gets the test used by the search.
    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
    setReplicatingGraph(boolean replicatingGraph)
    Sets the flag indicating whether the graph is in a replicating state.
    void
    setStable(boolean stable)
    Sets the stability flag for the search process, which may determine the search strategy or algorithm's behavior.
    void
    setTest(IndependenceTest test)
    Sets the test to be used by the search.
    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.
      Specified by:
      search in interface IFas
      Specified by:
      search in interface IGraphSearch
      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.

    • getTest

      public IndependenceTest getTest()
      Description copied from interface: IGraphSearch
      Gets the test used by the search.
      Specified by:
      getTest in interface IGraphSearch
      Returns:
      The test used by the search.

    • setTest

      public void setTest(IndependenceTest test)
      Description copied from interface: IGraphSearch
      Sets the test to be used by the search. The list of variables of the new proposed test must be equal to the list of variables of the existing test.
      Specified by:
      setTest in interface IGraphSearch
      Parameters:
      test - The test to be used by the search.

    • setDepth

      public void setDepth(int depth)
      Sets the depth for the search process.
      Specified by:
      setDepth in interface IFas
      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.
      Specified by:
      setKnowledge in interface IFas
      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.
      Specified by:
      getSepsets in interface IFas
      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.
      Specified by:
      setVerbose in interface IFas
      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.
      Specified by:
      setStable in interface IFas
      Parameters:
      stable - If true, enables a stable search strategy; otherwise, an unstable or alternative strategy is used.

    • setReplicatingGraph

      public void setReplicatingGraph(boolean replicatingGraph)
      Sets the flag indicating whether the graph is in a replicating state.
      Specified by:
      setReplicatingGraph in interface IFas
      Parameters:
      replicatingGraph - A boolean value; if true, the graph is considered to be in a replicating state. Otherwise, it is not.

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