Package edu.cmu.tetrad.search.utils

Class FciOrient

java.lang.Object
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.

Author:
Erin Korber, June 2004, Alex Smith, December 2008, josephramsey, Choh-Man Teng
See Also:

  • Constructor Details

    • FciOrient

      public FciOrient(SepsetProducer sepsets)
      Constructs a new FCI search for the given independence test and background knowledge.

  • 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.
      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.
      Returns:
      A list of uncovered circle undirectedPaths between n1 and n2.

    • isArrowheadAllowed

      public static boolean isArrowheadAllowed(Node x, Node y, Graph graph, Knowledge knowledge)

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

    • spirtesFinalOrientation

      public void spirtesFinalOrientation(Graph graph)

    • zhangFinalOrientation

      public void zhangFinalOrientation(Graph graph)

    • rulesR1R2cycle

      public void rulesR1R2cycle(Graph graph)

    • ruleR1

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

    • ruleR2

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

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

    • 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 L 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
 L....A --> C

      This is Zhang's rule R4, discriminating paths.

    • ddpOrient

      public void ddpOrient(Node a, Node b, Node c, Graph graph)
      a method to search "back from a" to find a DDP. It is called with a reachability list (first consisting only of a). This is breadth-first, utilizing "reachability" concept from Geiger, Verma, and Pearl 1990. The body of a DDP consists of colliders that are parents of c.

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

    • 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

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

    • doDdpOrientation

      public boolean doDdpOrientation(Node d, Node a, Node b, Node c, Graph graph)
      Orients the edges inside the definte discriminating path triangle. Takes the left endpoint, and a,b,c as arguments.

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

    • 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.
      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.
      Returns:
      Whether R9 was succesfully applied.

    • fciOrientbk

      public void fciOrientbk(Knowledge bk, Graph graph, List<Node> variables)
      Orients according to background knowledge

    • getMaxPathLength

      public int getMaxPathLength()
      Returns:
      the maximum length of any discriminating path, or -1 of unlimited.

    • setMaxPathLength

      public void setMaxPathLength(int 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.

    • getTruePag

      public Graph getTruePag()
      The true PAG if available. Can be null.

    • setTruePag

      public void setTruePag(Graph truePag)
      Sets the true PAG for comparison.
      Parameters:
      truePag - This PAG.

    • isChangeFlag

      public boolean isChangeFlag()
      Change flag for repeat rules
      Returns:
      True if a change has occurred.

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