edu.cmu.tetrad.search.utils.FciOrient

public final 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 which Jiji Zhang worked out in his Ph.D. dissertation, which is both 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.

Version:

$Id: $Id

Author:

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

See Also:

Constructor Summary

Constructors

Constructor

Description

FciOrient(SepsetProducer sepsets)

Constructs a new FCI search for the given independence test and background knowledge.
Method Summary

Modifier and Type

Method

Description

void

doFinalOrientation(Graph graph)

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

void

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

Orients according to background knowledge

int

getMaxPathLength()

Getter for the field maxPathLength.

SepsetProducer

getSepsets()

Returns the map from {x,y} to {z1,...,zn} for x _||_ y | z1,..,zn.

static List<List<Node>>

getUcCirclePaths(Node n1, Node n2, Graph graph)

Gets a list of every uncovered circle path between two nodes in the graph by iterating through the uncovered partially directed undirectedPaths and only keeping the circle undirectedPaths.

static List<List<Node>>

getUcPdPaths(Node n1, Node n2, Graph graph)

Gets a list of every uncovered partially directed path between two nodes in the graph.

static boolean

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

isArrowheadAllowed.

boolean

isCompleteRuleSetUsed()

isCompleteRuleSetUsed.

Graph

orient(Graph graph)

Performs final FCI orientation on the given graph.

void

orientTailPath(List<Node> path, Graph graph)

Orients every edge on a path as undirected (i.e.

void

ruleR0(Graph graph)

Orients colliders in the graph.

void

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

ruleR1.

void

ruleR10(Node a, Node c, Graph graph)

Tries to apply Zhang's rule R10 to a pair of nodes A and C which are assumed to be such that Ao->C.

void

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

ruleR2.

void

ruleR3(Graph graph)

Implements the double-triangle orientation rule, which states that if D*-oB, A*->B<-*C and A*-oDo-*C, and !adj(a, c), D*-oB, then D*->B.

void

ruleR4B(Graph graph)

The triangles that must be oriented this way (won't be done by another rule) all look like the ones below, where the dots are a collider path from E to A with each node on the path (except L) a parent of C.

void

ruleR5(Graph graph)

Implements Zhang's rule R5, orient circle undirectedPaths: for any Ao-oB, if there is an uncovered circle path u = [A,C,...,D,B] such that A,D nonadjacent and B,C nonadjacent, then A---B and orient every edge on u undirected.

void

ruleR6R7(Graph graph)

Implements Zhang's rules R6 and R7, applies them over the graph once.

boolean

ruleR8(Node a, Node c, Graph graph)

Tries to apply Zhang's rule R8 to a pair of nodes A and C which are assumed to be such that Ao->C.

boolean

ruleR9(Node a, Node c, Graph graph)

Tries to apply Zhang's rule R9 to a pair of nodes A and C which are assumed to be such that Ao->C.

void

rulesR1R2cycle(Graph graph)

rulesR1R2cycle.

void

rulesR8R9R10(Graph graph)

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

void

setChangeFlag(boolean changeFlag)

Sets the change flag--marks externally that a change has been made.

void

setCompleteRuleSetUsed(boolean completeRuleSetUsed)

Setter for the field completeRuleSetUsed.

void

setDoDiscriminatingPathColliderRule(boolean doDiscriminatingPathColliderRule)

Sets whether the discriminating path collider rule should be done.

void

setDoDiscriminatingPathTailRule(boolean doDiscriminatingPathTailRule)

Sets whether the discriminating path tail rule should be done.

void

setKnowledge(Knowledge knowledge)

Sets the knowledge to use for the final orientation.

void

setMaxPathLength(int maxPathLength)

Setter for the field maxPathLength.

void

setVerbose(boolean verbose)

Sets whether verbose output is printed.

void

spirtesFinalOrientation(Graph graph)

spirtesFinalOrientation.

void

zhangFinalOrientation(Graph graph)

zhangFinalOrientation.

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

Constructor Details
- FciOrient
  
  public FciOrient(SepsetProducer sepsets)
  
  Constructs a new FCI search for the given independence test and background knowledge.
  
  Parameters:
  
  sepsets - a SepsetProducer object representing the independence test, which must be given only if the discriminating path rule is used. Otherwise, it can be null.
Method Details
- getUcPdPaths
  
  public static List<List<Node>> getUcPdPaths(Node n1, Node n2, Graph graph)
  
  Gets a list of every uncovered partially directed path between two nodes in the graph.
  Probably extremely slow.
  
  Parameters:
  
  n1 - The beginning node of the undirectedPaths.
  
  n2 - The ending node of the undirectedPaths.
  
  graph - a Graph object
  
  Returns:
  
  A list of uncovered partially directed undirectedPaths from n1 to n2.
- getUcCirclePaths
  
  public static List<List<Node>> getUcCirclePaths(Node n1, Node n2, Graph graph)
  
  Gets a list of every uncovered circle path between two nodes in the graph by iterating through the uncovered partially directed undirectedPaths and only keeping the circle undirectedPaths.
  Probably extremely slow.
  
  Parameters:
  
  n1 - The beginning node of the undirectedPaths.
  
  n2 - The ending node of the undirectedPaths.
  
  graph - a Graph object
  
  Returns:
  
  A list of uncovered circle undirectedPaths between n1 and n2.
- isArrowheadAllowed
  
  public static boolean isArrowheadAllowed(Node x, Node y, Graph graph, Knowledge knowledge)
  
  isArrowheadAllowed.
  
  Parameters:
  
  x - a Node object
  
  y - a Node object
  
  graph - a Graph object
  
  knowledge - a Knowledge object
  
  Returns:
  
  a boolean
- orient
  
  public Graph orient(Graph graph)
  
  Performs final FCI orientation on the given graph.
  
  Parameters:
  
  graph - The graph to further orient.
  
  Returns:
  
  The oriented graph.
- getSepsets
  
  public SepsetProducer getSepsets()
  
  Returns the map from {x,y} to {z1,...,zn} for x _||_ y | z1,..,zn.
  
  Returns:
  
  Thia map.
- setKnowledge
  
  public void setKnowledge(Knowledge knowledge)
  
  Sets the knowledge to use for the final orientation.
  
  Parameters:
  
  knowledge - This knowledge.
- isCompleteRuleSetUsed
  
  public boolean isCompleteRuleSetUsed()
  
  isCompleteRuleSetUsed.
  
  Returns:
  
  true if Zhang's complete rule set should be used, false if only R1-R4 (the rule set of the original FCI) should be used. False by default.
- setCompleteRuleSetUsed
  
  public void setCompleteRuleSetUsed(boolean completeRuleSetUsed)
  
  Setter for the field completeRuleSetUsed.
  
  Parameters:
  
  completeRuleSetUsed - set to true if Zhang's complete rule set should be used, false if only R1-R4 (the rule set of the original FCI) should be used. False by default.
- ruleR0
  
  public void ruleR0(Graph graph)
  
  Orients colliders in the graph. (FCI Step C)
  Zhang's step F3, rule R0.
  
  Parameters:
  
  graph - The graph to orient.
- doFinalOrientation
  
  public void doFinalOrientation(Graph graph)
  
  Orients the graph according to rules in the graph (FCI step D).
  Zhang's step F4, rules R1-R10.
  
  Parameters:
  
  graph - a Graph object
- spirtesFinalOrientation
  
  public void spirtesFinalOrientation(Graph graph)
  
  spirtesFinalOrientation.
  
  Parameters:
  
  graph - a Graph object
- zhangFinalOrientation
  
  public void zhangFinalOrientation(Graph graph)
  
  zhangFinalOrientation.
  
  Parameters:
  
  graph - a Graph object
- rulesR1R2cycle
  
  public void rulesR1R2cycle(Graph graph)
  
  rulesR1R2cycle.
  
  Parameters:
  
  graph - a Graph object
- ruleR1
  
  public void ruleR1(Node a, Node b, Node c, Graph graph)
  
  ruleR1.
  
  Parameters:
  
  a - a Node object
  
  b - a Node object
  
  c - a Node object
  
  graph - a Graph object
- ruleR2
  
  public void ruleR2(Node a, Node b, Node c, Graph graph)
  
  ruleR2.
  
  Parameters:
  
  a - a Node object
  
  b - a Node object
  
  c - a Node object
  
  graph - a Graph object
- ruleR3
  
  public void ruleR3(Graph graph)
  
  Implements the double-triangle orientation rule, which states that if D*-oB, A*->B<-*C and A*-oDo-*C, and !adj(a, c), D*-oB, then D*->B.
  This is Zhang's rule R3.
  
  Parameters:
  
  graph - a Graph object
- ruleR4B
  
  public void ruleR4B(Graph graph)
  The triangles that must be oriented this way (won't be done by another rule) all look like the ones below, where the dots are a collider path from E to A with each node on the path (except L) a parent of C.
  B xo x is either an arrowhead or a circle / \ v v E....A --> C
  
  This is Zhang's rule R4, discriminating paths.
  Parameters:
  
  graph - a Graph object
- ruleR5
  
  public void ruleR5(Graph graph)
  
  Implements Zhang's rule R5, orient circle undirectedPaths: for any Ao-oB, if there is an uncovered circle path u = [A,C,...,D,B] such that A,D nonadjacent and B,C nonadjacent, then A---B and orient every edge on u undirected.
  
  Parameters:
  
  graph - a Graph object
- ruleR6R7
  
  public void ruleR6R7(Graph graph)
  
  Implements Zhang's rules R6 and R7, applies them over the graph once. Orient single tails. R6: If A---Bo-*C then A---B--*C. R7: If A--oBo-*C and A,C nonadjacent, then A--oB--*C
  
  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
- orientTailPath
  
  public void orientTailPath(List<Node> path, Graph graph)
  
  Orients every edge on a path as undirected (i.e. A---B).
  DOES NOT CHECK IF SUCH EDGES ACTUALLY EXIST: MAY DO WEIRD THINGS IF PASSED AN ARBITRARY LIST OF NODES THAT IS NOT A PATH.
  
  Parameters:
  
  path - The path to orient as all tails.
  
  graph - a Graph object
- ruleR8
  
  public boolean ruleR8(Node a, Node c, Graph graph)
  
  Tries to apply Zhang's rule R8 to a pair of nodes A and C which are assumed to be such that Ao->C.
  MAY HAVE WEIRD EFFECTS ON ARBITRARY NODE PAIRS.
  R8: If Ao->C and A-->B-->C or A--oB-->C, then A-->C.
  
  Parameters:
  
  a - The node A.
  
  c - The node C.
  
  graph - a Graph object
  
  Returns:
  
  Whether R8 was successfully applied.
- ruleR9
  
  public boolean ruleR9(Node a, Node c, Graph graph)
  
  Tries to apply Zhang's rule R9 to a pair of nodes A and C which are assumed to be such that Ao->C.
  MAY HAVE WEIRD EFFECTS ON ARBITRARY NODE PAIRS.
  R9: If Ao->C and there is an uncovered p.d. path u=<A,B,..,C> such that C,B nonadjacent, then A-->C.
  
  Parameters:
  
  a - The node A.
  
  c - The node C.
  
  graph - a Graph object
  
  Returns:
  
  Whether R9 was succesfully applied.
- fciOrientbk
  
  public void fciOrientbk(Knowledge bk, Graph graph, List<Node> variables)
  
  Orients according to background knowledge
  
  Parameters:
  
  bk - a Knowledge object
  
  graph - a Graph object
  
  variables - a List object
- getMaxPathLength
  
  public int getMaxPathLength()
  
  Getter for the field maxPathLength.
  
  Returns:
  
  the maximum length of any discriminating path, or -1 of unlimited.
- setMaxPathLength
  
  public void setMaxPathLength(int maxPathLength)
  
  Setter for the field maxPathLength.
  
  Parameters:
  
  maxPathLength - the maximum length of any discriminating path, or -1 if unlimited.
- setVerbose
  
  public void setVerbose(boolean verbose)
  
  Sets whether verbose output is printed.
  
  Parameters:
  
  verbose - True, if so.
- setChangeFlag
  
  public void setChangeFlag(boolean changeFlag)
  
  Sets the change flag--marks externally that a change has been made.
  
  Parameters:
  
  changeFlag - This flag.
- setDoDiscriminatingPathColliderRule
  
  public void setDoDiscriminatingPathColliderRule(boolean doDiscriminatingPathColliderRule)
  
  Sets whether the discriminating path collider rule should be done.
  
  Parameters:
  
  doDiscriminatingPathColliderRule - True is done.
- setDoDiscriminatingPathTailRule
  
  public void setDoDiscriminatingPathTailRule(boolean doDiscriminatingPathTailRule)
  
  Sets whether the discriminating path tail rule should be done.
  
  Parameters:
  
  doDiscriminatingPathTailRule - True if done.
- ruleR10
  
  public void ruleR10(Node a, Node c, Graph graph)
  
  Tries to apply Zhang's rule R10 to a pair of nodes A and C which are assumed to be such that Ao->C.
  MAY HAVE WEIRD EFFECTS ON ARBITRARY NODE PAIRS.
  R10: If Ao->C, B-->C<--D, there is an uncovered p.d. path u1=<A,M,...,B> and an uncovered p.d. path u2= <A,N,...,D> with M != N and M,N nonadjacent then A-->C.
  
  Parameters:
  
  a - The node A.
  
  c - The node C.
  
  graph - a Graph object

Class FciOrient

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

FciOrient

Method Details

getUcPdPaths

getUcCirclePaths

isArrowheadAllowed

orient

getSepsets

setKnowledge

isCompleteRuleSetUsed

setCompleteRuleSetUsed

ruleR0

doFinalOrientation

spirtesFinalOrientation

zhangFinalOrientation

rulesR1R2cycle

ruleR1

ruleR2

ruleR3

ruleR4B

ruleR5

ruleR6R7

rulesR8R9R10

orientTailPath

ruleR8

ruleR9

fciOrientbk

getMaxPathLength

setMaxPathLength

setVerbose

setChangeFlag

setDoDiscriminatingPathColliderRule

setDoDiscriminatingPathTailRule

ruleR10