Package edu.cmu.tetrad.search.utils

Class FciOrient

java.lang.Object
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 FGES-FCI 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 to use 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 2024-8-21, Choh-Man Teng

  • 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).
    int
    getMaxDiscriminatingPathLength()
    Returns the maximum path length, or -1 if unlimited.
    static boolean
    isArrowheadAllowed(Node x, Node y, Graph graph, Knowledge K)
    Determines if an arrowhead can be placed at node Y in the given graph, based on the adjacency relationships, endpoint types, and any provided prior knowledge constraints.
    boolean
    isCompleteRuleSetUsed()
    Checks if the complete rule set is being used.
    static Set<DiscriminatingPath>
    listDiscriminatingPaths(Graph graph, int maxDiscriminatingPathLength, boolean checkXyNonadjacency)
    Lists all the discriminating paths in the given graph.
    static Set<DiscriminatingPath>
    listDiscriminatingPaths(Graph graph, Node w, Node y, int maxDiscriminatingPathLength, boolean checkEcNonadjacency)
    Lists the discriminating paths for <w, y> in the graph.
    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 alpha, Node gamma, 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
    setCompleteRuleSetUsed(boolean completeRuleSetUsed)
    Sets the flag indicating if the complete rule set is being used.
    void
    setEndpointStrategy(SetEndpointStrategy endpointStrategy)
    Sets the endpoint strategy for this object.
    void
    setKnowledge(Knowledge knowledge)
    Sets the knowledge to use for the final orientation.
    void
    setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)
    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
    setUseR4(boolean useR4)
    Sets whether R4 should be run.
    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:

  • Method Details

    • isArrowheadAllowed

      public static boolean isArrowheadAllowed(Node x, Node y, Graph graph, Knowledge K)
      Determines if an arrowhead can be placed at node Y in the given graph, based on the adjacency relationships, endpoint types, and any provided prior knowledge constraints.
      Parameters:
      x - The first node under consideration in the graph.
      y - The second node under consideration in the graph, where the arrowhead placement is evaluated.
      graph - The graph object containing nodes and their relationships.
      K - An object representing prior knowledge that may impose requirements or restrictions on edges.
      Returns:
      true if an arrowhead is allowed at node Y under the given conditions; false otherwise.

    • listDiscriminatingPaths

      public static Set<DiscriminatingPath> listDiscriminatingPaths(Graph graph, int maxDiscriminatingPathLength, boolean checkXyNonadjacency)
      Lists all the discriminating paths in the given graph.
      Parameters:
      graph - the graph to analyze
      maxDiscriminatingPathLength - the maximum length of a discriminating path
      checkXyNonadjacency - whether to check for EC nonadjacency
      Returns:
      a set of discriminating paths found in the graph

    • listDiscriminatingPaths

      public static Set<DiscriminatingPath> listDiscriminatingPaths(Graph graph, Node w, Node y, int maxDiscriminatingPathLength, boolean checkEcNonadjacency)
      Lists the discriminating paths for <w, y> in the graph.
      Parameters:
      graph - The graph.
      w - The first node.
      y - The second node.
      maxDiscriminatingPathLength - The maximum length of w discriminating path.
      checkEcNonadjacency - Whether to check for EC nonadjacency.
      Returns:
      The set of discriminating paths for <w, y>.

    • 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 α ∘→ γ. Intuition: when there’s a directed path α → β → γ with a circle on the edge incident to β on one side, and α–γ is currently a circle–circle edge, we can orient α–γ toward γ.
      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 - the graph in which the nodes exist

    • 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 - the graph to orient.

    • 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 - The graph being oriented.
      Returns:
      Whether R9 was successfully applied.

    • ruleR10

      public void ruleR10(Node alpha, Node gamma, 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 ω ar e distinct, and are not adjacent, then orient α o→ γ as α → γ.
      Parameters:
      alpha - α
      gamma - γ
      graph - alpha Graph object

    • getMaxDiscriminatingPathLength

      public int getMaxDiscriminatingPathLength()
      Returns the maximum path length, or -1 if unlimited.
      Returns:
      the maximum path length

    • setMaxDiscriminatingPathLength

      public void setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)
      Sets the maximum length of any discriminating path.
      Parameters:
      maxDiscriminatingPathLength - 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.

    • setTestTimeout

      public void setTestTimeout(long testTimeout)
      Sets the timeout for running tests.
      Parameters:
      testTimeout - the timeout value in milliseconds

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

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

    • setUseR4

      public void setUseR4(boolean useR4)
      Sets whether R4 should be run.
      Parameters:
      useR4 - True, if so.