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: