edu.cmu.tetrad.search.utils.FciOrient

public class FciOrient extends Object

Performs the final orientation steps of the FCI algorithms, which is a useful tool to use in a variety of FCI-like algorithms.

There are two versions of these final orientation steps, one due to Peter Spirtes (the original, in Causation, Prediction and Search), which is arrow complete, and the other due to Jiji Zhang, which is arrow and tail complete. The references for these are as follows.

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

Zhang, J. (2008). On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17), 1873-1896.

These final rules are used in all algorithms in Tetrad that follow and refine the FCI algorithm--for example, the GFCI and RFCI algorihtms.

We've made the methods for each of the separate rules publicly accessible in case someone wants to use the individual rules in the context of their own algorithms.

Note: This class is a modified version of the original FciOrient class, in that we allow the R0 and R4 rules to be be overridden by subclasses. This is useful for the TeyssierScorer class, which needs to override these rules in order to calculate the score of the graph. It is also useful for DAG to PAG, which needs to override these rules in order using D-SEP. The R0 and R4 rules are the only ones that cannot be carried out by an examination of the graph but which require additional analysis of the underlying distribution or graph. In addition, several methods have been optimized.

Version:

$Id: $Id

Author:

Erin Korber, June 2004, Alex Smith, December 2008, josephramsey, Choh-Man Teng

See Also:

Constructor Summary

Constructors

Constructor

Description

FciOrient(R0R4Strategy strategy)

Initializes a new instance of the FciOrient class with the specified R4Strategy.
Method Summary

Modifier and Type

Method

Description

void

fciOrientbk(Knowledge bk, Graph graph, List<Node> variables)

Orient the edges of a graph based on the given knowledge.

void

finalOrientation(Graph graph)

Orients the graph (in place) according to rules in the graph (FCI step D).

Collection<Triple>

getInitialAllowedColliders()

Returns the initial allowed colliders based on the current strategy.

int

getMaxPathLength()

Returns the maximum path length, or -1 if unlimited.

static boolean

isArrowheadAllowed(Node x, Node y, Graph graph, Knowledge knowledge)

Determines whether an arrowhead is allowed between two nodes in a graph, based on specific conditions.

boolean

isCompleteRuleSetUsed()

Checks if the complete rule set is being used.

void

orient(Graph graph, Set<Triple> unshieldedTriples)

Performs FCI orientation on the given graph, including R0 and either the Spirtes or Zhang final orientation rules.

void

ruleR0(Graph graph, Set<Triple> unshieldedTriples)

Orients unshielded colliders in the graph.

void

ruleR1(Node a, Node b, Node c, Graph graph)

R1 If α ∗→ β o−−∗ γ, and α and γ are not adjacent, then orient the triple as α ∗→ β → γ.

void

ruleR10(Node a, Node c, Graph graph)

R10 Suppose α o→ γ, β → γ ← θ, p1 is an uncovered potentially directed (semidirected) path from α to β, and p2 is an uncovered p.d.

void

ruleR2(Node a, Node b, Node c, Graph graph)

R2 If α → β ∗→ γ or α ∗→ β → γ, and α ∗−o γ, then orient α ∗−o γ as α ∗→ γ.

void

ruleR3(Graph graph)

R3 If α ∗→ β ←∗ γ, α ∗−o θ o−∗ γ, α and γ are not adjacent, and θ ∗−o β, then orient θ ∗−o β as θ ∗→ β.

void

ruleR4(Graph graph)

R4 If u = <θ ,...,α,β,γ> is a discriminating path between θ and γ for β, and β o−−∗ γ; then if β ∈ Sepset(θ,γ), orient β o−−∗ γ as β → γ; otherwise orient the triple <α,β,γ> as α ↔ β ↔ γ.

void

ruleR5(Graph graph)

R5 For every (remaining) α o−−o β, if there is an uncovered circle path p = <α,γ,...,θ,β> between α and β s.t.

void

ruleR6(Graph graph)

R6 If α —- β o−−∗ γ (α and γ may or may not be adjacent), then orient β o−−∗ γ as β −−∗ γ.

void

ruleR7(Graph graph)

R7 If α −−o β o−−∗ γ, and α, γ are not adjacent, then orient β o−−∗ γ as β −−∗ γ.

boolean

ruleR8(Node a, Node c, Graph graph)

R8 If α → β → γ or α−−◦β → γ, and α o→ γ, orient α o→ γ as α → γ.

boolean

ruleR9(Node a, Node c, Graph graph)

R9 If α o→ γ, and p = <α,β,θ,...,γ> is an uncovered potentialy directed path from α to γ such that γ and β are not adjacent, then orient α o→ γ as α → γ.

void

rulesR1R2cycle(Graph graph)

Apply rules R1 and R2 in cycles for a given graph.

void

rulesR8R9R10(Graph graph)

Implements Zhang's rules R8, R9, R10, applies them over the graph once.

void

setAllowedColliders(Set<Triple> allowedColliders)

Sets the allowed colliders for this object.

void

setCompleteRuleSetUsed(boolean completeRuleSetUsed)

Sets the flag indicating if the complete rule set is being used.

void

setDoDiscriminatingPathColliderRule(boolean doDiscriminatingPathColliderRule)

Sets whether the discriminating path collider rule should be used.

void

setDoDiscriminatingPathTailRule(boolean doDiscriminatingPathTailRule)

Sets whether the discriminating path tail rule should be used.

void

setEndpointStrategy(SetEndpointStrategy endpointStrategy)

Sets the endpoint strategy for this object.

void

setInitialAllowedColliders(HashSet<Triple> initialAllowedColliders)

Sets the initial allowed colliders for the strategy.

void

setKnowledge(Knowledge knowledge)

Sets the knowledge to use for the final orientation.

void

setMaxPathLength(int maxPathLength)

Sets the maximum length of any discriminating path.

void

setParallel(boolean parallel)

Sets whether the discriminating path orientation should be run in parallel.

void

setTestTimeout(long testTimeout)

Sets the timeout for running tests.

void

setVerbose(boolean verbose)

Sets whether verbose output is printed.

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- FciOrient
  
  public FciOrient(R0R4Strategy strategy)
  
  Initializes a new instance of the FciOrient class with the specified R4Strategy.
  Parameters:
  
  strategy - The FciOrientDataExaminationStrategy to use for the examination.
  
  Throws:
  
  NullPointerException - If the strategy parameter is null.
  
  See Also:
  
  R0R4Strategy
Method Details
- isArrowheadAllowed
  
  public static boolean isArrowheadAllowed(Node x, Node y, Graph graph, Knowledge knowledge)
  
  Determines whether an arrowhead is allowed between two nodes in a graph, based on specific conditions.
  
  Parameters:
  
  x - The first node.
  
  y - The second node.
  
  graph - The graph data structure.
  
  knowledge - The knowledge base containing forbidden connections.
  
  Returns:
  
  true if an arrowhead is allowed between X and Y, false otherwise.
- orient
  
  public void orient(Graph graph, Set<Triple> unshieldedTriples)
  
  Performs FCI orientation on the given graph, including R0 and either the Spirtes or Zhang final orientation rules.
  
  Parameters:
  
  graph - The graph to orient.
  
  unshieldedTriples - The set of unshielded triples oriented by R0. This set is updated with new triples.
- setKnowledge
  
  public void setKnowledge(Knowledge knowledge)
  
  Sets the knowledge to use for the final orientation.
  
  Parameters:
  
  knowledge - This knowledge.
- isCompleteRuleSetUsed
  
  public boolean isCompleteRuleSetUsed()
  
  Checks if the complete rule set is being used.
  
  Returns:
  
  true if the complete rule set is being used, false otherwise.
- setCompleteRuleSetUsed
  
  public void setCompleteRuleSetUsed(boolean completeRuleSetUsed)
  
  Sets the flag indicating if the complete rule set is being used.
  
  Parameters:
  
  completeRuleSetUsed - boolean value indicating if the complete rule set is being used
