Package edu.cmu.tetrad.search

Class Sp

java.lang.Object

edu.cmu.tetrad.search.Sp

All Implemented Interfaces:

SuborderSearch

public class Sp
extends Object
implements SuborderSearch

Implements the SP (Sparsest Permutation) algorithm. This procedure goes through every permutation of the variables (so can be slow for more than 11 variables with no knowledge) looking for a permutation such that when a DAG is built it has the fewest number of edges (i.e., is a most 'frugal' or a 'sparsest' DAG). The procedure can in principle return all such sparsest permutations and their corresponding DAGs, but in this version it return one of them, and converts the result into a CPDAG.

Knowledge can be used with this search. If tiered knowledge is used, then the procedure is carried out for each tier separately, given the variable preceding that tier, which allows the SP algorithm to address tiered (e.g., time series) problems with more than 11 variables.

This class is meant to be used in the context of the PermutationSearch class (see). the proper use is PermutationSearch search = new PermutationSearch(new Sp(score));

Author:

bryanandrews, josephramsey

See Also:

• PermutationSearch

Constructor Summary

Constructors

Constructor	Description
Sp(Score score)	This algorithm will work with an arbitrary score.

Method Summary

Modifier and Type	Method	Description
Map<Node,Set<Node>>	getParents()
Score	getScore()
List<Node>	getVariables()
void	searchSuborder(List<Node> prefix, List<Node> suborder, Map<Node,GrowShrinkTree> gsts)	This is the method called by PermutationSearch per tier.
void	setKnowledge(Knowledge knowledge)

Methods inherited from class java.lang.Object

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

Constructor Details

Sp

public Sp(Score score)

This algorithm will work with an arbitrary score.

Parameters:

score - The Score to use.

Method Details

searchSuborder

public void searchSuborder(List<Node> prefix,
 List<Node> suborder,
 Map<Node,GrowShrinkTree> gsts)

This is the method called by PermutationSearch per tier.

Specified by:

searchSuborder in interface SuborderSearch

Parameters:

prefix - The variable preceding the suborder variables in the permutation, including all variables from previous tiers.

suborder - The suborder of the variables list beign searched over. Only the order of the variables in this suborder will be modified.

gsts - The GrowShrinkTree used for the search. This is an optimized score-caching class.

setKnowledge

public void setKnowledge(Knowledge knowledge)

Specified by:

setKnowledge in interface SuborderSearch

getVariables

public List<Node> getVariables()

Specified by:

getVariables in interface SuborderSearch

getParents

public Map<Node,Set<Node>> getParents()

Specified by:

getParents in interface SuborderSearch

getScore

public Score getScore()

Specified by:

getScore in interface SuborderSearch