- ruleR0
  
  public void ruleR0(Graph graph, Set<Triple> unshieldedTriples)
  
  Orients unshielded colliders in the graph. (FCI Step C, Zhang's step F3, rule R0.)
  
  Parameters:
  
  graph - The graph to orient.
  
  unshieldedTriples - The set of unshielded triples oriented by R0. This set is updated with new triples.
- finalOrientation
  
  public void finalOrientation(Graph graph)
  
  Orients the graph (in place) according to rules in the graph (FCI step D).
  Zhang's rules R1-R10.
  
  Parameters:
  
  graph - a Graph object
- rulesR1R2cycle
  
  public void rulesR1R2cycle(Graph graph)
  
  Apply rules R1 and R2 in cycles for a given graph.
  
  Parameters:
  
  graph - The graph to apply the rules on.
- ruleR1
  
  public void ruleR1(Node a, Node b, Node c, Graph graph)
  
  R1 If α ∗→ β o−−∗ γ, and α and γ are not adjacent, then orient the triple as α ∗→ β → γ.
  
  Parameters:
  
  a - α
  
  b - β
  
  c - γ
  
  graph - the graph containing the edges and nodes
- ruleR2
  
  public void ruleR2(Node a, Node b, Node c, Graph graph)
  
  R2 If α → β ∗→ γ or α ∗→ β → γ, and α ∗−o γ, then orient α ∗−o γ as α ∗→ γ.
  
  Parameters:
  
  a - α
  
  b - β
  
  c - γ
  
  graph - the graph in which the nodes exist
- ruleR3
  
  public void ruleR3(Graph graph)
  
  R3 If α ∗→ β ←∗ γ, α ∗−o θ o−∗ γ, α and γ are not adjacent, and θ ∗−o β, then orient θ ∗−o β as θ ∗→ β.
  
  Parameters:
  
  graph - a Graph object
- ruleR4
  
  public void ruleR4(Graph graph)
  
  R4 If u = <θ ,...,α,β,γ> is a discriminating path between θ and γ for β, and β o−−∗ γ; then if β ∈ Sepset(θ,γ), orient β o−−∗ γ as β → γ; otherwise orient the triple <α,β,γ> as α ↔ β ↔ γ.
  
  Parameters:
  
  graph - a Graph object
- ruleR5
  
  public void ruleR5(Graph graph)
  
  R5 For every (remaining) α o−−o β, if there is an uncovered circle path p = <α,γ,...,θ,β> between α and β s.t. α,θ are not adjacent and β,γ are not adjacent, then orient α o−−o β and every edge on p as undirected edges (--).
  
  Parameters:
  
  graph - a Graph object
- ruleR6
  
  public void ruleR6(Graph graph)
  
  R6 If α —- β o−−∗ γ (α and γ may or may not be adjacent), then orient β o−−∗ γ as β −−∗ γ.
  
  Parameters:
  
  graph - a Graph object
- ruleR7
  
  public void ruleR7(Graph graph)
  
  R7 If α −−o β o−−∗ γ, and α, γ are not adjacent, then orient β o−−∗ γ as β −−∗ γ.
  
  Parameters:
  
  graph - a Graph object
- rulesR8R9R10
  
  public void rulesR8R9R10(Graph graph)
  
  Implements Zhang's rules R8, R9, R10, applies them over the graph once. Orient arrow tails. I.e., tries R8, R9, and R10 in that sequence on each Ao->C in the graph.
  
  Parameters:
  
  graph - a Graph object
- ruleR8
  
  public boolean ruleR8(Node a, Node c, Graph graph)
  
  R8 If α → β → γ or α−−◦β → γ, and α o→ γ, orient α o→ γ as α → γ.
  
  Parameters:
  
  a - α
  
  c - γ
  
  graph - a Graph object
  
  Returns:
  
  Whether R8 was successfully applied.
- ruleR9
  
  public boolean ruleR9(Node a, Node c, Graph graph)
  
  R9 If α o→ γ, and p = <α,β,θ,...,γ> is an uncovered potentialy directed path from α to γ such that γ and β are not adjacent, then orient α o→ γ as α → γ.
  
  Parameters:
  
  a - The node A.
  
  c - The node C.
  
  graph - a Graph object
  
  Returns:
  
  Whether R9 was succesfully applied.
- ruleR10
  
  public void ruleR10(Node a, Node c, Graph graph)
  
  R10 Suppose α o→ γ, β → γ ← θ, p1 is an uncovered potentially directed (semidirected) path from α to β, and p2 is an uncovered p.d. path from α to θ. Let μ be the vertex adjacent to α on p1 (μ could be β), and ω be the vertex adjacent to α on p2 (ω could be θ). If μ and ω are distinct, and are not adjacent, then orient α o→ γ as α → γ.
  
  Parameters:
  
  a - α
  
  c - γ
  
  graph - a Graph object
- getMaxPathLength
  
  public int getMaxPathLength()
  
  Returns the maximum path length, or -1 if unlimited.
  
  Returns:
  
  the maximum path length
- setMaxPathLength
  
  public void setMaxPathLength(int maxPathLength)
  
  Sets the maximum length of any discriminating path.
  
  Parameters:
  
  maxPathLength - the maximum length of any discriminating path, or -1 if unlimited.
- setDoDiscriminatingPathTailRule
  
  public void setDoDiscriminatingPathTailRule(boolean doDiscriminatingPathTailRule)
  
  Sets whether the discriminating path tail rule should be used.
  
  Parameters:
  
  doDiscriminatingPathTailRule - True, if so.
- setDoDiscriminatingPathColliderRule
  
  public void setDoDiscriminatingPathColliderRule(boolean doDiscriminatingPathColliderRule)
  
  Sets whether the discriminating path collider rule should be used.
  
  Parameters:
  
  doDiscriminatingPathColliderRule - True, if so.
- setVerbose
  
  public void setVerbose(boolean verbose)
  
  Sets whether verbose output is printed.
  
  Parameters:
  
  verbose - True, if so.
- setTestTimeout
  
  public void setTestTimeout(long testTimeout)
  
  Sets the timeout for running tests.
  
  Parameters:
  
  testTimeout - the timeout value in milliseconds
- setAllowedColliders
  
  public void setAllowedColliders(Set<Triple> allowedColliders)
  
  Sets the allowed colliders for this object. These are passed to R4 is the set of unshielded colliders for the model is to be restricted. TODO Think this through again.
  
  Parameters:
  
  allowedColliders - the set of colliders allowed to interact with this object
- getInitialAllowedColliders
  
  public Collection<Triple> getInitialAllowedColliders()
  
  Returns the initial allowed colliders based on the current strategy. These are the unshielded colliders from R4's first run.
  TODO think this through again.
  
  Returns:
  
  a collection of Triple objects representing the initial allowed colliders.
- setInitialAllowedColliders
  
  public void setInitialAllowedColliders(HashSet<Triple> initialAllowedColliders)
  
  Sets the initial allowed colliders for the strategy.
  TODO: Think this thorugh again.
  
  Parameters:
  
  initialAllowedColliders - The set of initial allowed colliders.
- setParallel
  
  public void setParallel(boolean parallel)
  
  Sets whether the discriminating path orientation should be run in parallel.
  
  Parameters:
  
  parallel - True, if so.
- setEndpointStrategy
  
  public void setEndpointStrategy(SetEndpointStrategy endpointStrategy)
  
  Sets the endpoint strategy for this object.
  Parameters:
  
  endpointStrategy - the endpoint strategy to set
  
  See Also:
  
  SetEndpointStrategy
- fciOrientbk
  
  public void fciOrientbk(Knowledge bk, Graph graph, List<Node> variables)
  
  Orient the edges of a graph based on the given knowledge.
  
  Parameters:
  
  bk - The knowledge containing forbidden and required edges.
  
  graph - The graph to be oriented.
  
  variables - The list of nodes in the graph.

Class FciOrient

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

FciOrient

Method Details

isArrowheadAllowed

orient

setKnowledge

isCompleteRuleSetUsed

setCompleteRuleSetUsed

ruleR0

finalOrientation

rulesR1R2cycle

ruleR1

ruleR2

ruleR3

ruleR4

ruleR5

ruleR6

ruleR7

rulesR8R9R10

ruleR8

ruleR9

ruleR10

getMaxPathLength

setMaxPathLength

setDoDiscriminatingPathTailRule

setDoDiscriminatingPathColliderRule

setVerbose

setTestTimeout

setAllowedColliders

getInitialAllowedColliders

setInitialAllowedColliders

setParallel

setEndpointStrategy

fciOrientbk